校園導航系統(tǒng)

1、題號：第七題題目：校園導航問題1, 需求分析：設計你的學校的平面圖，至少包括10個以上的景點(場所)，每兩個景點間可以有不同的路，且路長也可能不同，找岀從任意景點到達另一景點的最佳路徑(最短路徑)。要求：(1) 以圖中頂點表示校園內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等 有關信息。(2) 為來訪客人提供圖中任意景點相關信息的查詢。(3) 為來訪客人提供任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一條最短路徑。(4) 修改景點信息。實現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設計校園平面圖是一個無向網(wǎng)。頂點和邊均含有相關信息。選做內(nèi)容：(1) 提供圖的編輯功能：

2、增、刪景點；增、刪道路；修改已有信息等。(2) 校園導游圖的仿真界面。2, 設計：2.1設計思想:<1>，數(shù)據(jù)結(jié)構(gòu)設計：(i)圖。采用鄰接矩陣存儲，其中圖所用到的結(jié)構(gòu)體為:typedef structSeqList vertices;/表示圖中的頂點int EdgeMaxVerticesMaxVertices;/ 表示圖中的邊int numOfEdge;/表示圖中邊的數(shù)目AdjMGraph;(2)景點。用順序表存儲。所用到的結(jié)構(gòu)體為：typedef struct/頂點名稱頂點代號/頂點信息簡介char n ame20;int code;char in troducti on 50;

3、DataType;(3) 景點之間的連接描述，所用到的結(jié)構(gòu)體為:typedef struct int row;int col;int weight;RowColWeight;用圖來存放所提供的所有景點，然后用線性表來存放每一個景點的信息，其中包括景點的名稱，代號，信息簡介，以及其它的一些信息。這樣就將對景點的操作，變成對圖中各頂點的操作<2>，算法設計：關于本課題的算法，很大部分來源于這學期數(shù)據(jù)結(jié)構(gòu)課程的學習，其中包括：圖的創(chuàng)建，線性表的一些操作。對于具體的問題實現(xiàn)，都有不同的算法，在下面的分析中，我將詳細說明2.2設計表示:<1>,函數(shù)調(diào)用關系及函數(shù)說明：首先，mai

