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

1、精品文檔武漢長江工商學院計算機科學與技術系工程名稱： 校園導游程序 學生姓名： 朱捷 學號： 1203090120 班級： 12801 指導教師： 劉瑩 2013年12月9日歡迎下載精品文檔目錄1.課程設計的目的與意義11.1課程設計的目的11.2課程設計的意義12.系統(tǒng)功能描述及設計13.系統(tǒng)存儲結構及描述34.系統(tǒng)功能實現(xiàn)及算法描述54.1校園景點信息的錄入54.2查詢圖中任意兩個景點間的最短路徑64.3查詢圖中任意一個景點到其他景點的所有路徑74.4查詢任意兩景點間的所有路徑85. 系統(tǒng)性能測試95.1 主界面95.2瀏覽校園全景95.3查詢圖中任意兩個景點間的最短路徑105.4查詢圖中

2、任意一點到其他景點間的所有路徑105.5查詢任意兩個景點間的所有路徑116.設計小結11參考文獻11源代碼清單12歡迎下載精品文檔1.課程設計的目的與意義1.1課程設計的目的隨著社會的開展，人們對生活的也要求越來越高，從以前的一切都用手用筆的時代到了一切都可以用機器代替的時代。現(xiàn)在的大學校園越來越大了，對于對新學校不熟悉和對于外來著更好的參觀和游覽學校，特做了這個校園導游圖，它能輸出所有校園景點的簡介供用戶參考，并且能找到兩個景點間最短路徑，讓用戶少走彎路和冤枉路，而且還可以找到一個景點到其他景點的最短路徑，可以提供使用者最好的游覽路徑。更多的功能將會在后續(xù)繼續(xù)參加。1.2課程設計的意義穩(wěn)固和

3、加深學生對數(shù)據(jù)結構的根本知識的理解和掌握,掌握C語言編程和程序調試的根本技能。利用數(shù)據(jù)結構進行根本的軟件設計,掌握書寫程序設計說明文檔的能力，提高運用數(shù)據(jù)結構解決實際問題的能力。培養(yǎng)我們綜合運用所學知識的能力和鍛煉實踐的能力,能夠做到善于發(fā)現(xiàn),提出,分析和解決實際問題。同時，進一步加深、穩(wěn)固我們所學專業(yè)課程?數(shù)據(jù)結構實用教程?的根本理論知識,如語句嵌套和循環(huán)，分支等結運用，理論聯(lián)系實際，進一步培養(yǎng)學生綜合分析問題和解決問題的能力。掌握運用C語言獨立地編寫、調試應用程序和進行其它相關設計的技能，擴展自己的知識面，充分發(fā)揮廣闊同學的潛力，提高程序開發(fā)能力，使我們通過這次課程設計而得到全面的鍛煉。2

4、.系統(tǒng)功能描述及設計整個系統(tǒng)主要包含三個大的模塊功能模塊圖見下列圖2-1菜單1：瀏覽校園全景，該功能的實現(xiàn)是通過編程著將所有信息事先錄入系統(tǒng)中，當用戶選擇時，會輸出學校所有的景點，編號及簡介。菜單2：查詢任意兩景點間的所有路徑。這個是根據(jù)弗洛伊德算法改編而來，該算法能很方便的找出用戶所輸入的兩景點間的最短路徑。當然，當你輸入的景點編號不存在時，就回提示重新輸入，知道輸入的兩個點都符合要求才會找出最短路徑。菜單3：查詢一個景點到其他所有景點的最短路徑。該系統(tǒng)能通過你所在的位置找出到其他所有景點的最短路徑。很方便的滿足客戶需要到達其他景點的路徑。菜單4：查詢圖中任意兩景點間的所有路徑。有了這個功能

5、，用戶可以很方便的找到圖中任意連個景點間的所有路徑。這樣用戶就可以選擇自己中意的路徑來到達自己的目的地了。菜單5：退出整個系統(tǒng)。圖2-1系統(tǒng)功能描述3.系統(tǒng)存儲結構及描述下面將給出程序代碼的局部代碼，將詳細介紹系統(tǒng)的存儲結構。如：struct infotypechar name20;int num;char introduction100;weighttype maxvalue;struct Mgraph infotype vexsMAXVER; /定義存儲定點信息的數(shù)組類型 infotype arcsMAXVERMAXVER; /定義存儲鄰接矩陣的數(shù)組類型 int vexnum,arcnum

