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

2、、刪道路；修改已有信息等。（2）校園導游圖的仿真界面。2，設計： 2.1 設計思想：，數據結構設計： （1）圖。采用鄰接矩陣存儲，其中圖所用到的結構體為：typedef struct SeqList vertices; /表示圖中的頂點int EdgeMaxVerticesMaxVertices; /表示圖中的邊int numOfEdge; /表示圖中邊的數目AdjMGraph;（2）景點。用順序表存儲。所用到的結構體為： typedef struct char name20; /頂點名稱 int code; /頂點代號 char introduction50; /頂點信息簡介DataType

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

4、數，用來創建圖，然后調用menu()函數來選擇用戶所要進行的操作。其中menu()函數就是一個菜單供使用者來選擇他所要進行的相關操作，比如信息的查詢，最短路徑查詢之類。main() menu()Creat() 對于要求1：以圖中頂點表示校園內各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等有關信息。圖的創建設計流程圖為：Creat() main()Creat()函數原型為：void Creat(AdjMGraph *G, DataType v, RowColWeight E, int n,int e)其中，G為所創建的圖結構體對象，v 為所有頂點的集合，它是DataType

5、型，這個類型前面已經介紹過；E 存放著各頂點之間的連接關系，它是RowColWeight型，前面也介紹過；n表示頂點的個數；e表示邊數。Creat()函數的功能就是實現圖的創建，將已知的景點的一些信息，轉換成圖的信息，并進行存儲。menu()對于要求2：為來訪客人提供圖中任意景點相關信息的查詢。流程圖為：Information()Information1()menu()函數的原型為： void menu() 他就是一個菜單，供用戶選擇他們所要進行的操作。 Information1()函數原型為： void Information1() 它的功能就是輸入查詢景點的信息，并調用Informatio

6、n() Information()函數原型為： void Information(AdjMGraph G, char scenery) G 依然是所創建的圖的結構體對象，后面所有的G 都是表示這個意思；scenery 是在Information1() 中輸入的景點的名稱。此函數的功能就是根據輸入的景點的名稱來查詢其相關的信息。 對于要求3：為來訪客人提供任意景點的問路查詢，即查詢任意兩個景點之間的一條最短路徑。流程圖為：Floyd()Path()Path1()menu()Path1()函數原型為： void Path1() 它的功能就是輸入查詢景點的名稱，并調用Path() Path ()函數

7、原型為： void Path(AdjMGraph G,char sceneryname, char sceneryname1)其中sceneryname, sceneryname1 就是在Path1()函數中所輸入的景點的名稱，這個函數的功能就是通過這兩個景點的名稱找到它們在線性表中的位置，然后調用Floyd()函數，查找出它們的最短路徑，并輸出所要的信息。 Floyd()函數原型為： void Floyd (int cost MaxVertices,int n,int weightMaxVertices,int pathMaxVertices)其中參數cost MaxVertices即是圖中

8、邊的鄰接存儲矩陣，weightMaxVertices用來存放經此算法后的各頂點間的最短路徑的值，pathMaxVertices就是每兩個頂點之間最短路徑中到達目的頂點的前一個頂點的位置。Path()函數中的輸出信息就是據此而來。 對于要求4：修改景點信息。流程圖為：Modify()menu() Modify()函數原型為： void Modify() 它不帶任何參數，功能是通過手動輸入景點名稱，然后找到景點的存儲空間，然后在修改相應的信息。對于選做要求：增加景點。其工作流程圖為：ListInsert()AddVertic()menu() AddVertic()函數原型為：void AddVer

9、tic() 他不帶任何參數，該函數的功能是在這個函數里面輸入景點的信息，然后調用ListInsert()函數，將所要增加的頂點信息插入到線性表中。 ListInsert()函數原型為：void ListInsert(SeqList *L, int i, DataType x) 參數L表示頂點存儲的線性表，i表示要插入的位置,x表示要插入的景點的信息。同時我在插入頂點時也將他與其他頂點之間的距離設置為MaxWeight，這樣做主要是為了方便在Floyd函數里面求最短路徑對于選做要求：刪除景點。其工作流程圖為ListDelete ()DeleteVertic()menu() DeleteVerti

10、c()函數原型為：void DeleteVertic() 他不帶任何參數，該函數的功能就是在函數體里面輸入要刪除的景點的名稱，然后根據名稱找到該景點在線性表中的存儲位置，然后調用線性表中的ListDelete ()函數進行相應頂點的刪除。 ListDelete ()函數原型為：ListDelete(SeqList *L, int i, DataType *x) 其中參數L為存放頂點信息的線性表，i表示要刪除頂點在線性表中的存放位置，,x就是要刪除的那一個景點。它的功能就是從線性表中刪除指定的頂點。 對于選做要求：增、刪道路，流程圖為：InsertEdge ()AddRoad()menu()De

