校園導(dǎo)航系統(tǒng)0001

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

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

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

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

5、Type型，這個(gè)類型前面已經(jīng)介紹過；E存放著各頂點(diǎn)之間的連接關(guān)系，它是RowColWeight型,前面也介紹過；n表示頂點(diǎn)的個(gè)數(shù)；e表示邊數(shù)。Creat()函數(shù)的功能就是實(shí)現(xiàn)圖的創(chuàng)建，將已知的景點(diǎn)的一些信息，轉(zhuǎn)換成圖的信息，并進(jìn)行存儲(chǔ)。對(duì)于要求2:為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。流程圖為:menu()In formatio n1()*1 In formatio n()menu()函數(shù)的原型為:void men u()他就是一個(gè)菜單，供用戶選擇他們所要進(jìn)行的操作。Information)函數(shù)原型為：voidIn formatio n1()它的功能就是輸入查詢景點(diǎn)的信息，并調(diào)用In fo

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

7、 ()函數(shù)原型為：void Path(AdjMGraph G ,char sceneryname, char sceneryname1) 其中seeneryname, seeneryname1就是在 Path1()函數(shù)中所輸入的景點(diǎn)的名稱，這個(gè)函數(shù)的功能就是通過這兩個(gè)景點(diǎn)的名稱找到它們?cè)诰€性表中的位置，然后調(diào)用Floyd()函數(shù)，查找出它們的最短路徑，并輸出所要的信息。Floyd()函數(shù)原型為：void Floyd (in t cost MaxVertices,i nt n,i nt weightMaxVertices,i nt p athMaxVertices) 其中參數(shù)cost MaxVe

8、rtices即是圖中邊的鄰接存儲(chǔ)矩陣，weightMaxVertices用來存放經(jīng)此算法后的各頂點(diǎn)間的最短路徑的值，PathMaxVertices就是每兩個(gè)頂點(diǎn)之間最短路徑中到達(dá)目的頂點(diǎn)的前一個(gè)頂點(diǎn)的位置。P ath()函數(shù)中的輸出信息就是據(jù)此而來。對(duì)于要求4:修改景點(diǎn)信息。流程圖為:menu()* Modify()ModifyO函數(shù)原型為：void ModifyO 它不帶任何參數(shù)，功能是通過手動(dòng)輸入景點(diǎn)名稱，然后找到景點(diǎn)的 存儲(chǔ)空間，然后在修改相應(yīng)的信息。對(duì)于選做要求：增加景點(diǎn)。其工作流程圖為：menu()* AddVertic()*1 ListI nsert()AddVerticO函數(shù)原型

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

10、e ()DeleteVerticO函數(shù)原型為：void DeleteVerticO他不帶任何參數(shù)，該函數(shù)的功能就是在函數(shù)體里面輸入要?jiǎng)h除的景點(diǎn)的名稱，然后根據(jù)名稱找到該景點(diǎn)在線性表中的存儲(chǔ)位置，然后調(diào)用線性表中的ListDelete ()函數(shù)進(jìn)行相應(yīng)頂點(diǎn)的刪除。ListDelete ()函數(shù)原型為：ListDelete(SeqList *L, int i, DataType *x) 其中參數(shù) L為存放頂點(diǎn)信息的線性表，i表示要?jiǎng)h除頂點(diǎn)在線性表中的存放位置，,x就是要?jiǎng)h除的那一個(gè)景點(diǎn)。它的功能就是從線性表中刪除指定的頂點(diǎn)。對(duì)于選做要求：增、刪道路，流程圖為：AddRoadO和DeleteRoad