6、;該存儲結構：在上面的結構體中，包含了圖中所需的景點名，景點個數(shù)，景點簡介，而且存儲了邊數(shù)，還利用數(shù)組來存儲兩景點間是否有邊，而且還包含了兩景點間的權值。for(i=0;i<G.vexnum;i+) G.vexsi.num=i;strcpy(G.,"弘德樓");strcpy(G.roduction,"學生公寓，主要為考研學生準備，環(huán)境良好。");上面簡單的幾行代碼就存儲了一個景點的編號，名稱，簡介for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) G.arcs

7、ij.maxvalue=FARMAX; G.arcs01.maxvalue=70; for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) G.arcsji.maxvalue=G.arcsij.maxvalue;上面的代碼利用了兩個for循環(huán)很快的定義出了任意兩個景點的關系，如是否存在邊，存在邊權值是大小沒有邊那么為事先定義的最大值，存在邊那么直接輸入權值，同時也作出了無向圖應有的特點，及是雙向的，并且兩邊權值相等。上面整個信息的錄入存儲了整個系統(tǒng)需要的數(shù)據(jù)，包括景點個數(shù)，邊數(shù)，名稱，簡介，距離。有了這個函數(shù)，方便以后所有的需要數(shù)據(jù)的地方來調用它

8、。4.系統(tǒng)功能實現(xiàn)及算法描述4.1校園景點信息的錄入 該功能的實現(xiàn)是通過利用定義好的變數(shù)，定點數(shù)，景點名，景點編號，景點間權值的，一次輸入G.，G.roduction，G.arcsii.maxvalue,而i，j的取值范圍是由G.vexnum和G.arcnum確定的。圖4-1：圖4-1校園景點信息的錄入4.2查詢圖中任意兩個景點間的最短路徑 該功能是利用弗洛伊德算法如果從k到j有邊，那么存在一條長度為arcskj的路徑，該路徑不一定是最短路徑?？紤]路徑k,u,j是否存在，假設存在，比擬k,j和k,u,j的長度，取較短者為從k到j的中間點序號不大于0的最短路

9、徑。以此類推，每次增加一個點，從而求出任意兩點間的最短路徑。這樣，經過n次比擬后，所求得的必為從k到j的最短路徑。按此方法，可以同時求得任意兩點間的最短路徑。流程圖如下4-2：4-2查詢圖中任意兩個景點間的最短路徑4.3查詢圖中任意一個景點到其他景點的所有路徑 這個功能的實現(xiàn)是通過數(shù)組存儲所有右邊的路徑，然后根據(jù)用戶輸入的一個景點的編號找到該景點與其他景點右邊的景點，然后以右邊的其他景點為起點，重復上述流程，直到找完每個景點即結束程序。如圖4-3：圖4-3查詢圖中任意一個景點到其他景點的所有路徑4.4查詢任意兩景點間的所有路徑 該功能是通過用戶輸入的兩個景點的編號找到對應的景點名，然后以第一個

10、點作為起點向其他點找邊，當邊的權值小于最大值時，說明存在邊，即可保存在數(shù)組中，直到找到終點對應的編號即為一天路徑，循環(huán)上述過程，直到出現(xiàn)重復路徑即結束函數(shù)，跳出循環(huán)。如圖圖4-4：圖4-4查詢任意兩景點間的所有路徑5. 系統(tǒng)性能測試5.1 主界面當程序成功被翻開時會出現(xiàn)如圖5-1所示的界面，該界面相當于一個菜單，用戶可以根據(jù)自己的需求選擇數(shù)字?！?瀏覽所有景點的信息，“2找出任意兩景點間所有路徑，“3找到一個景點到其他景點間的所有路徑，“4退出系統(tǒng) ，下面是“請選擇，輸入1-5鍵：的字樣。如圖5-1：圖5-1主界面測試圖5.2瀏覽校園全景當用戶選擇1時，程序即會根據(jù)之前存儲好的信息輸出景點間的

11、所有信息，供用戶瀏覽及參考。運行效果如下5-2圖片所示。圖5-2瀏覽校園全景5.3查詢圖中任意兩個景點間的最短路徑 當用戶選擇2時，那么會進入該系統(tǒng)，系統(tǒng)會提示“請輸入兩個景點的編號，當你輸入的景點不符合要求時，會提示重新輸入如10和2，當符合要求是，系統(tǒng)那么會輸入最短路徑，如我輸入了2和4，如圖5-3：圖5-3查詢圖中任意兩個景點間的最短路徑5.4查詢圖中任意一點到其他景點間的所有路徑當用戶輸入3是，那么會進入該系統(tǒng)，此時系統(tǒng)會提示輸入你要選擇的景點編號，當不合要求時，同樣會提示請再次輸入，直到符合要求為止，如我輸入了20，之后又輸入了了15，最后輸入5，才輸入路徑。如圖5-4：圖5-4查詢

