數(shù)據(jù)結構課程設計—校園導航問題報告

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：23 大?。?15.50KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩22頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　數(shù)學與計算機學院　　課程設計說明書　　課程名稱: 數(shù)據(jù)結構-課程設計 　　課程代碼: 　　題

2、目: 校園導航問題 　　年級/專業(yè)/班: 　　學生姓名: 　　學　　號: 　　開始時

3、間: 年月日　　完成時間: 年月日　　課程設計成績：　　指導教師簽名：年月日　　數(shù) 據(jù) 結構課程

4、設計任務書　　學院名稱：數(shù)學與計算機學院課程代碼： 8404181 　　專業(yè)：年級： 　　一、設計題目

5、　　校園導航問題　　二、主要內容　　設計西華大學的平面圖，至少包括10個以上的場所，找出從任意場所到達另一場所的最短路徑。　　三、具體要求及應提交的材料　　1．每個同學以自己的

6、學號和姓名建一個文件夾，如：“312009080611101張三”。里面應包括：學生按照課程設計的具體要求所開發(fā)的所有源程序（應該放到一個文件夾中）、任務書和課程設計說明書的電子文檔。　　2．打印的課程設計說明書（注意：在封面后夾入打印的“任務書”以后再裝訂）。　　四、主要技術路線提示　　涉及無向圖的操作。該設計

7、共分三部分，一是建立西華大學平面圖的存儲結構，二是解決單源點最短路徑問題，最后再實現(xiàn)任意一對場所之間的最短路徑問題。　　五、進度安排　　共計兩周時間，建議進度安排如下：　　選題，應該在上機實驗之前完成　　需求分析、概要設計可分配4學時

8、完成　　詳細設計可分配4學時　　調試和分析可分配10學時。　　2學時的機動，可用于答辯及按教師要求修改課程設計說明書。　　注：只用課內上機時間一般不能完成設計任務，所以需要學生自行安排時間做補充。　　六、推薦參考資料(不少于3篇)

9、　　［1］蘇仕華等編著，數(shù)據(jù)結構課程設計，機械工業(yè)出版社，2007　?。?］嚴蔚敏等編著，數(shù)據(jù)結構（C語言版），清華大學出版社，2003　?。?］嚴蔚敏等編著，數(shù)據(jù)結構題集（C語言版），清華大學出版社，2003　　指導教師簽名日期年月

10、日　　系主任審核日期年月日　　校園導航問題　　摘要：程序設計目的是用哈斯圖方式計算兩個旅游點的最短距離以及路線。編程所實現(xiàn)的功能除了可以查詢兩個旅游點的最短距離以及最短的路線，還可以看到旅游點的介紹，以及逛遍所有旅游點所能組成

11、的所有路線可能，實現(xiàn)全面查詢。 　　關鍵字：景點；路線；距離；校園導航　　課程設計題目 　　設計要求：設計你的學校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同　　的路，且路長也可能不同，找出從任意場所到達另一場所的最佳路徑（最短路徑）。</p&g

12、t;　　分析　　2．1設計基礎：要掌握最短路徑的實現(xiàn)方式。　　2．2分析設計課題的要求，要求編程實現(xiàn)以下功能：　?。?）查詢景點路徑　?。?）查詢景點信息&

13、lt;/b>　　（3）查看參觀路線　?。?）查詢各景點之間的距離　　2．3主控菜單設計　　為實現(xiàn)通信錄管理的操作功能，首先設計一個含有多個菜單項的主控菜單程序，然后&

14、lt;p>　　再為這些菜單項配上相應的功能。　　程序運行后，給出菜單項的內容和輸入提示，如下：　　1．學校簡介　　2．查詢景點路徑　　3. 查詢景點信息

15、　　4. 查看參觀路線　　5. 查詢各景點之間的距離　　6. 退出　　2．4設計課題已明確要求，有關的定義如下：　　typedefstructArcCel