11、()兩函數(shù)原型為：void AddRoadO和void DeleteRoad()。這兩個(gè)函數(shù)都不帶參數(shù)，它們的功能就是在這兩 個(gè)函數(shù)里面輸入要?jiǎng)h除要增加或者的邊連接的兩個(gè)景點(diǎn)的名稱，然后在線性表中找到這兩個(gè)景點(diǎn)的相對(duì)存儲(chǔ)空間，最后調(diào)用InsertEdge ()或者DeleteEdge ()函數(shù)。InsertEdge ()和 DeleteEdge ()兩函數(shù)原型為：void InsertEdge(AdjMGraph *G , int v1, int v2, int weight)void DeleteEdge(AdjMGraph *G, int v1, int v2) 這兩個(gè)函數(shù)中同名參數(shù)所代表

12、的意義 是相同的，其中v1, v2是所輸入景點(diǎn)在線性表中的相對(duì)位置；weight就是增加的邊的權(quán)值<2>函數(shù)接口說明我所設(shè)計(jì)整個(gè)程序就是一些子函數(shù)的集合，每個(gè)功能都對(duì)應(yīng)一個(gè)或者幾個(gè)子函數(shù)，他們之間可以沒有任何限制，只要能保證程序正確運(yùn)行就可以調(diào)用，特別是AdjMGra ph.h,AdjMGraph.h和SeqList.h頭文件之中的函數(shù)，他們被很多函數(shù)調(diào)用過。這其中都沒有任何 特殊類型的函數(shù)2.3詳細(xì)設(shè)計(jì):根據(jù)題目分析，對(duì)于信息查詢與修改功能，設(shè)計(jì)如下：1, 輸入景點(diǎn)名稱2, 從線性表頭掃描到表尾，if(找到該景點(diǎn))輸出景點(diǎn)結(jié)構(gòu)體信息 else輸出提示信息找不到該頂點(diǎn)實(shí)現(xiàn)查找最短路

13、徑，設(shè)計(jì)如下：景點(diǎn)名稱根據(jù)輸入的信息找到它們所在的線性表中的位置 調(diào)用Floyd算法找出最短路徑輸出信息1，2，3，4，實(shí)現(xiàn)增刪景點(diǎn)功能，設(shè)計(jì)如下：1, 增加或者刪除景點(diǎn)的名稱2, if(輸入景點(diǎn))，將景點(diǎn)信息保存在相應(yīng)的結(jié)構(gòu)體中，并插入到線性表尾；if(刪除景點(diǎn))，找到景點(diǎn)在線性表中所在的位置，然后將景點(diǎn)信息從線性表中刪除實(shí)現(xiàn)增刪道路功能，設(shè)計(jì)如下：1,入增加或刪除道路連接的兩個(gè)景點(diǎn)的名稱；2, 找到它們的相對(duì)位置；3, if(刪除道路)，將連接它們的邊置為 Maxweight ;if(增加道路)，將輸入的邊值賦給相應(yīng)的鄰接矩陣表;3, 調(diào)試分析:1，調(diào)試過程中遇到的問題與解決方案：1, 關(guān)

14、于最短路徑的輸出問題。在進(jìn)行最短路徑輸出時(shí)，我剛開始時(shí)只能正序輸出， 具體的描述為：比如，我要查尋從東區(qū)到東湖的最短路徑，那么它能正確輸出結(jié)果，他的形式為：東區(qū)一一 主樓 一一 西體育館 一一 隧道 一一 北大門 一一 東湖。但是，當(dāng)我逆 向輸出時(shí)，得到的結(jié)果卻有點(diǎn)問題，經(jīng)過分析調(diào)試后，找到了錯(cuò)誤的所在。在找最短路徑的時(shí)候我用的是Floyd算法，在這個(gè)算法中有三重循環(huán)，形式均為：for(k=0;kn;k+)，它們都是從零開始的，所以在順序輸出時(shí)沒問題，但是逆序的時(shí)候就需要進(jìn)行一個(gè)判斷，正序與逆序循環(huán)輸出是相反的。輸出的最短路Floyd算法那,，由于2,關(guān)于新增加景點(diǎn)后再找最短路徑問題。比如我再