4、n()函數(shù)調(diào)用Creat()函數(shù)，用來創(chuàng)建圖，然后調(diào)用menu()函數(shù)來選擇用戶所要進行的操作。其中對menu()函數(shù)就是一個菜單供使用者來選擇他所要進行的相關操作，比如信息的查詢，最短路徑查詢之類。，存放景點名稱、代號、簡介等信 息；以邊表示路徑，存放路徑長度等有關信息。圖的創(chuàng)建設計流程圖為：Creaa(n函數(shù)原型為1 Creat()void Creat(AdjMGraph *G, DataType v, RowColWeight E, i nt n,i nt e)其中，G為所創(chuàng)建的圖結(jié)構(gòu)體對象，v為所有頂點的集合，它是DataType型，這個類型前面已經(jīng)介紹過；E存放著各頂點之間的連接關系

5、，它是RowColWeight型，前面也介紹過；n表示頂點的個數(shù)；e表示邊數(shù)。Creat()函數(shù)的功能就是實現(xiàn)圖的創(chuàng)建，將已知的景點的一些信息，轉(zhuǎn)換成圖的信息，并進行存儲。In formati on()對于要求2:為來訪客人提供圖中任意景點相關信息的查詢。流程圖為：menu()函數(shù)的 原型為：Information1()void men u()他就是一個菜單，供用戶選擇他們所要進行的操作。Information")函數(shù)原型為:voidIn formatio n1()它的功能就是輸入查詢景點的信息，并調(diào)用In formatio n()Information。函數(shù)原型為：void In

6、formatio n(AdjMGraph G, char seen ery)G 依然是所創(chuàng)建的圖的結(jié)構(gòu)體對象，后面所有的G都是表示這個意思；seenery是在Information1()中輸入的景點的名稱。此函數(shù)的功能就是根據(jù)輸入的景點的名稱來查詢其相關的信息。對于要求3：為來訪客人提供任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一條 最短路徑。流程圖為：PathieT函數(shù)原型為：Path1()Path()F|oyd()void Path1()它的功能就是輸入查詢景點的名稱，并調(diào)用Path()Path ()函數(shù)原型為：v oid Path(AdjMGraph G,ehar see neryn

7、ame, char see neryn ame1)其中seeneryname, seeneryname1就是在 Path1()函數(shù)中所輸入的景點的名稱，這個函數(shù)的功能就是通過這兩個景點的名稱找到它們在線性表中的位置，然后調(diào)用Floyd()函數(shù)，查找出它們的最短路徑，并輸出所要的信息。Floyd()函數(shù)原型為：void Floyd (int eost MaxVertiees,int n,int weightMaxVertices,int pathMaxVertices) 其中參數(shù)eost MaxVertiees即是圖中邊的鄰接存儲矩陣，weightMaxVertiees用來存放經(jīng)此算法后的各頂點

8、間的最短路徑的值，pathMaxVertiees就是每兩個頂點之間最短路徑中到達目的頂點的前一個頂點的位置。Path()函數(shù)中的輸岀信息就是據(jù)此而來。對于要求4:修改景點信息。流程圖為：void Modify()它不帶任何參數(shù)，功能是通過手動輸入景點名稱，然后找到景點的存儲空間，然后在修改相應的信息。對于選做要求：增加景點。其工作流程圖為：AdavnuiCo 函數(shù)原型為：AddVertic()ListI nsert()void AddVertic()他不帶任何參數(shù)，該函數(shù)的功能是在這個函數(shù)里面輸入景點的信息，然后調(diào)用ListInsert()函數(shù)，將所要增加的頂點信息插入到線性表中。Listln

9、sert()函數(shù)原型為：void ListInsert(SeqList *L, int i, DataType x) 參數(shù)L表示頂點存儲的線性表，i表示要插入的位置,x表示要插入的景點的信息。同時我在插入頂點時也將他與其他頂點之間的距離設置為MaxWeight，這樣做主要是為了方便在Floyd函數(shù)里面求最短路徑對于選做要求：刪除景點。其工作流程圖為DeleteVertic()函數(shù)原型為：void DeleteVertic()他不帶任何參數(shù)，該函數(shù)的功能就是在函數(shù)體里面輸入要刪除的景點的名稱，然后根據(jù)名稱找到該景點在線性表中的存儲位置，然后調(diào)用線性表中的ListDelete ()函數(shù)進行相應頂點

10、的刪除。ListDelete ()函數(shù)原型為：ListDelete(SeqList *L, int i, DataType *x) 其中參數(shù)L為存放頂點信息的線性表，i表示要刪除頂點在線性表中的存放位置，,x就是要刪除的那一個景點。它的功能就是從線性表中刪除指定的頂點。對于選做要求：增、刪道路，流程圖為：void AddRoad()和void DeleteRoad()。這兩個函數(shù)都不帶參數(shù)，它們的功能就是在這兩個函數(shù)里面輸入要 刪除要增加或者的邊連接的兩個景點的名稱，然后在線性表中找到這兩個景點的相對存儲空間，最后調(diào)用InsertEdge ()或者 DeleteEdge ()函數(shù)。Insert

11、Edge ()和 DeleteEdge ()兩函數(shù)原型為：void InsertEdge(AdjMGraph *G, int v1, int v2, int weight)void DeleteEdge(AdjMGraph *G, i nt v1, i nt v2)這兩個函數(shù)中同名參數(shù)所代表的意義是相同的，其中v1, v2是所輸入景點在線性表中的相對位置；weight就是增加的邊的權(quán)值<2>函數(shù)接口說明我所設計整個程序就是一些子函數(shù)的集合，每個功能都對應一個或者幾個子函數(shù)，他們之間可以沒有任何限制，只要能保證程序正確運行就可以調(diào)用，特別是AdjMGraph.h,AdjMGraph.

12、h和SeqList.h頭文件之中的函數(shù)，他們被很多函數(shù)調(diào)用過。這其中都沒有任何特殊類型的函數(shù)2.3詳細設計：根據(jù)題目分析，對于信息查詢與修改功能，設計如下：1, 輸入景點名稱2, 從線性表頭掃描到表尾，if(找到該景點)輸出景點結(jié)構(gòu)體信息else輸出提示信息找不到該頂點實現(xiàn)查找最短路徑，設計如下：1, 景點名稱2，根據(jù)輸入的信息找到它們所在的線性表中的位置3, 調(diào)用Floyd算法找岀最短路徑4, 輸岀信息實現(xiàn)增刪景點功能，設計如下：1, 增加或者刪除景點的名稱2, if(輸入景點)，將景點信息保存在相應的結(jié)構(gòu)體中，并插入到線性表尾；if(刪除景點)，找到景點在線性表中所在的位置，然后將景點信息

13、從線性表中刪除 實現(xiàn)增刪道路功能，設計如下：1, 入增加或刪除道路連接的兩個景點的名稱；2, 找到它們的相對位置；3, if(刪除道路)，將連接它們的邊置為MaxWeight ;if(增加道路)，將輸入的邊值賦給相應的鄰接矩陣表；3，調(diào)試分析：1，調(diào)試過程中遇到的問題與解決方案：1,關于最短路徑的輸岀問題。在進行最短路徑輸岀時，我剛開始時只能正序輸岀，具體的描述為：比如，我要查尋從東區(qū)到東湖的最短路徑，那么它能正確輸岀結(jié)果，他的形式為：東區(qū)一一 主樓一一 西體育館 一一 隧道 一一 北大門 一一 東湖。但是，當我逆向輸岀時，得到的結(jié)果卻有點問題，經(jīng)過分析調(diào)試后， 找到了錯誤的所在。在找最短路徑

14、的時候我用的是Floyd算法，在這個算法中有三重循環(huán)，形式均為：for(k=0;k n;k+)，它們都是從零開始的，所以在順序輸岀時沒問題，但是逆序的時候就需要進行一個判斷， 正序與逆序循環(huán)輸岀是相反的。2,關于新增加景點后再找最短路徑問題。比如我再新增一個景點，如北區(qū)食堂，并輸入相關信息，然后插入到線性表尾，當我再找從東區(qū)到東湖的最短距離時，輸岀的最短路徑將變?yōu)椋簴|區(qū)一一食堂一一東湖。經(jīng)過分析調(diào)試后，其原因也是岀在Floyd 算法那，在Floyd 算法中，有這么一個判斷 if(weightijweightik+weightkj)，由于我在輸入新景點信息時并沒有建立它與其它景點之間的連接信息，

