數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計-校園地圖設(shè)計及其應(yīng)用

數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計題目校園地圖設(shè)計及其應(yīng)用學院（系）信息工程系專業(yè)計算機科學與技術(shù)目錄第1章需求分析和任務(wù)定義 第1章需求分析和任務(wù)定義1.1需求分析許多剛來學校的師生以及來訪學校的客人都對學校并不是很了解，不知道每一棟建筑的位置，比如教學樓、宿舍、食堂等所在位置，不了解任意兩個地點之間的路線?；诖吮尘?，我們小組決定開發(fā)這個項目，設(shè)計一個廣東理工學院校園地圖，為師生、來訪客人提供任意建筑地點相關(guān)信息的查詢，以及為來訪客人提供任意地點的問路查詢，即查詢?nèi)我鈨蓚€地點之間的一條最短的簡單路徑，從而方便各位師生和來訪客人。另外，構(gòu)建校園網(wǎng)的主要目的就是提高教學質(zhì)量，為學校的教育提供優(yōu)質(zhì)的教學服務(wù)，因此，師生和來訪客人必須盡可能的節(jié)省問路的時間，甚至是要避免迷路的情況。1.2任務(wù)定義本系統(tǒng)包含一個文件，設(shè)計分有菜單、顯示信息、floyd算法、迪杰斯特拉算法，其中floyd算法是求兩個地點之間距離最短的算法，同時在本系統(tǒng)中又添加一些新的功能，這些在模塊分析中將介紹到。本系統(tǒng)的基本任務(wù)有設(shè)計校園平面圖，在校園地點選15個左右地點。以圖中頂點表示校園內(nèi)各地點，存放地點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等有關(guān)信息。2）為來訪客人提供圖中任意地點相關(guān)信息的查詢。3）為來訪客人提供任意地點的問路查詢，即查詢?nèi)我鈨蓚€地點之間的一條最短路徑。

第2章數(shù)據(jù)結(jié)構(gòu)選擇2.1邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)采用無向加權(quán)圖結(jié)構(gòu)，如圖2-1圖2-1圖2-1為自定義地圖，工程制圖為無向流通圖。而在無向流通圖中，如果刪去頂點v，以及與v關(guān)聯(lián)的邊，圖的剩余部分就變成不連通，那么，則稱v是關(guān)節(jié)點。如果v、w、和x是互不相同的3個頂點，且v到w必過x，則x必是關(guān)節(jié)點。不存在關(guān)節(jié)點的無向連通稱為雙連通圖，也稱二連通圖。而在圖2-1中，有2個關(guān)節(jié)點（4后門和7招生辦），3個雙連通分量。2.2存儲結(jié)構(gòu)圖2-1鄰接矩陣如圖2-2，采用一維數(shù)組壓縮儲存，壓縮存儲結(jié)構(gòu)如圖2-3。圖2-2

圖2-2無向圖與無向加權(quán)圖的鄰接矩陣Anxn是對稱矩陣，可用一維數(shù)組壓縮存儲，僅存其下三角部分。又由于頂點沒有到自身的邊，鄰接矩陣對角線元素全為0，所以對角線元素也用不著存儲，而只存嚴格下三角部分。于是，可推導出圖2-3。圖2-3