15、新增一個(gè)景點(diǎn)，如北區(qū)食堂，并 輸入相關(guān)信息，然后插入到線性表尾，當(dāng)我再找從東區(qū)到東湖的最短距離時(shí)，徑將變?yōu)椋簴|區(qū)一一 食堂 一一 東湖。經(jīng)過分析調(diào)試后，其原因也是出在在 Floyd 算法中，有這么一個(gè)判斷if(weightijweightik+weightkj)我在輸入新景點(diǎn)信息時(shí)并沒有建立它與其它景點(diǎn)之間的連接信息，所以在圖中，該新景點(diǎn)與其它景點(diǎn)之間的邊得連接信息是空的，也就是說在鄰接矩陣中，它的邊得信息是空的， 那么在進(jìn)行 if(weightijweightik+weightkj)判斷時(shí) weight新增景點(diǎn)序號(hào)其它景點(diǎn)序號(hào)的值將是一個(gè)很大的負(fù)數(shù)，所以最短路徑將會(huì)出錯(cuò)。解決這個(gè)問題的方 法

16、就是在增加新景點(diǎn)時(shí)就將它與其它景點(diǎn)之間的邊(距離)設(shè)置為MaxWeight，這時(shí)如果再用Floyd函數(shù)進(jìn)行最短路徑的求解時(shí)就不會(huì)再出現(xiàn)問題了。不過都比較容易解決，這里我就另外，在做這個(gè)題時(shí)也還出現(xiàn)過一些其他的小問題， 不再列出了2,算法的時(shí)空復(fù)雜度分析對(duì)應(yīng)題目的要求，我總共提供了八個(gè)選項(xiàng)操作對(duì)于每一個(gè)操作的分析如下：1，相關(guān)信息的查詢。在這個(gè)操作中允許使用者輸入一個(gè)景點(diǎn)名稱，然后再根據(jù)景點(diǎn)名稱來或取其相關(guān)的信息，這個(gè)操作要掃描線性表，其時(shí)間復(fù)雜度為o(n)，空間復(fù)雜度為o(n);2, 最短路徑查詢。實(shí)現(xiàn)這個(gè)功能用到了Floyd算法，他用到了一個(gè)三重的for()循環(huán)，故其時(shí)間復(fù)雜度為 o(n人3

17、)，空間復(fù)雜度為o(1);3, 修改景點(diǎn)信息。要修改信息，必須首先找到景點(diǎn)所在的存儲(chǔ)位置，那么就需要掃描線性表，其時(shí)間復(fù)雜度為o(n)，空間復(fù)雜度為o(1);4, 增加景點(diǎn)。增加景點(diǎn)信息時(shí)，直接將此景點(diǎn)結(jié)構(gòu)體信息插入到線性表表尾，而不需要進(jìn)行遍歷，其時(shí)間復(fù)雜度與空間復(fù)雜度均為o(1);5, 刪除景點(diǎn)。刪除景點(diǎn)時(shí)必須找到所要?jiǎng)h除景點(diǎn)所在的位置，這樣就必須遍歷線性表，除此之外，刪除后線性表還要進(jìn)行移動(dòng)操作，其時(shí)間復(fù)雜度為o(n),空間復(fù)雜度為 0( n1);6, 增加道路。增加道路也要掃描線性表，找到要增加路的兩景點(diǎn)的存儲(chǔ)位置，然后再根據(jù)找到的存儲(chǔ)位置去改變鄰接矩陣的邊的值，改變鄰接矩陣的時(shí)間復(fù)雜

18、度為0(1),其總時(shí)間消耗在線性表的掃描上，故最終其時(shí)間復(fù)雜度為o( n)，空間復(fù)雜度為o(1);7, 刪除道路。刪除道路和增加道路類似，都是先找到存儲(chǔ)位置，然后再改變鄰接矩陣， 它的時(shí)空復(fù)雜度分別為 o(n) , o(1);8，瀏覽所有景點(diǎn)。瀏覽所有景點(diǎn)的實(shí)質(zhì)就是從頭到尾遍歷線性表，然后輸出遍歷到的 節(jié)點(diǎn)的信息，其時(shí)間復(fù)雜度為0(n),空間復(fù)雜度為0(1)。4, 用戶手冊(cè)：使用說明：當(dāng)用戶將程序經(jīng)過編譯，連接后，點(diǎn)擊運(yùn)行，在DOS環(huán)境里面將看到一個(gè)操作。選項(xiàng)菜單，菜單里面提供了 8種操作，同時(shí)輸出了一行提示信息：請(qǐng)選擇您想進(jìn)行的操作。 然后用戶可以輸入一個(gè) 18之間的數(shù)字進(jìn)行選擇性的操作，例