15、所以在圖中，該新景點與其它景點之間的邊得連接信息是空的，也就是說在鄰接矩陣中，它的邊得信息是空的，那么在進行if(weightijweightik+weightkj)判斷時weight新增景點序號其它景點序號的值將是一個很大的負數(shù)，所以最短路徑將會岀錯。解決這個問題的方法就是在增加新景點時就將它與其它景點之間的邊(距離)設置為MaxWeight，這時如果再用 Floyd函數(shù)進行最短路徑的求解時就不會再岀現(xiàn)問題了。另外，在做這個題時也還岀現(xiàn)過一些其他的小問題，不過都比較容易解決，這里我就不再列岀了2,算法的時空復雜度分析對應題目的要求，我總共提供了八個選項操作對于每一個操作的分析如下：1，相關信

16、息的查詢。在這個操作中允許使用者輸入一個景點名稱，然后再根據(jù)景點名稱來或取其相關的信息，這個操作要掃描線性表，其時間復雜度為o(n)，空間復雜度為 o(n)；2, 最短路徑查詢。實現(xiàn)這個功能用到了Floyd算法，他用到了一個三重的for()循環(huán)，故其時間復雜度為o(n人3)，空間復雜度為 o(1)；3, 修改景點信息。要修改信息，必須首先找到景點所在的存儲位置，那么就需要掃描線性表，其時間復雜 度為o(n)，空間復雜度為 o(1)；4, 增加景點。增加景點信息時，直接將此景點結(jié)構(gòu)體信息插入到線性表表尾，而不需要進行遍歷，其時間復雜度與空間復雜度均為o(1)；5, 刪除景點。刪除景點時必須找到所

