數(shù)據結構課程設計--校園導游程序

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

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

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

文檔簡介

1、　　2013年12月9日　項目名稱：校園導游程序 　學生姓名： 　學號： 　班級：

2、 　指導教師： 　　目錄　　1.課程設計的目的與意義1　　1.1課程設計的目的1　　1

3、.2課程設計的意義1　　2.系統(tǒng)功能描述及設計1　　3.系統(tǒng)存儲結構及描述3　　4.系統(tǒng)功能實現(xiàn)及算法描述5　　4.1校園景點信息的錄入5　　4.2查詢圖中任意兩個景點間的最短路徑6<p&

4、gt;　　4.3查詢圖中任意一個景點到其他景點的所有路徑7　　4.4查詢任意兩景點間的所有路徑8　　5. 系統(tǒng)性能測試9　　5.1 主界面9　　5.2瀏覽校園全景9　　5.3查詢圖中

5、任意兩個景點間的最短路徑10　　5.4查詢圖中任意一點到其他景點間的所有路徑10　　5.5查詢任意兩個景點間的所有路徑11　　6.設計小結11　　參考文獻11&l

6、t;p>　　源代碼清單12　　1.課程設計的目的與意義　　1.1課程設計的目的　　隨著社會的發(fā)展，人們對生活的也要求越來越高，從以前的一切都用手用筆的時代到了一切都可以用機器代替的時代?，F(xiàn)在的大學校園越來越大了，對于對新學校不熟悉和對于外來著更好的參觀和游覽學校，特做

7、了這個校園導游圖，它能輸出所有校園景點的簡介供用戶參考，并且能找到兩個景點間最短路徑，讓用戶少走彎路和冤枉路，而且還可以找到一個景點到其他景點的最短路徑，可以提供使用者最好的游覽路徑。更多的功能將會在后續(xù)繼續(xù)加入。　　1.2課程設計的意義　　鞏固和加深學生對數(shù)據結構的基本知識的理解和掌握,掌握C語言編程和程序調試的基本技能。利用數(shù)據結構進行基本的軟件設計

8、,掌握書寫程序設計說明文檔的能力，提高運用數(shù)據結構解決實際問題的能力。　　培養(yǎng)我們綜合運用所學知識的能力和鍛煉實踐的能力,能夠做到善于發(fā)現(xiàn),提出,分析和解決實際問題。同時，進一步加深、鞏固我們所學專業(yè)課程（《數(shù)據結構實用教程》）的基本理論知識,如語句嵌套和循環(huán)，分支等結運用，理論聯(lián)系實際，進一步培養(yǎng)學生綜合分析問題和解決問題的能力。掌握運用C語言獨立地編寫、調試應用程序和進行其它相關設計的技能，

9、擴展自己的知識面，充分發(fā)揮廣大同學的潛力，提高程序開發(fā)能力，使我們通過這次課程設計而得到全面的鍛煉。　　2.系統(tǒng)功能描述及設計　　整個系統(tǒng)主要包含三個大的模塊（功能模塊圖見下圖2-1）　　菜單1：瀏覽校園全景，該功能的實現(xiàn)是通過編程著將所有信息事先錄入系統(tǒng)中，當用戶選擇時，會輸出學校所有的景點，編號及簡介。菜單2

10、：查詢任意兩景點間的所有路徑。這個是根據弗洛伊德算法改編而來，該算法能很方便的找出用戶所輸入的兩景點間的最短路徑。當然，當你輸入的景點編號不存在時，就回提示重新輸入，知道輸入的兩個點都符合要求才會找出最短路徑。　　菜單3：查詢一個景點到其他所有景點的最短路徑。該系統(tǒng)能通過你所在的位置找出到其他所有景點的最短路徑。很方便的滿足客戶需要到達其他景點的路徑。