19、如，您想進(jìn)行信息的查詢 操作，您可以從鍵盤輸入數(shù)字 1'當(dāng)然，一般而言先應(yīng)該進(jìn)行 “瀏覽所有景點(diǎn)名稱”如果您選擇了瀏覽所有景點(diǎn)名稱操作，在屏幕上將會(huì)顯示出10個(gè)景點(diǎn)的名稱，這些景點(diǎn)是事先加進(jìn)去的，用戶可以對(duì)這些景點(diǎn)進(jìn)行任何程序所提供的操作。菜單將會(huì)繼續(xù)顯示出來，為下面，我將詳細(xì)介紹本程序的使用方法：在瀏覽景點(diǎn)后， 您提供操作選擇。1',然后程序?qū)?huì)提醒您輸入查2'，然后程序?qū)?huì)提醒您輸入 要注意的是景點(diǎn)名稱間如果您想進(jìn)行“相關(guān)信息的查詢”操作，輸入數(shù)字 詢景點(diǎn)的名稱，在您輸入景點(diǎn)名稱后回車即可。如果您想進(jìn)行“最短路徑查詢”操作，首先輸入數(shù)字 查詢的景點(diǎn)的名稱，您輸入按要

20、求輸入所提供的兩個(gè)景點(diǎn)名稱即可， 以空格隔開，最后程序就會(huì)告訴您最短的路徑，以及最短路的長度。如果您想修改景點(diǎn)的信息，同樣先輸入數(shù)字3然后程序就會(huì)提醒您輸入所要修改景點(diǎn)的名稱，您可以根據(jù)要求輸入一個(gè)景點(diǎn)的名稱，然后回車，之后屏幕上就會(huì)顯示您所輸入的景點(diǎn)的所有信息，同時(shí)會(huì)有三個(gè)修改選項(xiàng)供用戶選擇，然后您可以輸入13之間的一個(gè)數(shù)字進(jìn)行選擇性的修改。比如，您可以輸入1'對(duì)景點(diǎn)名稱進(jìn)行修改，修改完后又會(huì)返回到菜單項(xiàng)繼續(xù)選擇。如果您想進(jìn)行“增加景點(diǎn)”操作，可以輸入數(shù)字4',然后程序就會(huì)提示您輸入新增加的景點(diǎn)的名稱，代號(hào)，信息簡介，各種輸入之間以空格隔開。當(dāng)輸入完畢后回車，景點(diǎn)也 就成功加

21、入了，然后用戶可以再次選擇第八項(xiàng)操作瀏覽所有景點(diǎn)名稱，檢測(cè)新輸入的景點(diǎn)是否已經(jīng)成功添加。如果您想進(jìn)行“刪除景點(diǎn)”操作，可以輸入數(shù)字5'，回車后系統(tǒng)將會(huì)提示您輸入要?jiǎng)h除的景點(diǎn)的名稱，您可以輸入您想要?jiǎng)h除的景點(diǎn)的名稱，然后回車，這樣刪除景點(diǎn)的操作就已經(jīng)完成，您同樣可以選擇第八項(xiàng)操作，檢測(cè)是否成功刪除了景點(diǎn)。如果您想進(jìn)行“增加道路”操作，您可以輸入數(shù)字 6'，然后回車，系統(tǒng)將會(huì)提示您 輸入增加道路所連接的兩個(gè)景點(diǎn)的名稱， 輸入兩景點(diǎn)名稱后回車， 然后系統(tǒng)又會(huì)提示輸入增 加道路的長度，輸入后回車，這時(shí)增加道路操作也就完了。 用戶如果想要檢查道路是否增加 成功可以進(jìn)行“最短路徑查詢”操作