17、要刪除景點所在的位置，這樣就必須遍歷線性表，除此之外，刪除后線性表還要進行移動操作，其時間復雜度為o(n)，空間復雜度為 o(n1)；6, 增加道路。增加道路也要掃描線性表，找到要增加路的兩景點的存儲位置，然后再根據(jù)找到的存儲位置去改變鄰接矩陣的邊的值，改變鄰接矩陣的時間復雜度為o(1),其總時間消耗在線性表的掃描上，故最終其時間復雜度為o(n),空間復雜度為 0(1);7, 刪除道路。刪除道路和增加道路類似，都是先找到存儲位置，然后再改變鄰接矩陣，它的時空復雜度分 別為 o(n) ，0(1)；8, 瀏覽所有景點。瀏覽所有景點的實質(zhì)就是從頭到尾遍歷線性表，然后輸岀遍歷到的節(jié)點的信息，其時間 復

18、雜度為o(n),空間復雜度為 0(1)。4,用戶手冊:DOS環(huán)境里面將看到一個選項菜單，菜單里面 18之間的數(shù) 當然，一般而言先應該10個景點的名使用說明：當用戶將程序經(jīng)過編譯，連接后，點擊運行，在提供了 8種操作，同時輸岀了一行提示信息：請選擇您想進行的操作。然后用戶可以輸入一個 字進行選擇性的操作，例如，您想進行信息的查詢操作，您可以從鍵盤輸入數(shù)字1進行“瀏覽所有景點名稱”操作。如果您選擇了瀏覽所有景點名稱操作，在屏幕上將會顯示岀 稱，這些景點是事先加進去的，用戶可以對這些景點進行任何程序所提供的操作。下面，我將詳細介紹本程序的使用方法：在瀏覽景點后，菜單將會繼續(xù)顯示岀來，為您提供操作選擇

19、。如果您想進行“相關信息的查詢”操作，輸入數(shù)字1',然后程序?qū)嵝涯斎氩樵兙包c的名稱，在您輸入景點名稱后回車即可如果您想進行“最短路徑查詢”操作，首先輸入數(shù)字2',然后程序?qū)嵝涯斎氩樵兊木包c的名稱，您輸入按要求輸入所提供的兩個景點名稱即可，要注意的是景點名稱間以空格隔開，最后程序就會告訴您最短 的路徑，以及最短路的長度。如果您想修改景點的信息，同樣先輸入數(shù)字3',然后程序就會提醒您輸入所要修改景點的名稱，您可以根據(jù)要求輸入一個景點的名稱，然后回車，之后屏幕上就會顯示您所輸入的景點的所有信息，同時會有三個修 改選項供用戶選擇，然后您可以輸入13之間的一個數(shù)字進行

20、選擇性的修改。比如，您可以輸入T對景點名稱進行修改，修改完后又會返回到菜單項繼續(xù)選擇。如果您想進行“增加景點”操作，可以輸入數(shù)字4',然后程序就會提示您輸入新增加的景點的名稱，代號，信息簡介，各種輸入之間以空格隔開。當輸入完畢后回車，景點也就成功加入了，然后用戶可以再次選擇 第八項操作瀏覽所有景點名稱，檢測新輸入的景點是否已經(jīng)成功添加。如果您想進行“刪除景點”操作，可以輸入數(shù)字5',回車后系統(tǒng)將會提示您輸入要刪除的景點的名稱，您可以輸入您想要刪除的景點的名稱，然后回車，這樣刪除景點的操作就已經(jīng)完成，您同樣可以選擇第八項操 作，檢測是否成功刪除了景點。如果您想進行“增加道路”操作

21、，您可以輸入數(shù)字6',然后回車，系統(tǒng)將會提示您輸入增加道路所連接的兩個景點的名稱，輸入兩景點名稱后回車，然后系統(tǒng)又會提示輸入增加道路的長度，輸入后回車，這時增加 道路操作也就完了。用戶如果想要檢查道路是否增加成功可以進行“最短路徑查詢”操作。如果您想進行“刪除道路”操作，您可以輸入數(shù)字7',然后系統(tǒng)就會提示您輸入刪除道路所連接的兩景點的名稱，輸入名稱后回車即可，當然，如果您想檢測刪除是否成功您可以選擇“最短路徑查詢”操作。備注：經(jīng)過測試，本程序的所有操作都能正常執(zhí)行，您可以選擇性的對他進行操作，同時也可以混合著操 作，混合操作是檢測錯誤的最好的一個方法。5,測試數(shù)據(jù)及測試結(jié)果:

