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

1、一、設(shè)計(jì)題目：實(shí)驗(yàn)題目：設(shè)計(jì)你的學(xué)校的平面圖，至少包括 10個(gè)以上的場(chǎng)所，每?jī)蓚€(gè)場(chǎng)所間可以有不同的路，且路 長(zhǎng)也可能不同，找出從任意場(chǎng)所到達(dá)另一場(chǎng)所的最佳路徑（最短路徑）。需求分析實(shí)驗(yàn)設(shè)計(jì)的是實(shí)現(xiàn)一個(gè)簡(jiǎn)易的校園導(dǎo)航平面圖。本課題實(shí)現(xiàn)校園多個(gè)場(chǎng)所（至少10個(gè)）的最短路徑求解。（1）輸入的形式和輸入值的范圍：本系統(tǒng)主要數(shù)據(jù)類型為字符型和整形，字符型主要包括地點(diǎn)編號(hào)，地點(diǎn)名稱，地點(diǎn)簡(jiǎn)介，功能編號(hào)；輸入功能編號(hào)與單位編號(hào)進(jìn)行 操作。 輸出的形式：輸出則通過(guò)已有的信息數(shù)據(jù)，通過(guò)相關(guān)的操作輸出相應(yīng)信息。（3）程序所能達(dá)到的功能：可以為學(xué)生或旅客了解我校大概地點(diǎn)位置以及路徑， 主要功能：1.瀏覽校園地點(diǎn)及簡(jiǎn)

2、介；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)（中間用空格隔開(kāi)）、 D:ISDev98IyProjects1234DebugtZ34. exeJCS枚園導(dǎo) 恭查著所有到達(dá)路隹 =選銖出發(fā)點(diǎn)和目笊 4.查看地點(diǎn)信息 退出索統(tǒng)13北區(qū)食堂S I 8請(qǐng)輸入1個(gè)起:簡(jiǎn)介朝南旁邊為肚丄路車(chē)經(jīng)過(guò)站點(diǎn)4 多個(gè)籃球場(chǎng)。樓，埠層，前兩層是食堂，后一層是大學(xué)生之家。 一二樓均有閩應(yīng)

3、室丄以上是自習(xí)室和各種藏書(shū)。 標(biāo)準(zhǔn)養(yǎng)堂，F(xiàn) 學(xué)生醫(yī)務(wù)室。軟件工程學(xué)生實(shí)驗(yàn)樓以及一些教師辦公室。層，蓿潔衛(wèi)生。d.參看地點(diǎn)信息等待輸入地點(diǎn)編號(hào):三、概要設(shè)計(jì)本系統(tǒng)包含菜單（menu）,顯示信息（show）,弗洛伊德算法（floyd），迪杰斯特拉算 法（shotpath_dj），查找地點(diǎn)信息等程序段 （search）。主程序?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 mai n（）;進(jìn)入系統(tǒng)主菜單函數(shù)，根據(jù)用戶的選擇

4、可分別進(jìn)入：1.瀏覽各地點(diǎn)及簡(jiǎn)介；2. 查看所有游覽路徑；3. 選擇出發(fā)點(diǎn)和目的地求出最短路徑；4. 查看地點(diǎn)信息；5. 退出系統(tǒng)。選擇“1”項(xiàng)，顯示十個(gè)地點(diǎn)的有關(guān)信息，包括地點(diǎn)編號(hào)，地點(diǎn)名稱，地點(diǎn)簡(jiǎn)介。選擇“ 2”項(xiàng)，會(huì)進(jìn)入輸入起始地點(diǎn)編號(hào)的界面，輸入正確編號(hào)后會(huì)顯示起始地點(diǎn)到其余九個(gè)地點(diǎn)的所有路徑。選擇3”項(xiàng)，會(huì)進(jìn)入輸入起始地點(diǎn)與目的地點(diǎn)的界面，輸入起始地 點(diǎn)與目的地點(diǎn)，并有空格隔開(kāi)就得到兩地點(diǎn)之間的最短路徑。選擇4”項(xiàng)，會(huì)進(jìn)入輸入要查看的地點(diǎn)的界面，輸入地點(diǎn)編號(hào)后會(huì)顯示該地點(diǎn)的有關(guān) 信息。選擇“ 5”項(xiàng)，就會(huì)退出程序。F圖為程序總框架圖，表示函數(shù)之間的函數(shù)關(guān)系：Menu函數(shù)aShw 函數(shù)

