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

1、<p>　　2013年12月9日</p><p>　項(xiàng)目名稱： 校園導(dǎo)游程序 </p><p>　學(xué)生姓名： </p><p>　學(xué)號(hào)： </p><p>　班級(jí)：

2、 </p><p>　指導(dǎo)教師： </p><p><b>　　目錄</b></p><p>　　1.課程設(shè)計(jì)的目的與意義1</p><p>　　1.1課程設(shè)計(jì)的目的1</p><p>　　1

3、.2課程設(shè)計(jì)的意義1</p><p>　　2.系統(tǒng)功能描述及設(shè)計(jì)1</p><p>　　3.系統(tǒng)存儲(chǔ)結(jié)構(gòu)及描述3</p><p>　　4.系統(tǒng)功能實(shí)現(xiàn)及算法描述5</p><p>　　4.1校園景點(diǎn)信息的錄入5</p><p>　　4.2查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑6</p><p&

4、gt;　　4.3查詢圖中任意一個(gè)景點(diǎn)到其他景點(diǎn)的所有路徑7</p><p>　　4.4查詢?nèi)我鈨删包c(diǎn)間的所有路徑8</p><p>　　5. 系統(tǒng)性能測(cè)試9</p><p><b>　　5.1 主界面9</b></p><p>　　5.2瀏覽校園全景9</p><p>　　5.3查詢圖中

5、任意兩個(gè)景點(diǎn)間的最短路徑10</p><p>　　5.4查詢圖中任意一點(diǎn)到其他景點(diǎn)間的所有路徑10</p><p>　　5.5查詢?nèi)我鈨蓚€(gè)景點(diǎn)間的所有路徑11</p><p><b>　　6.設(shè)計(jì)小結(jié)11</b></p><p><b>　　參考文獻(xiàn)11</b></p>&l

6、t;p><b>　　源代碼清單12</b></p><p>　　1.課程設(shè)計(jì)的目的與意義</p><p>　　1.1課程設(shè)計(jì)的目的</p><p>　　隨著社會(huì)的發(fā)展，人們對(duì)生活的也要求越來越高，從以前的一切都用手用筆的時(shí)代到了一切都可以用機(jī)器代替的時(shí)代?，F(xiàn)在的大學(xué)校園越來越大了，對(duì)于對(duì)新學(xué)校不熟悉和對(duì)于外來著更好的參觀和游覽學(xué)校，特做

7、了這個(gè)校園導(dǎo)游圖，它能輸出所有校園景點(diǎn)的簡介供用戶參考，并且能找到兩個(gè)景點(diǎn)間最短路徑，讓用戶少走彎路和冤枉路，而且還可以找到一個(gè)景點(diǎn)到其他景點(diǎn)的最短路徑，可以提供使用者最好的游覽路徑。更多的功能將會(huì)在后續(xù)繼續(xù)加入。</p><p>　　1.2課程設(shè)計(jì)的意義</p><p>　　鞏固和加深學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)的理解和掌握,掌握C語言編程和程序調(diào)試的基本技能。利用數(shù)據(jù)結(jié)構(gòu)進(jìn)行基本的軟件設(shè)計(jì)

8、,掌握書寫程序設(shè)計(jì)說明文檔的能力，提高運(yùn)用數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問題的能力。</p><p>　　培養(yǎng)我們綜合運(yùn)用所學(xué)知識(shí)的能力和鍛煉實(shí)踐的能力,能夠做到善于發(fā)現(xiàn),提出,分析和解決實(shí)際問題。同時(shí)，進(jìn)一步加深、鞏固我們所學(xué)專業(yè)課程（《數(shù)據(jù)結(jié)構(gòu)實(shí)用教程》）的基本理論知識(shí),如語句嵌套和循環(huán)，分支等結(jié)運(yùn)用，理論聯(lián)系實(shí)際，進(jìn)一步培養(yǎng)學(xué)生綜合分析問題和解決問題的能力。掌握運(yùn)用C語言獨(dú)立地編寫、調(diào)試應(yīng)用程序和進(jìn)行其它相關(guān)設(shè)計(jì)的技能，