22、菜單顯示為：*菜*1, 相關信息查詢2, 最短路徑查詢3, 修改景點信息4, 增加景點5, 刪除景點6, 增加道路7, 刪除道路8, 瀏覽所有景點名稱*請選擇您想進行的操作：8東區(qū) 博物館主樓 圖書館西體育館 北大門東湖請選擇您想進行的操作：1請輸入您所想要查詢的景點的名稱：博物館您輸入的景點的名稱是：博物館您輸入的景點的代碼為：11您輸入的景點的相關信息有：有各種化石請選擇您想進行的操作：2請輸入你要查詢的兩景點的名稱：東區(qū)東湖隧道 北綜北體育館最短路徑為：108從東區(qū)點到東湖景點的最短路徑為：東區(qū)一一 主樓一一 西體育館一一 隧道一一 北大門一一 東湖請選擇您想進行的操作：3您想修改的景點

23、的名稱為：隧道您輸入的景點的名稱是：隧道您輸入的景點的代碼為：15您輸入的景點的相關信息有：自主修建您想修改什么信息？1,名稱；2,代號；3,信息簡介：1請輸入要修改的的景點的新名稱：地大隧道請選擇您想進行的操作：8東區(qū) 博物館 主樓 圖書館 西體育館地大隧道東湖請選擇您想進行的操作：4請輸入增加節(jié)點的 名稱，代號，信息簡介： 北一樓34教師辦公室請選擇您想進行的操作：1請輸入您所想要查詢的景點的名稱：北一樓您輸入的景點的名稱是：北一樓您輸入的景點的代碼為：34您輸入的景點的相關信息有：教師辦公室請選擇您想進行的操作：5請輸入您要刪除景點的名稱：北一樓請選擇您想進行的操作：8東區(qū) 博物館 主樓

24、 圖書館 西體育館地大隧道北綜北體育館北綜北體育館北大門北大門東湖請選擇您想進行的操作：6輸入您要增加的道路鏈接的兩個景點名稱：東區(qū)北綜輸入您要增加的道路的長度:50請選擇您想進行的操作：2請輸入你要查詢的兩景點的名稱：東區(qū)北綜最短路徑為：50從東區(qū)點到北綜景點的最短路徑為：東區(qū) 北綜請選擇您想進行的操作：7輸入您要刪除的道路鏈接的兩個景點名稱：東區(qū)北綜請選擇您想進行的操作：2請輸入你要查詢的兩景點的名稱：東區(qū)北綜最短路徑為：103從東區(qū)點到北綜景點的最短路徑為：東區(qū)> 主樓>西體育館> 地大隧道> 北大門> 北綜6,源程序清單：school.cpp程序源文件Ad

25、jMGraph.h/圖的相關操作頭文件AdjMGraphCreat.h/創(chuàng)建圖的頭文件SeqList.h線性表操作頭文件Floyd.h/Floyd算法頭文件Operati on.h/自己所定義的一些操作的頭文件In quiry.h/查詢信息包含的頭文件/詳細school.cpp程序源文件#i nclude <stdio.h>#in clude <stri ng.h>#i nclude <malloc.h>#defi ne MaxSize 20/線性表的最大數(shù)組空間#defi ne MaxVertices 20景點個數(shù)所允許的最大值#defi ne MaxWe

26、ight 1000/無窮邊權(quán)值#i nclude "Floyd.h"#i nclude "AdjMGraphCreat.h"#i nclude "In quiry.h"AdjMGraph G;#i nclude "Operatio n.h"void mai n()初始景點信息DataType a="東區(qū)",10,"研究生院","博物館",11,"有各種化石","主樓",12,"學校的標志建筑" ,

27、"圖 書館",13,"藏書50萬冊","西體育館",14,"主要供西區(qū)學生使用","隧道",15,"自主修建","北綜",16,"北區(qū)標志樓","北體育館",17,"主要供北區(qū)學生使用 ","北大門",18,"外岀通道","東湖",19," 武漢最美的湖"；鄰接矩陣的表示RowColWeightrcw=0,1,20,0

