第一篇：校園導(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<<“您想查詢哪個景點的詳細信息?”< cin>>i>>j;if(i>n||i<=0||j>n||j<=0){ cout<<“輸入信息錯誤！”< cout<<“請輸入要查詢的兩個景點的編號(1-10的數(shù)字編號):”< void dy::floyed(){ int i,j,k;for(i=1;i 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 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<<“您想查詢哪個景點的詳細信息?”< 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ù)字編號):”< 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)!----------------”< 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)游實驗報告 學(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&&v0 flag=0;} for(v=1;v final[v]=0; D[v]=G->arcs[v0][v].adj;for(w=1;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;i min=INFINITY; for(w=1;w if(!final[w]) if(D[w] final[v]=1; for(w=1;w if(!final[w]&&(min+G->arcs[v][w].adj { D[w]=min+G->arcs[v][w].adj; for(x=0;x p[w][x]=p[v][x]; p[w][w]=1; } } } for(v=1;v flag=0;min=INFINITY; for(w=1;w { if(p[v][w]&&w!=v0) { flag=1; if(D[w] } } if(flag) { if(G->vexs[w1].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].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&&v0 flag=0;} flag=1;while(flag){ printf(“請您輸入一個目的地景點編號，按回車鍵結(jié)束:”); scanf(“%d”,&v1); if(v1<0||v1>G->vexnum) { printf(“景點編號不存在!請重新輸入景點編號:”); scanf(“%d”,&v1); } if(v1>=0&&v1 flag=0;} for(v=0;v final[v]=0; D[v]=G->arcs[v0][v].adj; for(w=0;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;i min=INFINITY; for(w=0;w if(!final[w]) if(D[w] final[v]=1; for(w=0;w if(!final[w]&&(min+G->arcs[v][w].adj { D[w]=min+G->arcs[v][w].adj; for(x=0;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;w { if(p[v][w]&&w!=v0) { flag=1; if(D[w] } } if(flag) { if(G->vexs[w1].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].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&&k 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é)出版社 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 長 春 大 學(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 /*定義符號常量*/ #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*/ 共 頁 第 頁 數(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 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<<“請輸入要查詢的景點名稱”< 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<<“請輸入要查詢的兩個景點名稱”< 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): 9、校園導(dǎo)游咨詢 問題描述： 設(shè)計一個校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)。基本要求： ⑴設(shè)計華東交通大學(xué)的校園平面圖，所含景點不少于10個。以圖中頂點表示校內(nèi)各景點，⑵存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。⑶為來訪客人提供圖中任意景點相關(guān)信息的查詢。⑷為來訪客人提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一條最短的簡單路徑。 #include //最大頂點個數(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í)行菜單功能 }第二篇：校園導(dǎo)游實驗報告
第三篇：課程設(shè)計(校園導(dǎo)游)
第四篇：校園導(dǎo)游實驗報告——數(shù)據(jù)結(jié)構(gòu)
第五篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計校園導(dǎo)游咨詢
點擊咨詢 