22、。如果您想進(jìn)行“刪除道路”操作，您可以輸入數(shù)字 7'，然后系統(tǒng)就會(huì)提示您輸入刪 除道路所連接的兩景點(diǎn)的名稱， 輸入名稱后回車即可，當(dāng)然，如果您想檢測(cè)刪除是否成功您 可以選擇“最短路徑查詢”操作。備注：經(jīng)過測(cè)試，本程序的所有操作都能正常執(zhí)行，您可以選擇性的對(duì)他進(jìn)行操作， 同時(shí)也可以混合著操作，混合操作是檢測(cè)錯(cuò)誤的最好的一個(gè)方法。-/5, 測(cè)試數(shù)據(jù)及測(cè)試結(jié)果:菜單顯示為:*單 *1, 相關(guān)信息查詢2, 最短路徑查詢3, 修改景點(diǎn)信息4, 增加景點(diǎn)5, 刪除景點(diǎn)6, 增加道路7, 刪除道路8, 瀏覽所有景點(diǎn)名稱幵*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*卄*2,8請(qǐng)選擇您想進(jìn)行的操作:4

23、請(qǐng)選擇您想進(jìn)行的操作： 東區(qū) 博物館主樓 北大門東湖8圖書館西體育館隧道 北綜北體育館請(qǐng)選擇您想進(jìn)行的操作：請(qǐng)輸入您所想要查詢的景點(diǎn)的名稱: 您輸入的景點(diǎn)的名稱是： 您輸入的景點(diǎn)的代碼為： 您輸入的景點(diǎn)的相關(guān)信息有：博物館博物館11有各種化石請(qǐng)選擇您想進(jìn)行的操作：請(qǐng)輸入你要查詢的兩景點(diǎn)的名稱：最短路徑為：108從東區(qū)點(diǎn)到東湖景點(diǎn)的最短路徑為：東區(qū)一一 主樓一一 西體育館一一 隧道一一 北大門一一 東湖東區(qū)東湖請(qǐng)選擇您想進(jìn)行的操作： 您想修改的景點(diǎn)的名稱為： 您輸入的景點(diǎn)的名稱是： 您輸入的景點(diǎn)的代碼為： 您輸入的景點(diǎn)的相關(guān)信息有:3隧道隧道15自主修建您想修改什么信息？1,名稱;請(qǐng)輸入要修改的

24、的景點(diǎn)的新名稱： 請(qǐng)選擇您想進(jìn)行的操作： 東區(qū) 博物館主樓 體育館 北大門東湖代號(hào)；3，信息簡介：1 地大隧道圖書館西體育館地大隧道北綜 北-/請(qǐng)輸入增加節(jié)點(diǎn)的名稱，代號(hào)，信息簡介北一樓34教師辦公室請(qǐng)選擇您想進(jìn)行的操作：1請(qǐng)輸入您所想要查詢的景點(diǎn)的名稱： 您輸入的景點(diǎn)的名稱是：北一樓您輸入的景點(diǎn)的代碼為：34您輸入的景點(diǎn)的相關(guān)信息有：教師辦公室北一樓請(qǐng)選擇您想進(jìn)行的操作：5請(qǐng)輸入您要?jiǎng)h除景點(diǎn)的名稱：北一樓請(qǐng)選擇您想進(jìn)行的操作： 東區(qū) 博物館主樓 體育館北大門東湖8圖書館西體育館地大隧道北綜 北請(qǐng)選擇您想進(jìn)行的操作：輸入您要增加的道路鏈接的兩個(gè)景點(diǎn)名稱: 輸入您要增加的道路的長度：50 請(qǐng)選擇