16、l{　　intadj; // 相鄰接的景點之間的路程　　char *info;　　}ArcCell; // 定義邊的類型　　typedefstructVertexType{　　int number; // 景點編號</p&g

17、t;　　char *sight; // 景點名稱　　char *description; // 景點描述　　}VertexType; // 定義頂點的類型　　typedefstruct{　　VertexType vex[NUM]; // 圖中的頂點，

18、即為景點　　ArcCell arcs[NUM][NUM]; // 圖中的邊，即為景點間的距離　　intvexnum,arcnum; // 頂點數(shù)，邊數(shù)　　}MGraph; // 定義圖的類型　　共0條評論...

19、　　3．步驟　　3.1函數(shù)調用圖　　函數(shù)調用關系　　3.2主代碼#include<iostream > 　　#include

20、<string.h>　　#include <stdio.h> 　　#include <stdlib.h>　　#define Max 32767　　#define NUM 11　　typedef

21、struct ArcCell{　　int adj; // 相鄰接的景點之間的路程 　　char *info;　　}ArcCell; // 定義邊的類型 　　typedef struct VertexType{　　int numbe

22、r; // 景點編號 　　char *sight; // 景點名稱 　　char *description; // 景點描述 　　}VertexType; // 定義頂點的類型 　　typedef struct{　　VertexT

23、ype vex[NUM]; // 圖中的頂點，即為景點 　　ArcCell arcs[NUM][NUM]; // 圖中的邊，即為景點間的距離 　　int vexnum,arcnum; // 頂點數(shù)，邊數(shù) 　　}MGraph; // 定義圖的類型 　　MGraph G; /

24、/ 把圖定義為全局變量 　　int P[NUM][NUM]; // //　　long int D[NUM]; // 輔助變量存儲最短路徑長度 　　int x[13]={0}; 　　void CreateUDN(int v,int a); // 創(chuàng)建圖的函數(shù) </p&

25、gt;　　void pingmu(); //屏幕輸出函數(shù)　　void introduce();　　void ShortestPath(int num); //最短路徑函數(shù)　　void output(int sight1,int sight2); //輸出函數(shù)<p

26、>　　void PrintMGraph();　　char Menu(); // 主菜單 　　void search(); 　　;// 查詢景點信息 　　char SearchMenu(); // 查詢子菜單 　　void H

27、aMiTonian(int); // 哈密爾頓圖的遍歷 　　void NextValue(int); 　　void display(); // 顯示遍歷結果 　　void main() // 主函數(shù) 　　{ int v0,v1;&

28、lt;b>　　char ck;　　system("color 0");　　CreateUDN(NUM,11);　　do　　{

29、　　ck=Menu();　　switch(ck)　　{　　case'1':　　introduce();　　printf

30、("\n\n\t\t\t%-25s\n\n",G.vex[0].description);　　getchar();　　getchar();　　break;　　case '2':&l

31、t;/b>　　system("cls");　　pingmu();　　printf("\n\n\t\t\t請選擇起點景點（1～10）：");　　scanf("%d",&a

32、mp;v0);　　printf("\t\t\t請選擇終點景點（1～10）：");　　scanf("%d",&v1);　　ShortestPath(v0); // 計算兩個景點之間的最短路徑 　　output(v0,v1);

33、// 輸出結果 　　printf("\n\n\t\t\t\t請按回車鍵繼續(xù)...\n");　　getchar();　　getchar();　　break;　　case &#

34、39;3':search();　　break;　　case '4':　　system("cls");　　pingmu();</b

35、>　　x[0]=1; 　　HaMiTonian(1); 　　printf("\n\n\t\t\t\t請按回車鍵繼續(xù)...\n");　　getchar();　　getc

36、har();　　break;　　case'5':　　PrintMGraph();　　printf("\n\n\t\t\t\t請按回車鍵繼續(xù)...\n");<

37、;/p>　　getchar();　　getchar();　　break;　　};　　}while(ck!='e');<p&

38、gt;　　}　　char Menu() // 主菜單 //　　{　　char c;　　int flag;</p&g

39、t;　　do{　　flag=1;　　system("cls");　　pingmu();　　introduce();&

40、lt;/p>　　printf("\n\t\t\n");　　printf("\t\t \n");　　printf("\t\t 1.學校簡介 \n");　　printf("\t\t 2.查詢景點路徑 \n");

41、　　printf("\t\t 3.查詢景點信息 \n");　　printf("\t\t 4.查看參觀路線 \n");　　printf("\t\t 5.查詢各景點之間的距離 \n");　　printf("

42、\t\t e.退出 \n");　　printf("\t\t \n");　　printf("\t\t\n");　　printf("\t\t\t\t請輸入您的選擇：");　　scanf("%c&q

43、uot;,&c);　　if(c=='1'||c=='2'||c=='3'||c=='4'||c=='5'||c=='e')　　flag=0;　　}while(flag);&

44、lt;/p>　　return c;　　}　　char SearchMenu() // 查詢子菜單 　　{　　ch

