數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

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

2、有路徑105.5查詢?nèi)我鈨蓚€景點間的所有路徑116.設(shè)計小結(jié)11參考文獻11源代碼清單121.課程設(shè)計的目的與意義1.1課程設(shè)計的目的隨著社會的發(fā)展，人們對生活的也要求越來越高，從以前的一切都用手用筆的時代到了一切都可以用機器代替的時代?，F(xiàn)在的大學(xué)校園越來越大了，對于對新學(xué)校不熟悉和對于外來著更好的參觀和游覽學(xué)校，特做了這個校園導(dǎo)游圖，它能輸出所有校園景點的簡介供用戶參考，并且能找到兩個景點間最短路徑，讓用戶少走彎路和冤枉路，而且還可以找到一個景點到其他景點的最短路徑，可以提供使用者最好的游覽路徑。更多的功能將會在后續(xù)繼續(xù)加入。1.2課程設(shè)計的意義鞏固和加深學(xué)生對數(shù)據(jù)結(jié)構(gòu)的基本知識的理解和掌握

3、,掌握C語言編程和程序調(diào)試的基本技能。利用數(shù)據(jù)結(jié)構(gòu)進行基本的軟件設(shè)計,掌握書寫程序設(shè)計說明文檔的能力，提高運用數(shù)據(jù)結(jié)構(gòu)解決實際問題的能力。培養(yǎng)我們綜合運用所學(xué)知識的能力和鍛煉實踐的能力,能夠做到善于發(fā)現(xiàn),提出,分析和解決實際問題。同時，進一步加深、鞏固我們所學(xué)專業(yè)課程（數(shù)據(jù)結(jié)構(gòu)實用教程）的基本理論知識,如語句嵌套和循環(huán)，分支等結(jié)運用，理論聯(lián)系實際，進一步培養(yǎng)學(xué)生綜合分析問題和解決問題的能力。掌握運用C語言獨立地編寫、調(diào)試應(yīng)用程序和進行其它相關(guān)設(shè)計的技能，擴展自己的知識面，充分發(fā)揮廣大同學(xué)的潛力，提高程序開發(fā)能力，使我們通過這次課程設(shè)計而得到全面的鍛煉。2.系統(tǒng)功能描述及設(shè)計整個系統(tǒng)主要包含三個

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

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

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

7、xnum;i+) for(j=0;jG.vexnum;j+) G.arcsji.maxvalue=G.arcsij.maxvalue;上面的代碼利用了兩個for循環(huán)很快的定義出了任意兩個景點的關(guān)系，如是否存在邊，存在邊權(quán)值是大?。]有邊則為事先定義的最大值，存在邊則直接輸入權(quán)值），同時也作出了無向圖應(yīng)有的特點，及是雙向的，并且兩邊權(quán)值相等。上面整個信息的錄入存儲了整個系統(tǒng)需要的數(shù)據(jù)，包括景點個數(shù)，邊數(shù)，名稱，簡介，距離。有了這個函數(shù)，方便以后所有的需要數(shù)據(jù)的地方來調(diào)用它。4.系統(tǒng)功能實現(xiàn)及算法描述4.1校園景點信息的錄入 該功能的實現(xiàn)是通過利用定義好的變數(shù)，定點數(shù)，景點名，景點編號，景點間權(quán)值

8、的，一次輸入G.，G.roduction，G.arcsii.maxvalue,而i，j的取值范圍是由G.vexnum和G.arcnum確定的。圖4-1：圖4-1校園景點信息的錄入4.2查詢圖中任意兩個景點間的最短路徑 該功能是利用弗洛伊德算法如果從k到j(luò)有邊，則存在一條長度為arcskj的路徑，該路徑不一定是最短路徑?？紤]路徑（k,u,j）是否存在，若存在，比較（k,j）和（k,u,j）的長度，取較短者為從k到j(luò)的中間點序號不大于0的最短路徑。以此類推，每次增加一個點，從而求出任意兩點間的最短路徑。這樣，經(jīng)過n次比較后，所求得的必為從k到j(luò)的最短路徑。按此

9、方法，可以同時求得任意兩點間的最短路徑。流程圖如下4-2：4-2查詢圖中任意兩個景點間的最短路徑4.3查詢圖中任意一個景點到其他景點的所有路徑 這個功能的實現(xiàn)是通過數(shù)組存儲所有右邊的路徑，然后根據(jù)用戶輸入的一個景點的編號找到該景點與其他景點右邊的景點，然后以右邊的其他景點為起點，重復(fù)上述流程，直到找完每個景點即結(jié)束程序。如圖4-3：圖4-3查詢圖中任意一個景點到其他景點的所有路徑4.4查詢?nèi)我鈨删包c間的所有路徑 該功能是通過用戶輸入的兩個景點的編號找到對應(yīng)的景點名，然后以第一個點作為起點向其他點找邊，當(dāng)邊的權(quán)值小于最大值時，說明存在邊，即可保存在數(shù)組中，直到找到終點對應(yīng)的編號即為一天路徑，循環(huán)