11、　菜單4：查詢圖中任意兩景點間的所有路徑。有了這個功能，用戶可以很方便的找到圖中任意連個景點間的所有路徑。這樣用戶就可以選擇自己中意的路徑來到達自己的目的地了。　　菜單5：退出整個系統(tǒng)。　　圖2-1系統(tǒng)功能描述　　3.系統(tǒng)存儲結構及描述　　下面將給出程序代碼的部分代碼，將

12、詳細介紹系統(tǒng)的存儲結構。如：　　struct infotype　　{　　char name[20];　　int num;　　char introducti

13、on[100];　　weighttype maxvalue;　　};　　struct Mgraph　　{ infotype vexs[MAXVER]; //定義存儲定點信息的數(shù)組類型<p&g

14、t;　　infotype arcs[MAXVER][MAXVER]; //定義存儲鄰接矩陣的數(shù)組類型　　int vexnum,arcnum;　　};　　該存儲結構：在上面的結構體中，包含了圖中所需的景點名，景點個數(shù)，景點簡介，而且存儲了邊數(shù)，還利用數(shù)組來存儲兩景點間是否有邊

15、，而且還包含了兩景點間的權值。　　for(i=0;i<G.vexnum;i++)　　G.vexs[i].num=i;　　strcpy(G.vexs[0].name,"弘德樓");　　strcpy(G.vexs[0].introduction,&q

16、uot;學生公寓，主要為考研學生準備，環(huán)境良好。");　　上面簡單的幾行代碼就存儲了一個景點的編號，名稱，簡介　　for(i=0;i<G.vexnum;i++)　　for(j=0;j<G.vexnum;j++)　　G.arcs[i][j].maxva

17、lue=FARMAX;　　G.arcs[0][1].maxvalue=70;　　for(i=0;i<G.vexnum;i++)　　for(j=0;j<G.vexnum;j++)　　G.arcs[j][i].maxvalue=G.arcs[i][j].maxva

18、lue;　　}　　上面的代碼利用了兩個for循環(huán)很快的定義出了任意兩個景點的關系，如是否存在邊，存在邊權值是大?。]有邊則為事先定義的最大值，存在邊則直接輸入權值），同時也作出了無向圖應有的特點，及是雙向的，并且兩邊權值相等。　　上面整個信息的錄入存儲了整個系統(tǒng)需要的數(shù)據，包

19、括景點個數(shù)，邊數(shù)，名稱，簡介，距離。有了這個函數(shù)，方便以后所有的需要數(shù)據的地方來調用它。　　4.系統(tǒng)功能實現(xiàn)及算法描述　　4.1校園景點信息的錄入　　該功能的實現(xiàn)是通過利用定義好的變數(shù)，定點數(shù)，景點名，景點編號，景點間權值的，一次輸入G.vexs[i].name，G.vexs[i].introduction，G.

20、arcs[i][i].maxvalue,而i，j的取值范圍是由G.vexnum和G.arcnum確定的。圖4-1：　　圖4-1校園景點信息的錄入　　4.2查詢圖中任意兩個景點間的最短路徑　　該功能是利用弗洛伊德算法如果從k到j有邊，則存在一條長度為arcs[k][j]的路徑，該路徑不一定是最短路徑?？紤]路徑（k,

21、u,j）是否存在，若存在，比較（k,j）和（k,u,j）的長度，取較短者為從k到j的中間點序號不大于0的最短路徑。以此類推，每次增加一個點，從而求出任意兩點間的最短路徑。這樣，經過n次比較后，所求得的必為從k到j的最短路徑。按此方法，可以同時求得任意兩點間的最短路徑。流程圖如下4-2：　　4-2查詢圖中任意兩個景點間的最短路徑　　4.3查詢圖中任意一個景

22、點到其他景點的所有路徑　　這個功能的實現(xiàn)是通過數(shù)組存儲所有右邊的路徑，然后根據用戶輸入的一個景點的編號找到該景點與其他景點右邊的景點，然后以右邊的其他景點為起點，重復上述流程，直到找完每個景點即結束程序。如圖4-3：　　圖4-3查詢圖中任意一個景點到其他景點的所有路徑　　4.4查詢任意兩景點間的所有路徑</