9、擴(kuò)展自己的知識(shí)面，充分發(fā)揮廣大同學(xué)的潛力，提高程序開發(fā)能力，使我們通過這次課程設(shè)計(jì)而得到全面的鍛煉。</p><p>　　2.系統(tǒng)功能描述及設(shè)計(jì)</p><p>　　整個(gè)系統(tǒng)主要包含三個(gè)大的模塊（功能模塊圖見下圖2-1）</p><p>　　菜單1：瀏覽校園全景，該功能的實(shí)現(xiàn)是通過編程著將所有信息事先錄入系統(tǒng)中，當(dāng)用戶選擇時(shí)，會(huì)輸出學(xué)校所有的景點(diǎn)，編號(hào)及簡介。菜單2

10、：查詢?nèi)我鈨删包c(diǎn)間的所有路徑。這個(gè)是根據(jù)弗洛伊德算法改編而來，該算法能很方便的找出用戶所輸入的兩景點(diǎn)間的最短路徑。當(dāng)然，當(dāng)你輸入的景點(diǎn)編號(hào)不存在時(shí)，就回提示重新輸入，知道輸入的兩個(gè)點(diǎn)都符合要求才會(huì)找出最短路徑。</p><p>　　菜單3：查詢一個(gè)景點(diǎn)到其他所有景點(diǎn)的最短路徑。該系統(tǒng)能通過你所在的位置找出到其他所有景點(diǎn)的最短路徑。很方便的滿足客戶需要到達(dá)其他景點(diǎn)的路徑。</p><p>　

11、　菜單4：查詢圖中任意兩景點(diǎn)間的所有路徑。有了這個(gè)功能，用戶可以很方便的找到圖中任意連個(gè)景點(diǎn)間的所有路徑。這樣用戶就可以選擇自己中意的路徑來到達(dá)自己的目的地了。</p><p>　　菜單5：退出整個(gè)系統(tǒng)。</p><p>　　圖2-1系統(tǒng)功能描述</p><p>　　3.系統(tǒng)存儲(chǔ)結(jié)構(gòu)及描述</p><p>　　下面將給出程序代碼的部分代碼，將

12、詳細(xì)介紹系統(tǒng)的存儲(chǔ)結(jié)構(gòu)。如：</p><p>　　struct infotype</p><p><b>　　{</b></p><p>　　char name[20];</p><p><b>　　int num;</b></p><p>　　char introducti

13、on[100];</p><p>　　weighttype maxvalue;</p><p><b>　　};</b></p><p>　　struct Mgraph</p><p>　　{ infotype vexs[MAXVER]; //定義存儲(chǔ)定點(diǎn)信息的數(shù)組類型</p><p&g

14、t;　　infotype arcs[MAXVER][MAXVER]; //定義存儲(chǔ)鄰接矩陣的數(shù)組類型</p><p>　　int vexnum,arcnum;</p><p><b>　　};</b></p><p>　　該存儲(chǔ)結(jié)構(gòu)：在上面的結(jié)構(gòu)體中，包含了圖中所需的景點(diǎn)名，景點(diǎn)個(gè)數(shù)，景點(diǎn)簡介，而且存儲(chǔ)了邊數(shù)，還利用數(shù)組來存儲(chǔ)兩景點(diǎn)間是否有邊

15、，而且還包含了兩景點(diǎn)間的權(quán)值。</p><p>　　for(i=0;i<G.vexnum;i++)</p><p>　　G.vexs[i].num=i;</p><p>　　strcpy(G.vexs[0].name,"弘德樓");</p><p>　　strcpy(G.vexs[0].introduction,&q

16、uot;學(xué)生公寓，主要為考研學(xué)生準(zhǔn)備，環(huán)境良好。");</p><p>　　上面簡單的幾行代碼就存儲(chǔ)了一個(gè)景點(diǎn)的編號(hào)，名稱，簡介</p><p>　　for(i=0;i<G.vexnum;i++)</p><p>　　for(j=0;j<G.vexnum;j++)</p><p>　　G.arcs[i][j].maxva

17、lue=FARMAX;</p><p>　　G.arcs[0][1].maxvalue=70;</p><p>　　for(i=0;i<G.vexnum;i++)</p><p>　　for(j=0;j<G.vexnum;j++)</p><p>　　G.arcs[j][i].maxvalue=G.arcs[i][j].maxva

18、lue;</p><p><b>　　}</b></p><p>　　上面的代碼利用了兩個(gè)for循環(huán)很快的定義出了任意兩個(gè)景點(diǎn)的關(guān)系，如是否存在邊，存在邊權(quán)值是大?。]有邊則為事先定義的最大值，存在邊則直接輸入權(quán)值），同時(shí)也作出了無向圖應(yīng)有的特點(diǎn)，及是雙向的，并且兩邊權(quán)值相等。</p><p>　　上面整個(gè)信息的錄入存儲(chǔ)了整個(gè)系統(tǒng)需要的數(shù)據(jù)，包