10、上述過程，直到出現(xiàn)重復(fù)路徑即結(jié)束函數(shù)，跳出循環(huán)。如圖圖4-4：圖4-4查詢?nèi)我鈨删包c間的所有路徑5. 系統(tǒng)性能測試5.1 主界面當(dāng)程序成功被打開時會出現(xiàn)如圖5-1所示的界面，該界面相當(dāng)于一個菜單，用戶可以根據(jù)自己的需求選擇數(shù)字?！?”瀏覽所有景點的信息，“2”找出任意兩景點間所有路徑，“3”找到一個景點到其他景點間的所有路徑，“4”退出系統(tǒng) ，下面是“請選擇，輸入1-5鍵：”的字樣。如圖5-1：圖5-1主界面測試圖5.2瀏覽校園全景當(dāng)用戶選擇1時，程序即會根據(jù)之前存儲好的信息輸出景點間的所有信息，供用戶瀏覽及參考。運行效果如下5-2圖片所示。圖5-2瀏覽校園全景5.3查詢圖中任意兩個景點間的最

11、短路徑 當(dāng)用戶選擇2時，則會進入該系統(tǒng)，系統(tǒng)會提示“請輸入兩個景點的編號”，當(dāng)你輸入的景點不符合要求時，會提示重新輸入如10和2，當(dāng)符合要求是，系統(tǒng)則會輸入最短路徑，如我輸入了2和4，如圖5-3：圖5-3查詢圖中任意兩個景點間的最短路徑5.4查詢圖中任意一點到其他景點間的所有路徑當(dāng)用戶輸入3是，則會進入該系統(tǒng)，此時系統(tǒng)會提示輸入你要選擇的景點編號，當(dāng)不合要求時，同樣會提示請再次輸入，直到符合要求為止，如我輸入了20，之后又輸入了了15，最后輸入5，才輸入路徑。如圖5-4：圖5-4查詢圖中任意一點到其他景點間的所有路徑5.5查詢?nèi)我鈨蓚€景點間的所有路徑當(dāng)用戶選擇4時即可進入該系統(tǒng)，系統(tǒng)會提示用戶

12、輸入要查詢的兩個景點的編號。相同的當(dāng)有編號不存在時，系統(tǒng)會提示重新輸入正確的編號，如我輸入了一個2和10時，系統(tǒng)會提示輸入有誤，請重新輸入，最后我輸入了2和7，則輸出了所有路徑：如圖5-5所示。圖5-5查詢?nèi)我鈨蓚€景點間的所有路徑6.設(shè)計小結(jié) 通過幾周的課程設(shè)計，我學(xué)到了很多東西：（1）對自己所學(xué)的數(shù)據(jù)結(jié)構(gòu)有了更熟練的運用和更深刻的了解。（2）提高了我的動手能力，學(xué)會了自覺主動地查找文獻知識，如到圖書館翻閱書籍和上網(wǎng)查閱等。（3）提高了自己的辦事效率，面對挑戰(zhàn)不退縮，敢于迎韌而上，除此還學(xué)會了遇事沉著冷靜，認真思考，邏輯清晰的列出解決方案。（4）提高了我對市場的了解，使自己很好的將市場與C語言

13、程序設(shè)計相結(jié)合，使自己能學(xué)以致用，聯(lián)系實際生活。（5）學(xué)會了感恩，了解到老師和父母對我們的付出都很大。參考文獻1 徐孝凱數(shù)據(jù)結(jié)構(gòu)使用教程清華大學(xué)出版社：徐培忠，20062 徐孝凱C+語言基礎(chǔ)清華大學(xué)出版社：徐培忠，19993 徐孝凱數(shù)據(jù)結(jié)構(gòu)使用教程習(xí)題參考解答清華大學(xué)出版社：徐培忠，20064 胡成松C語言課程設(shè)計北京高等教育出版社：林孝平，20065 劉云計算機網(wǎng)絡(luò)實用教程北京高等教育出版社：徐培忠，2004 6 徐孝凱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計清華大學(xué)出版社：徐培忠，2006源代碼清單#include#include #include#include#include#define FARMAX 10