23、p>　　該功能是通過用戶輸入的兩個景點的編號找到對應的景點名，然后以第一個點作為起點向其他點找邊，當邊的權值小于最大值時，說明存在邊，即可保存在數(shù)組中，直到找到終點對應的編號即為一天路徑，循環(huán)上述過程，直到出現(xiàn)重復路徑即結束函數(shù)，跳出循環(huán)。如圖圖4-4：　　圖4-4查詢任意兩景點間的所有路徑　　5. 系統(tǒng)性能

24、測試　　5.1 主界面　　當程序成功被打開時會出現(xiàn)如圖5-1所示的界面，該界面相當于一個菜單，用戶可以根據自己的需求選擇數(shù)字?！?”瀏覽所有景點的信息，“2”找出任意兩景點間所有路徑，“3”找到一個景點到其他景點間的所有路徑，“4”退出系統(tǒng) ，下面是“請選擇，輸入1-5鍵：”的字樣。如圖5-1：&

25、lt;/p>　　圖5-1主界面測試圖　　5.2瀏覽校園全景　　當用戶選擇1時，程序即會根據之前存儲好的信息輸出景點間的所有信息，供用戶瀏覽及參考。運行效果如下5-2圖片所示。　　圖5-2瀏覽校園全景　　5.

26、3查詢圖中任意兩個景點間的最短路徑　　當用戶選擇2時，則會進入該系統(tǒng)，系統(tǒng)會提示“請輸入兩個景點的編號”，當你輸入的景點不符合要求時，會提示重新輸入如10和2，當符合要求是，系統(tǒng)則會輸入最短路徑，如我輸入了2和4，如圖5-3：　　圖5-3查詢圖中任意兩個景點間的最短路徑　　5.4查詢圖中任意一點到其他景點間的所有

27、路徑　　當用戶輸入3是，則會進入該系統(tǒng)，此時系統(tǒng)會提示輸入你要選擇的景點編號，當不合要求時，同樣會提示請再次輸入，直到符合要求為止，如我輸入了20，之后又輸入了了15，最后輸入5，才輸入路徑。如圖5-4：　　圖5-4查詢圖中任意一點到其他景點間的所有路徑　　5.5查詢任意兩個景點間的所有路徑

28、　　當用戶選擇4時即可進入該系統(tǒng)，系統(tǒng)會提示用戶輸入要查詢的兩個景點的編號。相同的當有編號不存在時，系統(tǒng)會提示重新輸入正確的編號，如我輸入了一個2和10時，系統(tǒng)會提示輸入有誤，請重新輸入，最后我輸入了2和7，則輸出了所有路徑：如圖5-5所示。　　圖5-5查詢任意兩個景點間的所有路徑　　6.設計小結

29、　　通過幾周的課程設計，我學到了很多東西：　?。?）對自己所學的數(shù)據結構有了更熟練的運用和更深刻的了解。　?。?）提高了我的動手能力，學會了自覺主動地查找文獻知識，如到圖書館翻閱書籍和上網查閱等。　?。?）提高了自己的辦事效率，面對挑戰(zhàn)不退縮，敢于迎韌而上，除此還學會了遇

30、事沉著冷靜，認真思考，邏輯清晰的列出解決方案。　　（4）提高了我對市場的了解，使自己很好的將市場與C語言程序設計相結合，使自己能學以致用，聯(lián)系實際生活。　?。?）學會了感恩，了解到老師和父母對我們的付出都很大。　　參考文獻　　[1]

31、徐孝凱．數(shù)據結構使用教程．清華大學出版社：徐培忠，2006．　　[2] 徐孝凱．C++語言基礎．清華大學出版社：徐培忠，1999．　　[3] 徐孝凱．數(shù)據結構使用教程習題參考解答．清華大學出版社：徐培忠，2006．　　[4] 胡成松．C語言課程設計．北京高等教育出版社：林孝平，2006．&