19、括景點(diǎn)個(gè)數(shù)，邊數(shù)，名稱，簡介，距離。有了這個(gè)函數(shù)，方便以后所有的需要數(shù)據(jù)的地方來調(diào)用它。</p><p>　　4.系統(tǒng)功能實(shí)現(xiàn)及算法描述</p><p>　　4.1校園景點(diǎn)信息的錄入</p><p>　　該功能的實(shí)現(xiàn)是通過利用定義好的變數(shù)，定點(diǎn)數(shù)，景點(diǎn)名，景點(diǎn)編號(hào)，景點(diǎn)間權(quán)值的，一次輸入G.vexs[i].name，G.vexs[i].introduction，G.

20、arcs[i][i].maxvalue,而i，j的取值范圍是由G.vexnum和G.arcnum確定的。圖4-1：</p><p>　　圖4-1校園景點(diǎn)信息的錄入</p><p>　　4.2查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑</p><p>　　該功能是利用弗洛伊德算法如果從k到j(luò)有邊，則存在一條長度為arcs[k][j]的路徑，該路徑不一定是最短路徑?？紤]路徑（k,

21、u,j）是否存在，若存在，比較（k,j）和（k,u,j）的長度，取較短者為從k到j(luò)的中間點(diǎn)序號(hào)不大于0的最短路徑。以此類推，每次增加一個(gè)點(diǎn)，從而求出任意兩點(diǎn)間的最短路徑。這樣，經(jīng)過n次比較后，所求得的必為從k到j(luò)的最短路徑。按此方法，可以同時(shí)求得任意兩點(diǎn)間的最短路徑。流程圖如下4-2：</p><p>　　4-2查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑</p><p>　　4.3查詢圖中任意一個(gè)景

22、點(diǎn)到其他景點(diǎn)的所有路徑</p><p>　　這個(gè)功能的實(shí)現(xiàn)是通過數(shù)組存儲(chǔ)所有右邊的路徑，然后根據(jù)用戶輸入的一個(gè)景點(diǎn)的編號(hào)找到該景點(diǎn)與其他景點(diǎn)右邊的景點(diǎn)，然后以右邊的其他景點(diǎn)為起點(diǎn)，重復(fù)上述流程，直到找完每個(gè)景點(diǎn)即結(jié)束程序。如圖4-3：</p><p>　　圖4-3查詢圖中任意一個(gè)景點(diǎn)到其他景點(diǎn)的所有路徑</p><p>　　4.4查詢?nèi)我鈨删包c(diǎn)間的所有路徑</

23、p><p>　　該功能是通過用戶輸入的兩個(gè)景點(diǎn)的編號(hào)找到對(duì)應(yīng)的景點(diǎn)名，然后以第一個(gè)點(diǎn)作為起點(diǎn)向其他點(diǎn)找邊，當(dāng)邊的權(quán)值小于最大值時(shí)，說明存在邊，即可保存在數(shù)組中，直到找到終點(diǎn)對(duì)應(yīng)的編號(hào)即為一天路徑，循環(huán)上述過程，直到出現(xiàn)重復(fù)路徑即結(jié)束函數(shù)，跳出循環(huán)。如圖圖4-4：</p><p>　　圖4-4查詢?nèi)我鈨删包c(diǎn)間的所有路徑</p><p><b>　　5. 系統(tǒng)性能