25、您想進(jìn)行的操作：2請(qǐng)輸入你要查詢的兩景點(diǎn)的名稱： 最短路徑為：50從東區(qū)點(diǎn)到北綜景點(diǎn)的最短路徑為: 東區(qū) > 北綜東區(qū)東區(qū)北綜請(qǐng)選擇您想進(jìn)行的操作：7輸入您要?jiǎng)h除的道路鏈接的兩個(gè)景點(diǎn)名稱： 請(qǐng)選擇您想進(jìn)行的操作：2請(qǐng)輸入你要查詢的兩景點(diǎn)的名稱： 最短路徑為：103 從東區(qū)點(diǎn)到北綜景點(diǎn)的最短路徑為： 東區(qū) > 主樓 > 西體育館 > 地大隧道東區(qū)東區(qū)北綜北綜北綜>北大門一一 >北綜6,源程序清單:school.c PPAdjMGra ph.hAdjMGra phCreat.hSeqList.hFloyd.hOp erati on.hIn quiry.h/程序源

26、文件/圖的相關(guān)操作頭文件/創(chuàng)建圖的頭文件線性表操作頭文件/Floyd算法頭文件/自己所定義的一些操作的頭文件/查詢信息包含的頭文件II 詳細(xì) school.cpp程序源文件#i nclude <stdio.h>#in elude <stri ng.h>#in elude <malloc.h>#defi ne MaxSize 20#defi ne MaxVertices 20#defi ne MaxWeight 1000/線性表的最大數(shù)組空間/景點(diǎn)個(gè)數(shù)所允許的最大值/無窮邊權(quán)值#i nclude "Floyd.h"#i nclude &qu

27、ot;AdjMGra phCreat.h"#in clude "I nqu iry.h"AdjMGra ph G;#in elude "Op eratio n.h" void mai n()/初始景點(diǎn)信息DataType a="東區(qū)",10,"研究生院”博物館",11,"有各種化石”主樓",12,"學(xué) 校的標(biāo)志建筑" ,"圖書館",13,"藏書50萬冊(cè)","西體育館",14,"主要供西區(qū)學(xué) 生使用

28、","隧道",15,"自主修建","北綜",16,"北區(qū)標(biāo)志樓","北體育館",17," 主要供北區(qū)學(xué)生使用","北大門",18,"外出通道","東湖",19,"武漢最美的湖"/鄰接矩陣的表示RowColWeightrcw=0,1,20,0,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,20,3,2,15,3,4,3

29、0,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;/景點(diǎn)數(shù)與邊數(shù)Creat(&G,a,rcw, n,e);構(gòu)造圖menu();/詳細(xì)Floyd.h頭文件void Floyd(i nt costMaxVertices,i nt n,i nt weightMaxVertices,i nt p athMaxVertices) /初始化int i,j,k;for(i=0;i< n; i+)f