32、lt;p>　　[5] 劉云．計算機網絡實用教程．北京高等教育出版社：徐培忠，2004． 　　[6] 徐孝凱．數(shù)據結構課程設計．清華大學出版社：徐培忠，2006．　　源代碼清單　　#include<stdio.h>

33、　#include <stdlib.h>　　#include<iostream.h>　　#include<strstrea.h>　　#include<string.h>　　#define FARMAX 1000</p&

34、gt;　　typedef int weighttype; //定義邊上權值的類型　　const int MAXVER=10; //定義圖的最多頂點數(shù)　　typedef int adjmatrixtype[MAXVER]; //定義adjmatrix為存儲鄰接矩陣的數(shù)組類型

35、　　struct infotype　　{　　char name[20];　　int num;　　char introduction[100];<p

36、>　　weighttype maxvalue;　　};　　struct Mgraph　　{ infotype vexs[MAXVER]; //定義存儲定點信息的數(shù)組類型　　infotype arcs[MAXVER]

37、[MAXVER]; //定義存儲鄰接矩陣的數(shù)組類型　　int vexnum,arcnum;　　};　　void jiben(Mgraph &G)　　{<p&

38、gt;　　int i,j;　　G.vexnum=8;　　G.arcnum=10;　　for(i=0;i<G.vexnum;i++)　　G.vexs[i].num=i;　　strcpy(G

39、.vexs[0].name,"弘德樓");　　strcpy(G.vexs[0].introduction,"學生公寓，主要為考研學生準備，環(huán)境良好。");　　strcpy(G.vexs[1].name,"靜思湖");　　strcpy(G.vexs[1].

40、introduction,"學生晨讀的好地方，夏日滿塘的荷花，很漂亮。");　　strcpy(G.vexs[2].name,"體育運動中心");　　strcpy(G.vexs[2].introduction,"學校最大的運動場所。");　　strcpy(

41、G.vexs[3].name,"圖書館");　　strcpy(G.vexs[3].introduction,"圖書館其中有大量的書籍，供學生免費閱讀而且環(huán)境良好。");　　strcpy(G.vexs[4].name,"綜合樓");　　strcpy(G.v

42、exs[4].introduction,"主要的教學樓，包括老師的辦公室。");　　strcpy(G.vexs[5].name,"學生食堂");　　strcpy(G.vexs[5].introduction,"提供各種食物，品種多樣。");　　strcp

43、y(G.vexs[6].name,"學生公園");　　strcpy(G.vexs[6].introduction,"學校新建的小公園，環(huán)境良好。");　　strcpy(G.vexs[7].name,"九棟宿舍");　　strcpy(G.vexs[7].i

44、ntroduction,"學生的主要住所，條件一般般。");　　for(i=0;i<G.vexnum;i++)　　for(j=0;j<G.vexnum;j++)　　G.arcs[i][j].maxvalue=FARMAX;　　G.arcs[

45、0][1].maxvalue=70;　　G.arcs[0][4].maxvalue=40;　　G.arcs[1][5].maxvalue=30;　　G.arcs[1][3].maxvalue=60;　　G.arcs[2][3].maxvalue=20;

46、　　G.arcs[3][4].maxvalue=30;　　G.arcs[4][5].maxvalue=40;　　G.arcs[4][7].maxvalue=80;　　G.arcs[5][7].maxvalue=50;　　G.arcs[6][7].ma

47、xvalue=30;　　for(i=0;i<G.vexnum;i++)　　for(j=0;j<G.vexnum;j++)　　G.arcs[j][i].maxvalue=G.arcs[i][j].maxvalue;　　}&l

48、t;/p>　　void menu() // 菜單　　{　　cout<<endl<<" 武漢長江工商學院校園導游圖 &quo

49、t;<<endl;　　cout<<" ╔═══════════════════════╗"<<endl; 　　cout<<" ║ 1.瀏覽校園全景

50、 ║"<<endl;　　cout<<" ║ 2.查詢圖中任意兩個景點間的最短路徑 ║"<<endl;　　cout<<" ║ 3.查詢圖中