24、測(cè)試</b></p><p><b>　　5.1 主界面</b></p><p>　　當(dāng)程序成功被打開時(shí)會(huì)出現(xiàn)如圖5-1所示的界面，該界面相當(dāng)于一個(gè)菜單，用戶可以根據(jù)自己的需求選擇數(shù)字?！?”瀏覽所有景點(diǎn)的信息，“2”找出任意兩景點(diǎn)間所有路徑，“3”找到一個(gè)景點(diǎn)到其他景點(diǎn)間的所有路徑，“4”退出系統(tǒng) ，下面是“請(qǐng)選擇，輸入1-5鍵：”的字樣。如圖5-1：&

25、lt;/p><p>　　圖5-1主界面測(cè)試圖</p><p><b>　　5.2瀏覽校園全景</b></p><p>　　當(dāng)用戶選擇1時(shí)，程序即會(huì)根據(jù)之前存儲(chǔ)好的信息輸出景點(diǎn)間的所有信息，供用戶瀏覽及參考。運(yùn)行效果如下5-2圖片所示。</p><p>　　圖5-2瀏覽校園全景</p><p>　　5.

26、3查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑</p><p>　　當(dāng)用戶選擇2時(shí)，則會(huì)進(jìn)入該系統(tǒng)，系統(tǒng)會(huì)提示“請(qǐng)輸入兩個(gè)景點(diǎn)的編號(hào)”，當(dāng)你輸入的景點(diǎn)不符合要求時(shí)，會(huì)提示重新輸入如10和2，當(dāng)符合要求是，系統(tǒng)則會(huì)輸入最短路徑，如我輸入了2和4，如圖5-3：</p><p>　　圖5-3查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑</p><p>　　5.4查詢圖中任意一點(diǎn)到其他景點(diǎn)間的所有

27、路徑</p><p>　　當(dāng)用戶輸入3是，則會(huì)進(jìn)入該系統(tǒng)，此時(shí)系統(tǒng)會(huì)提示輸入你要選擇的景點(diǎn)編號(hào)，當(dāng)不合要求時(shí)，同樣會(huì)提示請(qǐng)?jiān)俅屋斎?，直到符合要求為止，如我輸入?0，之后又輸入了了15，最后輸入5，才輸入路徑。如圖5-4：</p><p>　　圖5-4查詢圖中任意一點(diǎn)到其他景點(diǎn)間的所有路徑</p><p>　　5.5查詢?nèi)我鈨蓚€(gè)景點(diǎn)間的所有路徑</p>

28、<p>　　當(dāng)用戶選擇4時(shí)即可進(jìn)入該系統(tǒng)，系統(tǒng)會(huì)提示用戶輸入要查詢的兩個(gè)景點(diǎn)的編號(hào)。相同的當(dāng)有編號(hào)不存在時(shí)，系統(tǒng)會(huì)提示重新輸入正確的編號(hào)，如我輸入了一個(gè)2和10時(shí)，系統(tǒng)會(huì)提示輸入有誤，請(qǐng)重新輸入，最后我輸入了2和7，則輸出了所有路徑：如圖5-5所示。</p><p>　　圖5-5查詢?nèi)我鈨蓚€(gè)景點(diǎn)間的所有路徑</p><p><b>　　6.設(shè)計(jì)小結(jié)</b>

29、</p><p>　　通過幾周的課程設(shè)計(jì)，我學(xué)到了很多東西：</p><p>　?。?）對(duì)自己所學(xué)的數(shù)據(jù)結(jié)構(gòu)有了更熟練的運(yùn)用和更深刻的了解。</p><p>　?。?）提高了我的動(dòng)手能力，學(xué)會(huì)了自覺主動(dòng)地查找文獻(xiàn)知識(shí)，如到圖書館翻閱書籍和上網(wǎng)查閱等。</p><p>　?。?）提高了自己的辦事效率，面對(duì)挑戰(zhàn)不退縮，敢于迎韌而上，除此還學(xué)會(huì)了遇

30、事沉著冷靜，認(rèn)真思考，邏輯清晰的列出解決方案。</p><p>　?。?）提高了我對(duì)市場的了解，使自己很好的將市場與C語言程序設(shè)計(jì)相結(jié)合，使自己能學(xué)以致用，聯(lián)系實(shí)際生活。</p><p>　　（5）學(xué)會(huì)了感恩，了解到老師和父母對(duì)我們的付出都很大。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]