45、ar c;　　int flag;　　do{　　flag=1;　　system("cls");&

46、lt;p>　　pingmu();　　introduce();　　printf("\n\t\t\n");　　printf("\t\t \n");　　printf("\t\t 1、按

47、照景點編號查詢 \n");　　printf("\t\t 2、按照景點名稱查詢 \n");　　printf("\t\t e、返回 \n");　　printf("\t\t \n");　　printf(&qu

48、ot;\t\t \n");　　printf("\t\t\t請輸入您的選擇：");　　scanf("%c",&c);　　if(c=='1'||c=='2'||c=='e')<p&g

49、t;　　flag=0;　　}while(flag);　　return c;　　}　　void search() // 查詢景點信息 &

50、lt;p>　　{　　int num;　　int i;　　char c;　　char name[20];</p

51、>　　do　　{　　system("cls");　　c=SearchMenu();　　switch (c)

52、　　{　　case '1': 　　system("cls");　　introduce();　　pingmu();　　p

53、rintf("\n\n\t\t請輸入您要查找的景點編號：");　　scanf("%d",&num);　　for(i=0;i<NUM;i++)　　{　　if(num==G.vex[i

54、].number)　　{　　printf("\n\n\t\t\t您要查找景點信息如下:");　　printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description);<p&g

55、t;　　printf("\n\t\t\t按任回車返回...");　　getchar();　　getchar();　　break;　　}

56、　　}　　if(i==NUM)　　{　　printf("\n\n\t\t\t沒有找到！");　　printf("\n\n\t\t\t按回車鍵返回...");

57、　　getchar();　　getchar();　　}　　break;　　case '2':<

58、/p>　　system("cls");　　pingmu();　　introduce();　　printf("\n\n\t\t請輸入您要查找的景點名稱：");　　sca

59、nf("%s",name);　　for(i=1;i<NUM;i++)　　{　　if(!strcmp(name,　　G.vex[i].sight))

60、　{　　printf("\n\n\t\t\t您要查找景點信息如下:");　　printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description);　　printf("\n\t\t\t按回車鍵返回..."

61、);　　getchar();　　getchar();　　break;　　}　　}<p&

62、gt;　　if(i==NUM)　　{　　printf("\n\n\t\t\t沒有找到！");　　printf("\n\n\t\t\t按回車鍵返回...");　　getchar();</p&

63、gt;　　getchar();　　}　　break;　　}　　}while(c!='e');&l

64、t;p>　　}　　void CreateUDN(int v,int a) // 創(chuàng)建圖的函數(shù) 　　{ 　　int i,j;　　G.vexnum=v; /

65、/ 初始化結構中的景點數(shù)和邊數(shù) 　　G.arcnum=a;　　for(i=1;i<G.vexnum;++i) G.vex[i].number=i; // 初始化每一個景點的編號 　　// 初始化沒一個景點名及其景點描述 　　G.vex[0].sight="

66、學校簡介";　　G.vex[1].sight="東大門";　　G.vex[2].sight="培訓樓";　　G.vex[3].sight="氣象樓";　　G.vex[4].sight="文德樓

67、";　　G.vex[5].sight="明德樓";　　G.vex[6].sight="尚賢樓";　　G.vex[7].sight="電影院";　　G.vex[8].sight="北辰樓&quo

68、t;;　　G.vex[9].sight="圖書館";　　G.vex[10].sight="實驗樓";　　// 這里把所有的邊假定為32767，含義是這兩個景點之間是不可到達 　　for(i=1;i<G.vexnum;++i)&

69、lt;/p>　　{　　for(j=1;j<G.vexnum;++j) 　　{　　G.arcs[i][j].adj=Max;　　G.arcs[i][j].info=

70、NULL;　　}　　}　　//下邊是可直接到達的景點間的距離，由于兩個景點間距離是互相的，　　// 所以要對圖中對稱的邊同時賦值。　　G.arcs[1][

71、4].adj=G.arcs[4][1].adj=200;　　G.arcs[1][3].adj=G.arcs[3][1].adj=150;　　G.arcs[3][5].adj=G.arcs[5][3].adj=100;　　G.arcs[3][10].adj=G.arcs[10][3].adj=400;</p&

72、gt;　　G.arcs[4][6].adj=G.arcs[6][4].adj=200;　　G.arcs[2][5].adj=G.arcs[5][2].adj=200;　　G.arcs[2][4].adj=G.arcs[4][2].adj=100;　　G.arcs[5][7].adj=G.ar

73、cs[7][5].adj=150;　　G.arcs[4][6].adj=G.arcs[6][4].adj=150;　　G.arcs[4][7].adj=G.arcs[7][4].adj=150;　　G.arcs[6][8].adj=G.arcs[8][6].adj=150;

74、;　　G.arcs[7][8].adj=G.arcs[8][7].adj=100;　　G.arcs[6][9].adj=G.arcs[9][6].adj=200;　　}　　// 打印出鄰接矩陣　　void PrintMGraph()&

