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

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