31、徐孝凱．?dāng)?shù)據(jù)結(jié)構(gòu)使用教程．清華大學(xué)出版社：徐培忠，2006．</p><p>　　[2] 徐孝凱．C++語言基礎(chǔ)．清華大學(xué)出版社：徐培忠，1999．</p><p>　　[3] 徐孝凱．?dāng)?shù)據(jù)結(jié)構(gòu)使用教程習(xí)題參考解答．清華大學(xué)出版社：徐培忠，2006．</p><p>　　[4] 胡成松．C語言課程設(shè)計(jì)．北京高等教育出版社：林孝平，2006．</p>&

32、lt;p>　　[5] 劉云．計(jì)算機(jī)網(wǎng)絡(luò)實(shí)用教程．北京高等教育出版社：徐培忠，2004． </p><p>　　[6] 徐孝凱．?dāng)?shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)．清華大學(xué)出版社：徐培忠，2006．</p><p><b>　　源代碼清單</b></p><p>　　#include<stdio.h></p><p>　

33、　#include <stdlib.h></p><p>　　#include<iostream.h></p><p>　　#include<strstrea.h></p><p>　　#include<string.h></p><p>　　#define FARMAX 1000</p&

34、gt;<p>　　typedef int weighttype; //定義邊上權(quán)值的類型</p><p>　　const int MAXVER=10; //定義圖的最多頂點(diǎn)數(shù)</p><p>　　typedef int adjmatrixtype[MAXVER]; //定義adjmatrix為存儲(chǔ)鄰接矩陣的數(shù)組類型</p>

35、<p>　　struct infotype</p><p><b>　　{</b></p><p>　　char name[20];</p><p><b>　　int num;</b></p><p>　　char introduction[100];</p><p

36、>　　weighttype maxvalue;</p><p><b>　　};</b></p><p>　　struct Mgraph</p><p>　　{ infotype vexs[MAXVER]; //定義存儲(chǔ)定點(diǎn)信息的數(shù)組類型</p><p>　　infotype arcs[MAXVER]

37、[MAXVER]; //定義存儲(chǔ)鄰接矩陣的數(shù)組類型</p><p>　　int vexnum,arcnum;</p><p><b>　　};</b></p><p>　　void jiben(Mgraph &G)</p><p><b>　　{</b></p><p&

38、gt;<b>　　int i,j;</b></p><p>　　G.vexnum=8;</p><p>　　G.arcnum=10;</p><p>　　for(i=0;i<G.vexnum;i++)</p><p>　　G.vexs[i].num=i;</p><p>　　strcpy(G

39、.vexs[0].name,"弘德樓");</p><p>　　strcpy(G.vexs[0].introduction,"學(xué)生公寓，主要為考研學(xué)生準(zhǔn)備，環(huán)境良好。");</p><p>　　strcpy(G.vexs[1].name,"靜思湖");</p><p>　　strcpy(G.vexs[1].

40、introduction,"學(xué)生晨讀的好地方，夏日滿塘的荷花，很漂亮。");</p><p>　　strcpy(G.vexs[2].name,"體育運(yùn)動(dòng)中心");</p><p>　　strcpy(G.vexs[2].introduction,"學(xué)校最大的運(yùn)動(dòng)場所。");</p><p>　　strcpy(

41、G.vexs[3].name,"圖書館");</p><p>　　strcpy(G.vexs[3].introduction,"圖書館其中有大量的書籍，供學(xué)生免費(fèi)閱讀而且環(huán)境良好。");</p><p>　　strcpy(G.vexs[4].name,"綜合樓");</p><p>　　strcpy(G.v

42、exs[4].introduction,"主要的教學(xué)樓，包括老師的辦公室。");</p><p>　　strcpy(G.vexs[5].name,"學(xué)生食堂");</p><p>　　strcpy(G.vexs[5].introduction,"提供各種食物，品種多樣。");</p><p>　　strcp

43、y(G.vexs[6].name,"學(xué)生公園");</p><p>　　strcpy(G.vexs[6].introduction,"學(xué)校新建的小公園，環(huán)境良好。");</p><p>　　strcpy(G.vexs[7].name,"九棟宿舍");</p><p>　　strcpy(G.vexs[7].i

44、ntroduction,"學(xué)生的主要住所，條件一般般。");</p><p>　　for(i=0;i<G.vexnum;i++)</p><p>　　for(j=0;j<G.vexnum;j++)</p><p>　　G.arcs[i][j].maxvalue=FARMAX;</p><p>　　G.arcs[

45、0][1].maxvalue=70;</p><p>　　G.arcs[0][4].maxvalue=40;</p><p>　　G.arcs[1][5].maxvalue=30;</p><p>　　G.arcs[1][3].maxvalue=60;</p><p>　　G.arcs[2][3].maxvalue=20;</p>

46、<p>　　G.arcs[3][4].maxvalue=30;</p><p>　　G.arcs[4][5].maxvalue=40;</p><p>　　G.arcs[4][7].maxvalue=80;</p><p>　　G.arcs[5][7].maxvalue=50;</p><p>　　G.arcs[6][7].ma

47、xvalue=30;</p><p>　　for(i=0;i<G.vexnum;i++)</p><p>　　for(j=0;j<G.vexnum;j++)</p><p>　　G.arcs[j][i].maxvalue=G.arcs[i][j].maxvalue;</p><p><b>　　}</b>&l