5、+JShort-path珂口、辻函數(shù)心Search函數(shù)心四、系統(tǒng)詳細(xì)設(shè)計(jì)（1）十個(gè)校園地點(diǎn)圖：0:正大門(mén)1 :南三棟2 :西區(qū)籃球場(chǎng) 3 :食堂4 :教三棟5 :圖書(shū)館6 :北區(qū)食堂7 :醫(yī)務(wù)室8 :軟件樓9 :北門(mén)(2 )主程序流程圖：(3)迪結(jié)斯特拉算法實(shí)現(xiàn)的頂點(diǎn)V1到其他頂點(diǎn)的最短路徑：void ShortPath_Dj(MGraph * G)int v,w,i, min ,t=0,x,flag=1,v0;int final20, D20, p2020;cout編號(hào)地點(diǎn)名稱簡(jiǎn)介endl;for(v=0;vvex nu m;v+)coutvexsv .num vexsv .n ame ve

6、xsv.i ntroduct ionen dl; while(flag)cout v0;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(

7、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+;總路線長(zhǎng) DvG-vexnum-1&v0!=v) cout 五、調(diào)試分析（1）經(jīng)驗(yàn)和體會(huì)：C+ 數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)需要的是嚴(yán)謹(jǐn)?shù)膽B(tài)度和思維，不容一點(diǎn)隨意，格式的對(duì)錯(cuò)，類 型的一致， 嵌套和調(diào)用實(shí)現(xiàn)的目的， 這些都要明確， 首先要

8、設(shè)計(jì)這個(gè)程序要有你想導(dǎo)航的大 概地圖，即校園的藍(lán)圖。然后利用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)查找路徑和最短路徑，最后用 menu函數(shù)實(shí)現(xiàn)系統(tǒng)入口調(diào)用算法求路徑。六、使用說(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)

9、的所有路 徑。若輸入的地點(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“。1、測(cè)試結(jié)果菜單界面I地i 瀏疆地點(diǎn)及簡(jiǎn)介 趴查看所有到達(dá) 選屢出

10、發(fā)點(diǎn)和氐查晉地點(diǎn)信息 5 退田系統(tǒng) 選擇2、進(jìn)入“瀏覽各地點(diǎn)及簡(jiǎn)介”后，輸出地點(diǎn)信息的界面。系統(tǒng)瀏躅也簡(jiǎn)介2 查書(shū)所有到達(dá)路逢3 選擡出發(fā)點(diǎn)和目芮地4-查著地點(diǎn)信息5 退岀系統(tǒng) 選彈丄 編尋地點(diǎn)名禰 :鬆aS 2西區(qū)籃球場(chǎng) 3 J _ 堂 2 Si I E北區(qū)食堂 8 | I2 查著所有到達(dá)路隹 氛選提出發(fā)點(diǎn)和目的地4 查看地點(diǎn)信息 乩退出系統(tǒng)肚擇- 教葢書(shū)，前兩層是食堂，后一層是丈學(xué)生之家匚匚 *D:ISDev98IyProjects1234Debug1234 exe:簡(jiǎn)介朝希.旁邊為2路車(chē)經(jīng)過(guò)站點(diǎn)&帛個(gè)遁球場(chǎng)。董毅有噩窒溝島舉 自習(xí)室和各種藏書(shū)。 霽誰(shuí)學(xué)星實(shí)驗(yàn)樓以及一些教師辦公室。3、進(jìn)入

11、“查看所有游覽了路線“后，輸入”0 “到其他9個(gè)地點(diǎn)的路徑:進(jìn)入“選擇出發(fā)點(diǎn)和目的地”，輸入出發(fā)點(diǎn)1和目的點(diǎn)9后輸出的的最佳路線的界面?？找粮袅?=r-咎一4、j9皇一辰務(wù)室一北門(mén)總路線長(zhǎng)洛及簡(jiǎn)介5、進(jìn)入“查看地點(diǎn)信息”，輸入要查看的地點(diǎn)編號(hào)，輸出地點(diǎn)信息的界面。圖書(shū)館 一二樓均有閱覽室f以上是自習(xí)室和各種藏書(shū)。6、輸入要查詢的地點(diǎn)編號(hào)錯(cuò)誤，提示重新輸入。親嚳雲(yún)黑羸靈地點(diǎn)編號(hào):7、退出程序界面。地 介篇 心簡(jiǎn)路目 勵(lì)及達(dá)和息 魚(yú)到點(diǎn)信 一地有發(fā)點(diǎn)統(tǒng) 賢所出地系 瀏查選查退程 12 3 4七、心得體會(huì)：程序設(shè)計(jì)前應(yīng)該設(shè)計(jì)好系統(tǒng)實(shí)現(xiàn)的目的，系統(tǒng)大概流程。這個(gè)系統(tǒng)在設(shè)計(jì)前就是要是實(shí)現(xiàn)校園地圖的設(shè)計(jì)，

12、地點(diǎn)與地點(diǎn)間的的路徑、權(quán)值等；數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)、和算法的實(shí)現(xiàn)；但 覺(jué)的一個(gè)人設(shè)計(jì)程序系統(tǒng)實(shí)驗(yàn)量大，難以一下確定方向，所以應(yīng)該推廣團(tuán)隊(duì)合作、分工，因?yàn)橐粋€(gè)人的思維得到發(fā)散。附錄：系統(tǒng)相關(guān)代碼 ：#define infinity 10000#define max_vertex_num 40#define MAX 40#include#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)介等信息， ch

