第一篇：校園導(dǎo)游課程設(shè)計實驗報告

《數(shù)據(jù)結(jié)構(gòu)》

課 程 設(shè) 計 實 驗 報 告

課程名稱：

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 課程設(shè)計題目： 校園導(dǎo)游 姓名：

邱可昉 院系：

計算機學(xué)院 專業(yè)：

計算機科學(xué)與技術(shù) 班級：

10052313 學(xué)號：

10051319 指導(dǎo)老師：

王立波

2012年5月18日

目錄

1.課程設(shè)計的目的?????????????????????3 2.問題分析????????????????????????3 3.課程設(shè)計報告內(nèi)容????????????????????3（1）概要設(shè)計?????????????????????3（2）詳細設(shè)計?????????????????????3（3）測試結(jié)果?????????????????????7（4）程序清單?????????????????????9 4.個人小結(jié) ???????????????????????14

1.課程設(shè)計的目的

《數(shù)據(jù)結(jié)構(gòu)》是計算機軟件的一門基礎(chǔ)課程，計算機科學(xué)各領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。學(xué)好數(shù)據(jù)結(jié)構(gòu)對掌握實際編程能力是很有幫助的。為了學(xué)好《數(shù)據(jù)結(jié)構(gòu)》，必須編寫一些在特定數(shù)據(jù)結(jié)構(gòu)上的算法，通過上機調(diào)試，才能更好地掌握各種數(shù)據(jù)結(jié)構(gòu)及其特點，同時提高解決計算機應(yīng)用實際問題的能力。

2.問題分析

[問題描述]（1）設(shè)計你的學(xué)校的校園平面圖，所含景點不少于10個。以圖中頂點表示學(xué)校各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。

（2）為來訪客人提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一條最短的簡單路徑。

（3）為來訪客人提供圖中任意景點相關(guān)信息的查詢。[測試數(shù)據(jù)] 由讀者根據(jù)實際情況指定。

3.課程設(shè)計報告內(nèi)容

（1）概要設(shè)計

根據(jù)學(xué)校具體分布構(gòu)建無向連通圖，再通過幾個模塊運行函數(shù)完成校園信息簡介查詢，校園景點間最短距離計算和輸出以及退出功能。

（2）詳細設(shè)計

//定義全局變量 int bian[n][n];int zhjl[n][n];int path[n][n];//構(gòu)建dy類 class dy{ public: dy();

~dy();void jj();int zuiduan();void floyed();void shuchu(int,int);

// 邊的值

// 兩點間的最短距離