12、圖中任意一點到其他景點間的所有路徑5.5查詢任意兩個景點間的所有路徑當用戶選擇4時即可進入該系統(tǒng)，系統(tǒng)會提示用戶輸入要查詢的兩個景點的編號。相同的當有編號不存在時，系統(tǒng)會提示重新輸入正確的編號，如我輸入了一個2和10時，系統(tǒng)會提示輸入有誤，請重新輸入，最后我輸入了2和7，那么輸出了所有路徑：如圖5-5所示。圖5-5查詢任意兩個景點間的所有路徑6.設計小結 通過幾周的課程設計，我學到了很多東西：1對自己所學的數(shù)據(jù)結構有了更熟練的運用和更深刻的了解。2提高了我的動手能力，學會了自覺主動地查找文獻知識，如到圖書館翻閱書籍和上網查閱等。3提高了自己的辦事效率，面對挑戰(zhàn)不退縮，敢于迎韌而上，除此還學會了

13、遇事沉著冷靜，認真思考，邏輯清晰的列出解決方案。4提高了我對市場的了解，使自己很好的將市場與C語言程序設計相結合，使自己能學以致用，聯(lián)系實際生活。5學會了感恩，了解到老師和父母對我們的付出都很大。參考文獻1 徐孝凱數(shù)據(jù)結構使用教程清華大學出版社：徐培忠，20062 徐孝凱C+語言根底清華大學出版社：徐培忠，19993 徐孝凱數(shù)據(jù)結構使用教程習題參考解答清華大學出版社：徐培忠，20064 胡成松C語言課程設計北京高等教育出版社：林孝平，20065 劉云計算機網絡實用教程北京高等教育出版社：徐培忠，2004 6 徐孝凱數(shù)據(jù)結構課程設計清華大學出版社：徐培忠，2006源代碼清單#include<

14、;stdio.h>#include <stdlib.h>#include<iostream.h>#include<strstrea.h>#include<string.h>#define FARMAX 1000typedef int weighttype; /定義邊上權值的類型const int MAXVER=10; /定義圖的最多頂點數(shù)typedef int adjmatrixtypeMAXVER; /定義adjmatrix為存儲鄰接矩陣的數(shù)組類型struct infotypechar name20;int num;char introd

15、uction100;weighttype maxvalue;struct Mgraph infotype vexsMAXVER; /定義存儲定點信息的數(shù)組類型 infotype arcsMAXVERMAXVER; /定義存儲鄰接矩陣的數(shù)組類型 int vexnum,arcnum;void jiben(Mgraph &G)int i,j;G.vexnum=8;G.arcnum=10;for(i=0;i<G.vexnum;i+) G.vexsi.num=i;strcpy(G.,"弘德樓");strcpy(G.roduction

16、,"學生公寓，主要為考研學生準備，環(huán)境良好。"); strcpy(G.,"靜思湖"); strcpy(G.roduction,"學生晨讀的好地方，夏日滿塘的荷花，很漂亮。"); strcpy(G.,"體育運動中心"); strcpy(G.roduction,"學校最大的運動場所。"); strcpy(G.,"圖書館"); strcpy(G.roduction,&q

17、uot;圖書館其中有大量的書籍，供學生免費閱讀而且環(huán)境良好。"); strcpy(G.,"綜合樓"); strcpy(G.roduction,"主要的教學樓，包括老師的辦公室。"); strcpy(G.,"學生食堂"); strcpy(G.roduction,"提供各種食物，品種多樣。"); strcpy(G.,"學生公園"); strcpy(G.roduction,&qu

18、ot;學校新建的小公園，環(huán)境良好。"); strcpy(G.,"九棟宿舍"); strcpy(G.roduction,"學生的主要住所，條件一般般。");for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) G.arcsij.maxvalue=FARMAX; G.arcs01.maxvalue=70; G.arcs04.maxvalue=40; G.arcs15.maxvalue=30; G.arcs13.maxvalue=60; G.arcs23.maxv

19、alue=20; G.arcs34.maxvalue=30; G.arcs45.maxvalue=40; G.arcs47.maxvalue=80; G.arcs57.maxvalue=50; G.arcs67.maxvalue=30; for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) G.arcsji.maxvalue=G.arcsij.maxvalue;void menu() / 菜單cout<<endl<<" 武漢長江工商學院校園導游圖 "<<endl;cout<<&