13、ar name30;int num;char introduction100;/ 簡(jiǎn)介infotype;typedef structinfotype vexsmax_vertex_num;AdjMatrix arcs;int vexnum,arcnum;MGraph;MGraph b;MGraph InitGraph();void Menu();void show(MGraph *G);void ShortPath_Dj(MGraph * G);void Floyd(MGraph *G);void Search(MGraph *G);MGraph InitGraph()/ 定義地點(diǎn)編號(hào)，名稱及

14、簡(jiǎn)介MGraph G;int i,j;G.vexnum=10;/ 十個(gè)地點(diǎn)(十個(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, 朝南 . 旁邊為 211 路車(chē)經(jīng)過(guò)站點(diǎn)。 ）; strcpy（G., 南區(qū) 六棟 ）; strcpy（G.roduction, 軟件學(xué)生宿舍。 ）; strcpy（G., 西區(qū)籃球場(chǎng) ）; strcpy（G.

15、roduction, 多個(gè)籃球場(chǎng)。 ）; strcpy（G., 食堂 ）;strcpy（G.roduction, 緊鄰教三樓，共 3 層，前兩層是食堂，后一層是大學(xué)生之家。 ）;strcpy（G., 教 三 棟 ）; strcpy（G.roduction, 學(xué)校的主要教學(xué)樓。 ）; strcpy（G., 圖 書(shū) 館 ）;strcpy（G.roduction, 一二樓均有閱覽室 ，以上是自習(xí)室和各種藏書(shū)。 ）; strcpy（G., 北區(qū) 食堂

16、）;strcpy（G.roduction, 標(biāo)準(zhǔn)食堂，兩層，清潔衛(wèi)生。 ）; strcpy（G., 醫(yī) 務(wù) 室 ）;strcpy（G.roduction, 學(xué)生醫(yī)務(wù)室。 ）; strcpy（G., 軟 件 樓 ）;strcpy（G.roduction, 軟件工程學(xué)生實(shí)驗(yàn)樓以及一些教師辦公室。 ）; strcpy（G., 北門(mén) ）;strcpy（G.roduction, 學(xué)校北大門(mén)。 ）; for（i=0;iG.vexnum;i+）for（j=0;jG.vexnum

17、;j+） G.arcsij.adj=infinity;/各地點(diǎn)之間的距離，沒(méi)有的均為無(wú)窮大 G.arcs01.adj=50;G.arcs05.adj=35;G.arcs06.adj=15;G.arcs09.adj=100;G.arcs12.adj=5;G.arcs13.adj=20;G.arcs23.adj=10;G.arcs34.adj=15;G.arcs45.adj=20;G.arcs56.adj=20;G.arcs57.adj=25;G.arcs58.adj=45;G.arcs67.adj=5;G.arcs79.adj=35;G.arcs89.adj=75; for（i=0;iG.vex

18、num;i+）for（j=0;jG.vexnum;j+）G.arcsji.adj=G .arcsij.adj; return G;void Menu()cout 校園導(dǎo)航系統(tǒng) endl; cout 1. 瀏覽各地點(diǎn)及簡(jiǎn)介endl;cout 2. 查看所有到達(dá)路徑endl;cout 3. 選擇出發(fā)點(diǎn)和目的地endl;cout 4. 查看地點(diǎn)信息endl;cout 5. 退出系統(tǒng)endl;cout 選擇 :;void show(MGraph *G)/ 顯示地點(diǎn)編號(hào)、名稱、簡(jiǎn)介int v; cout 編號(hào) 地點(diǎn)名稱 簡(jiǎn)介 endl;for(v=0;vvexnum;v+)coutvexsv.num v

19、 roductionendl; void ShortPath_Dj(MGraph * G)/ 迪結(jié)斯特拉算法實(shí)現(xiàn)的頂點(diǎn) V1 到其他頂點(diǎn)的最短路徑 int v,w,i,min,t=0,x,flag=1,v0;int final20, D20, p2020;cout 編號(hào) 地點(diǎn)名稱 簡(jiǎn)介 endl; for(v=0;vvexnum;v+)coutvexsv.num roductionendl; while(flag)coutv0;if(v0G-vexnum)coutv0;if(v0=0&v0vexnum)flag=0;f

20、or(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;

21、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;void Floyd(MGraph *G)/ 弗洛伊德算法int v,u,i,w,k,j,flag=1,p101010,D1010;cout 編號(hào) 地點(diǎn)名稱 簡(jiǎn)介 endl; for(v=0;vvexnum;v+)coutvexsv.num roductionendl; 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+) p