48、t;/p><p>　　void menu() // 菜單</p><p><b>　　{</b></p><p>　　cout<<endl<<" 武漢長江工商學(xué)院校園導(dǎo)游圖 &quo

49、t;<<endl;</p><p>　　cout<<" ╔═══════════════════════╗"<<endl; </p><p>　　cout<<" ║ 1.瀏覽校園全景

50、 ║"<<endl;</p><p>　　cout<<" ║ 2.查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑 ║"<<endl;</p><p>　　cout<<" ║ 3.查詢圖中

51、一個(gè)景點(diǎn)到其他所有景點(diǎn)的最短路徑 ║"<<endl;</p><p>　　cout<<" ║ 4.查詢?nèi)我鈨删包c(diǎn)間的所有路徑 ║"<<endl;</p><p>　　cout<<" ║ 5.退出系統(tǒng)

52、 ║"<<endl;</p><p>　　cout<<" ╚═══════════════════════╝"<<endl;</p><p>　　cout<<" 請(qǐng)輸入你的選擇：

53、 "<<endl;</p><p><b>　　}</b></p><p>　　void information(Mgraph G) //簡介</p><p><b>　　{</b></p><p>　　cout<<&q

54、uot; ╔══╦═══════╦══════════════════════════╗"<<endl;</p><p>　　cout<<" ║編號(hào)║景點(diǎn)名稱 ║ 簡介 ║"<<endl;</p><p>　　cout&