11、leteEdge ()DeleteRoad()AddRoad()和DeleteRoad()兩函數原型為：void AddRoad()和void DeleteRoad()。這兩個函數都不帶參數，它們的功能就是在這兩個函數里面輸入要刪除要增加或者的邊連接的兩個景點的名稱，然后在線性表中找到這兩個景點的相對存儲空間，最后調用InsertEdge ()或者DeleteEdge ()函數。 InsertEdge ()和DeleteEdge ()兩函數原型為：void InsertEdge(AdjMGraph *G, int v1, int v2, int weight)void DeleteEdge(A

12、djMGraph *G, int v1, int v2) 這兩個函數中同名參數所代表的意義是相同的，其中v1, v2是所輸入景點在線性表中的相對位置；weight就是增加的邊的權值函數接口說明 我所設計整個程序就是一些子函數的集合，每個功能都對應一個或者幾個子函數，他們之間可以沒有任何限制，只要能保證程序正確運行就可以調用，特別是AdjMGraph.h , AdjMGraph.h和SeqList.h頭文件之中的函數，他們被很多函數調用過。這其中都沒有任何特殊類型的函數 2.3 詳細設計：根據題目分析，對于信息查詢與修改功能，設計如下：1，輸入景點名稱2，從線性表頭掃描到表尾，if(找到該景點)

13、 輸出景點結構體信息else 輸出提示信息找不到該頂點實現查找最短路徑，設計如下：1， 景點名稱2，根據輸入的信息找到它們所在的線性表中的位置3，調用Floyd算法找出最短路徑4，輸出信息實現增刪景點功能，設計如下： 1，增加或者刪除景點的名稱2，if(輸入景點)，將景點信息保存在相應的結構體中，并插入到線性表尾； if(刪除景點)，找到景點在線性表中所在的位置，然后將景點信息從線性表中刪除實現增刪道路功能，設計如下： 1，入增加或刪除道路連接的兩個景點的名稱；2，找到它們的相對位置； 3，if(刪除道路)，將連接它們的邊置為MaxWeight； if(增加道路)，將輸入的邊值賦給相應的鄰接矩