30、or(j=0;j< n;j+)weightij=costij; p athij=-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;頭文件/詳細(xì)void In formati on( AdjMGra ph G , char sce nery)In quiry.hint i;for(i=0;i<G .vertices.size;i+)if(strcmp(G .v

31、,scenery)=0) printf(”您輸入的景點(diǎn)的名稱是： printf(”您輸入的景點(diǎn)的代碼為： printf(”您輸入的景點(diǎn)的相關(guān)信息有： break;%sn"Gvertices.listi. name);%dn",G.vertices.listi.code);%snn",G.vertices.listi.i ntroductio n);-/if(i=G.vertices.size)nrr);printf("您所查詢的景點(diǎn)不在我們所提供的范圍內(nèi)!void P ath(AdjMGra ph G,char sce

32、neryn ame, char sceneryn ame1) int i,j,k ,n, m,co un t=0;n=G.vertices.size;int weightMaxVerticesMaxVertices, pathMaxVerticesMaxVertices;int valueMaxVertices;for(i=0;i<G .vertices.size;i+)if(strcmp(G .,sceneryname)=0)j=i;if(strcmp(G .,sceneryname1)=0)k=i;Floyd

33、(G.Edge ,n, weight, path);m=p athjk;printf(” 最短路徑為：%dn”,weightjk);if(m=-1)printf(” 從 %s 點(diǎn)到 %s 景點(diǎn)的最短路徑為：n”,seeneryname,sceneryname1);prin tf("%s>%sn ”,see neryn ame,sce neryn ame1);else while(m!=-1)valueco un t=m; if(j<k) k=m; else j=m;m=p athjk; coun t+;printf(” 從 %s 點(diǎn)到 %s 景點(diǎn)的最短路徑為：n”,see

34、neryname,sceneryname1);prin tf("%s>",sce neryn ame);if(j<k)for(i=co un t-1;i>=0;i-)prin tf("%s>",G.vertices.listvaluei. name); prin tf("%sn",sce neryn ame1);elsefor(i=0;i<co un t;i+)prin tf("%s>",G .vertices.listvaluei. name);prin tf("%s

35、n",sce neryn ame1);/詳細(xì)Operation.h頭文件 void menu();/查詢景點(diǎn)信息的函數(shù)void In formati on 1()char sceneryn ame20;”);”);printf(”請(qǐng)輸入您所想要查詢的景點(diǎn)的名稱: sca nf("%s",sce neryn ame);In formati on(G ,sce neryn ame);menu();/查詢最短路徑的函數(shù)void P ath1()char sceneryn ame20,sce neryn ame120;printf(”請(qǐng)輸入你要查詢的兩景點(diǎn)的名稱：sca

36、nf("%s%s",sce neryn ame,sce neryn ame1);P ath(G,sce neryn ame,sce neryn ame1);menu();prin tf("n");-/修改景點(diǎn)信息的函數(shù)void ModifyOchar sceneryn ame20;int i,x;printf(”您想修改的景點(diǎn)的名稱為：sca nf("%s",sce neryn ame);Information(G ,sceneryname);for(i=0;i<G .vertices.size;i+)if(strcmp(G .

37、,sceneryname)=0) printf(”您想修改什么信息？1,名稱；2，scan f("%d"，& x);if(x=1)printf("請(qǐng)輸入要修改的的景點(diǎn)的新名稱：sca nf("%s",G.vertices.listi. name); break;if(x=2)printf("請(qǐng)輸入要修改的的景點(diǎn)的新代號(hào)： scanf("%d",&(G .vertices.listi.code);break;if(x=3)printf("請(qǐng)輸入要修改的的

38、景點(diǎn)的新信息簡介: sca nf("%s",G.vertices.listi.i ntroduct ion);break;menu();”);代號(hào)；3,信息簡介：");”);");");/增加景點(diǎn)的函數(shù)void AddVertic()int i,k;DataT ype ver;printf(”請(qǐng)輸入增加節(jié)點(diǎn)的名稱，代號(hào)，信息簡介:n");sca nf("%s%d%s",ver. name,&( ver.code),ver.i ntroduct ion);ListInsert(&(G .vertice

39、s), G.vertices.size, ver); k= G.vertices.size-1;for(i=0;i<G .vertices.size;i+)if(k!=i)G.Edgeki=MaxWeight;G.Edgeik=MaxWeight;else G.Edgeki=0;menu();void DeleteVertic()DataT ype x;char n ame20;int i,k;”);printf(”請(qǐng)輸入您要?jiǎng)h除景點(diǎn)的名稱：sca nf("%s", name);for(i=0;i<G.vertices.size;i+)if(strcmp(G .

40、,name)=0) k=i;ListDelete(&(G .vertices),k，&x);for(i=0;i<G .vertices.size;i+)if(k!=i)G.Edgeki=MaxWeight;G.Edgeik=MaxWeight;else G.Edgeki=0;menu();刪除景點(diǎn)的函數(shù)void AddRoad()char name20, name120;int len gth,i,j,k;printf("輸入您要增加的道路鏈接的兩個(gè)景點(diǎn)名稱:sca nf("%s%s", name ,n