// 經(jīng)過的景點

};首先，通過dy類的構(gòu)造函數(shù)構(gòu)建鄰接矩陣。dy::dy(){ for(int i=0;i

bian[1][3]=bian[3][1]=150;bian[1][6]=bian[6][1]=300;bian[2][3]=bian[3][2]=100;bian[3][4]=bian[4][3]=50;bian[3][5]=bian[5][3]=200;bian[4][5]=bian[5][4]=100;bian[4][8]=bian[8][4]=350;

bian[4][9]=bian[9][4]=250;bian[5][6]=bian[6][5]=100;bian[5][7]=bian[7][5]=250;bian[5][8]=bian[8][5]=300;bian[6][7]=bian[7][6]=200;bian[7][8]=bian[8][7]=100;bian[8][9]=bian[9][8]=400;bian[9][10]=bian[10][9]=100;//將各點到自己的距離定義為0 bian[1][1]=bian[2][2]=bian[3][3]=bian[4][4]=bian[5][5]=0;bian[6][6]=bian[7][7]=bian[8][8]=bian[9][9]=bian[10][10]=0;} 接著，jj函數(shù)實現(xiàn)景點列表輸出和景點查詢。void dy::jj(){ int a;cout<<“您想查詢哪個景點的詳細信息?”<>a;getchar();cout<

cin>>i>>j;if(i>n||i<=0||j>n||j<=0){ cout<<“輸入信息錯誤！”<

cout<<“請輸入要查詢的兩個景點的編號(1-10的數(shù)字編號):”<>i>>j;} else { floyed();shuchu(i,j);} return 1;} 再者，floyed函數(shù)用三個for循環(huán)求解最短路，將兩點間的n個點看做一個點，用path數(shù)組記錄這個點，在依次求出各點間最短路，并用zdjl數(shù)組保存起來。

void dy::floyed(){ int i,j,k;for(i=1;i(zdjl[i][k]+zdjl[k][j])){//用path[][]記錄從i到j(luò)的最短路徑上點j的前驅(qū)景點的序號

zdjl[i][j]=zdjl[i][k]+zdjl[k][j];path[i][j]=k;path[j][i]=k;} } 最后，shuchu函數(shù)判斷輸入兩景點編號大小，完成正序輸出和逆序輸出。void dy::shuchu(int i,int j){ int a,b;a=i;b=j;cout<<“您要查詢的兩景點間最短路徑是:”<

cout<<“<-”<

“<“<

”<”<

（4）測試結(jié)果

（4）程序清單

#include //#include

using namespace std;

#define INT_MAX 10000 #define n 11

//定義全局變量 int bian[n][n];int zdjl[n][n];int path[n][n];

class dy{ public:

dy();~dy();void jj();int zuiduan();void floyed();

// 邊的值

// 兩點間的最短距離

// 經(jīng)過的景點

void shuchu(int,int);};dy::dy(){ for(int i=0;i

bian[1][3]=bian[3][1]=150;bian[1][6]=bian[6][1]=300;bian[2][3]=bian[3][2]=100;bian[3][4]=bian[4][3]=50;bian[3][5]=bian[5][3]=200;bian[4][5]=bian[5][4]=100;bian[4][8]=bian[8][4]=350;

bian[4][9]=bian[9][4]=250;bian[5][6]=bian[6][5]=100;bian[5][7]=bian[7][5]=250;bian[5][8]=bian[8][5]=300;bian[6][7]=bian[7][6]=200;bian[7][8]=bian[8][7]=100;bian[8][9]=bian[9][8]=400;bian[9][10]=bian[10][9]=100;bian[1][1]=bian[2][2]=bian[3][3]=bian[4][4]=bian[5][5]=0;bian[6][6]=bian[7][7]=bian[8][8]=bian[9][9]=bian[10][10]=0;} dy::~dy(){} void dy::jj()int a;{ cout<<“您想查詢哪個景點的詳細信息?”<>a;getchar();cout<

cout<

break;case 2:

cout<<“校醫(yī)院是學(xué)校內(nèi)設(shè)的公益性、非盈利性的醫(yī)療機構(gòu)。承擔(dān)學(xué)校社區(qū)范圍內(nèi)師生員工的“六位一體”的醫(yī)療工作。”<

cout<

break;case 3: cout<<“圖書館現(xiàn)有藏書215萬冊,其中印刷型圖書146萬冊，電子圖書69萬冊,長期訂閱的中外文期刊2500余種。建有“中國學(xué)術(shù)期刊”、“萬方數(shù)據(jù)資源”、“人大復(fù)印報刊資料”全文數(shù)據(jù)庫、“超星數(shù)字圖書館”等信息資源鏡像站。”<

cout<

cout<

break;case 5: cout<<“ 問鼎廣場是杭州電子科技大學(xué)標(biāo)志性建筑，位于校圖書館正面。”<

cout<

break;case 6: cout<<“3教是學(xué)校機房重地。”<

cout<

break;case 7: cout<<“據(jù)說杭電正大門可是花了500萬啊，可以說是杭電最奢侈的一個建筑物了，所以大家不可不看啊，不能錯過啊~~”<

cout<

break;case 8: cout<<“行政樓學(xué)校領(lǐng)導(dǎo)工作和處理事務(wù)的地方。”<

cout<

break;case 9: cout<<“體育館是學(xué)校舉行大型活動的場所，有一個很大的籃球場。”<

break;case 10: cout<<“宿舍是學(xué)生生活的基本場所，有多個食堂提供不同風(fēng)味的食物，還有2個超市方便同學(xué)們的日常生活。”<

cout<<“請輸入1-10的數(shù)字編號:”<

break;} } int dy::zuiduan(){ int i,j;cout<<“請輸入要查詢的兩個景點的編號(1-10的數(shù)字編號):”<>i>>j;if(i>n||i<=0||j>n||j<=0){ cout<<“輸入信息錯誤！”<>i>>j;} else { floyed();shuchu(i,j);} return 1;} void dy::floyed(){ int i,j,k;for(i=1;i(zdjl[i][k]+zdjl[k][j])){//用path[][]記錄從i到j(luò)的最短路徑上點j的前驅(qū)景點的序號

zdjl[i][j]=zdjl[i][k]+zdjl[k][j];path[i][j]=k;path[j][i]=k;} } void dy::shuchu(int i,int j){ int a,b;a=i;b=j;cout<<“您要查詢的兩景點間最短路徑是:”<“<“<

”<”<

int main(){ int i,j,s=1,k;dy dy;while(s){ cout<<“----------------杭州電子科技大學(xué)導(dǎo)游系統(tǒng)!----------------”<>k;switch(k){ case 1: cout<<“進入景點信息查詢:”;dy.jj();break;case 2: cout<<“進入最短路徑查詢:”<

4.個人小結(jié)

在前兩次編寫程序之后，我已經(jīng)能夠輕車熟路的編寫程序了，對于C++的數(shù)據(jù)結(jié)構(gòu)風(fēng)格也有所領(lǐng)悟，感覺相對輕松一些。

經(jīng)過這次練習(xí)，我發(fā)現(xiàn)我還是有一些沒有注意的地方，我發(fā)現(xiàn)我對于書本上的知識吸收還有欠缺，然后編寫程序不夠仔細，有一些小差錯導(dǎo)致編譯出現(xiàn)錯誤，后來檢查后修正了。我要在以后的學(xué)習(xí)中注意以下幾點：

1.認真上好專業(yè)課，多在實踐中鍛煉自己。2.寫程序要考慮周到，嚴密。

3.在做設(shè)計的時候要有信心，有耐心，不浮躁。

4.認真學(xué)習(xí)課本知識，掌握課本中的知識點，并在此基礎(chǔ)上學(xué)會靈活運用。

5.在課余時間多寫程序，熟練掌握在調(diào)試程序過程中常見的錯誤，一邊節(jié)約調(diào)試程序的時間。

第二篇：校園導(dǎo)游實驗報告

校園導(dǎo)游實驗報告

學(xué)號：200930457018

姓名：熊博 班級：09計科1班 完成日期：2010-12-21

1、問題描述

制作陶瓷學(xué)院的校園導(dǎo)游圖，游客通過終端可詢問：（1）從某一景點到另一景點的最短路徑。

（2）游客從公園進入，選取一條最佳路線3，使游客可以不重復(fù)地游覽各景點，最后回到出口（出口就在入口處旁邊）

2、要求

（1）將導(dǎo)游圖看作一張帶權(quán)無向圖，頂點表示公園的各個景點，邊表示各景點之間的道路，邊上的權(quán)值表示距離。為此圖選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)。

（2）把各種路徑都顯示給游客，由游客自己選擇游覽路線。（3）畫出景點分布圖于屏幕上。

3、實現(xiàn)提示

（1）第一實際是最短路徑問題，如果有幾條路徑長度相同，可選擇途徑景點較少的路徑提供給游客。

（2）第二問可采用深度優(yōu)先搜索，如果有多種路徑可選擇，則選擇帶權(quán)路徑最小的路線提供給游客。

2.概要設(shè)計：

typedef struct ArCell { int adj;

//路徑長度

}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct

//圖中頂點表示主要景點，存放景點的信息 { char name[30];int num;int x;int y;char introduction[500];//簡介 }infotype;typedef struct { infotype vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;}MGraph;MGraph b;

void dij(MGraph *);計算出起點到其他各個頂點之間的最短路徑 void floyd(MGraph *);計算任意兩個景點之間的最短路徑 void Search(MGraph *G);查看景點信息 void jdbrowser();查看主要景點布局圖

3.詳細設(shè)計：

main函數(shù)： void main(){

int k;system(“color cf”);system(“mode con: cols=140 lines=130”);b=InitGraph();system(“cls”);printf(“

歡迎您進入景德鎮(zhèn)陶瓷學(xué)院學(xué)校園導(dǎo)游咨詢系統(tǒng)n”);printf(“ttn”);Sleep(1000);do {

while(1)

{

printf(“

n”);

printf(“

主要景點列表

n”);

printf(“

n”);

printf(“

<1> 操場

<2> 游泳館

n”);

printf(“

<3> 3教

<4> 體育館

n”);

printf(“

<5> 2教

<6> 1教

n”);

printf(“

<7> 圖書館

<8> 2實驗樓

n”);

printf(“

<9> 9實驗樓

<10> 醫(yī)院

n”);

printf(“

<11> 東西辦

<12> 9#宿舍樓 n”);

printf(“

<13> 綜合食堂

<14> 二三食堂 n”);

printf(“

<15> 80廣場

<16>大門

n”);

printf(“

n”);

printf(“ttn”);

printf(“

┏━━━━━━━━━━━━━━━━━━━━━━━┓n”);

printf(“

┃

1.查看主要景點布局圖

┃n”);

printf(“

┃

2.查看景點信息

┃n”);

printf(“

┃

3.查看某一景點到其他景點的最短路徑

┃n”);

printf(“

┃

4.查看任意兩個景點之間的最短路徑

┃n”);

printf(“

┃

0.退出系統(tǒng)

┃n”);

printf(“

┗━━━━━━━━━━━━━━━━━━━━━━━┛n”);

printf(“請輸入您的選擇選擇，按回車鍵結(jié)束:”);

scanf(“%d”,&k);

if(k<0||k>5)

{

printf(“輸入有誤請重新輸入，按回車鍵結(jié)束!n”);

scanf(“%d”,&k);

}

else break;} switch(k){ case 1:jdbrowser();system(“cls”);break;case 2:Search(&b);system(“cls”);break;case 3:dij(&b);system(“cls”);break;case 4:floyd(&b);system(“cls”);break;case 0:exit(0);

} }while(1);}

圖形初始化函數(shù)： MGraph InitGraph(){ MGraph G;int i,j;G.vexnum=17;G.arcnum=19;for(i=0;i

G.vexs[i].num=i;strcpy(G.vexs[1].name,“操場”);strcpy(G.vexs[1].introduction,“足球場，現(xiàn)代化塑膠跑道,人造草坪,鍛煉身體的場所”);strcpy(G.vexs[2].name,“游泳館”);strcpy(G.vexs[2].introduction,“一般只是暑假期間開放，水不是很干凈”);strcpy(G.vexs[3].name,“3教”);strcpy(G.vexs[3].introduction,“多媒體教學(xué)場所,設(shè)施先進,環(huán)境良好”);strcpy(G.vexs[4].name,“體育館”);strcpy(G.vexs[4].introduction,“里面有籃球場還有羽毛球場，平時用作羽毛球場地”);strcpy(G.vexs[5].name,“2教”);strcpy(G.vexs[5].introduction,“學(xué)院第二大教學(xué)樓,環(huán)境較差”);strcpy(G.vexs[6].name,“1教”);strcpy(G.vexs[6].introduction,“學(xué)院最大的教學(xué)樓,共5層，環(huán)形建筑,適宜學(xué)習(xí)”);strcpy(G.vexs[7].name,“圖書館”);strcpy(G.vexs[7].introduction,“藏書60萬冊,設(shè)施良好，2樓為電子閱覽室，環(huán)境幽雅”);strcpy(G.vexs[8].name,“2實驗樓”);strcpy(G.vexs[8].introduction,“信息科學(xué)與技術(shù)學(xué)院所在地”);strcpy(G.vexs[9].name,“9實驗樓”);strcpy(G.vexs[9].introduction,“學(xué)校機房所在地”);strcpy(G.vexs[10].name,“醫(yī)院”);strcpy(G.vexs[10].introduction,“校醫(yī)院,設(shè)施不是很齊全，收費較貴”);strcpy(G.vexs[11].name,“春暉樓”);strcpy(G.vexs[11].introduction,“全體教師辦公場所，樓高12層，各種設(shè)施齊全”);strcpy(G.vexs[12].name,“9#宿舍樓”);strcpy(G.vexs[12].introduction,“裝飾古樸，設(shè)施還算齊全，就是擠了點”);strcpy(G.vexs[13].name,“綜合食堂”);strcpy(G.vexs[13].introduction,“新建標(biāo)準(zhǔn)化食堂，食物種類多，但是價格比較貴。”);strcpy(G.vexs[14].name,“二三食堂”);strcpy(G.vexs[14].introduction,“收費比較便宜的食堂，二樓的套餐還可以，主要是便宜，不過菜有點難吃”);strcpy(G.vexs[15].name,“80廣場 ”);strcpy(G.vexs[15].introduction,“新建的廣場，據(jù)說由80界校友捐贈。”);strcpy(G.vexs[16].name,“大門”);strcpy(G.vexs[16].introduction,“我們學(xué)校的大門，車輛進出的地方。設(shè)有保安。”);G.vexs[1].x=1;G.vexs[1].y=3;G.vexs[2].x=2;G.vexs[2].y=3;G.vexs[3].x=1;G.vexs[3].y=2;G.vexs[4].x=2;G.vexs[4].y=2;G.vexs[5].x=2;G.vexs[5].y=1;G.vexs[6].x=3;G.vexs[6].y=1;G.vexs[7].x=3;G.vexs[7].y=2;G.vexs[8].x=3;G.vexs[8].y=3;G.vexs[9].x=3;G.vexs[9].y=4;G.vexs[10].x=4;G.vexs[10].y=1;G.vexs[11].x=5;G.vexs[11].y=1;G.vexs[12].x=5;G.vexs[12].y=4;G.vexs[13].x=6;G.vexs[13].y=1;G.vexs[14].x=6;G.vexs[14].y=3;G.vexs[15].x=5;G.vexs[15].y=3;for(i=0;i

for(j=0;j

G.arcs[i][j].adj=INFINITY;G.arcs[1][2].adj=40;G.arcs[2][8].adj=80;

G.arcs[2][4].adj=50;G.arcs[3][4].adj=10;

G.arcs[4][7].adj=42;

G.arcs[4][5].adj=50;G.arcs[5][6].adj=40;

G.arcs[6][7].adj=50;

G.arcs[6][16].adj=20;G.arcs[6][10].adj=100;G.arcs[7][8].adj=50;G.arcs[8][9].adj=100;G.arcs[8][15].adj=200;G.arcs[10][11].adj=100;G.arcs[11][13].adj=50;

G.arcs[15][14].adj=80;G.arcs[13][14].adj=100;G.arcs[11][15].adj=100;G.arcs[12][15].adj=10;for(i=1;i

for(j=1;j

G.arcs[i][j].adj=G.arcs[j][i].adj;

return G;}//InitGraph end 迪杰斯特拉算法求一點到任意其他景點的最短路徑： void dij(MGraph * G){ int v,w,w1,i,j,min,t=0,x,flag=1,v0;

int final[20], D[20], p[20][20];while(flag){

printf(“請您輸入一個起始景點編號，按回車鍵結(jié)束:”);

scanf(“%d”,&v0);

if(v0<0||v0>G->vexnum)

{

printf(“景點編號不存在!請重新輸入景點編號,按回車鍵結(jié)束:”);

scanf(“%d”,&v0);

}

if(v0>=0&&v0vexnum)

flag=0;} for(v=1;vvexnum;v++){

final[v]=0;

D[v]=G->arcs[v0][v].adj;for(w=1;wvexnum;w++)

p[v][w]=0;if(D[v]

{

p[v][v0]=1;p[v][v]=1;

} } D[v0]=1;final[v0]=1;for(i=1;ivexnum;i++){

min=INFINITY;

for(w=1;wvexnum;w++)

if(!final[w])

if(D[w]

final[v]=1;

for(w=1;wvexnum;w++)

if(!final[w]&&(min+G->arcs[v][w].adj

{

D[w]=min+G->arcs[v][w].adj;

for(x=0;xvexnum;x++)

p[w][x]=p[v][x];

p[w][w]=1;

}

} } for(v=1;vvexnum;v++){ if(v!=v0){ printf(“%s”,G->vexs[v0].name);w1=v0;} else continue;do {

flag=0;min=INFINITY;

for(w=1;wvexnum;w++)

{

if(p[v][w]&&w!=v0)

{

flag=1;

if(D[w]

}

}

if(flag)

{

if(G->vexs[w1].xvexs[j].x)

printf(“向東走%dm”,G->arcs[w1][j].adj);

if(G->vexs[w1].x>G->vexs[j].x)

printf(“向西走%dm”,G->arcs[w1][j].adj);

if(G->vexs[w1].yvexs[j].y)

printf(“向北走%dm”,G->arcs[w1][j].adj);

if(G->vexs[w1].y>G->vexs[j].y)

printf(“向南走%dm”,G->arcs[w1][j].adj);

printf(“-->%s”,G->vexs[j].name);

w1=j;

p[v][j]=0;

}

else break;

}while(1);

printf(“n

總路線長%dmnn”,D[v]);} printf(“完畢，按任意鍵繼續(xù)!n”);getch();Floyd算法求任意兩點間的最短距離： void floyd(MGraph * G)

// 計算任意兩個景點之間的最短路徑 { int v,w,w1,i,j,v1,min,t=0,x,flag=1,v0;

int final[20], D[20], p[20][20];while(flag){

printf(“請您輸入一個起始景點編號，按回車鍵結(jié)束:”);

scanf(“%d”,&v0);

if(v0<0||v0>G->vexnum)

{

printf(“景點編號不存在!請重新輸入景點編號:”);

scanf(“%d”,&v0);

}

if(v0>=0&&v0vexnum)

flag=0;} flag=1;while(flag){

printf(“請您輸入一個目的地景點編號，按回車鍵結(jié)束:”);

scanf(“%d”,&v1);

if(v1<0||v1>G->vexnum)

{

printf(“景點編號不存在!請重新輸入景點編號:”);

scanf(“%d”,&v1);

}

if(v1>=0&&v1vexnum)

flag=0;} for(v=0;vvexnum;v++){

final[v]=0;

D[v]=G->arcs[v0][v].adj;

for(w=0;wvexnum;w++)

p[v][w]=0;

if(D[v]

{

p[v][v0]=1;p[v][v]=1;

} } D[v0]=0;final[v0]=1;for(i=1;ivexnum;i++){

min=INFINITY;

for(w=0;wvexnum;w++)

if(!final[w])

if(D[w]

final[v]=1;

for(w=0;wvexnum;w++)

if(!final[w]&&(min+G->arcs[v][w].adj

{

D[w]=min+G->arcs[v][w].adj;

for(x=0;xvexnum;x++)

p[w][x]=p[v][x];

p[w][w]=1;

} }

v=v1;

w1=v0;

printf(“%s”,G->vexs[v0].name);do {

flag=0;min=INFINITY;

for(w=0;wvexnum;w++)

{

if(p[v][w]&&w!=v0)

{

flag=1;

if(D[w]

}

}

if(flag)

{

if(G->vexs[w1].xvexs[j].x)

printf(“向東走%dm”,G->arcs[w1][j].adj);

if(G->vexs[w1].x>G->vexs[j].x)

printf(“向西走%dm”,G->arcs[w1][j].adj);

if(G->vexs[w1].yvexs[j].y)

printf(“向北走%dm”,G->arcs[w1][j].adj);

if(G->vexs[w1].y>G->vexs[j].y)

printf(“向南走%dm”,G->arcs[w1][j].adj);

printf(“-->%s”,G->vexs[j].name);

w1=j;

p[v][j]=0;

}

else break;

}while(1);printf(“n

總路線長%dmnn”,D[v]);printf(“完畢，按任意鍵繼續(xù)!n”);getch();}

查詢景點信息函數(shù)： void Search(MGraph *G){ int k,flag=1;while(flag){

printf(“請您輸入要查詢的景點編號，按回車鍵結(jié)束:”);

scanf(“%d”,&k);

if(k<0||k>=G->vexnum)

{

printf(“景點編號不存在!請重新輸入景點編號:”);

scanf(“%d”,&k);

}

if(k>=0&&kvexnum)

flag=0;} printf(“┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓n”);printf(“┃編號┃景點名稱

┃簡介

┃n”);printf(“┃%-4d┃%-16s┃%-96s┃n”,G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction);printf(“┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛n”);printf(“完畢，按任意鍵繼續(xù)!n”);getch();}

主要的景點顯示函數(shù)： void jdbrowser(){ printf(“●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●n”);printf(“●

●n”);

printf(“●

(9)九實驗樓

(12)九棟

●n”);

printf(“●

┃

┃

●n”);

printf(“●

┃

┃

●n”);

printf(“●

(1)操場━━(2)游泳館━━━━(8)二實驗樓━━━━━━━━━━━━━━━━━(15)80廣場━━━━(14)二三食堂

●n”);printf(“●

┃

┃

┃

┃

●n”);

printf(“●

┃

┃

┃

┃

●n”);

printf(“●

(3)三教━━(4)體育館━━━━━(7)圖書館

┃

┃

●n”);printf(“●

┃

┃

┃

┃

●n”);

printf(“●

┃

┃

┃

┃

●n”);

printf(“●

(5)二教━━━━━━(6)一教━━━━━━━━━━━━(10)醫(yī)院━━━━━(11)東西辦━━━━(13)綜合食堂

●n”);printf(“●

┃

●n”);

printf(“●

(16)大門

●n”);

printf(“●

●n”);

printf(“●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●n”);printf(“輸出完畢，按任意鍵返回!n”);getch();}

4.使用說明：

（1）.查看主要景點布局圖（2）.查看景點信息

（3）.查看某一景點到其他景點的最短路徑（4）.查看任意兩個景點之間的最短路徑

（0）.退出系統(tǒng)

5.測試結(jié)果：

主界面

景點圖

景點信息

從某點到其他點的最短路徑

任意兩點的最短路徑

退出系統(tǒng)

6.參考資料：

1、《數(shù)據(jù)結(jié)構(gòu)（C語言版）》 嚴蔚敏，吳偉民 清華大學(xué)出版社

2、《數(shù)據(jù)結(jié)構(gòu)—C語言描述》 耿國華等 西安電子科技大學(xué)出版社

3、Data Structure &Program Design in C Robert L.Kruse 清華大學(xué)出版社

4、《數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述）》 殷人昆 清華大學(xué)出版社

第三篇：課程設(shè)計(校園導(dǎo)游)

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 長 春 大 學(xué)

課程設(shè)計紙

一、設(shè)計題目

校園導(dǎo)游咨詢

二、需求分析

（1）設(shè)計你的學(xué)校的校園平面圖，所含景點不少于10個。以圖中頂點表示學(xué)校各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。

（2）為來訪客人提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一條最短的簡單路徑。

（3）為來訪客人提供圖中任意景點相關(guān)信息的查詢。（4）界面美觀，方便使用。通過主菜單操作。

三、總體設(shè)計

3.1 設(shè)計思路

設(shè)計一個校園導(dǎo)游系統(tǒng)，應(yīng)用到數(shù)據(jù)結(jié)構(gòu)中學(xué)到的圖的建立，各景點應(yīng)存在一個圖中，而計算不重復(fù)路線的時候需要應(yīng)用到弗洛伊德圖的遍歷。計算倆景點間最短路徑應(yīng)用到最小生成樹的遍歷。

景點數(shù)據(jù)裝在一個圖中，能夠輸入圖的頂點和邊的信息，并存儲到相應(yīng)存儲結(jié)構(gòu)中然后輸出圖的鄰接矩陣。

鄰接矩陣是表示頂點之間相鄰關(guān)系。

生成樹是指：如果G是一個圖，這個圖的生成子圖T是樹，那么可以說T為G的生成樹。一個圖有生成樹當(dāng)且僅當(dāng)這個圖連通。可通過求該網(wǎng)絡(luò)的最小生成樹達到求解線路或總代價最小的最佳方案。

弗洛伊德算法是通過一個圖的權(quán)值矩陣求出它的每兩點間的最短路徑矩陣。它是從圖的帶權(quán)鄰接矩A=[a(i,j)] n×n開始，遞歸地進行n次更新，即由矩陣D(0)=A，按一個公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；??；最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j(luò)號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點矩陣path來記錄兩點間的最短路徑。3、2系統(tǒng)功能設(shè)計

本系統(tǒng)除了有主程序模塊外還有3個子功能菜單。3個子功能的設(shè)計描述如下。（1）學(xué)校景點介紹

學(xué)校景點介紹由函數(shù)introduce()實現(xiàn)。當(dāng)用戶選擇該功能，系統(tǒng)即能輸出學(xué)校全部景點的信息：包括景點編號、景點名稱及景點簡介。

共 頁

第 頁

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 長 春 大 學(xué)

課程設(shè)計紙

（2）查看兩景點間最短路徑

查看兩景點間最短路徑由函數(shù)shortestdistance()實現(xiàn)。該功能采用弗洛伊德（Floyd）算法實現(xiàn)。當(dāng)用戶選擇該功能，系統(tǒng)能根據(jù)用戶輸入的起始景點及目的地景點編號，查詢?nèi)我鈨蓚€景點之間的最短路徑線路及距離。

（3）退出

即退出校園導(dǎo)游系統(tǒng)，由exit(0)函數(shù)實現(xiàn)。3、3 模塊間調(diào)用關(guān)系

主程序模塊

（界面）

景點最短路徑查詢

景點信息查詢

退出

四、詳細設(shè)計 4、1數(shù)據(jù)存儲

(1)無向帶權(quán)圖（無向網(wǎng)）的定義

int i,j;

char k;

for(i=0;i<=n;i++)

for(j=0;j<=n;j++)

{

cost[i][j]=INT_MAX;

}

cost[1][3]=cost[3][1]=2;

cost[2][3]=cost[3][2]=1;

cost[2][4]=cost[4][2]=2;

cost[3][10]=cost[10][3]=4;

cost[1][10]=cost[10][1]=4;

cost[2][10]=cost[10][2]=4;

cost[4][10]=cost[10][4]=4;

cost[1][4]=cost[4][1]=5;

cost[4][5]=cost[5][4]=3;

cost[4][9]=cost[9][4]=4;

共 頁

第 頁

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 長 春 大 學(xué)

課程設(shè)計紙

cost[5][9]=cost[9][5]=8;cost[5][7]=cost[7][5]=4;cost[5][6]=cost[6][5]=2;cost[6][7]=cost[7][6]=1;cost[7][8]=cost[8][7]=3;cost[8][6]=cost[6][8]=4;cost[1][1]=cost[2][2]=cost[3][3]=cost[4][4]=cost[5][5]=0;cost[6][6]=cost[7][7]=cost[8][8]=cost[9][9]=cost[10][10]=0;

（2）全局變量定義

#define INT_MAX 10000 #define n 10 int cost[n][n];

/* 邊的值*/ int shortest[n][n];

/* 兩點間的最短距離*/ int path[n][n];

/* 經(jīng)過的景點*/ 4、2主程序模塊

用于作為界面，顯示校園景點和概況描述，提供各子模塊的連接 如上圖所示 程序設(shè)計 while(1)

{

printf(“----------------歡迎使用中北大學(xué)導(dǎo)游系統(tǒng)!----------------n”);

printf(“1.景點信息查詢???請按 i(introduc)鍵n”);

printf(“2.景點最短路徑查詢?請按 s(shortestdistance)鍵n”);

printf(“3.退出系統(tǒng)?????請按 e(exit)鍵n”);

printf(“學(xué)校景點列表:n”);

printf(“1:學(xué)校南門

”);

printf(“2:學(xué)生公寓

”);

printf(“3:柏林園

”);

printf(“4:餐廳

”);

printf(“5:體育館n”);

printf(“6:圖書館

”);

printf(“7:重點實驗室

”);

printf(“8:主樓

”);

printf(“9:科藝苑

”);

printf(“10:國防生公寓n”);

printf(“請選擇服務(wù):”);

scanf(“n%c”,&k);

共 頁

第 頁

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 長 春 大 學(xué)

課程設(shè)計紙

switch(k)

{

case 'i':

printf(“進入景點信息查詢:”);

introduce();

break;

case 's':

printf(“進入最短路徑查詢:”);

shortestdistance();

break;

case 'e':

exit(0);

default:

printf(“輸入信息錯誤！n請輸入字母i或s或e.n”);

break;

}

} 4、3景點信息查詢模塊

在主菜單下，用戶輸入i回車，根據(jù)屏幕提示輸入一個要查詢的景點編號3回車后，運行結(jié)果如上圖所示。

不足之處：僅能根據(jù)景點編號進行查詢，可以增加根據(jù)景點名進行查詢的功能。

程序設(shè)計

void introduce(){/*景點介紹*/

int a;

printf(“您想查詢哪個景點的詳細信息?請輸入景點編號:”);

scanf(“%d”,&a);

getchar();

printf(“n”);

switch(a)

{

case 1:

printf(“1:學(xué)校南門nn 學(xué)校的正門，前面豎立著一尊彭德華的石

共 頁

第 頁

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 長 春 大 學(xué)

課程設(shè)計紙

像，氣勢宏偉。nn”);break;

case 2:

printf(“2:學(xué)生公寓集中的地方。nn”);break;

case 3:

printf(“3:柏林園nn 晨讀鍛煉得地方。nn”);break;

case 4:

printf(“4:餐廳nn 學(xué)生老師就餐的地方nn”);break;

case 5:

printf(“5:體育館nn 體育館nn 學(xué)生上體育課及運動的場地，設(shè)有田徑場、足球場、籃球場等。nn”);break;

case 6:

printf(“6:圖書館nn 學(xué)校信息資源中心，內(nèi)設(shè)大量的自習(xí)室。nn”);break;

case 7:

printf(“7:重點實驗室nn 我校的研究科研中心nn”);break;

case 8:

printf(“8:主樓nn 學(xué)校行政辦公的主樓。nn”);break;

case 9:

printf(“9:科藝苑nn 有咖啡廳和放映室。nnn”);break;

case 10:

printf(“10: 國防生公寓nn 國防生居住地地方。nn”);break;

default:

printf(“景點編號輸入錯誤！請輸入1->10的數(shù)字編號！nn”);break;

} }/*introduce*/ 4、4景點最短路徑查詢模塊

在主菜單下，用戶輸入3回車，根據(jù)屏幕提示輸入一個出發(fā)景點編號及目的地景點號：6“,”3回車后，運行結(jié)果如上圖所示。

不足之處：只能看到最短路徑編號，但不知具體名稱，設(shè)計還不夠人性化。

程序設(shè)計（由floyed()和display(i,j)兩個子模塊完成）void floyed(){/*用floyed算法求兩個景點的最短路徑*/

共 頁

第 頁

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 長 春 大 學(xué)

課程設(shè)計紙

int i,j,k;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

shortest[i][j]=cost[i][j];

path[i][j]=0;

}

for(k=1;k<=n;k++)

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(shortest[i][j]>(shortest[i][k]+shortest[k][j]))

{/*用path[][]記錄從i到j(luò)的最短路徑上點j的前驅(qū)景點的序號*/

shortest[i][j]=shortest[i][k]+shortest[k][j];

path[i][j]=k;

path[j][i]=k;

} }/*floyed*/

void display(int i,int j){/* 打印兩個景點的路徑及最短距離 */

int a,b;

a=i;

b=j;

printf(“您要查詢的兩景點間最短路徑是:nn”);

if(shortest[i][j]!=INT_MAX)

{

if(i

{

printf(“%d”,b);

while(path[i][j]!=0)

{/* 把i到j(luò)的路徑上所有經(jīng)過的景點按逆序打印出來*/

printf(“<-%d”,path[i][j]);

if(i

j=path[i][j];

else

i=path[j][i];

}

printf(“<-%d”,a);

printf(“nn”);

printf(“(%d->%d)最短距離是:%d米nn”,a,b,shortest[a][b]);

}

else

{

printf(“%d”,a);

while(path[i][j]!=0)

{/* 把i到j(luò)的路徑上所有經(jīng)過的景點按順序打印出來*/

printf(“->%d”,path[i][j]);

共 頁

第 頁

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 長 春 大 學(xué)

課程設(shè)計紙

if(i

j=path[i][j];

else

i=path[j][i];

}

printf(“->%d”,b);

printf(“nn”);

printf(“(%d->%d)最短距離是:%5d米nn”,a,b,shortest[a][b]);

}

}

else

printf(“輸入錯誤！不存在此路！nn”);

printf(“n”);}/*display*/ 4、5退出

在主菜單下，用戶輸入e回車，即退出校園導(dǎo)游系統(tǒng)。

五、設(shè)計總結(jié)5、1用戶手冊

1．本程序執(zhí)行文件為：湖北第二師范學(xué)院校園導(dǎo)游系統(tǒng).exe 2．進入本系統(tǒng)之后，隨即顯示系統(tǒng)主菜單界面。用戶可在該界面下輸入各子菜單前對應(yīng)的數(shù)字并按回車，執(zhí)行相應(yīng)子菜單命令。

3．查詢景點信息都是通過輸入景點編號并按回車實現(xiàn)，兩個景點號之間用空格隔開。進入本系統(tǒng)后，建議先選擇子菜單1――學(xué)校景點介紹，以了解景點名稱和景點編號的對應(yīng)關(guān)系。5、2心得體會

通過本次課程設(shè)計實驗，使我更能熟練地掌握c語言和數(shù)據(jù)結(jié)構(gòu)等知識的綜合運

共 頁

第 頁

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 長 春 大 學(xué)

課程設(shè)計紙

用。當(dāng)然在課程設(shè)計期間，也遇到了大大小小的一些問題，是我看到了自己的不足之處，使我認識到在以后的學(xué)習(xí)中要善于發(fā)現(xiàn)自己的不足，找出自己的薄弱環(huán)節(jié)，以便能夠更好的去鞏固所學(xué)的。

本次設(shè)計中要求求最短路徑，不重復(fù)走完一個圖，就必須了解最短路徑的算發(fā)和圖的遍歷。在拿到題目時，通過查找相關(guān)的資料才回憶起這兩種方法的具體算法。根據(jù)程序的具體要求來設(shè)計算法。在選用存儲方法是，要盡量選用時間復(fù)雜度較小的方法，這樣能夠節(jié)省程序執(zhí)行時間，提高查詢效率。

課程設(shè)計中所使用的計算機語言其使用范圍比較廣闊，在很多編程中都可以用到，所以無論以后我們從事計算機編程、軟件設(shè)計還是硬件、網(wǎng)絡(luò)等領(lǐng)域，都應(yīng)該學(xué)會、學(xué)精一門編程語言，這對我們以后的學(xué)習(xí)和工作有很大的幫助。

共 頁

第 頁

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 長 春 大 學(xué)

課程設(shè)計紙

附錄

/*包含頭文件*/ #include #include

/*定義符號常量*/ #define INT_MAX 10000 #define n 10

/*定義全局變量*/ int cost[n][n];/* 邊的值*/ int shortest[n][n];/* 兩點間的最短距離*/ int path[n][n];/* 經(jīng)過的景點*/

/*自定義函數(shù)原型說明*/ void introduce();int shortestdistance();void floyed();

void display(int i,int j);

void main(){/*主函數(shù)*/

int i,j;

char k;

for(i=0;i<=n;i++)

for(j=0;j<=n;j++)

cost[i][j]=INT_MAX;

cost[1][3]=cost[3][1]=2;

cost[2][3]=cost[3][2]=1;

cost[2][4]=cost[4][2]=2;cost[3][10]=cost[10][3]=4;cost[1][10]=cost[10][1]=4;cost[2][10]=cost[10][2]=4;cost[4][10]=cost[10][4]=4;

cost[1][4]=cost[4][1]=5;cost[4][5]=cost[5][4]=3;cost[4][9]=cost[9][4]=4;cost[5][9]=cost[9][5]=8;cost[5][7]=cost[7][5]=4;

cost[5][6]=cost[6][5]=2;

共 頁

第 頁

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 長 春 大 學(xué)

課程設(shè)計紙

cost[6][7]=cost[7][6]=1;

cost[7][8]=cost[8][7]=3;

cost[8][6]=cost[6][8]=4;

cost[1][1]=cost[2][2]=cost[3][3]=cost[4][4]=cost[5][5]=0;

cost[6][6]=cost[7][7]=cost[8][8]=cost[9][9]=cost[10][10]=0;

while(1)

{

printf(“----------------歡迎使用中北大學(xué)導(dǎo)游系統(tǒng)!----------------n”);

printf(“1.景點信息查詢???請按 i(introduc)鍵n”);

printf(“2.景點最短路徑查詢?請按 s(shortestdistance)鍵n”);

printf(“3.退出系統(tǒng)?????請按 e(exit)鍵n”);

printf(“學(xué)校景點列表:n”);

printf(“1:學(xué)校南門

”);

printf(“2:學(xué)生公寓

”);

printf(“3:柏林園

”);

printf(“4:餐廳

”);

printf(“5:體育館n”);

printf(“6:圖書館

”);

printf(“7:重點實驗室

”);

printf(“8:主樓

”);

printf(“9:科藝苑

”);

printf(“10:國防生公寓n”);

printf(“請選擇服務(wù):”);

scanf(“n%c”,&k);

switch(k)

{

case 'i':

printf(“進入景點信息查詢:”);

introduce();

break;

case 's':

printf(“進入最短路徑查詢:”);

shortestdistance();

break;

case 'e':

exit(0);

default:

printf(“輸入信息錯誤！n請輸入字母i或s或e.n”);

break;

}

} }/*main*/

共 頁

第 頁

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 長 春 大 學(xué)

課程設(shè)計紙

void introduce(){/*景點介紹*/

int a;

printf(“您想查詢哪個景點的詳細信息?請輸入景點編號:”);

scanf(“%d”,&a);

getchar();

printf(“n”);

switch(a)

{

case 1:

printf(“1:學(xué)校南門nn 學(xué)校的正門，前面豎立著一尊彭德華的石像，氣勢宏偉。nn”);break;

case 2:

printf(“2:學(xué)生公寓集中的地方。nn”);break;

case 3:

printf(“3:柏林園nn 晨讀鍛煉得地方。nn”);break;

case 4:

printf(“4:餐廳nn 學(xué)生老師就餐的地方nn”);break;

case 5:

printf(“5:體育館nn 體育館nn 學(xué)生上體育課及運動的場地，設(shè)有田徑場、足球場、籃球場等。nn”);break;

case 6:

printf(“6:圖書館nn 學(xué)校信息資源中心，內(nèi)設(shè)大量的自習(xí)室。nn”);break;

case 7:

printf(“7:重點實驗室nn 我校的研究科研中心nn”);break;

case 8:

printf(“8:主樓nn 學(xué)校行政辦公的主樓。nn”);break;

case 9:

printf(“9:科藝苑nn 有咖啡廳和放映室。nnn”);break;

case 10:

printf(“10: 國防生公寓nn 國防生居住地地方。nn”);break;

default:

printf(“景點編號輸入錯誤！請輸入1->10的數(shù)字編號！nn”);break;

} }/*introduce*/

int shortestdistance(){/*要查找的兩景點的最短距離*/

int i,j;

printf(“請輸入要查詢的兩個景點的編號(1->10的數(shù)字編號并用','間隔):”);

共 頁

第 頁

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 長 春 大 學(xué)

課程設(shè)計紙

scanf(“%d,%d”,&i,&j);

if(i>n||i<=0||j>n||j<0)

{

printf(“輸入信息錯誤！nn”);

printf(“ 請輸入要查詢的兩個景點的編號(1->10的數(shù)字編號并用','間隔):n”);

scanf(“%d,%d”,&i,&j);

}

else

{

floyed();

display(i,j);

}

return 1;}/*shortestdistance*/

void floyed(){/*用floyed算法求兩個景點的最短路徑*/

int i,j,k;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

shortest[i][j]=cost[i][j];

path[i][j]=0;

}

for(k=1;k<=n;k++)

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(shortest[i][j]>(shortest[i][k]+shortest[k][j]))

{/*用path[][]記錄從i到j(luò)的最短路徑上點j的前驅(qū)景點的序號*/

shortest[i][j]=shortest[i][k]+shortest[k][j];

path[i][j]=k;

path[j][i]=k;

} }/*floyed*/

void display(int i,int j){/* 打印兩個景點的路徑及最短距離 */

int a,b;

a=i;

b=j;

共 頁

第 頁

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 長 春 大 學(xué)

課程設(shè)計紙

printf(“您要查詢的兩景點間最短路徑是:nn”);

if(shortest[i][j]!=INT_MAX)

{

if(i

{

printf(“%d”,b);

while(path[i][j]!=0)

{/* 把i到j(luò)的路徑上所有經(jīng)過的景點按逆序打印出來*/

printf(“<-%d”,path[i][j]);

if(i

j=path[i][j];

else

i=path[j][i];

}

printf(“<-%d”,a);

printf(“nn”);

printf(“(%d->%d)最短距離是:%d米nn”,a,b,shortest[a][b]);

}

else

{

printf(“%d”,a);

while(path[i][j]!=0)

{/* 把i到j(luò)的路徑上所有經(jīng)過的景點按順序打印出來*/

printf(“->%d”,path[i][j]);

if(i

j=path[i][j];

else

i=path[j][i];

}

printf(“->%d”,b);

printf(“nn”);

printf(“(%d->%d)最短距離是:%5d米nn”,a,b,shortest[a][b]);

}

}

else

printf(“輸入錯誤！不存在此路！nn”);

printf(“n”);}/*display*/

共 頁

第 頁

第四篇：校園導(dǎo)游實驗報告——數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)實驗報告

——實驗六 簡單校園導(dǎo)游程序的設(shè)計與實現(xiàn)

本實驗的目的是通過對校園導(dǎo)游程序的設(shè)計與實現(xiàn)來熟練掌握圖型結(jié)構(gòu)在實際問題中的應(yīng)用。

一、【問題描述】

當(dāng)人們到一個陌生的地方去旅游的時候可能會找一個導(dǎo)游為自己在游玩的過程中提供方便。導(dǎo)游可以提供很多服務(wù)，比如介紹參觀景點的歷史背景等相關(guān)信息，推薦到下一個景點的最佳路徑，以及解答旅游者所提出的關(guān)于旅游經(jīng)典的相關(guān)問詢等等。對于新生剛剛來到校園，對校園環(huán)境不熟悉的情況也如此，一般都是高年級的學(xué)生充當(dāng)了“校園導(dǎo)游員”的角色，如果能夠提供一個程序讓新生或來訪的客人自主的通過與機器的“對話”來獲得相關(guān)的信息的話，將會節(jié)省大量的人力和時間。而且所提供的信息也能夠做到盡可能的準(zhǔn)確、詳盡。一個成功的校園導(dǎo)游程序可以替代現(xiàn)實生活中這些“校園導(dǎo)游員”，更方便了大家查詢校園相關(guān)的信息。

本次實驗需要開發(fā)一個簡單的校園導(dǎo)游程序，程序的主體功能為：

1、顯示校園平面圖，方便用戶直觀的看到校園的全景示意圖，并確定自己的位置。

2、為用戶提供對平面圖中任意場所的相關(guān)信息的查詢。

3、為用戶提供對平面圖中任意場所的問路查詢。

二、【數(shù)據(jù)結(jié)構(gòu)設(shè)計】

由于各個場所通過校園中的道路相連，各個場所和連接它們的道路構(gòu)成了整個校園的地理環(huán)境，所以使用圖這種數(shù)據(jù)結(jié)構(gòu)對他們?nèi)ミM行描述。以圖中的頂點表示校園內(nèi)各個場所，應(yīng)包含場所名稱、代號、簡介等信息；以邊表示連接各個場所的道路，應(yīng)包含道路的代號、路徑的長度等信息。頂點和邊均使用結(jié)構(gòu)體定義，整個圖的數(shù)據(jù)結(jié)構(gòu)可以采用教材中介紹的各種表示方法，例如帶權(quán)的鄰接矩陣。

三、【功能（函數(shù)）設(shè)計】

1、顯示校園平面圖的功能模塊。

通過讀文件的方式將各個地點的信息讀入程序中.平面圖中應(yīng)醒目的標(biāo)識出場所的準(zhǔn)確名稱以備用戶查詢。河北大學(xué)校園導(dǎo)游的基本地點信息。

***************歡迎進入河北大學(xué)校園導(dǎo)游系統(tǒng)!**************-----------------------景點名稱---------------------------

主樓 多功能館 毓秀園 圖書館

操場

留學(xué)生樓

七教 八教

九教 成教 南大門 北大門

一教 逸夫樓 博物館 物理樓

電信樓 化學(xué)樓 生科樓 建工樓

北院食堂

南院食堂

竹園 梅園

桂園 菊園 易百超市 北院生活園區(qū)

---------------------------地點的存儲

typedef struct Vertex//頂點結(jié)構(gòu)體 { int No;//地點編號

char name[20];//地點名稱

char info[1000];//地點簡介 }Vertex;typedef struct //無向圖結(jié)構(gòu)體 { Vertex view[Max_Vertex];int edges[Max_Vertex][Max_Vertex];//邊的鄰接矩陣

int vnum,anum;//頂點和邊的個數(shù) }Graph;

2、查詢?nèi)我鈭鏊南嚓P(guān)信息查詢的功能模塊。

此模塊接收用戶所輸入的場所名稱，并將場所的簡介信息反饋給用戶。查找出查詢的場所將其信息輸出,信息通過文本文件讀入 函數(shù)void introduction(Graph &G)實現(xiàn)

先通過strcpy進行查找，再講找到頂點v1 G.view[v1].info輸出

3、任意場所的問路查詢的功能模塊。

void shortpath(Graph &G,int v0,int v1)；此函數(shù)運用克魯斯卡爾算法計算兩點間最短路徑。

void dispath(Graph &G)//查詢最短路徑 { ?shortpath(G, v0, v1)； } 此模塊接收用戶所輸入的場所名稱，并在調(diào)用shortpath(G, v0, v1)；計算出最短路徑相關(guān)項的信息反饋給用戶。

4、求單源點到其他各點的最短路徑的功能模塊。

此模塊計算并記錄從校園門口到各個場所的最短路徑。for(i=0;i

四、【界面設(shè)計】

本程序為方便用戶所設(shè)計，由于使用的最終用戶大多對校園的情況并不熟悉，所以在圖中給出的任何提示信息一定要準(zhǔn)確，盡量的避免歧義。

五、【編碼實現(xiàn)】 #include #include #include #include #include #define Max_Vertex 100 #define Maxnum 1000 typedef struct Vertex//頂點結(jié)構(gòu)體 { int No;//地點編號

char name[20];//地點名稱

char info[1000];//地點簡介 }Vertex;typedef struct //無向圖結(jié)構(gòu)體 { Vertex view[Max_Vertex];

int edges[Max_Vertex][Max_Vertex];//邊的鄰接矩陣

int vnum,anum;//頂點和邊的個數(shù) }Graph;void Creat(Graph &G){ ifstream infile(“view.txt”,ios::in);

if(!infile)

{

cout<<“文件打開錯誤”<

abort();

}

int i,j,k,w;

infile>>G.vnum;

infile>>G.anum;

//cout<

for(i=0;i

{

infile>>G.view[i].No>>G.view[i].name>>G.view[i].info;

}

for(i=0;i

{

for(j=0;j

G.edges[i][j]=Maxnum;

}

ifstream weight_file(“weight.txt”,ios::in);

if(!weight_file)

{

cout<<“文件打開錯誤”<

abort();

}

for(k=0;k

{

weight_file>>i>>j>>w;

i--;

j--;

G.edges[i][j]=w;

G.edges[j][i]=G.edges[i][j];

} } void introduction(Graph &G){ char temp[20];cout<<“請輸入要查詢的景點名稱”<>temp;int v1,i,count=0;for(i=0;i

if(strcmp(G.view[i].name,temp)==0)

{

v1=i;

count++;

} } if(count!=1){

cout<<“輸入的名稱不存在”<

return;} else {

cout<<“該景點簡介為”<

cout<

return;} } void shortpath(Graph &G,int v0,int v1){

int P[100];float D[100];int i,j,w;int v,pre;float min;

int final[Max_Vertex];for(v=0;v

{

final[v]=0;

D[v]=G.edges[v0][v];

if(D[v]

P[v]=v0;

if(D[v]==Maxnum)

P[v]=-2;

} D[v0]=0;final[v0]=1;P[v0]=-1;

for(i=1;i

min=Maxnum;

//min為當(dāng)前所知離源點的最近距離

for(w=0;w

if(!final[w])

if(D[w]

{

j=w;

//記憶此點

min=D[w];

}

final[j]=1;

//離源點最近的j加入S集合 for(w=0;w

//更新其它點地當(dāng)前最短路徑

if(!final[w] &&(min+G.edges[j][w]

{

D[w]=min+G.edges[j][w];

P[w]=j;

//將w的前驅(qū)結(jié)點改為j

} }

if(P[v1]==-2)

cout<<“max”<

else

{

pre=P[v1];

cout<

cout<

cout<

while(pre>0)

{

cout<<“←”<

pre=P[pre];

}

if(v0==0)

cout<<“←”<

else

cout<

cout<

}

}

void dispath(Graph &G)//查詢最短路徑 { int v1,v0,i;int count=0;char temp1[20],temp2[20];cout<<“請輸入要查詢的兩個景點名稱”<>temp1>>temp2;

for(i=0;i

if(strcmp(G.view[i].name,temp1)==0)

{

v0=i;

count++;

}

if(strcmp(G.view[i].name,temp2)==0)

{

v1=i;

count++;

} } if(count!=2){

cout<<“輸入的名稱不存在”<

return;} else {

shortpath(G,v0,v1);

return;} } void main(){ Graph G;Creat(G);int i;char ch1;

cout<<“t***************歡迎進入河北大學(xué)校園導(dǎo)游系統(tǒng)!**************”<

cout<<“t-----------------------景點名稱---------------------------”<

for(i=0;i

{

if(i%4==0)

{

cout<

cout<

}

else

{

cout<

}

}

cout<

cout<<“t---------------------------”<

cout<<“t__________________________________________________________”<

cout<<“tt 請選擇要進行的操作”<

cout<<“ tt 1.查詢景點信息”<

cout<<“ tt 2:顯示大門到各個地點的最短路徑”<

cout<<“ tt 3:查詢兩個景點之間的最短路徑”<

cout<<“ tt 0:退出”<

cout<<“t__________________________________________________________”<

cout<<“請選擇(0~2):”;

cin>>ch1;

while(!(ch1<='3'&&ch1>='0'))

{

cout<<“數(shù)據(jù)輸入錯誤，請重新選擇(0~2):”;

cin>>ch1;

}

switch(ch1)

{

case '1': introduction(G);break;

case '2' :

for(i=0;i

shortpath(G,10,i);

break;

case '3' : dispath(G);

break;

}

}while(ch1!=0);}

六、【運行與測試】

***************歡迎進入河北大學(xué)校園導(dǎo)游系統(tǒng)!**************

-----------------------景點名稱---------------------------

主樓

多功能館

毓秀園

圖書館

操場

留學(xué)生樓

七教

八教

九教

成教

南大門

北大門

一教

逸夫樓

博物館

物理樓

電信樓

化學(xué)樓

生科樓

建工樓

北院食堂

南院食堂

竹園

梅園

桂園

菊園

易百超市

北院生活園區(qū)

---------------------------

__________________________________________________________

請選擇要進行的操作

1.查詢景點信息

2:顯示大門到各個地點的最短路徑

3:查詢兩個景點之間的最短路徑

0:退出

__________________________________________________________ 請選擇(0~2):1 請輸入要查詢的景點名稱 主樓

該景點簡介為

是河北大學(xué)本部標(biāo)志性建筑，這H型高大的建筑，正對著河北大學(xué)校本部南院黑

校門，此樓于2001年建成。主要為教學(xué)、科研、辦公服務(wù)。

__________________________________________________________

請選擇要進行的操作

1.查詢景點信息

2:顯示大門到各個地點的最短路徑

3:查詢兩個景點之間的最短路徑

0:退出

__________________________________________________________ 請選擇(0~2):1 請輸入要查詢的景點名稱 哈哈

輸入的名稱不存在

__________________________________________________________

請選擇要進行的操作

1.查詢景點信息

2:顯示大門到各個地點的最短路徑

3:查詢兩個景點之間的最短路徑

0:退出

__________________________________________________________ 請選擇(0~2):2 南大門到主樓最短路徑為50米 主樓←南大門

南大門到多功能館最短路徑為60米 多功能館←南大門

南大門到毓秀園最短路徑為60米 毓秀園←圖書館←南大門

南大門到圖書館最短路徑為40米 圖書館←南大門

南大門到操場最短路徑為160米 操場←毓秀園←圖書館←南大門 南大門到留學(xué)生樓最短路徑為180米

留學(xué)生樓←操場←毓秀園←圖書館←南大門

南大門到七教最短路徑為115米

七教←桂園←毓秀園←圖書館←南大門

南大門到八教最短路徑為65米 八教←圖書館←南大門

南大門到九教最短路徑為70米 九教←圖書館←南大門

南大門到成教最短路徑為75米 成教←八教←圖書館←南大門

南大門到南大門最短路徑為0米 南大門

南大門到北大門最短路徑為25米 北大門←南大門

南大門到一教最短路徑為35米 一教←北大門←南大門

南大門到逸夫樓最短路徑為60米

逸夫樓←博物館←物理樓←北大門←南大門

南大門到博物館最短路徑為45米 博物館←物理樓←北大門←南大門

南大門到物理樓最短路徑為35米 物理樓←北大門←南大門

南大門到電信樓最短路徑為60米 電信樓←一教←北大門←南大門

南大門到化學(xué)樓最短路徑為50米 化學(xué)樓←物理樓←北大門←南大門

南大門到生科樓最短路徑為145米

生科樓←建工樓←化學(xué)樓←物理樓←北大門←南大門

南大門到建工樓最短路徑為100米

建工樓←化學(xué)樓←物理樓←北大門←南大門

南大門到北院食堂最短路徑為115米

北院食堂←化學(xué)樓←物理樓←北大門←南大門

南大門到南院食堂最短路徑為80米 南院食堂←八教←圖書館←南大門

南大門到竹園最短路徑為135米

竹園←七教←桂園←毓秀園←圖書館←南大門

南大門到梅園最短路徑為145米

梅園←七教←桂園←毓秀園←圖書館←南大門

南大門到桂園最短路徑為95米 桂園←毓秀園←圖書館←南大門

南大門到菊園最短路徑為125米 菊園←八教←圖書館←南大門

南大門到易百超市最短路徑為145米

易百超市←七教←桂園←毓秀園←圖書館←南大門

南大門到北院生活園區(qū)最短路徑為159米

北院生活園區(qū)←北院食堂←化學(xué)樓←物理樓←北大門←南大門

__________________________________________________________

請選擇要進行的操作

1.查詢景點信息

2:顯示大門到各個地點的最短路徑

3:查詢兩個景點之間的最短路徑

0:退出

__________________________________________________________ 請選擇(0~2): 請輸入要查詢的兩個景點名稱 主樓 七教

主樓到七教最短路徑為75米 七教←桂園←毓秀園←主樓

__________________________________________________________

請選擇要進行的操作

1.查詢景點信息

2:顯示大門到各個地點的最短路徑

3:查詢兩個景點之間的最短路徑

0:退出

__________________________________________________________ 請選擇(0~2):3 請輸入要查詢的兩個景點名稱 桌嘍 菊園

輸入的名稱不存在

__________________________________________________________

請選擇要進行的操作

1.查詢景點信息

2:顯示大門到各個地點的最短路徑

3:查詢兩個景點之間的最短路徑

0:退出

__________________________________________________________

請選擇(0~2):

第五篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計校園導(dǎo)游咨詢

9、校園導(dǎo)游咨詢 問題描述：

設(shè)計一個校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)。基本要求：

⑴設(shè)計華東交通大學(xué)的校園平面圖，所含景點不少于10個。以圖中頂點表示校內(nèi)各景點，⑵存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。⑶為來訪客人提供圖中任意景點相關(guān)信息的查詢。⑷為來訪客人提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一條最短的簡單路徑。

#include #define MAXV 100

//最大頂點個數(shù) #define INF 32767

//用32767表示∞ #include

//調(diào)用函數(shù)system改變字體顏色的頭文件

typedef int InfoType;#define MAXV 100

//最大頂點個數(shù) //以下定義鄰接矩陣類型 typedef struct {

int no;

//頂點編號

InfoType info;

//頂點其他信息 } VertexType;

//頂點類型 typedef struct

//圖的定義 {

int edges[MAXV][MAXV];//鄰接矩陣

int vexnum,arcnum;

//頂點數(shù)，弧數(shù)

VertexType vexs[MAXV];//存放頂點信息 } MGraph;

void ecjtumap()//建立華東交通大學(xué)地圖

{ printf(“t|------------------------------|n”);printf(“t|

|n”);printf(“t|

|n”);printf(“t|

----------

|n”);printf(“t|

==============================| 國防生宿舍|

|n”);printf(“t|。

----------

|n”);printf(“t|。

。

|n”);printf(“t|。

。

|n”);printf(“t|。

。

|n”);printf(“t|。

。

|n”);printf(“t|。

。

|n”);printf(“t|

|南區(qū)四食堂|

----------

|n”);printf(“t|。

|南區(qū)禮堂 |

|n”);printf(“t|。

----------

|n”);printf(“t|。

。

|n”);printf(“t|。

。

|n”);printf(“t|。

--------。

|n”);printf(“t|

================| 校訓(xùn)牌|。。。。

|n”);printf(“t|

=

--------

|n”);printf(“t|

=。

|n”);printf(“t|

=。

|n”);printf(“t|

--------

---------

|n”);printf(“t|----| 南區(qū)后門 |---------| 南區(qū)大門 |------------------------|n”);printf(“t|

--------

---------

|n”);printf(“t|

---------

|n”);printf(“t|-------------------------| 北區(qū)大門 |------------------------|n”);printf(“t|

--------

|n”);printf(“t|。

--------------

|n”);printf(“t|

===========================| 15棟綜合教學(xué)樓 |

|n”);printf(“t|

=

--------------

|n”);printf(“t|

=。

|n”);printf(“t|

=。

|n”);printf(“t|

=。

|n”);printf(“t|

=。

|n”);printf(“t|

=

----------

|n”);printf(“t|

===============================| 經(jīng)管食堂 |

|n”);printf(“t|

=

----------

|n”);printf(“t|

=

=

|n”);printf(“t|

=

=

|n”);printf(“t|

-----------

=

|n”);printf(“t|

|軌道交通食堂|====================| 學(xué)生宿舍 |

|n”);printf(“t|

------------

|n”);printf(“t|

|n”);printf(“t|------------------------------|n”);printf(“n”);} void DispMat(MGraph g)

//輸出鄰接矩陣g，即輸出地圖各景點的圖的距離 { int i,j;for(i=0;i

for(j=0;j

if(g.edges[i][j]==INF)

printf(“%3s”,“∞”);//這里分別用%3s和%3d控制輸出字符∞或數(shù)字寬度為3個字符

else printf(“%3d”,g.edges[i][j]);//這樣比較方便觀看景點的圖的鄰接矩陣g

printf(“n”);} } void listmap()//建立 景點的相關(guān)信息的總瀏覽表

{ printf(“t

華東交通大學(xué)景點一覽

nn”);printf(“t|--------|n”);printf(“t| 1：南區(qū)大門

|n”);printf(“t|--------|n”);printf(“t| 2：校訓(xùn)牌

|n”);printf(“t|--------|n”);printf(“t| 3：圖書館

|n”);printf(“t|--------|n”);printf(“t| 4：南區(qū)一食堂

|n”);printf(“t|--------|n”);printf(“t| 5：孔目湖

|n”);printf(“t|--------|n”);printf(“t| 6：北區(qū)大門

|n”);printf(“t|--------|n”);printf(“t| 7：15棟教學(xué)樓

|n”);printf(“t|--------|n”);printf(“t| 8：北區(qū)食堂

|n”);printf(“t|--------|n”);printf(“t| 9：科技樓

|n”);printf(“t|--------|n”);printf(“t| 10：北區(qū)籃球場

|n”);printf(“t|--------|n”);} void introduce()//根據(jù)上面的瀏覽表，對應(yīng)出相關(guān)信息 { int a=1;printf(“n”);printf(“請輸入要查看的景點:n”);printf(“輸入1~10的數(shù)字選擇景點，其他數(shù)字返回上一級n”);while(0

switch(a)

{case 1:printf(“1：南區(qū)大門是進入華東交通大學(xué)南區(qū)的正門n”);break;

case 2:printf(“2：校訓(xùn)牌是激勵我們大學(xué)生積極向上n”);break;

case 3:printf(“3：圖書館是給我們大學(xué)生豐富知識的海洋n”);break;

case 4:printf(“4：南區(qū)一食堂是南區(qū)學(xué)生的吃飯的地方n”);break;

case 5:printf(“5：孔目湖是華東交通大學(xué)最迷人的地方n”);break;

case 6:printf(“6：北區(qū)大門是進入華東交通大學(xué)北區(qū)的正門n”);break;

case 7:printf(“7：15棟教學(xué)樓是一棟綜合型的教學(xué)樓n”);break;

case 8:printf(“8：北區(qū)食堂是北區(qū)學(xué)生吃飯的地方n”);break;

case 9:printf(“9：科技樓是大學(xué)生上機做實驗的教學(xué)樓n”);break;

case 10:printf(“10：北區(qū)籃球場是大學(xué)生鍛煉身體的地方n”);break;

} } } void show_didian(int n)//根據(jù)算法求出的整型數(shù)，對應(yīng)出地點//根據(jù) xx算法求出的數(shù)字，轉(zhuǎn)化為文字描述 { switch(n){case 0:printf(“1.南區(qū)大門”);break;case 1:printf(“2.校訓(xùn)牌”);break;case 2:printf(“3.圖書館 ”);break;case 3:printf(“4.南區(qū)一食堂”);break;case 4:printf(“5.孔目湖”);break;case 5:printf(“6.北區(qū)大門”);break;case 6:printf(“7.15棟教學(xué)樓”);break;case 7:printf(“8.北區(qū)食堂”);break;case 8:printf(“9.科技樓”);break;case 9:printf(“10.北區(qū)籃球場”);break;} } void ppath(int path[][MAXV],int i,int j)//求最短路徑經(jīng)過的地點 { int k=path[i][j];if(k==-1)return;ppath(path,i,k);show_didian(k);printf(“->> ”);ppath(path,k,j);} void put_shortdistance(int x,int y,int A[][MAXV],int path[][MAXV],int n){ int i,j;for(i=0;i

for(j=0;j

if(A[i][j]==INF)

{

if(i!=j)printf(“從%d到%d沒有路徑n”,i,j);

}

else

{

if(i==x&&j==y)

{ printf(“最短路徑為：從--”);

show_didian(i);

printf(“--到--”);

show_didian(j);

printf(“--路徑為--:n”);

show_didian(i);//輸出起點

printf(“->>”);

ppath(path,i,j);//求最短路徑經(jīng)過的中間路徑，若沒有則不輸出

show_didian(j);//輸出 終點

printf(“nt路徑長度為:%dn”,A[i][j]);

}

} } void shortdistance(MGraph g,int x,int y)//求最短路徑用的是弗洛伊德算法

{ int A[MAXV][MAXV],path[MAXV][MAXV];//path為中間路徑不包括 起點 終點

int i,j,k,n=g.vexnum;for(i=0;i

//給A數(shù)組置初值

for(j=0;j

{

A[i][j]=g.edges[i][j];path[i][j]=-1;

} for(k=0;k

//計算Ak {

for(i=0;i

for(j=0;j

//這里的3個for循環(huán)

if(A[i][j]>(A[i][k]+A[k][j]))//所以時間復(fù)雜度O(n3)

{

A[i][j]=A[i][k]+A[k][j];path[i][j]=k;

} } put_shortdistance(x,y,A,path,n);} void menu(MGraph g)//建立 菜單 頁面，可以無數(shù)次選擇菜單，當(dāng)輸入5時退出系統(tǒng) { int m=1,x=1,y=1;//m的菜單選擇的功能x,y分別表示從x到y(tǒng)的問路查詢

while(m!=5){ printf(“ttt|------------------------|n”);

printf(“ttt|----------菜單----------|n”);

printf(“ttt| 1：查看地圖

|n”);

printf(“ttt| 2：地圖詳解

|n”);

printf(“ttt| 3：景點一覽表

|n”);

printf(“ttt| 4：問路查詢

|n”);

printf(“ttt| 5：退出

|n”);

printf(“ttt|------------------------|n”);

printf(“請輸入1~5的數(shù)字n”);

scanf(“%d”,&m);

switch(m)

{case 1:ecjtumap();break;

case 2:listmap();

introduce();break;

case 3:listmap();

introduce();

printf(“n”);break;

case 4:listmap();

printf(“請輸入起點:”);

scanf(“%d”,&x);x+=-1;

printf(“請輸入終點:”);

scanf(“%d”,&y);y+=-1;

shortdistance(g,x,y);break;

case 5:printf(“ttt感想使用本系統(tǒng)，歡迎下次繼續(xù)使用n”);break;

} } } void main(){ system(“color 0a”);//輸出字體為綠色

int i,j;MGraph g;int A[MAXV][10]={

{INF, 1,INF,INF,INF, 1,INF,INF,INF,INF}，{ 1,INF, 5, 6, 7,INF,INF,INF,INF,INF}，{INF, 5,INF,INF, 2,INF,INF,INF,INF,INF}，{INF, 6,INF,INF, 5,INF,INF,INF,INF,INF}，{INF, 7, 2, 5,INF,INF,INF,INF,INF,INF}，{ 1,INF,INF,INF,INF,INF, 3,INF, 5,INF}，{INF,INF,INF,INF,INF, 3,INF, 2,INF,INF}，{INF,INF,INF,INF,INF,INF, 2,INF, 8, 10}，{INF,INF,INF,INF,INF, 5,INF, 8,INF, 2}，{INF,INF,INF,INF,INF,INF,INF, 10, 2,INF}};g.vexnum=11;g.arcnum=11;for(i=0;i

for(j=0;j

g.edges[i][j]=A[i][j];printf(“n”);printf(“ttt華東交通大學(xué)導(dǎo)游咨詢系統(tǒng)n”);menu(g);//進入導(dǎo)游系統(tǒng)，執(zhí)行菜單功能 }