14、陣表； 3，調試分析： ，調試過程中遇到的問題與解決方案： 1, 關于最短路徑的輸出問題。在進行最短路徑輸出時，我剛開始時只能正序輸出，具體的描述為：比如，我要查尋從東區到東湖的最短路徑，那么它能正確輸出結果，他的形式為：東區 主樓 西體育館 隧道 北大門 東湖。但是，當我逆向輸出時，得到的結果卻有點問題，經過分析調試后，找到了錯誤的所在。在找最短路徑的時候我用的是Floyd算法，在這個算法中有三重循環，形式均為：for(k=0;k食堂 東湖。經過分析調試后，其原因也是出在Floyd算法那，在Floyd算法中，有這么一個判斷if(weightijweightik+weightkj)，由于我在輸

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

16、供了八個選項操作對于每一個操作的分析如下： 1，相關信息的查詢。在這個操作中允許使用者輸入一個景點名稱，然后再根據景點名稱來或取其相關的信息，這個操作要掃描線性表，其時間復雜度為o(n)，空間復雜度為o(n)；2，最短路徑查詢。實現這個功能用到了Floyd算法，他用到了一個三重的for()循環，故其時間復雜度為o(n3)，空間復雜度為o(1)；3，修改景點信息。要修改信息，必須首先找到景點所在的存儲位置，那么就需要掃描線性表，其時間復雜度為o(n)，空間復雜度為o(1)；4，增加景點。增加景點信息時，直接將此景點結構體信息插入到線性表表尾，而不需要進行遍歷，其時間復雜度與空間復雜度均為o(1)

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

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

19、您提供操作選擇。 如果您想進行“相關信息的查詢”操作，輸入數字1，然后程序將會提醒您輸入查詢景點的名稱，在您輸入景點名稱后回車即可。 如果您想進行“最短路徑查詢”操作，首先輸入數字2，然后程序將會提醒您輸入查詢的景點的名稱，您輸入按要求輸入所提供的兩個景點名稱即可，要注意的是景點名稱間以空格隔開，最后程序就會告訴您最短的路徑，以及最短路的長度。 如果您想修改景點的信息，同樣先輸入數字3，然后程序就會提醒您輸入所要修改景點的名稱，您可以根據要求輸入一個景點的名稱，然后回車，之后屏幕上就會顯示您所輸入的景點的所有信息，同時會有三個修改選項供用戶選擇，然后您可以輸入13之間的一個數字進行選擇性的修改

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

21、統將會提示您輸入增加道路所連接的兩個景點的名稱，輸入兩景點名稱后回車，然后系統又會提示輸入增加道路的長度，輸入后回車，這時增加道路操作也就完了。用戶如果想要檢查道路是否增加成功可以進行“最短路徑查詢”操作。如果您想進行“刪除道路”操作，您可以輸入數字7，然后系統就會提示您輸入刪除道路所連接的兩景點的名稱，輸入名稱后回車即可，當然，如果您想檢測刪除是否成功您可以選擇“最短路徑查詢”操作。備注：經過測試，本程序的所有操作都能正常執行，您可以選擇性的對他進行操作，同時也可以混合著操作，混合操作是檢測錯誤的最好的一個方法。5，測試數據及測試結果： 菜單顯示為： *菜單* 1,相關信息查詢 2,最短路徑

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

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

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

25、 /程序源文件AdjMGraph.h /圖的相關操作頭文件AdjMGraphCreat.h /創建圖的頭文件SeqList.h /線性表操作頭文件Floyd.h /Floyd算法頭文件Operation.h /自己所定義的一些操作的頭文件Inquiry.h /查詢信息包含的頭文件/ 詳細school.cpp 程序源文件#include #include #include #define MaxSize 20 /線性表的最大數組空間#define MaxVertices 20 /景點個數所允許的最大值#define MaxWeight 1000 /無窮邊權值#include Floyd.h #i

26、nclude AdjMGraphCreat.h#include Inquiry.hAdjMGraph G;#include Operation.hvoid main() /初始景點信息 DataType a=東區,10,研究生院,博物館,11,有各種化石,主樓,12,學校的標志建筑 ,圖書館,13,藏書50萬冊,西體育館,14,主要供西區學生使用,隧道,15,自主修建,北綜,16,北區標志樓,北體育館,17,主要供北區學生使用,北大門,18,外出通道,東湖,19,武漢最美的湖; /鄰接矩陣的表示RowColWeightrcw=0,1,20,0,2,30,0,3,35,1,0,20,1,3,20

27、,2,0,30,2,3,15,2,4,30,3,0,35,3,1,20,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; /景點數與邊數 Creat(&G,a,rcw,n,e); /構造圖 menu();/ 詳細Floyd.h頭文件void Floyd(int costMaxVertices,int n,int weightMaxVertices,int pathMaxVe

28、rtices)/初始化int i,j,k;for(i=0;in;i+)for(j=0;jn;j+)weightij=costij;pathij=-1;/n次遞推for(k=0;kn;k+)for(i=0;in;i+)for(j=0;jweightik+weightkj)weightij=weightik+weightkj;pathij=k;/詳細Inquiry.h 頭文件void Information(AdjMGraph G, char scenery)int i;for(i=0;iG.vertices.size;i+)if(strcmp(G.,scen

29、ery)=0)printf(您輸入的景點的名稱是： %sn,G.);printf(您輸入的景點的代碼為： %dn,G.vertices.listi.code);printf(您輸入的景點的相關信息有： %snn,G.roduction);break;if(i=G.vertices.size)printf(您所查詢的景點不在我們所提供的范圍內！nn);void Path(AdjMGraph G,char sceneryname, char sceneryname1)int i,j,k,n,m,count=0;n=G.ver

30、tices.size;int weightMaxVerticesMaxVertices,pathMaxVerticesMaxVertices;int valueMaxVertices;for(i=0;i%sn,sceneryname,sceneryname1); else while(m!=-1) valuecount=m;if(j,sceneryname);if(j=0;i-) printf(%s,G.); printf(%sn,sceneryname1);else for(i=0;i,G.);

31、printf(%sn,sceneryname1);/詳細Operation.h頭文件void menu();/查詢景點信息的函數void Information1()char sceneryname20; printf(請輸入您所想要查詢的景點的名稱： ); scanf(%s,sceneryname); Information(G ,sceneryname);menu();/查詢最短路徑的函數void Path1()char sceneryname20,sceneryname120;printf(請輸入你要查詢的兩景點的名稱： );scanf(%s%s,sceneryname,sceneryn

32、ame1); Path(G,sceneryname,sceneryname1);menu();printf(n);/修改景點信息的函數void Modify()char sceneryname20;int i,x;printf(您想修改的景點的名稱為： );scanf(%s,sceneryname);Information(G,sceneryname);for(i=0;iG.vertices.size;i+)if(strcmp(G.,sceneryname)=0)printf(您想修改什么信息？ 1，名稱；2，代號；3，信息簡介: );scanf(%d,&

33、x);if(x=1)printf(請輸入要修改的的景點的新名稱： );scanf(%s,G.);break;if(x=2)printf(請輸入要修改的的景點的新代號： );scanf(%d,&(G.vertices.listi.code);break;if(x=3)printf(請輸入要修改的的景點的新信息簡介： );scanf(%s,G.roduction);break;menu();/增加景點的函數void AddVertic()int i,k;DataType ver; printf(請輸入增加節點的 名稱，代號，

34、信息簡介:n);scanf(%s%d%s,,&(ver.code),roduction);ListInsert(&(G.vertices), G.vertices.size, ver);k= G.vertices.size-1;for(i=0;iG.vertices.size;i+)if(k!=i) G.Edgeki=MaxWeight; G.Edgeik=MaxWeight;else G.Edgeki=0;menu();void DeleteVertic()DataType x;char name20;int i,k;printf(請輸入您要刪除景點的名稱： )

35、; scanf(%s,name); for(i=0;iG.vertices.size;i+)if(strcmp(G.,name)=0)k=i;ListDelete(&(G.vertices),k,&x);for(i=0;iG.vertices.size;i+)if(k!=i) G.Edgeki=MaxWeight; G.Edgeik=MaxWeight;else G.Edgeki=0;menu();/刪除景點的函數void AddRoad()char name20,name120;int length,i,j,k; printf(輸入您要增加的道路鏈接的兩個景點名稱： ); scanf(%s%s,name