第3章算法設(shè)計與實現(xiàn)3.1算法設(shè)計3.1.1設(shè)計思路校園地圖是由各個地點和地點以及場所和場所之間的路徑組成的，所以這完全可以用數(shù)據(jù)結(jié)構(gòu)中的圖來模擬。用圖的結(jié)點代表地點或場所，用圖的邊代表地點或場所之間的路徑。所以首先應(yīng)創(chuàng)建圖的存儲結(jié)構(gòu)。結(jié)點值代表地點信息，邊的權(quán)值代表地點間的距離。結(jié)點值及邊的權(quán)值采用圖存儲。本系統(tǒng)需要查詢地點信息和求一個地點到另一個地點的最短路徑長度及路線，為方便操作，所以給每個地點一個代碼，用結(jié)構(gòu)體類型實現(xiàn)。計算路徑長度，最短路線和最佳路徑時可分別用迪杰斯特拉（Dijkastra）算法和哈密而頓回路算法實現(xiàn)。最后用switch選擇語句選擇執(zhí)行瀏覽地點信息或查詢最短路徑和距離。3.1.2算法描述采用工程思想，將系統(tǒng)共分一下幾個模塊:數(shù)據(jù)結(jié)構(gòu)定義模塊、導航圖建立模塊、求最短路徑模塊、主菜單；下面是具體各功能簡單的實際應(yīng)用：數(shù)據(jù)結(jié)構(gòu)定義模塊：模塊定義了導航圖中各個節(jié)點的基本結(jié)構(gòu)類型，主要采用鄰接矩陣的存儲結(jié)構(gòu)來真實反映各節(jié)點到其他所有節(jié)點的路徑長度（權(quán)值大?。Ш綀D建立模塊：采用上述結(jié)構(gòu)體類型對導航圖中每個節(jié)點進行賦值。包括：各定點的名稱（地點名），各個節(jié)點到其他所有節(jié)點的真實路徑長度（賦權(quán)值）。求最短路徑模塊：本模塊的基本思想是采用迪杰斯特拉算法求最短路徑。次模塊是本校園導航系統(tǒng)的核心模塊，求兩點間的最短路徑與求一點到其他所有點最短路徑兩個子功能均是在最短路徑算法模塊的基礎(chǔ)上進行調(diào)用，進而實現(xiàn)導航功能。主菜單：主菜單中主要是顯示導航圖中的所有導航節(jié)點，能夠快速方便的對各個地點進行導航。以上程序的幾個模塊，構(gòu)成了校園導航系統(tǒng)的基本組成部分，程序運行良好，達到了課程設(shè)計的基本要求。流程如圖3-1。圖3-1圖3-13.2算法實現(xiàn)3.2.1算法關(guān)鍵函數(shù)1.#defineMax32767//用Max來表示權(quán)值為此時的兩點間直接不可達#defineNUM15//選取了學校的十七個地點用數(shù)組存儲，其中數(shù)組第一個元素不存儲地點以方便操作typedefstructVertexType{ intnumber; char*sight;}VertexType;//定義頂點的結(jié)構(gòu)體類型，number表示頂點編號，字符數(shù)組表示頂點的名稱typedefstruct{ VertexTypevex[NUM]; intarcs[NUM][NUM]; intvexnum;}MGraph;//定義圖的結(jié)構(gòu)體類型，vex[NUM]數(shù)組存儲頂點，arcsp[NUM][NUM]矩陣存儲邊的權(quán)值，vexnum表示頂點的個數(shù)MGraphG;{生成G表示結(jié)構(gòu)體變量MGraph}intP[NUM][NUM];//定義全局變量P[NUM][NUM]存儲點之間的最短路徑longintD[NUM];//定義全局變量D[NUM]存儲點之間最短路徑的權(quán)值2.Dijkstra(intnum)//通過迪杰斯特拉算法求num點到其余點的最短路徑，并將最短路徑保存在數(shù)組P[NUM][NUM]中，將最短路徑的權(quán)值保存在數(shù)組D[NUM]中voidDijkstra(intnum){ intv,w,i,t; intfinal[NUM]; intmin; for(v=1;v<NUM;v++) { final[v]=0;//置空最短路徑終點集 D[v]=G.arcs[num][v];//置初始的最短路徑長度 for(w=1;w<NUM;w++) P[v][w]=0;//置空最短路徑 if(D[v]<32767) { P[v][num]=1; P[v][v]=1; } } D[num]=0; final[num]=1;//初始化num頂點屬于S集 for(i=1;i<NUM;++i)//開始循環(huán),每次求得num到某個頂點的最短路徑,并添加到S集 { min=Max;//min為當前所知的num到頂點的最短距離 for(w=1;w<NUM;++w) if(!final[w])//w頂點在V-S集中 if(D[w]<min) { v=w; min=D[w]; } final[v]=1;//與num相距最近的頂點并入S集 for(w=1;w<NUM;++w)//更新最短路徑 if(!final[w]&&((min+G.arcs[v][w])<D[w]))//修改D[w]和P[w]，w在V-S集中 { D[w]=min+G.arcs[v][w]; for(t=0;t<NUM;t++) P[w][t]=P[v][t]; P[w][w]=1; } }}charMenu()//主菜單顯示于操作界面從而讓用戶選擇查詢路徑功能或者查詢地點信息功能 charc; intflag;//定義標志flag確定循環(huán)條件 do{ flag=1; Map(); printf("\t\t1.查詢地點路徑\n"); printf("\t\t2.地點信息簡介\n"); printf("\t\te.退出\n"); printf("\t*************廣東理工學院*****\n"); printf("\t\t\t請輸入您的選擇："); scanf("%c",&c); if(c=='1'||c=='2'||c=='e') flag=0; }while(flag); returnc;}3.voidDisplay(intsight1,intsight2)//輸出函數(shù)用于通過數(shù)組P[NUM][NUM]提取出從點sight1到點sight2的最短路徑，從D[NUM]中輸出點sight1到點sight2的最短路徑的權(quán)值{ inta,b,c,d,q=0; a=sight2; if(a!=sight1) { printf("\n\t從%s到%s的最短路徑是",G.vex[sight1].sight,G.vex[sight2].sight); printf("\t(最短距離為%dm.)\n\n\t",D[a]);//從D[NUM]中提取出sight1到sight2的最短距離的權(quán)值輸出 printf("\t%s",G.vex[sight1].sight); d=sight1; for(c=0;c<NUM;++c) { P[a][sight1]=0; for(b=0;b<NUM;b++) { if(G.arcs[d][b]<32767&&P[a][b]) { printf("-->%s",G.vex[b].sight);//通過P[NUM][NUM]確定sight1到sight2的最短路徑 q=q+1; P[a][b]=0; d=b; if(q%8==0)printf("\n"); } } } }}3.2.2main函數(shù)圖：主函數(shù)對各個函數(shù)的調(diào)用voidmain()//主函數(shù){ intv0,v1; chare; charck; CreateMGraph(NUM); Do//用dowhile循環(huán)確保循環(huán)至少進行一次 { system("cls");//用system("cls")清屏使屏幕簡潔 ck=Menu(); switch(ck)//用switch語句確定用戶選擇功能 { case'1':gate://門函數(shù)使程序退回到gate位置 system("cls"); Map(); do { printf("\n\n\t\t\t請選擇出發(fā)地序號（1～14）："); scanf("%d",&v0); if(v0<1||v0>17) printf("\n\n\t\t\t\t輸入錯誤!\n"); }while(v0<1||v0>17); do { printf("\t\t\t請選擇目的地序號（1～14）："); scanf("%d",&v1); if(v1<1||v1>14||v1==v0) printf("\n\n\t\t\t\t輸入錯誤!\n"); }while(v1<1||v1>14||v1==v0); Dijkstra(v0); Display(v0,v1); printf("\n\n\t\t\t\t請按任意鍵繼續(xù),按e退回首頁\n"); getchar(); scanf("%c",&e); if(e=='e'){當標識符e等于e時跳出語句} break; gotogate; case'2': system("cls"); Info(); printf("\n\n\t\t\t\t請按回車鍵退回首頁...\n"); getchar(); getchar(); break; }; }while(ck!='e');//當標識符ck不等于e時繼續(xù)循環(huán)}3.3算法分析1.本程序?qū)崿F(xiàn)了查詢校園中任意兩景點的最短路徑的功能，同時也顯示了兩景點最短路徑的實際距離。也可以查詢?nèi)我饩包c的信息，包括按景點編號查詢和按景點名稱查詢。2.考慮道路網(wǎng)多是稀疏網(wǎng)，故采用鄰接矩陣作存儲結(jié)構(gòu)。對于一個具有n個頂點，m條邊的圖來說，其空間復(fù)雜度為O（n2），此時的時間復(fù)雜度也為O（n2）。構(gòu)建鄰接矩陣的時間復(fù)雜度為O（m），輸出路徑的時間復(fù)雜度為O（n+m）。由此，本系統(tǒng)程序的時間復(fù)雜度為O（n）+O（m）=O（n+m）。3.在創(chuàng)建造圖函數(shù)時，由于兩個地點的距離是相互的，所以要對圖中對稱的邊要同時賦值開始時沒有注意到這一點，導致程序總是有錯誤。4.本程序除了迪杰斯特拉算法外，基本全是用最簡單的c++語言編寫的，行數(shù)比較多。5.可擴展的功能有求校園圖的關(guān)節(jié)點，提供校園圖中多個地點的最佳訪問路線查詢，即求途經(jīng)這多個地點的最佳路徑。