51、一個景點到其他所有景點的最短路徑 ║"<<endl;　　cout<<" ║ 4.查詢任意兩景點間的所有路徑 ║"<<endl;　　cout<<" ║ 5.退出系統(tǒng)

52、 ║"<<endl;　　cout<<" ╚═══════════════════════╝"<<endl;　　cout<<" 請輸入你的選擇：

53、 "<<endl;　　}　　void information(Mgraph G) //簡介　　{　　cout<<&q

54、uot; ╔══╦═══════╦══════════════════════════╗"<<endl;　　cout<<" ║編號║景點名稱 ║ 簡介 ║"<<endl;　　cout&

55、lt;<" ╠══╬═══════╬══════════════════════════╣"<<endl;　　for(int i=0;i<G.vexnum;i++)　　printf(" ║%-4d║%-14s║%-52s║\n",G.vexs[i].num,G.vexs[i].name,

56、G.vexs[i].introduction);　　cout<<" ╚══╩═══════╩══════════════════════════╝"<<endl;　　}　　void Floyd(Mgraph G){

57、 //兩點間最短路徑　　int v,u,i,w,k,j,flag=1,p[8][8][8],D[8][8];　　for(v=0;v<G.vexnum;v++)　　for(w=0;w<G.vexnum;w++){　　D[v][w]=G.arcs[

58、v][w].maxvalue;　　for(u=0;u<G.vexnum;u++)　　p[v][w][u]=0;　　if(D[v][w]<FARMAX)　　{　　p[v][w][v]

59、=1;　　p[v][w][w]=1;　　}　　}　　for(u=0;u<G.vexnum;u++)　　for(v=0;v<G.vexnum;v

60、++)　　for(w=0;w<G.vexnum;w++)　　if(D[v][u]+D[u][w]<D[v][w]) {　　D[v][w]=D[v][u]+D[u][w];　　for(i=0;i<G.vexnum;i++)<p

61、>　　p[v][w][i]=p[v][u][i]||p[u][w][i];　　}　　while(flag)　　{　　cout<<"請輸入出發(fā)點和目的地的編號:"

62、;;　　cin>>k>>j;　　if(k<0||k>G.vexnum||j<0||j>G.vexnum)　　{　　cout<<"景點編號不存在!請重新輸入出發(fā)點和目

63、的地的編號:";　　cin>>k>>j;　　}　　if(k>=0 && k<G.vexnum && j>=0 && j<G.vexnum)<

64、p>　　flag=0;　　}　　cout<<G.vexs[k].name;　　for(u=0;u<G.vexnum;u++)　　if(p[k][j][u]&&

65、;k!=u&&j!=u)　　cout<<"-->"<<G.vexs[u].name;　　cout<<"-->"<<G.vexs[j].name;　　cout<<" 總路線長&q

66、uot;<<D[k][j]<<"m";　　}　　void farf(Mgraph G) //一點到其他所有路徑　　{　　int v,w,i,min