28、,2,30,0,3,35,1,0,20,1,3,20,2,0,30,2,3,15,2,4,30,3,0,35,3,1,2 0,3,2,15,3,4,30,4,2,30,4,3,30,4,5,10,5,4,10,5,6,35,5,8,8,6,5,35,6,7,20,6,8,25,6,9,5,7,6,20,7,8,10,8,5,8,8,6,25,8,7,10,9,6,5;int n=10,e=28;景點數(shù)與邊數(shù)Creat(&G,a,rcw, n,e);/ 構(gòu)造圖men u();/詳細Floyd.h頭文件void Floyd( int costMaxVertices,i nt n,i nt

29、weightMaxVertices,i nt pathMaxVertices)初始化int i,j,k;for(i=0;i< n;i+)for(j=0;j< n;j+)weightij=costij;pathij=-1;n次遞推for(k=0;k <n ;k+)for(i=0;i <n ;i+)for(j=0;j< n;j+)if(weightij>weightik+weightkj)weightij=weightik+weightkj;pathij=k;/詳細Inquiry.h 頭文件void In formatio n(AdjMGraph G, char

30、 sce nery)int i;break;printf("您所查詢的景點不在我們所提供的范圍內(nèi)！nn");void Path(AdjMGraph G,char sce neryn ame, char sce neryn ame1)int i,j,k ,n, m,cou nt=O;int weightMaxVerticesMaxVertices,pathMaxVerticesMaxVertices;int valueMaxVertices;j=i;k=i;Floyd(G.Edge ,n, weight,path);m=pathjk;printf(“ 最短路徑為：%dn&qu

31、ot;,weightjk);if(m=-1)printf("從 s 點到 s 景點的最短路徑為：n",sceneryname,scenerynamel);prin tf("%s>%sn",sce neryn ame,sce neryn ame1);elsewhile(m!=-1)valuecou nt=m;if(j<k) k=m;else j=m;m=pathjk;cou nt+;printf("從 %s 點到 %s 景點的最短路徑為：n",sceneryname,sceneryname1);pri ntf("%

32、s>",sce neryn ame);if(jvk)for(i=cou nt-1;i>=O;i-)prin tf("%sn",sce neryn ame1);elsefor(i=0;i<cou nt;i+)prin tf("%sn",sce neryn ame1);/詳細Operation.h頭文件void men u();/查詢景點信息的函數(shù)void In formati on 1()char sce neryn ame20;printf(“請輸入您所想要查詢的景點的名稱：“)；sca nf("%s",s

33、ce neryn ame);In formati on(G ,sce neryn ame);men u();/查詢最短路徑的函數(shù)void Path1()char sce neryn ame20,sce neryn ame120;printf("請輸入你要查詢的兩景點的名稱：“)；sca nf("%s%s",sce neryn ame,sce neryn ame1);Path(G,sce neryn ame,sce neryn ame1);men u();pri ntf("n");/修改景點信息的函數(shù)void Modify()char sce n

34、eryn ame20;int i,x;printf(“您想修改的景點的名稱為：");sca nf("%s",sce neryn ame);In formati on( G,sce neryn ame);printf("您想修改什么信息？ 1,名稱；2,代號；3,信息簡介：");sca nf("%d", &x);if(x=1)pri ntf("請輸入要修改的的景點的新名稱：“)；break;if(x=2)pri ntf("請輸入要修改的的景點的新代號：“)；break;if(x=3)printf(&

35、quot;請輸入要修改的的景點的新信息簡介：“)；break;men u();/增加景點的函數(shù)void AddVertic()int i,k;DataType ver;printf("請輸入增加節(jié)點的名稱，代號，信息簡介：n");sea nf("%s%d%s",ver .n ame，&(ver.code),ver.i ntroducti on);if(k!=i)G.Edgeki=MaxWeight;G.Edgeik=MaxWeight;else G.Edgeki=0;men u();void DeleteVertic()DataType x;char n ame20;int i,k;printf("請輸入您要刪除景點的名稱：“)；sca nf("%s", name);k=i;ListDelete(&(G.vertices),k, &x);if(k!=i)G.Edgeki=MaxWeight;G.Edgeik=MaxWeight;else G.Edgeki=0;men