第4章調(diào)試分析4.1測試用例設(shè)計在程序系統(tǒng)中，對功能的測試，在本章就開始進行基本的功能測試，所以在測試中，主要是測試邏輯結(jié)構(gòu)是否正確，是否符合最初的性能需求。首先設(shè)計測試用例。1.測試在沒有選中起始點與終點時，系統(tǒng)是否會崩潰。在系統(tǒng)剛開始運行時，并沒有選擇起始點和終點，運行系統(tǒng)，看是否會出錯。打開系統(tǒng)，進入到導航主系統(tǒng)，什么操作也不做，點擊查詢路徑按鈕，看系統(tǒng)是否會崩潰。2.測試系統(tǒng)的性能，連續(xù)輸入錯誤兩次或兩次以上，看系統(tǒng)是否會崩潰。用例ID1用例名稱頁面搜索查詢用例描述進入程序后選擇查詢地點最短路徑頁面信息包括：地點序號，選擇出發(fā)及目的地輸入框用例入口打開程序進入系統(tǒng)查詢頁面，輸入1，回車鍵進入查詢最短路徑界面測試用例ID場景測試步驟預(yù)期結(jié)果備注TC1初始頁面顯示從用例入口處進入頁面元素完整，顯示與詳細設(shè)計一致TC2初始頁面顯示，請輸入你的選擇輸入2輸入成功TC3介紹頁面輸入e顯示地點介紹TC4介紹頁面輸入3輸入失敗，程序無反應(yīng)輸入數(shù)據(jù)不在規(guī)定選項中TC5初始頁面顯示，請輸入你的選擇輸入1顯示地點序號TC6出發(fā)地選擇頁面顯示輸入出發(fā)地序號1顯示出發(fā)地序號TC7目的地選擇頁面顯示輸入目的地序號2輸入成功，顯示出目的地序號和1，2兩點之間最短路徑TC8出發(fā)地選擇頁面顯示輸入出發(fā)地序號2顯示出發(fā)地序號TC9目的地選擇頁面顯示輸入目的地序號2程序無反應(yīng)出發(fā)地與目的地序號相同，需重新輸入目的地TC10目的地選擇頁面顯示輸入目的地序號4輸入成功，顯示2,4之間的最短路徑…….…..…..4.2運行結(jié)果進入演示程序后隨即顯示如下的文本方式的用戶界面如圖4-1圖4-1輸入2，進入“廣東理工學院各地點介紹”，結(jié)果如圖4-2圖4-2輸入e，結(jié)果如圖4-3所示，再按回車鍵則退出程序圖4-3