67、,t=0,x,flag=1,v0;　　int final[16], D[16], p[16][16];　　while(flag)　　{　　cout<<"請輸入一個起始景點編號:";

68、　　cin>>v0;　　if(v0<0||v0>G.vexnum)　　{　　cout<<"景點編號不存在!請重新輸入景點編號:";<

69、p>　　cin>>v0;　　}　　if(v0>=0&&v0<G.vexnum)　　flag=0;

70、;　　}　　for(v=0;v<G.vexnum;v++)　　{　　final[v]=0;　　D[v]=G.arcs[v0][v].maxvalue;　　for(w=

71、0;w<G.vexnum;w++)　　p[v][w]=0;　　if(D[v]<FARMAX)　　{　　p[v][v0]=1;p[v][v]=1;　　}</b

72、>　　}　　D[v0]=0;final[v0]=1;　　for(i=1;i<G.vexnum;i++)　　{　　min=FARMAX;<

73、/p>　　for(w=0;w<G.vexnum;w++)　　if(!final[w])　　if(D[w]<min)　　{　　v=w;

74、　　min=D[w];　　}　　final[v]=1;　　for(w=0;w<G.vexnum;w++)　　if(!final[w]&&(min+G.arc

75、s[v][w].maxvalue<D[w]))　　{　　D[w]=min+G.arcs[v][w].maxvalue;　　for(x=0;x<G.vexnum;x++) 　　p[w][x]=p[v][x];</p&g

76、t;　　p[w][w]=1;　　}　　}　　for(v=0;v<G.vexnum;v++){　　if(v0!=v) 　　cou

77、t<<G.vexs[v0].name;　　for(w=0;w<G.vexnum;w++){　　if(p[v][w]&&w!=v0) 　　cout<<"-->"<<G.vexs[w].name;<p&

78、gt;　　t++;　　}　　if(t>G.vexnum-1&&v0!=v)　　cout<<" 總路線長"<<D[v]<<"m"&

79、lt;<endl;　　}　　}　　int D[MAXVER];　　int visited[MAXVER];　　int a=0;&l

80、t;/b>　　void path(Mgraph G,int i,int j,int k)　　{　　int s;　　if(D[k]==j)<b&

81、gt;　　{　　a++;　　cout<<"第"<<a<<"條路徑為:";　　for(s=1;s<k;s++)　　cout<&l

82、t;G.vexs[D[s]].name<<"-->";　　cout<<G.vexs[D[s]].name;　　cout<<endl;　　}　　else&l

83、t;/b>　　{　　s=1;　　while(s<G.vexnum)　　{　　if(s!

84、=i)　　{　　if(G.arcs[D[k]][s].maxvalue!=FARMAX&&visited[s]==0)　　{　　visited[s]=1;<

85、;/p>　　D[k+1]=s;　　path(G,i,j,k+1);　　visited[s]=0;　　}　　}

86、　　s++;　　}　　}　　}　　void searchpath(Mgraph G)</p&g

87、t;　　{　　int i,j,k,flag=1;　　while(flag)　　{　　cout<<"請輸入出發(fā)點和目的地的編號:";</p

88、>　　cin>>i>>j;　　if(i<0||i>G.vexnum||j<0||j>G.vexnum)　　{　　cout<<"景點編號不存在!請重新輸入出發(fā)點和目的地的編號:&q

89、uot;;　　cin>>i>>j;　　}　　if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum)<

90、;b>　　flag=0;　　}　　for(k=0;k<G.vexnum;k++)　　{　　if(i==G.vexs[k].num)<p

91、>　　{　　i=k;　　break;　　}　　}&l

92、t;p>　　for(int s=0;s<G.vexnum;s++)　　{　　if(j==G.vexs[s].num)　　{　　j=s;</p

93、>　　break;　　}　　}　　cout<<"從"<<G.vexs[i].name<<"到"&

94、lt;<G.vexs[j].name<<"的所有路徑有:"<<endl;　　D[1]=i;　　for(k=0;k>G.vexnum;k++)　　visited[i]=0;<

95、b>　　a=0;　　path(G,i,j,1);　　}　　void casaf(Mgraph G) //菜單及選擇　　{&

96、lt;b>　　int i=1;　　while(i!=5)　　{　　cin>>i;　　switch(i)

97、;　　{　　case 1:system("cls");information(G);menu();break;　　case 2:system("cls");Floyd(G);menu();break;　　case

98、3:system("cls");farf(G);menu();break;　　case 4:system("cls");searchpath(G);menu();break;　　case 5:exit(1);break;　　default:break;

99、　　}　　}　　}　　void main()　　{　　sy

100、stem("color 2f");　　system("mode con: cols=100 lines=40");　　Mgraph G;　　jiben(G);

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

溫馨提示

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

數(shù)據結構課程設計--校園導游程序

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據結構課程設計--校園導游程序

文檔簡介

溫馨提示

最新文檔

評論

免費下載