75、lt;/p>　　{　　int i,j;　　cout<<"\n ====================================================================\n\n ";<

76、/p>　　for(i=1;i<G.vexnum;++i)　　{　　cout<<G.vex[i].sight<<" ";　　}<p&

77、gt;　　cout<<endl;　　for(i=1;i<G.vexnum;++i)　　{　　cout<<"\n\n"<<G.vex[i].sight<<" ";

78、　　for(j=1;j<G.vexnum;++j)　　{　　if(G.arcs[i][j].adj==Max)　　cout<<" no ";　　else<

79、;/b>　　cout<<" "<<G.arcs[i][j].adj;　　}　　}　　cout<<"\n\n\n\n=====

80、==============================================================\n\n\n";　　}　　void introduce() // 介紹函數(shù) 　　{

81、　　int i;　　for(i=1;i<=NUM;i++)　　{ 　　G.vex[0].description="南京信息工程大學是江蘇省人民政府和中國氣象局共建的全國重點高校，是江蘇省十一五重點建設的

82、15所大學之一。";　　G.vex[1].description="東大門，有五根大柱子 ";　　G.vex[2].description="留學生學習的地方";　　G.vex[3].description="氣象樓，特色樓 ";</p&

83、gt;　　G.vex[4].description="全校最大的教學樓 ";　　G.vex[5].description="又一個教學樓";　　G.vex[6].description="實驗樓，歷史悠久";　　G.vex[7].d

84、escription="經(jīng)常放恐怖片 ";　　G.vex[8].description="聽說有靈異事件發(fā)生過 ";　　G.vex[9].description="很不錯";　　G.vex[10].description="剛建好的，蠻新的，不

85、錯";　　}　　}　　void pingmu() // 屏幕輸出函數(shù) 　　{ 　　int

86、 i;　　printf("\n\n\t\t***************歡迎來到南京信息工程大學**************\n\n");　　printf("\t\t\n");　　printf("\t\t\t\t學校簡介\t\t\n"

87、,1,1);　　printf("\t\t\n");　　printf("\t\t\t\t學校概況\t\t\n",6,6);　　printf("\t\t\n");　　for(i=1;i<NUM;i++)<

88、/p>　　{　　printf("\t\t%c\t\t(%2d)%-20s%c\t\t\t",1,i,G.vex[i].sight,1); // 輸出景點列表 　　}　　printf(&quo

89、t;\t\t\n\n");　　}　　void ShortestPath(int num) // 迪杰斯特拉算法最短路徑函數(shù) num為入口點的編號 　　{ 　　int v,w,i,t; /

90、/ i、w和v為計數(shù)變量 　　int final[NUM]; 　　int min;　　for(v=1;v<NUM;v++)　　{　　final[v]

91、=0; // 假設從頂點num到頂點v沒有最短路徑 　　D[v]=G.arcs[num][v].adj;// 將與之相關的權值放入D中存放 　　for(w=1;w<NUM;w++) // 設置為空路徑 　　P[v][w]=0;　　if(D[v]<32767)

92、// 存在路徑 　　{ 　　P[v][num]=1; // 存在標志置為一 　　P[v][v]=1; // 自身到自身 　　}　　}&l

93、t;/b>　　D[num]=0;　　final[num]=1; // 初始化num頂點屬于S集合 　　// 開始主循環(huán)，每一次求得num到某個頂點的最短路徑，并將其加入到S集合 　　for(i=1;i<NUM;++i) /

94、/ 其余G.vexnum-1個頂點 　　{　　min=Max; // 當前所知離頂點num的最近距離 　　for(w=1;w<NUM;++w)　　if(!final[w]) // w頂點在v-s中 <

95、;p>　　if(D[w]<min) // w頂點離num頂點更近 　　{　　v=w;　　min=D[w];　　} </b&

96、gt;　　final[v]=1; // 離num頂點更近的v加入到s集合 　　for(w=1;w<NUM;++w) // 更新當前最短路徑極其距離 　　if(!final[w]&&((min+G.arcs[v][w].adj)<D[w]))// 不在s集合，并且比以前所找到的路徑都短就

97、更新當前路徑 //　　{　　D[w]=min+G.arcs[v][w].adj;　　for(t=0;t<NUM;t++)　　P[w][t]=P[v][t];　　P[w][w]=1;<

98、;/p>　　}　　}　　}　　void output(int sight1,int sight2) // 輸出函數(shù) <b&g

99、t;　　{　　int a,b,c,d,q=0;　　a=sight2; // 將景點二賦值給a 　　if(a!=sight1) // 如果景點二不和景點一輸入重合，則進行... 　　{<

100、p>　　printf("\n\t從%s到%s的最短路徑是",G.vex[sight1].sight,G.vex[sight2].sight);// 輸出提示信息 　　printf("\t(最短距離為 %dm.)\n\n\t",D[a]); // 輸出sight1到sight2的最短路徑長度，存放在D[]數(shù)組中

101、;　　printf("\t%s",G.vex[sight1].sight); // 輸出景點一的名稱 　　d=sight1; // 將景點一的編號賦值給d 　　for(c=0;c<NUM;++c)　　{　　g

102、ate:; // 標號，可以作為goto語句跳轉的位置 　　P[a][sight1]=0;　　for(b=0;b<NUM;b++)　　{　　if(G.arcs[d][b].adj<32767&&P[a][b

103、]) // 如果景點一和它的一個臨界點之間存在路徑且最短路徑 　　{　　printf("-->%s",G.vex[b].sight); // 輸出此節(jié)點的名稱 　　q=q+1; // 計數(shù)變量加一，滿8控制輸出時的換行 <

104、;p>　　P[a][b]=0;　　d=b; // 將b作為出發(fā)點進行下一次循環(huán)輸出，如此反復 　　if(q%8==0) printf("\n");　　goto gate;　　}<

105、p>　　}　　}　　}　　}　　void HaMiTonian(int m) // 哈密爾頓圖的遍歷 </p