20、quot; "<<endl; cout<<" 1.瀏覽校園全景 "<<endl; cout<<" 2.查詢圖中任意兩個景點間的最短路徑 "<<endl; cout<<" 3.查詢圖中一個景點到其他所有景點的最短路徑 "<<endl;cout<<" 4.查詢任意兩景點間的所有路徑 "<<endl; cout<<" 5.退出系統(tǒng) "<<endl; cout&l

21、t;<" "<<endl;cout<<" 請輸入你的選擇： "<<endl;void information(Mgraph G) /簡介cout<<" "<<endl; cout<<" 編號景點名稱 簡介 "<<endl;cout<<" "<<endl; for(int i=0;i<G.vexnum;i+)printf(" %-4d%-14s%-52sn",

22、G.vexsi.num,G.,G.roduction);cout<<" "<<endl;void Floyd(Mgraph G) /兩點間最短路徑 int v,u,i,w,k,j,flag=1,p888,D88; for(v=0;v<G.vexnum;v+) for(w=0;w<G.vexnum;w+) Dvw=G.arcsvw.maxvalue; for(u=0;u<G.vexnum;u+) pvwu=0; if(Dvw<FARMAX) pvwv=1;pvww=1; for(u=0;u&

23、lt;G.vexnum;u+) for(v=0;v<G.vexnum;v+) for(w=0;w<G.vexnum;w+) if(Dvu+Duw<Dvw) Dvw=Dvu+Duw; for(i=0;i<G.vexnum;i+) pvwi=pvui|puwi; while(flag) cout<<"請輸入出發(fā)點和目的地的編號:" cin>>k>>j; if(k<0|k>G.vexnum|j<0|j>G.vexnum) cout<<"景點編號不存在!請重新輸入出發(fā)點和目的地

24、的編號:" cin>>k>>j; if(k>=0 && k<G.vexnum && j>=0 && j<G.vexnum) flag=0; cout<<G.; for(u=0;u<G.vexnum;u+) if(pkju&&k!=u&&j!=u) cout<<"->"<<G.; cout<<"->"<<

25、G.; cout<<" 總路線長"<<Dkj<<"m"void farf(Mgraph G) /一點到其他所有路徑int v,w,i,min,t=0,x,flag=1,v0;int final16, D16, p1616;while(flag)cout<<"請輸入一個起始景點編號:"cin>>v0;if(v0<0|v0>G.vexnum)cout<<"景點編號不存在!請重新輸入景點編號:"cin>>v

26、0; if(v0>=0&&v0<G.vexnum) flag=0; for(v=0;v<G.vexnum;v+) finalv=0; Dv=G.arcsv0v.maxvalue; for(w=0;w<G.vexnum;w+) pvw=0; if(Dv<FARMAX) pvv0=1;pvv=1; Dv0=0;finalv0=1; for(i=1;i<G.vexnum;i+) min=FARMAX; for(w=0;w<G.vexnum;w+) if(!finalw) if(Dw<min)v=w;min=Dw; finalv=1; f

27、or(w=0;w<G.vexnum;w+) if(!finalw&&(min+G.arcsvw.maxvalue<Dw) Dw=min+G.arcsvw.maxvalue; for(x=0;x<G.vexnum;x+) pwx=pvx; pww=1; for(v=0;v<G.vexnum;v+) if(v0!=v) cout<<G.; for(w=0;w<G.vexnum;w+) if(pvw&&w!=v0) cout<<"->"<<G.vexsw.

28、name; t+; if(t>G.vexnum-1&&v0!=v) cout<<" 總路線長"<<Dv<<"m"<<endl; int DMAXVER;int visitedMAXVER;int a=0;void path(Mgraph G,int i,int j,int k)int s;if(Dk=j)a+;cout<<"第"<<a<<"條路徑為:"for(s=1;s<k;s+)cout<<

29、G.vexsD<<"->"cout<<G.vexsD;cout<<endl;elses=1;while(s<G.vexnum)if(s!=i)if(G.arcsDks.maxvalue!=FARMAX&&visiteds=0)visiteds=1;Dk+1=s;path(G,i,j,k+1);visiteds=0;s+;void searchpath(Mgraph G)int i,j,k,flag=1;while(flag) cout<<"請輸入出發(fā)點和目的地的編號:" cin>&