數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-校園導(dǎo)航

.課 程 設(shè) 計(jì) 報(bào) 告課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 題 目 校園導(dǎo)航 指導(dǎo)教師 設(shè)計(jì)起始日期 5.95.16 學(xué) 院 計(jì)算機(jī)學(xué)院 系 別 計(jì)算機(jī)科學(xué)與工程 學(xué)生姓名 班級(jí)/學(xué)號(hào) 成 績(jī) 一、 需求分析 本次實(shí)驗(yàn)設(shè)計(jì)的任務(wù)是實(shí)現(xiàn)一個(gè)簡(jiǎn)易的北京信息科技大學(xué)的校園導(dǎo)航平面圖。設(shè)計(jì)要包括下列要求：設(shè)計(jì)你的學(xué)校的平面圖，至少包括10個(gè)以上的場(chǎng)所，每?jī)蓚€(gè)場(chǎng)所間可以有不同的路，且路長(zhǎng)也可能不同，找出從任意場(chǎng)所到達(dá)另一場(chǎng)所的最佳路徑（最短路徑）。本課題實(shí)現(xiàn)校園多個(gè)場(chǎng)所（至少10個(gè)）的最短路徑求解。（1）輸入的形式和輸入值的范圍：本系統(tǒng)主要數(shù)據(jù)類(lèi)型為字符型char及整形int,char型主要包括單位編號(hào)，單位名稱，單位簡(jiǎn)介，功能編號(hào)；輸入功能編號(hào)與單位編號(hào)進(jìn)行操作。 (2 ) 輸出的形式：輸出則通過(guò)已有的信息數(shù)據(jù)，通過(guò)相關(guān)的操作輸出相應(yīng)信息。 (3) 程序所能達(dá)到的功能：本程序可供任何人使用，主要功能1.瀏覽各單位及簡(jiǎn)介；2.查看所有游覽路線；3.選擇出發(fā)點(diǎn)和目的地求出最佳路徑；4.查看某一單位信息。（4）測(cè)試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。a.首先看到的是校園導(dǎo)航系統(tǒng)的菜單：b查看瀏覽路線等待輸入起始景點(diǎn)：C選擇出發(fā)點(diǎn)與目的地 等待輸入起始景點(diǎn)與目的地編號(hào)：d參看景點(diǎn)信息等待輸入景點(diǎn)編號(hào)：二、 概要設(shè)計(jì) 本系統(tǒng)包含一個(gè)文件。設(shè)計(jì)分有菜單，顯示信息，弗洛伊德算法，迪杰斯特拉算法，查找景點(diǎn)信息等程序段。主程序?yàn)檎到y(tǒng)的入口處，菜單主要實(shí)現(xiàn)顯示系統(tǒng)功能，顯示信息主要實(shí)現(xiàn)顯示景點(diǎn)信息，弗洛伊德算法主要實(shí)現(xiàn)求兩景點(diǎn)之間最短路徑，迪杰斯特拉算法實(shí)現(xiàn)求兩景點(diǎn)之間最短路徑，查找景點(diǎn)信息主要實(shí)現(xiàn)顯示某一景點(diǎn)信息。 系統(tǒng)首先通過(guò)主程序調(diào)用void main( );進(jìn)入系統(tǒng)主菜單函數(shù)，根據(jù)用戶的選擇可分別進(jìn)入：1.瀏覽各景點(diǎn)及簡(jiǎn)介；2.查看所有游覽路線；3.選擇出發(fā)點(diǎn)和目的地求出最佳路徑；4.查看景點(diǎn)信息；5.退出系統(tǒng)。選擇“瀏覽各景點(diǎn)及簡(jiǎn)介”項(xiàng)，顯示十個(gè)景點(diǎn)的有關(guān)信息，包括景點(diǎn)編號(hào)，景點(diǎn)名稱，景點(diǎn)簡(jiǎn)介。選擇“查看所有游覽路線”項(xiàng)，會(huì)進(jìn)入輸入起始景點(diǎn)編號(hào)的界面，輸入正確編號(hào)后會(huì)顯示起始景點(diǎn)到其余九個(gè)景點(diǎn)的最短路線的方案。選擇“選擇出發(fā)點(diǎn)和目的地”項(xiàng)，會(huì)進(jìn)入輸入起始景點(diǎn)與目的景點(diǎn)的界面，輸入起始景點(diǎn)與目的景點(diǎn)，并有空格隔開(kāi)就得到兩景點(diǎn)之間的最佳路徑。選擇“查看景點(diǎn)信息”項(xiàng)，會(huì)進(jìn)入輸入要查看的景點(diǎn)的界面，如入后會(huì)顯示該景點(diǎn)的有關(guān)信息。選擇“退出系統(tǒng)”項(xiàng)，就會(huì)退出程序。三、 詳細(xì)設(shè)計(jì) （1）十三個(gè)單位的圖 0： 前門(mén) 1：圖書(shū)館 2：教二樓3：實(shí)驗(yàn)樓4：操場(chǎng)5：教一樓6：食堂7： 水房8：學(xué)一公寓9：學(xué)二公寓10：學(xué)三公寓11：學(xué)四公寓12：后門(mén) （2）主程序流程圖： （3）弗洛伊德的算法：void Floyd(MGraph *G) int v,u,i,w,k,j,flag=1,p101010,D1010;/定義參數(shù)for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) Dvw=G-arcsvw.adj; for(u=0;uvexnum;u+) pvwu=0; if(DvwINFINITY) pvwv=1;pvww=1; for(u=0;uvexnum;u+) for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) if(Dvu+DuwDvw) Dvw=Dvu+Duw; for(i=0;ivexnum;i+) pvwi=pvui|puwi; while(flag) coutkj; if(kG-vexnum|jG-vexnum) /判斷輸入的景點(diǎn)編號(hào)正確與否 coutkj; if(k=0&kvexnum&j=0&jvexnum) flag=0; ; /輸出景點(diǎn)名稱 for(u=0;uvexnum;u+) if(pkju&k!=u&j!=u) /輸出路線 ;;cout 總路線長(zhǎng)Dkjendl; /輸出總路線長(zhǎng)度四、 調(diào)試分析 （1） 在程序設(shè)計(jì)中遇到了輸出景點(diǎn)信息的表不整齊，用setw（）解決了；默認(rèn)的界面太小，不能完整的看到輸出信息，用了system(mode con: cols=100 lines=40)命令語(yǔ)句設(shè)置了行數(shù)和列數(shù)。（2）經(jīng)驗(yàn)和體會(huì)經(jīng)過(guò)一段時(shí)間來(lái)的努力，終于初步實(shí)現(xiàn)系統(tǒng)功能，但肯定還存在不少漏洞。這是我們第三次做課程設(shè)計(jì)，也是第三次編寫(xiě)一個(gè)比較完整和具有一定功能的的系統(tǒng)代碼，第二次幾個(gè)人合作制作系統(tǒng)，制作過(guò)程中存在儲(chǔ)多的不足，遇到過(guò)許多的困難，曾經(jīng)灰心喪氣過(guò)，但是最終還是堅(jiān)持了下來(lái)，雖然做得不怎么樣，但我們已經(jīng)努力地去做了，由于基礎(chǔ)也不怎么扎實(shí)，所以困難會(huì)比其它組更多更艱巨。剛開(kāi)始做系統(tǒng)缺乏全局觀念，分工也不是很合理，做得很零碎，所以在組合的時(shí)候也出現(xiàn)了很多問(wèn)題。五、 使用說(shuō)明和測(cè)試結(jié)果打開(kāi)系統(tǒng)，首先會(huì)進(jìn)入系統(tǒng)的主菜單：1. 瀏覽各景點(diǎn)及簡(jiǎn)介 2. 查看所有游覽路線 3. 選擇出發(fā)點(diǎn)和目的地4. 查看景點(diǎn)信息5. 退出系統(tǒng)用戶可以進(jìn)行如下操作： 1、如果你想瀏覽各景點(diǎn)及簡(jiǎn)介的話，請(qǐng)輸入“1”，并回車(chē)。此時(shí)界面上將顯示出各景點(diǎn)的編號(hào)、名稱及其簡(jiǎn)介。2、如果你想查看某一景點(diǎn)的所有游覽路線，可選擇2操作。輸入“2”，并回車(chē)。此時(shí)，系統(tǒng)會(huì)提示你輸入某景點(diǎn)的編號(hào)。輸入編號(hào)后，回車(chē)，便可以看到該景點(diǎn)的所有游覽路線。若輸入的景點(diǎn)編號(hào)錯(cuò)誤就會(huì)有提示重新輸入。3、如果你想查看兩個(gè)景點(diǎn)之間的最短路線的，可選擇3操作。輸入“3”，并回車(chē)。此時(shí)，系統(tǒng)會(huì)提示你要輸入起始景點(diǎn)與終點(diǎn)的編號(hào)。輸入編號(hào)后，回車(chē)，此時(shí)，便可以見(jiàn)到這兩個(gè)景點(diǎn)之間的最短路徑。4、如果你想查看具體某些景點(diǎn)的簡(jiǎn)介及信息，可以選擇4操作。輸入“4”，并回車(chē)。此時(shí)，系統(tǒng)會(huì)提示全部景點(diǎn)的對(duì)應(yīng)的編號(hào)，選擇你要查看的景點(diǎn)信息，輸入其編號(hào)，回車(chē)，此時(shí)，屏幕上將會(huì)顯示出該景點(diǎn)的各種信息。若輸入的景點(diǎn)編號(hào)錯(cuò)誤就會(huì)有提示重新輸入。 5、在主菜單鍵入“5” ，退出程序。測(cè)試結(jié)果1、 菜單界面2、 進(jìn)入“瀏覽各景點(diǎn)及簡(jiǎn)介”后，輸出景點(diǎn)信息的界面。3、 進(jìn)入“查看所有游覽路線”，顯示輸出景點(diǎn)編號(hào)為0的景點(diǎn)到其余九個(gè)景點(diǎn)的最佳路線。4、 進(jìn)入“選擇出發(fā)點(diǎn)和目的地”，輸入出發(fā)點(diǎn)1和目的點(diǎn)9后輸出的的最佳路線的界面。 5、 進(jìn)入“查看景點(diǎn)信息”，輸入要查看的景點(diǎn)編號(hào)，輸出景點(diǎn)信息的界面。 6、 輸入要查詢的景點(diǎn)編號(hào)錯(cuò)誤，提示重新輸入。 7、 退出程序界面。六、 心得體會(huì)做一個(gè)系統(tǒng)之前還應(yīng)該做好全面的安排，對(duì)一個(gè)系統(tǒng)的整個(gè)流程及功能實(shí)現(xiàn)有一個(gè)很好的統(tǒng)籌，幾個(gè)人合作的功能可拆才拆，不可則由一個(gè)人主要負(fù)責(zé)，其它人幫忙思考，出意見(jiàn)，做系統(tǒng)之前幾個(gè)人必須先做對(duì)系統(tǒng)做一次較詳細(xì)的探討研究，然后才開(kāi)始分工，一個(gè)階段后組員應(yīng)互相交流情況，以達(dá)到一致。另在遇到困難時(shí)組員不能解決，應(yīng)查資料或問(wèn)其它懂的同學(xué)，參考一下意見(jiàn)，再結(jié)合自己的想法，最后實(shí)現(xiàn)自己想實(shí)現(xiàn)的功能。七、 附錄 #define INFINITY 10000 /*無(wú)窮大*/#define MAX_VERTEX_NUM 40#define MAX 40#include#include#include using namespace std;#include typedef struct ArCellint adj; /路徑長(zhǎng)度ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱、簡(jiǎn)介等信息，char name30;int num;char introduction100;/簡(jiǎn)介infotype;typedef structinfotype vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;MGraph;MGraph b;MGraph InitGraph(void);void Menu(void);void Browser(MGraph *G);void ShortestPath_DIJ(MGraph * G);void Floyd(MGraph *G);void Search(MGraph *G);/*主函數(shù)*/void main(void) system(color 1f); system(mode con: cols=100 lines=40); int i; b=InitGraph(); Menu(); cini; while(i!=5) switch(i) case 1:system(cls);Browser(&b);Menu();break; case 2:system(cls);ShortestPath_DIJ(&b);Menu();break; case 3:system(cls);Floyd(&b);Menu();break; case 4:system(cls);Search(&b);Menu();break; case 5:exit(1);break; default:break; cini; /*/*定義景點(diǎn)編號(hào)，名稱及簡(jiǎn)介*/MGraph InitGraph(void) MGraph G; int i,j; G.vexnum=10; /十個(gè)景點(diǎn) G.arcnum=14; /鄰接矩陣 for(i=0;iG.vexnum;i+) G.vexsi.num=i; /各景點(diǎn)的代碼，名稱及簡(jiǎn)介 strcpy(G.,前門(mén) ); strcpy(G.roduction,面南.對(duì)面為北京外國(guó)專(zhuān)家大廈 ); strcpy(G.,圖書(shū)館 ); strcpy(G.roduction,藏書(shū)幾十萬(wàn)冊(cè)，設(shè)施良好，一二樓均有閱覽室 ); strcpy(G.,教二樓 ); strcpy(G.roduction,學(xué)校的主要教學(xué)樓，共六層，有多個(gè)專(zhuān)業(yè)實(shí)驗(yàn) ); strcpy(G.,實(shí)驗(yàn)樓 ); strcpy(G.roduction,緊鄰教二樓，共七層，主要為公共實(shí)驗(yàn)室，六層有通宵自習(xí)室 ); strcpy(G.,操場(chǎng) ); strcpy(G.roduction,全新塑膠跑道，中間為人工草皮足球場(chǎng)，排球場(chǎng)和籃球場(chǎng) ); strcpy(G.,教一樓 ); strcpy(G.roduction,學(xué)校各機(jī)關(guān)單位辦公樓和雙語(yǔ)教室 ); strcpy(G.,食堂 ); strcpy(G.roduction,標(biāo)準(zhǔn)食堂，兩層，清潔衛(wèi)生 ); strcpy(G.,水房 ); strcpy(G.roduction,配備自動(dòng)刷卡系統(tǒng) ); strcpy(G.,學(xué)一公寓); strcpy(G.roduction,光電通信學(xué)院男生公寓 ); strcpy(G.,學(xué)二公寓); strcpy(G.roduction,女生公寓 ); strcpy(G.,學(xué)三公寓); strcpy(G.roduction,計(jì)算機(jī)學(xué)院男生公寓 ); strcpy(G.,學(xué)四公寓); strcpy(G.roduction,大一新生公寓 ); strcpy(G.,后門(mén) ); strcpy(G.roduction,面北，對(duì)面有便利的小超市 ); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij.adj=INFINITY;/各景點(diǎn)之間的距離，沒(méi)有的均為無(wú)窮大 G.arcs01.adj=50; G.arcs02.adj=100; G.arcs15.adj=20; G.arcs16.adj=75; G.arcs23.adj=10; G.arcs25.adj=60; G.arcs34.adj=20; G.arcs411.adj=30; G.arcs56.adj=30; G.arcs67.adj=10; G.arcs78.adj=20; G.arcs89.adj=10; G.arcs910.adj=20; G.arcs1012.adj=120; G.arcs1112.adj=150; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsji.adj=G.arcsij.adj; return G;/*/*主菜單（顯示輸入提示）*/void Menu() cout 北京信息科技大學(xué)大學(xué)導(dǎo)游圖 endl;cout endl;cout 1.瀏覽各景點(diǎn)及簡(jiǎn)介 endl;cout 2.查看所有游覽路線 endl;cout 3.選擇出發(fā)點(diǎn)和目的地 endl;cout 4.查看景點(diǎn)信息 endl;cout 5.退出系統(tǒng) endl;cout endl;coutOption-:;/*顯示景點(diǎn)編號(hào)、名稱、簡(jiǎn)介*/void Browser(MGraph *G) int v;coutendl;cout編號(hào)景點(diǎn)名稱 簡(jiǎn)介 endl; for(v=0;vvexnum;v+)coutvexsv.numsetw(5)setw(10)roductionsetw(3)endl;coutendl;/*迪杰斯特拉算法來(lái)計(jì)算出起點(diǎn)到各個(gè)頂點(diǎn)之間的最短路徑,v0為起點(diǎn)*/void ShortestPath_DIJ(MGraph * G) int v,w,i,min,t=0,x,flag=1,v0; int final20, D20, p2020;coutendl;cout編號(hào)景點(diǎn)名稱 簡(jiǎn)介 endl; for(v=0;vvexnum;v+)coutvexsv.numsetw(5)setw(10)roductionsetw(3)endl;coutendl; while(flag) coutv0; if(v0G-vexnum) coutv0; if(v0=0&v0vexnum) flag=0; for(v=0;vvexnum;v+) finalv=0; Dv=G-arcsv0v.adj; for(w=0;wvexnum;w+) pvw=0; if(DvINFINITY) pvv0=1;pvv=1; Dv0=0;finalv0=1; for(i=1;ivexnum;i+) min=INFINITY; for(w=0;wvexnum;w+) if(!finalw) if(Dwmin)v=w;min=Dw; finalv=1; for(w=0;wvexnum;w+) if(!finalw&(min+G-arcsvw.adjarcsvw.adj; for(x=0;xvexnum;x+) pwx=pvx; pww=1; for(v=0;vvexnum;v+) if(v0!=v) ; for(w=0;wvexnum;w+) if(pvw&w!=v0) ; t+; if(tG-vexnum-1&v0!=v) cout 總路線長(zhǎng)Dvendl; /*Floyd函數(shù)*/void Floyd(MGraph *G) int v,u,i,w,k,j,flag=1,p101010,D1010;coutendl;cout編號(hào)景點(diǎn)名稱 簡(jiǎn)介 endl; for(v=0;vvexnum;v+)coutvexsv.numsetw(5)setw(10)roductionsetw(3)endl;coutendl; for(v=0;vvexnum;v+) for(w=0