106、>　　{ 　　if(m>8) return; 　　L: NextValue(m); 　　if(x[m]==0) 　　return; <

107、;p>　　if(m==7&&G.arcs[1][x[8]-1].adj!=32767) 　　display(); 　　else 　　HaMiTonian(m+1); 　　goto L; <

108、/b>　　} 　　void NextValue(int k) 　　{ 　　int j; 　　l:x[k]=(x

109、[k]+1)%10; 　　if(x[k]==0) 　　return; 　　if(G.arcs[x[k-1]-1][x[k]-1].adj!=32767) 　　{ <p

110、>　　for(j=0;j<k;j++) 　　if(x[j]==x[k]) 　　goto l; 　　return; 　　}

111、　　else 　　goto l; 　　} 　　void display() 　　{

112、;　　int i=1;　　printf("\n\n\t");　　for(i=1;i<8;i++) 　　printf("%s->",G.vex[x[i]-1].sight); &l

113、t;p>　　printf("出口"); 　　printf("\n");　　} 　　3.3實現(xiàn)截圖　　一開始的頁面

114、　　學校的簡介　　所需要的兩個景點的最短路線及距離　　所要參觀的景點的介紹　　所有景點的參觀路線　　每兩個景點間的距離

115、;　　總結討論　　在寫輸入語句中沒有正確引用，例如在scanf("%d",&num);中沒有　　對num加&引用而只寫了num；原因是在下面的num=G.vex[i].number=i語句中，num地址存放了操作數(shù)字，不引用系統(tǒng)就會出錯。其

116、他地方的scanf語句也是出現(xiàn)同樣的問題，例如scanf("%d",&v0); scanf("%d",&v1);在輸入起始點和終點的時候，V0,V1沒有用引用地址符號，因此在執(zhí)行輸入的時候，系統(tǒng)就會認定是非法寫入操作，從而導致系統(tǒng)出錯。　　語法邏輯出錯，在執(zhí)行的時候，有的時候出現(xiàn)死循環(huán)，有的時候屏幕出現(xiàn)null和亂碼。

117、　　語句的編寫有誤，不合法。如在我寫主菜單和子菜單里寫switch語句的時候，do while 語句與if else語句嵌套使用，使程序邏輯出現(xiàn)混亂，造成調試出錯。　　變量名的定義出錯，造成調用的時候出錯，不過改過來就好了　　算法的編寫不全面，漏掉個別語句，如在調試的時候檢查發(fā)現(xiàn)寫迪杰斯特拉（DijkStra）算法的時候并沒有寫完整，

118、造成輸出結果不正確；開始查找錯誤的時候并不知道錯在哪里，但經(jīng)過與書本上的算法進行核對以后，才找出問題根源所在。　　定義數(shù)據(jù)類型出錯，前面定義的數(shù)據(jù)類型是字符型后怯定義成整形，即數(shù)據(jù)類型不一致，造成調試出錯。　　程序調試出來了，但沒有達到預先想要的結果。　　這些小問題都是比較熟悉的問題，開始進行調試的時候都會出現(xiàn)，

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結構課程設計—校園導航問題報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載