14、00typedef int weighttype; /定義邊上權(quán)值的類型const int MAXVER=10; /定義圖的最多頂點數(shù)typedef int adjmatrixtypeMAXVER; /定義adjmatrix為存儲鄰接矩陣的數(shù)組類型struct infotypechar name20;int num;char introduction100;weighttype maxvalue;struct Mgraph infotype vexsMAXVER; /定義存儲定點信息的數(shù)組類型 infotype arcsMAXVERMAXVER; /定義存儲鄰接矩陣的數(shù)組類型 int vexn

15、um,arcnum;void jiben(Mgraph &G)int i,j;G.vexnum=8;G.arcnum=10;for(i=0;iG.vexnum;i+) G.vexsi.num=i;strcpy(G.,弘德樓);strcpy(G.roduction,學(xué)生公寓，主要為考研學(xué)生準(zhǔn)備，環(huán)境良好。); strcpy(G.,靜思湖); strcpy(G.roduction,學(xué)生晨讀的好地方，夏日滿塘的荷花，很漂亮。); strcpy(G.,體育運動中心); strcpy(G.r

16、oduction,學(xué)校最大的運動場所。); strcpy(G.,圖書館); strcpy(G.roduction,圖書館其中有大量的書籍，供學(xué)生免費閱讀而且環(huán)境良好。); strcpy(G.,綜合樓); strcpy(G.roduction,主要的教學(xué)樓，包括老師的辦公室。); strcpy(G.,學(xué)生食堂); strcpy(G.roduction,提供各種食物，品種多樣。); strcpy(G.,學(xué)生公園); strcpy(G.roducti

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

18、5.maxvalue=40; G.arcs47.maxvalue=80; G.arcs57.maxvalue=50; G.arcs67.maxvalue=30; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsji.maxvalue=G.arcsij.maxvalue;void menu() / 菜單coutendl 武漢長江工商學(xué)院校園導(dǎo)游圖 endl;cout endl; cout 1.瀏覽校園全景 endl; cout 2.查詢圖中任意兩個景點間的最短路徑 endl; cout 3.查詢圖中一個景點到其他所有景點的最短路徑 endl;c

19、out 4.查詢?nèi)我鈨删包c間的所有路徑 endl; cout 5.退出系統(tǒng) endl; cout endl;cout 請輸入你的選擇： endl;void information(Mgraph G) /簡介cout endl; cout 編號景點名稱 簡介 endl;cout endl; for(int i=0;iG.vexnum;i+)printf( %-4d%-14s%-52sn,G.vexsi.num,G.,G.roduction);cout endl;void Floyd(Mgraph G) /兩點間最短路徑 int v,u,i,w,k,j,fla

20、g=1,p888,D88; for(v=0;vG.vexnum;v+) for(w=0;wG.vexnum;w+) Dvw=G.arcsvw.maxvalue; for(u=0;uG.vexnum;u+) pvwu=0; if(DvwFARMAX) pvwv=1;pvww=1; for(u=0;uG.vexnum;u+) for(v=0;vG.vexnum;v+) for(w=0;wG.vexnum;w+) if(Dvu+DuwDvw) Dvw=Dvu+Duw; for(i=0;iG.vexnum;i+) pvwi=pvui|puwi; while(flag) coutkj; if(kG.ve

21、xnum|jG.vexnum) coutkj; if(k=0 & k=0 & jG.vexnum) flag=0; coutG.; for(u=0;uG.vexnum;u+) if(pkju&k!=u&j!=u) coutG.; coutG.; cout 總路線長Dkjm;void farf(Mgraph G) /一點到其他所有路徑int v,w,i,min,t=0,x,flag=1,v0;int final16, D16, p1616;while(flag)coutv0;if(v0G.vexnum)coutv0; if(v0=0&v

22、0G.vexnum) flag=0; for(v=0;vG.vexnum;v+) finalv=0; Dv=G.arcsv0v.maxvalue; for(w=0;wG.vexnum;w+) pvw=0; if(DvFARMAX) pvv0=1;pvv=1; Dv0=0;finalv0=1; for(i=1;iG.vexnum;i+) min=FARMAX; for(w=0;wG.vexnum;w+) if(!finalw) if(Dwmin)v=w;min=Dw; finalv=1; for(w=0;wG.vexnum;w+) if(!finalw&(min+G.arcsvw.maxvalu

23、eDw) Dw=min+G.arcsvw.maxvalue; for(x=0;xG.vexnum;x+) pwx=pvx; pww=1; for(v=0;vG.vexnum;v+) if(v0!=v) coutG.; for(w=0;wG.vexnum;w+) if(pvw&w!=v0) coutG.vexnum-1&v0!=v) cout 總路線長Dvmendl; 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;sk;s+)coutG.vexsD;coutG.vexsD;coutendl;elses=1;while(sG.vexnum