輸入1進入“查詢地點之間最短路徑”，結(jié)果如圖4-4圖4-4輸入出發(fā)地序號1，再輸入目的地序號2，結(jié)果如圖4-5圖4-5

若輸入出發(fā)地和目的地的序號相同，則錯誤，需重新輸入目的地，結(jié)果如圖4-6圖4-6再次輸入目的地4，結(jié)果如圖4-7圖4-7

按回車鍵后，返回查詢地點之間最短路徑界面，結(jié)果如圖4-8圖4-8輸入e后，返回首頁，結(jié)果如圖4-9圖4-94.3調(diào)試過程問題分析調(diào)試過程中出現(xiàn)閃屏問題，應(yīng)該是程序中的未知BUG問題；調(diào)試中又可能會出現(xiàn)崩潰，可能是調(diào)試過程調(diào)試不當，或者是程序語法有細小錯誤。解決問題方法：及時修復(fù)漏洞，完善語法。

第5章總結(jié)5.1收獲與經(jīng)驗總結(jié)隨著計算機軟硬件的不斷發(fā)展，導航系統(tǒng)在客戶需求中的應(yīng)用已成必然。

本系統(tǒng)在開發(fā)中也是嚴格按照學校的實際情況進行開發(fā)的，在開發(fā)中，查閱了很多相關(guān)的算法資