55、lt;<" ╠══╬═══════╬══════════════════════════╣"<<endl;</p><p>　　for(int i=0;i<G.vexnum;i++)</p><p>　　printf(" ║%-4d║%-14s║%-52s║\n",G.vexs[i].num,G.vexs[i].name,

56、G.vexs[i].introduction);</p><p>　　cout<<" ╚══╩═══════╩══════════════════════════╝"<<endl;</p><p><b>　　}</b></p><p>　　void Floyd(Mgraph G){

57、 //兩點(diǎn)間最短路徑</p><p>　　int v,u,i,w,k,j,flag=1,p[8][8][8],D[8][8];</p><p>　　for(v=0;v<G.vexnum;v++)</p><p>　　for(w=0;w<G.vexnum;w++){</p><p>　　D[v][w]=G.arcs[

58、v][w].maxvalue;</p><p>　　for(u=0;u<G.vexnum;u++)</p><p>　　p[v][w][u]=0;</p><p>　　if(D[v][w]<FARMAX)</p><p><b>　　{</b></p><p>　　p[v][w][v]

59、=1;</p><p>　　p[v][w][w]=1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(u=0;u<G.vexnum;u++)</p><p>　　for(v=0;v<G.vexnum;v

60、++)</p><p>　　for(w=0;w<G.vexnum;w++)</p><p>　　if(D[v][u]+D[u][w]<D[v][w]) {</p><p>　　D[v][w]=D[v][u]+D[u][w];</p><p>　　for(i=0;i<G.vexnum;i++)</p><p

61、>　　p[v][w][i]=p[v][u][i]||p[u][w][i];</p><p><b>　　}</b></p><p>　　while(flag)</p><p><b>　　{</b></p><p>　　cout<<"請(qǐng)輸入出發(fā)點(diǎn)和目的地的編號(hào):"

62、;;</p><p>　　cin>>k>>j;</p><p>　　if(k<0||k>G.vexnum||j<0||j>G.vexnum)</p><p><b>　　{</b></p><p>　　cout<<"景點(diǎn)編號(hào)不存在!請(qǐng)重新輸入出發(fā)點(diǎn)和目

63、的地的編號(hào):";</p><p>　　cin>>k>>j;</p><p><b>　　}</b></p><p>　　if(k>=0 && k<G.vexnum && j>=0 && j<G.vexnum)</p><

64、p><b>　　flag=0;</b></p><p><b>　　}</b></p><p>　　cout<<G.vexs[k].name;</p><p>　　for(u=0;u<G.vexnum;u++)</p><p>　　if(p[k][j][u]&&

65、;k!=u&&j!=u)</p><p>　　cout<<"-->"<<G.vexs[u].name;</p><p>　　cout<<"-->"<<G.vexs[j].name;</p><p>　　cout<<" 總路線長&q

66、uot;<<D[k][j]<<"m";</p><p><b>　　}</b></p><p>　　void farf(Mgraph G) //一點(diǎn)到其他所有路徑</p><p><b>　　{</b></p><p>　　int v,w,i,min

67、,t=0,x,flag=1,v0;</p><p>　　int final[16], D[16], p[16][16];</p><p>　　while(flag)</p><p><b>　　{</b></p><p>　　cout<<"請(qǐng)輸入一個(gè)起始景點(diǎn)編號(hào):";</p>

68、<p><b>　　cin>>v0;</b></p><p>　　if(v0<0||v0>G.vexnum)</p><p><b>　　{</b></p><p>　　cout<<"景點(diǎn)編號(hào)不存在!請(qǐng)重新輸入景點(diǎn)編號(hào):";</p><

69、p><b>　　cin>>v0;</b></p><p><b>　　}</b></p><p>　　if(v0>=0&&v0<G.vexnum)</p><p><b>　　flag=0;</b></p><p><b>

70、;　　}</b></p><p>　　for(v=0;v<G.vexnum;v++)</p><p><b>　　{</b></p><p>　　final[v]=0;</p><p>　　D[v]=G.arcs[v0][v].maxvalue;</p><p>　　for(w=

71、0;w<G.vexnum;w++)</p><p>　　p[v][w]=0;</p><p>　　if(D[v]<FARMAX)</p><p><b>　　{</b></p><p>　　p[v][v0]=1;p[v][v]=1;</p><p><b>　　}</b

72、></p><p><b>　　}</b></p><p>　　D[v0]=0;final[v0]=1;</p><p>　　for(i=1;i<G.vexnum;i++)</p><p><b>　　{</b></p><p>　　min=FARMAX;<

73、/p><p>　　for(w=0;w<G.vexnum;w++)</p><p>　　if(!final[w])</p><p>　　if(D[w]<min)</p><p><b>　　{</b></p><p><b>　　v=w;</b></p>

74、<p><b>　　min=D[w];</b></p><p><b>　　}</b></p><p>　　final[v]=1;</p><p>　　for(w=0;w<G.vexnum;w++)</p><p>　　if(!final[w]&&(min+G.arc

75、s[v][w].maxvalue<D[w]))</p><p><b>　　{</b></p><p>　　D[w]=min+G.arcs[v][w].maxvalue;</p><p>　　for(x=0;x<G.vexnum;x++) </p><p>　　p[w][x]=p[v][x];</p&g

76、t;<p>　　p[w][w]=1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(v=0;v<G.vexnum;v++){</p><p>　　if(v0!=v) </p><p>　　cou

77、t<<G.vexs[v0].name;</p><p>　　for(w=0;w<G.vexnum;w++){</p><p>　　if(p[v][w]&&w!=v0) </p><p>　　cout<<"-->"<<G.vexs[w].name;</p><p&

78、gt;<b>　　t++;</b></p><p><b>　　}</b></p><p>　　if(t>G.vexnum-1&&v0!=v)</p><p>　　cout<<" 總路線長"<<D[v]<<"m"&

79、lt;<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int D[MAXVER];</p><p>　　int visited[MAXVER];</p><p><b>　　int a=0;&l

80、t;/b></p><p>　　void path(Mgraph G,int i,int j,int k)</p><p><b>　　{</b></p><p><b>　　int s;</b></p><p>　　if(D[k]==j)</p><p><b&

81、gt;　　{</b></p><p><b>　　a++;</b></p><p>　　cout<<"第"<<a<<"條路徑為:";</p><p>　　for(s=1;s<k;s++)</p><p>　　cout<&l

82、t;G.vexs[D[s]].name<<"-->";</p><p>　　cout<<G.vexs[D[s]].name;</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p><b>　　else&l

83、t;/b></p><p><b>　　{</b></p><p><b>　　s=1;</b></p><p>　　while(s<G.vexnum)</p><p><b>　　{</b></p><p><b>　　if(s!

84、=i)</b></p><p><b>　　{</b></p><p>　　if(G.arcs[D[k]][s].maxvalue!=FARMAX&&visited[s]==0)</p><p><b>　　{</b></p><p>　　visited[s]=1;<

85、;/p><p><b>　　D[k+1]=s;</b></p><p>　　path(G,i,j,k+1);</p><p>　　visited[s]=0;</p><p><b>　　}</b></p><p><b>　　}</b></p>

86、<p><b>　　s++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void searchpath(Mgraph G)</p&g

87、t;<p><b>　　{</b></p><p>　　int i,j,k,flag=1;</p><p>　　while(flag)</p><p><b>　　{</b></p><p>　　cout<<"請(qǐng)輸入出發(fā)點(diǎn)和目的地的編號(hào):";</p

88、><p>　　cin>>i>>j;</p><p>　　if(i<0||i>G.vexnum||j<0||j>G.vexnum)</p><p><b>　　{</b></p><p>　　cout<<"景點(diǎn)編號(hào)不存在!請(qǐng)重新輸入出發(fā)點(diǎn)和目的地的編號(hào):&q

89、uot;;</p><p>　　cin>>i>>j;</p><p><b>　　}</b></p><p>　　if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum)</p><p><

90、;b>　　flag=0;</b></p><p><b>　　}</b></p><p>　　for(k=0;k<G.vexnum;k++)</p><p><b>　　{</b></p><p>　　if(i==G.vexs[k].num)</p><p

91、><b>　　{</b></p><p><b>　　i=k;</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p>&l

92、t;p>　　for(int s=0;s<G.vexnum;s++)</p><p><b>　　{</b></p><p>　　if(j==G.vexs[s].num)</p><p><b>　　{</b></p><p><b>　　j=s;</b></p

93、><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　cout<<"從"<<G.vexs[i].name<<"到"&

94、lt;<G.vexs[j].name<<"的所有路徑有:"<<endl;</p><p><b>　　D[1]=i;</b></p><p>　　for(k=0;k>G.vexnum;k++)</p><p>　　visited[i]=0;</p><p><

95、b>　　a=0;</b></p><p>　　path(G,i,j,1);</p><p><b>　　}</b></p><p>　　void casaf(Mgraph G) //菜單及選擇</p><p><b>　　{</b></p><p>&

96、lt;b>　　int i=1;</b></p><p>　　while(i!=5)</p><p><b>　　{</b></p><p><b>　　cin>>i;</b></p><p><b>　　switch(i)</b></p>

97、;<p><b>　　{</b></p><p>　　case 1:system("cls");information(G);menu();break;</p><p>　　case 2:system("cls");Floyd(G);menu();break;</p><p>　　case

98、3:system("cls");farf(G);menu();break;</p><p>　　case 4:system("cls");searchpath(G);menu();break;</p><p>　　case 5:exit(1);break;</p><p>　　default:break;</p>

99、<p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　sy

100、stem("color 2f");</p><p>　　system("mode con: cols=100 lines=40");</p><p><b>　　Mgraph G;</b></p><p><b>　　jiben(G);</b></p><p>