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

1、<p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p>　　課程名稱： 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì) </p><p>　　設(shè)計(jì)題目： 校園導(dǎo)游咨詢 </p><p>　　專 業(yè)： 軟件工程 </p><p>　　班 級(jí)： 2010軟

2、件工程 </p><p>　　學(xué)生姓名： </p><p>　　學(xué) 號(hào)： </p><p>　　起止日期： </p><p>　　指導(dǎo)教師：

3、 </p><p><b>　　注意事項(xiàng)</b></p><p><b>　　一、設(shè)計(jì)目的</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)》是一門實(shí)踐性較強(qiáng)的軟件基礎(chǔ)課，為了學(xué)好這門課程，必須在掌握理論知識(shí)的同時(shí)，加強(qiáng)上機(jī)實(shí)踐。本課程設(shè)計(jì)的目的就是要達(dá)到理論與實(shí)際應(yīng)用相結(jié)合，使同學(xué)們能夠根據(jù)數(shù)據(jù)對象的特性，學(xué)會(huì)數(shù)

4、據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問題在計(jì)算機(jī)內(nèi)部表示出來，并培養(yǎng)基本的、良好的程序設(shè)計(jì)技能。</p><p><b>　　二、設(shè)計(jì)要求</b></p><p>　　1．通過這次課程設(shè)計(jì)，要求在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深課程基本內(nèi)容的理解。同時(shí)，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)

5、練。</p><p>　　2．學(xué)生必須仔細(xì)研讀《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)要求，以學(xué)生自學(xué)為主、指導(dǎo)教師指導(dǎo)為輔，獨(dú)立完成課程設(shè)計(jì)的任務(wù)，有問題及時(shí)主動(dòng)與指導(dǎo)教師溝通。</p><p>　　3．本次課程設(shè)計(jì)按照教學(xué)要求需要在本學(xué)期15周前完成，學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課程設(shè)計(jì)的時(shí)間計(jì)劃，并在課程設(shè)計(jì)過程中不斷檢測自己的計(jì)劃完成情況，及時(shí)向指導(dǎo)教師匯報(bào)。</p>

6、<p>　　4．編程語言：C 語言。</p><p>　　三、課程設(shè)計(jì)說明書的格式要求 </p><p>　　設(shè)計(jì)文檔的撰寫必須提前進(jìn)行，以保證使文檔與程序同步提交。 </p><p>　　1．設(shè)計(jì)題目 2．運(yùn)行環(huán)境（軟、硬件環(huán)境）</p><p>　　3．算法的需求分析

7、 4．算法概要設(shè)計(jì)</p><p>　　5．算法詳細(xì)設(shè)計(jì) 6．算法的測試</p><p>　　7．運(yùn)行結(jié)果分析 8．收獲及體會(huì)</p><p>　　四、問題分析、設(shè)計(jì)和測試過程要規(guī)范化</p><p>　　1．需求分析：將題目中要求的功能進(jìn)行敘述分析。</p><

8、;p>　　2．概要設(shè)計(jì)：算法的設(shè)計(jì)說明，描述解決此問題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲(chǔ)的，按照指定的設(shè)計(jì)），描述算法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語句的時(shí)間復(fù)雜度。</p><p>　　3．詳細(xì)設(shè)計(jì)：即各個(gè)算法的具體實(shí)現(xiàn)步驟，每個(gè)題目要有相應(yīng)的源程序，其中每個(gè)功能模塊采用不同的函數(shù)實(shí)現(xiàn)。源程序要規(guī)范編寫：結(jié)構(gòu)要清晰，注釋要清楚。重點(diǎn)函數(shù)的重點(diǎn)變量和重點(diǎn)功能部分要加上清楚的程序注釋。<

9、/p><p>　　4．調(diào)試和測試：給出實(shí)現(xiàn)功能的一組或多組測試數(shù)據(jù)，程序調(diào)試后，將按照此測試數(shù)據(jù)進(jìn)行測試的結(jié)果列出來 。在調(diào)試過程中遇到的問題和解決方法也要記錄下來。程序要能夠正常運(yùn)行，還要有基本的容錯(cuò)功能。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)。</p><p>　　5．改進(jìn)措施： 對有些題目提出算法改進(jìn)方案，比較不同算法的優(yōu)缺點(diǎn)。</p><p>　　五、對指導(dǎo)

10、教師的要求</p><p>　　指導(dǎo)教師要關(guān)心學(xué)生的課程設(shè)計(jì)進(jìn)展，認(rèn)真答疑。對課程設(shè)計(jì)報(bào)告的撰寫要給予充分的指導(dǎo)，報(bào)告中切忌出現(xiàn)大篇源代碼，應(yīng)嚴(yán)格要求學(xué)生將主要篇幅放在“原理實(shí)現(xiàn)”上，即如何用框圖表達(dá)設(shè)計(jì)和實(shí)施思想。課程設(shè)計(jì)報(bào)告要用紅筆批閱，最終成績以優(yōu)、良、中、及格與不及格分等計(jì)算。</p><p><b>　　目錄</b></p><p>

11、<b>　　摘要1</b></p><p>　　1 設(shè)計(jì)內(nèi)容和要求- 2 -</p><p>　　1.1設(shè)計(jì)內(nèi)容- 2 -</p><p>　　1.1設(shè)計(jì)要求- 2 -</p><p><b>　　2 概要設(shè)計(jì)2</b></p><p>　　2.1 程序的模塊圖2

12、</p><p>　　2.2 主函數(shù)的概要設(shè)計(jì)3</p><p>　　2.3 查找介紹函數(shù)的概要設(shè)計(jì)3</p><p>　　2.4 查找最短路徑函數(shù)的概要設(shè)計(jì)3</p><p>　　2.5 景點(diǎn)分布圖的概要設(shè)計(jì)3</p><p>　　2.6 退出函數(shù)的概要設(shè)計(jì)3</p><p><

13、;b>　　3 詳細(xì)設(shè)計(jì)5</b></p><p>　　3.1 程序的流程圖5</p><p>　　3.2 主函數(shù)的詳細(xì)設(shè)計(jì)6</p><p>　　3.3 查找介紹函數(shù)的詳細(xì)設(shè)計(jì)6</p><p>　　3.4 查找最短路徑函數(shù)的詳細(xì)設(shè)計(jì)7</p><p>　　3.5 景點(diǎn)分布圖的詳細(xì)設(shè)計(jì)8&

14、lt;/p><p>　　3.6 退出函數(shù)的詳細(xì)設(shè)計(jì)9</p><p>　　3.7 數(shù)據(jù)結(jié)構(gòu)的詳細(xì)設(shè)計(jì)9</p><p><b>　　4 軟件測試10</b></p><p>　　4.1 菜單的測試10</p><p>　　4.2 查找景點(diǎn)簡介的測試11</p><p>

15、;　　4.3 查找兩個(gè)景點(diǎn)之間的最短距離的測試12</p><p>　　4.4 查看景點(diǎn)分布圖的測試13</p><p>　　4.5 退出的測試14</p><p>　　5 軟件使用說明15</p><p><b>　　6 參考文獻(xiàn)16</b></p><p><b>　　7

16、附錄17</b></p><p>　　7.1 系統(tǒng)完整代碼17</p><p><b>　　摘要</b></p><p>　　現(xiàn)代快節(jié)奏的生活使得都市人越來越渴望親近自然，因此外出旅游現(xiàn)在被越來越多的都市人所看中，所以如何快速方便的找到我們想要的旅游景點(diǎn)的信息和最短路徑就成了一個(gè)很重要的問題。</p><p&

17、gt;　　本設(shè)計(jì)基于圖的結(jié)構(gòu)，創(chuàng)建一個(gè)無向圖，針對游客的實(shí)際需求，將瓊州學(xué)院的景點(diǎn)編號(hào)、名稱、介紹等信息放入到圖的頂點(diǎn)當(dāng)中并保存在景點(diǎn)文本文件當(dāng)中，將兩個(gè)景點(diǎn)的編號(hào)和它們之間的距離當(dāng)作權(quán)值也保存到權(quán)值文本文件當(dāng)中，利用迪杰斯特拉算法來求從一個(gè)景點(diǎn)到另一個(gè)景點(diǎn)的最短距離，利用Search( );函數(shù)來查找景點(diǎn)，并顯示出它的信息，從而解決了要查找景點(diǎn)信息和景點(diǎn)之間的最短路徑的問題，最后按照顯示屏上的提示進(jìn)行相關(guān)的操作。</p>

18、<p>　　關(guān)鍵詞：分布圖、查找信息、最短距離、校園導(dǎo)游咨詢</p><p><b>　　1 設(shè)計(jì)內(nèi)容和要求</b></p><p><b>　　1.1設(shè)計(jì)內(nèi)容</b></p><p>　　依據(jù)課程設(shè)計(jì)的要求，利用一個(gè)無向圖的結(jié)構(gòu)，將景點(diǎn)當(dāng)作圖的頂點(diǎn)，將景點(diǎn)之間的距離當(dāng)作權(quán)值來儲(chǔ)存，然后根據(jù)游客自己的需求，按照

19、顯示屏上的提示來進(jìn)行查找景點(diǎn)介紹，查找兩個(gè)景點(diǎn)之間的最短距離，退出程序等基本操作。</p><p><b>　　1.1設(shè)計(jì)要求</b></p><p>　　本軟件為校園導(dǎo)游咨詢系統(tǒng)，根據(jù)游客的實(shí)際需求而設(shè)計(jì)，首先創(chuàng)建一個(gè)無向圖，然后從文件當(dāng)中讀取所有景點(diǎn)的編號(hào)、名稱、介紹和兩點(diǎn)之間的權(quán)值，并將它們寫入到無向圖當(dāng)中。功能主要包括查找已知景點(diǎn)的信息，查找從一個(gè)景點(diǎn)到另一個(gè)

20、景點(diǎn)的最短路徑，退出等基本操作。</p><p>　　軟件的界面要求使用VC++6.0的運(yùn)行環(huán)境。</p><p>　　軟件的數(shù)據(jù)庫包括校園景點(diǎn)的編號(hào)、名稱、介紹和兩個(gè)景點(diǎn)之間的距離（權(quán)值），首先要定義頂點(diǎn)的數(shù)據(jù)類型結(jié)構(gòu)體，里面包括景點(diǎn)的編號(hào)、名稱、介紹，然后定義一個(gè)鄰接矩陣結(jié)構(gòu)體來儲(chǔ)存邊的信息，最后定義一個(gè)無向圖類型的結(jié)構(gòu)體來儲(chǔ)存頂點(diǎn)的信息，邊的信息，頂點(diǎn)的個(gè)數(shù)，邊的條數(shù)。</p&

21、gt;<p>　　最后游客按照顯示屏上的提示來進(jìn)行相關(guān)的操作。</p><p><b>　　2 概要設(shè)計(jì)</b></p><p>　　2.1 程序的模塊圖</p><p>　　本軟件的算法依據(jù)無向圖的操作通過查找函數(shù)查找景點(diǎn)的信息，通過費(fèi)洛伊德函數(shù)來查找最短距離，開始時(shí)首先從文件當(dāng)中讀取景點(diǎn)的編號(hào)、名稱、介紹和兩個(gè)景點(diǎn)之間的距離即

22、權(quán)值，然后將其加入到圖當(dāng)中，再調(diào)用查找函數(shù)查找景點(diǎn)的信息，調(diào)用費(fèi)洛伊德函數(shù)來查找最短距離，調(diào)用退出函數(shù)實(shí)現(xiàn)退出功能，其模塊圖如圖2.5所示：</p><p><b>　　圖2.5模塊圖</b></p><p>　　2.2 主函數(shù)的概要設(shè)計(jì)</p><p>　　基于程序的操作要求，對于主函數(shù)的設(shè)計(jì)首先是顯示一個(gè)可視化的操作界面提醒游客進(jìn)行相關(guān)的操

23、作和提示游客其可供選擇的景點(diǎn)的名稱，便于其在后面的操作過程當(dāng)中能夠快速方便的找到其需要查找的景點(diǎn)的名稱。而后就是一個(gè)switch（）；的選擇函數(shù)，提供查找景點(diǎn)信息，查找兩個(gè)景點(diǎn)之間的最短距離和退出的相關(guān)的選擇操作而后進(jìn)入到每一個(gè)操作界面當(dāng)中，從而實(shí)現(xiàn)所需要的功能。</p><p>　　2.3 查找介紹函數(shù)的概要設(shè)計(jì)</p><p>　　當(dāng)游客選擇了要查找景點(diǎn)的信息的介紹這一項(xiàng)功能的時(shí)候，就

24、會(huì)進(jìn)入到查找的界面，對于查找景點(diǎn)信息就是利用Search( );函數(shù)，當(dāng)游客輸入景點(diǎn)的名稱的時(shí)候看其是否與文件當(dāng)中的數(shù)據(jù)相匹配，如果有則輸出它的介紹，如果沒有則輸出錯(cuò)誤的提示提醒游客進(jìn)行相關(guān)的操作來進(jìn)入到正確的操作過程當(dāng)中。</p><p>　　2.4 查找最短路徑函數(shù)的概要設(shè)計(jì)</p><p>　　對于查找最短路徑的這一項(xiàng)功能，可以利用迪杰斯特拉算法，但我是用的費(fèi)洛伊德算法，相對來說步驟

25、跟簡單一點(diǎn)。后面有詳細(xì)介紹。</p><p>　　2.5 景點(diǎn)分布圖的概要設(shè)計(jì)</p><p>　　先手稿繪制所有景點(diǎn)的分布，利用printf（）；函數(shù)打印分布圖的框架構(gòu)造。各景點(diǎn)之間用線條鏈接，通過分布圖能全面的對校園各景點(diǎn)有個(gè)方位感。</p><p>　　2.6 退出函數(shù)的概要設(shè)計(jì)</p><p>　　關(guān)于退出函數(shù)，則是當(dāng)游客執(zhí)行完了他想

26、要進(jìn)行的操作過后選擇退出的功能的時(shí)候就調(diào)用退出函數(shù)exit(0);跳入到退出界面實(shí)現(xiàn)退出的功能。</p><p><b>　　3 詳細(xì)設(shè)計(jì)</b></p><p>　　3.1 程序的流程圖</p><p>　　當(dāng)我們想要更加實(shí)際的了解一個(gè)程序的算法過程的時(shí)候，我們就要依據(jù)程序的流程圖來給我們一個(gè)比較實(shí)際的過程，從流程圖當(dāng)中能夠更加清楚整個(gè)程序?qū)?/p>

27、現(xiàn)的過程是怎樣的。其流程圖如圖3.1所示：</p><p><b>　　圖3.1流程圖</b></p><p>　　3.2 主函數(shù)的詳細(xì)設(shè)計(jì)</p><p>　　主函數(shù)是一個(gè)程序的主體，當(dāng)我們要進(jìn)行我們所需要的操作的時(shí)候我們就要根據(jù)主函數(shù)中的顯示信息和它給我們的相關(guān)的提示信息來進(jìn)行所需要的操作，因此在這次的程序?qū)崿F(xiàn)的過程當(dāng)中，調(diào)用Browse

28、r();提示游客根據(jù)switch();的選擇語句，選擇來進(jìn)入到相關(guān)的操作界面實(shí)現(xiàn)程序的基本功能。， </p><p>　　3.3 查找介紹函數(shù)的詳細(xì)設(shè)計(jì)</p><p>　　當(dāng)游客選擇了要查找景點(diǎn)的信息的介紹這一項(xiàng)功能的時(shí)候，程序就會(huì)調(diào)用Search( );函數(shù)進(jìn)入到查找景點(diǎn)的介紹的界面，當(dāng)游客輸入了需要查找的景點(diǎn)的編號(hào)的時(shí)候，程序通過結(jié)構(gòu)體，自動(dòng)匹配相應(yīng)的信息，查找是否有這個(gè)景點(diǎn)。<

29、;/p><p>　　void Search(MGraph *G)</p><p><b>　　{</b></p><p>　　int k,flag=1;</p><p>　　while(flag){</p><p>　　printf("請輸入要查詢的景點(diǎn)編號(hào):");</p&g

30、t;<p>　　scanf("%d",&k);</p><p>　　if(k<=0||k>G->vexnum){</p><p>　　printf("景點(diǎn)編號(hào)不存在!請重新輸入景點(diǎn)編號(hào):");</p><p>　　scanf("%d",&k);</p&g

31、t;<p><b>　　}</b></p><p>　　if(k>0&&k<=G->vexnum) flag=0;</p><p><b>　　}</b></p><p>　　printf("\n┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━

32、━━━━━━━━━━┓\n");</p><p>　　printf("┃編號(hào)┃景點(diǎn)名稱 ┃簡介 ┃\n");</p><p>　　printf("┃%-4d┃%-16s┃%-62s┃\n",G->vexs[k

33、].num,G->vexs[k].name,G->vexs[k].introduction);</p><p>　　printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");</p><p>　　}，找到將它的編號(hào)返回，并輸出它的介紹，沒有找到這輸出錯(cuò)誤提示，提醒游客進(jìn)行相關(guān)的操作進(jìn)入正確的操作過程當(dāng)

34、中。</p><p>　　3.4 查找最短路徑函數(shù)的詳細(xì)設(shè)計(jì)</p><p>　　當(dāng)游客選擇了要查找兩個(gè)景點(diǎn)之間的最短距離這一項(xiàng)功能的時(shí)候，函數(shù)進(jìn)入到查找兩個(gè)景點(diǎn)之間的最短距離的操作界面當(dāng)中，當(dāng)游客輸入了兩個(gè)景點(diǎn)的名稱過后，程序會(huì)判斷是否有這兩個(gè)景點(diǎn)，如果有則返回他們各自的編號(hào)，并調(diào)用Floyd( );函數(shù)進(jìn)入到查找最短路徑問題的程序當(dāng)中。</p><p>　　vo

35、id Floyd(MGraph *G)</p><p><b>　　{</b></p><p>　　int v,u,i,w,k,j,flag=1,p[14][14][14],D[14][14];</p><p>　　for(v=1;v<=G->vexnum;v++)</p><p>　　for(w=1;w&l

36、t;=G->vexnum;w++)</p><p><b>　　{</b></p><p>　　D[v][w]=G->arcs[v][w].adj;</p><p>　　for(u=1;u<=G->vexnum;u++)</p><p>　　p[v][w][u]=0;</p><

37、;p>　　if(D[v][w]<INFINITY)</p><p><b>　　{</b></p><p>　　p[v][w][v]=1;p[v][w][w]=1;</p><p><b>　　}</b></p><p><b>　　}</b></p>

38、<p>　　for(u=1;u<=G->vexnum;u++)</p><p>　　for(v=1;v<=G->vexnum;v++)</p><p>　　for(w=1;w<=G->vexnum;w++)</p><p>　　if(D[v][u]+D[u][w]<D[v][w])</p><

39、p><b>　　{</b></p><p>　　D[v][w]=D[v][u]+D[u][w];</p><p>　　for(i=1;i<=G->vexnum;i++)</p><p>　　p[v][w][i]=p[v][u][i] || p[u][w][i];</p><p><b>　　}

40、</b></p><p>　　while(flag)</p><p><b>　　{</b></p><p>　　printf("請輸入出發(fā)點(diǎn)和目的地的編號(hào):");</p><p>　　scanf("%d%d",&k,&j);</p>&l

41、t;p>　　if(k<=0 || k>G->vexnum || j<=0 || j>G->vexnum)</p><p><b>　　{</b></p><p>　　printf("景點(diǎn)編號(hào)不存在!請重新輸入出發(fā)點(diǎn)和目的地的編號(hào):");</p><p>　　scanf("%

42、d%d",&k,&j);</p><p><b>　　}</b></p><p><b>　　if(k==j)</b></p><p><b>　　{</b></p><p>　　printf("出發(fā)點(diǎn)和目的地一樣!請重新輸入出發(fā)點(diǎn)和目的地的

43、編號(hào):");</p><p>　　scanf("%d%d",&k,&j);</p><p><b>　　}</b></p><p>　　if(k>0 && k<=G->vexnum && j>0 && j<=G->v

44、exnum)</p><p><b>　　flag=0;</b></p><p><b>　　}</b></p><p>　　printf("\n最短游覽路線：%s",G->vexs[k].name);</p><p><b>　　if(k>j){</

45、b></p><p>　　for(u=G->vexnum;u>0;u--)</p><p>　　if(p[k][j][u] && k!=u && j!=u)</p><p>　　printf("-->%s",G->vexs[u].name);}</p><p>

46、<b>　　if(k<j){</b></p><p>　　for(u=1;u<=G->vexnum;u++)</p><p>　　if(p[k][j][u] && k!=u && j!=u)</p><p>　　printf("-->%s",G->vexs[u].

47、name);}</p><p>　　printf("-->%s",G->vexs[j].name);</p><p>　　printf(" 總路線長%dm\n",D[k][j]);</p><p><b>　　}</b></p><p>　　已知有n個(gè)頂點(diǎn)的有向圖,佛洛

48、伊德算法可以求解出每一對頂點(diǎn)之間的最短路徑。假設(shè)使用鄰接矩陣d ( i, j)來對圖進(jìn)行存儲(chǔ), d ( i, j)表示υi 到υj 之間的距離,但是該距離不一定是最短距離。佛洛伊德算法的基本思想是:為求頂點(diǎn)υi→υj 之間的最短距離,需要進(jìn)行n次試探。首先將υ0 加入路徑,考慮路徑υi →υ0 →υj 是否存在,如果存在,則比較υi →υj和υi →υ0 →υj 的路徑長度,取長度短的路徑作為υi →υj 的路徑,記作(υi ,υj )

49、 。接著在路徑上再增加一個(gè)頂點(diǎn)υ1 ,比較υi→υ1 →υj 和(υi ,υj )的路徑長度, 取長度短的路徑作為(υi ,υj) 。不斷將頂點(diǎn)υ2 ,υ3 , .,υn - 1加入進(jìn)行試探, 最后得到的(υi ,υj )必定為υi →υj 的最短路徑。若使用數(shù)組dk ( i, j)表示加入頂點(diǎn)k后,最短路徑長度的變化情況,使用數(shù)組pk ( i, j)表示加入頂點(diǎn)k后,最短路徑上頂點(diǎn)的變化情況, 這樣就求得了最短路徑和最短路徑長度。&l

50、t;/p><p>　　3.5 景點(diǎn)分布圖的詳細(xì)設(shè)計(jì)</p><p>　　這里不詳細(xì)介紹，具體代碼，查看附錄browse_view_distribute ( ) 函數(shù)。</p><p>　　3.6 退出函數(shù)的詳細(xì)設(shè)計(jì)</p><p>　　對于退出函數(shù)，當(dāng)游客選擇了退出這一個(gè)操作的時(shí)候，程序就會(huì)調(diào)用exit(0); 函數(shù)實(shí)現(xiàn)退出主函數(shù)的功能。最后會(huì)提

51、示游客，歡迎下次繼續(xù)使用！</p><p>　　3.7 數(shù)據(jù)結(jié)構(gòu)的詳細(xì)設(shè)計(jì)</p><p>　　本軟件的數(shù)據(jù)結(jié)構(gòu)包括3個(gè)部分：</p><p><b>　　鄰接矩陣</b></p><p>　　typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];</p&g

52、t;<p>　　定義一個(gè)鄰接矩陣，用鄰接矩陣來定義和儲(chǔ)存邊的相關(guān)信息。</p><p><b>　　2. 頂點(diǎn)的結(jié)構(gòu)體</b></p><p>　　typedef struct Vertex//定義圖中頂點(diǎn)的數(shù)據(jù)類型</p><p><b>　　{</b></p><p>　　int

53、num;//景點(diǎn)編號(hào)</p><p>　　char name[30];//景點(diǎn)名稱</p><p>　　char introduction[200];//景點(diǎn)介紹</p><p><b>　　}Vertex;</b></p><p>　　定義一個(gè)頂點(diǎn)的結(jié)構(gòu)體，用來儲(chǔ)存景點(diǎn)的編號(hào)、景點(diǎn)得名稱和景點(diǎn)的介紹等關(guān)于景點(diǎn)的信息。&

54、lt;/p><p><b>　　3.無向圖的結(jié)構(gòu)體</b></p><p>　　typedef struct //定義圖的數(shù)據(jù)類型</p><p><b>　　{</b></p><p>　　Vertex vexs[MAX_VERTEX_NUM];//頂點(diǎn)的結(jié)構(gòu)體</p><p>

55、;　　AdjMatrix arcs;//邊的鄰接矩陣</p><p>　　int vexnum,arcnum;//頂點(diǎn)的個(gè)數(shù)，邊的個(gè)數(shù)</p><p><b>　　}MGraph;</b></p><p>　　定義一個(gè)圖的結(jié)構(gòu)體，用來儲(chǔ)存頂點(diǎn)的信息、邊的信息、頂點(diǎn)的個(gè)數(shù)和邊的個(gè)數(shù)等相關(guān)的信息便于我們以后在用的時(shí)候能夠方便快捷的調(diào)用。</p

56、><p>　　定義好這些結(jié)構(gòu)體后，當(dāng)我們以后需要調(diào)用的時(shí)候，我們就能夠方便快捷的調(diào)用這些結(jié)構(gòu)體，從而使得我們在運(yùn)行程序的時(shí)候能夠更加的快速能夠提高我們的程序的運(yùn)行效率，大大的節(jié)省了我們的時(shí)間還使得程序變得更加的簡單。</p><p><b>　　4 軟件測試</b></p><p><b>　　4.1 菜單的測試</b><

57、;/p><p>　　對于菜單函數(shù)的測試，首先菜單是一個(gè)可示化的界面，它能夠提示游客依據(jù)顯示屏上出現(xiàn)的提示來進(jìn)行相關(guān)的操作，查看所有的景點(diǎn)從而方便游客進(jìn)行相關(guān)的操作，因而我們在運(yùn)行程序的時(shí)候首先就會(huì)進(jìn)入到菜單函數(shù)當(dāng)中，經(jīng)過測試其能夠?qū)崿F(xiàn)我們所要實(shí)現(xiàn)得基本功能，其效果圖如圖4.1所示：</p><p><b>　　圖4.1菜單</b></p><p>

58、　　4.2 查找景點(diǎn)簡介的測試</p><p>　　對于查找景點(diǎn)的介紹的測試，首先依據(jù)顯示屏上的提示首先輸入要進(jìn)行的操作輸入3進(jìn)入查找景點(diǎn)信息的操作界面，然后輸入需要查找的景點(diǎn)的名稱即可顯示出景點(diǎn)的介紹信息，經(jīng)過測試可以得出其沒有什么錯(cuò)誤，程序能夠按照我的要求實(shí)現(xiàn)它的功能，其效果圖如圖4.2所示：</p><p>　　圖4.2查找景點(diǎn)信息</p><p>　　4.3

59、 查找兩個(gè)景點(diǎn)之間的最短距離的測試</p><p>　　同查找景點(diǎn)的信息一樣，對于查找景點(diǎn)之間的最短距離的測試，我們就要依據(jù)提示輸入2進(jìn)入到查詢最短路徑的界面，依次輸入所需要查找的兩個(gè)景點(diǎn)就會(huì)顯示出怎樣到達(dá)這兩個(gè)景點(diǎn)并顯示出它們之間的最短路徑，經(jīng)過測試可見程序能夠按照我的要求來實(shí)現(xiàn)其所需要的功能，其效果圖如圖4.3所示：</p><p>　　圖4.3查找兩個(gè)景點(diǎn)之間的最短距離</p&

60、gt;<p>　　4.4 查看景點(diǎn)分布圖的測試</p><p>　　對于查看景點(diǎn)分布圖的測試，我需要依據(jù)顯示屏上的提示，需要輸入1進(jìn)入到分布圖的界面，系統(tǒng)就會(huì)直接調(diào)用browse_view_distribute();函數(shù)，在屏幕上打印出景點(diǎn)的分布圖。</p><p>　　圖4.4景點(diǎn)分布圖界面</p><p><b>　　4.5 退出的測試&

61、lt;/b></p><p>　　原理同上，對于退出函數(shù)的測試，我需要依據(jù)顯示屏上的提示，需要輸入4進(jìn)入到退出的界面，系統(tǒng)就會(huì)直接調(diào)用退出的函數(shù)，顯示出“歡迎下次繼續(xù)使用！”的話，退出了系統(tǒng)，其效果圖如圖4.4所示：</p><p><b>　　圖4.5退出界面</b></p><p><b>　　5 軟件使用說明</b&

62、gt;</p><p>　　對于軟件的使用，對于第一次使用軟件的游客來說，要讓他們在第一次用的時(shí)候就能夠快速輕松的掌握軟件的用法，因此在程序一開始運(yùn)行的時(shí)候，我們要進(jìn)行如下的操作：</p><p>　?。?）首先我會(huì)給游客提供一個(gè)可視化的菜單操作界面，在顯示屏上提示用戶其可以進(jìn)行的操作和他能夠查詢的景點(diǎn)的編號(hào)、名稱。</p><p>　?。?）用戶輸入了“1”后，屏

63、幕上會(huì)顯示出所有景點(diǎn)的位置關(guān)系平面圖。能夠大致了解景點(diǎn)的分布。</p><p>　　（3）當(dāng)用戶輸入了“2”后，進(jìn)入到查詢?nèi)我鈨删包c(diǎn)間最短路徑的界面，然后提示用戶依次輸入兩個(gè)景點(diǎn)的編號(hào)，程序就會(huì)將這兩個(gè)景點(diǎn)的最短路徑給我們表示出來并顯示出最短路徑是多少。</p><p>　　（4）用戶輸入了“3”后，進(jìn)入到查詢景點(diǎn)信息的界面，然后提示用戶輸入景點(diǎn)的編號(hào)（一次限一個(gè)），程序就會(huì)顯示出這個(gè)景點(diǎn)

64、的詳細(xì)介紹。</p><p>　　（5）當(dāng)用戶輸入了“4”后，進(jìn)入到退出界面，這時(shí)系統(tǒng)就會(huì)顯示“歡迎下次繼續(xù)使用!”的提示語，最后按下任意鍵退出系統(tǒng)。</p><p><b>　　6 參考文獻(xiàn)</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)(C語言版) 嚴(yán)蔚敏 吳偉民 編著 清華大學(xué)出版社 2002</p><p>　　C程序設(shè)計(jì)

65、經(jīng)典教程，[美]Deitel,H.M.，[美]Deitel,P.J.著，清華大學(xué)出版社 2006</p><p>　　Windows程序設(shè)計(jì)，[美] Charles Petzold 著，北京大學(xué)出版社 2004</p><p>　　Data Structures：A Pseudecode（Approach with C）[美]Richard F.Gilberg，[美]Behrouz A.F

66、orouzan著</p><p><b>　　7 附錄</b></p><p>　　7.1 系統(tǒng)完整代碼</p><p>　　#define INFINITY 10000 /*無窮大*/</p><p>　　#define MAX_VERTEX_NUM 40</p><

67、p>　　#define MAX 40</p><p>　　#include<stdlib.h></p><p>　　#include<stdio.h></p><p>　　#include<conio.h></p><p>　　#include<string.h></p>&

68、lt;p>　　#include "Exit.h"</p><p>　　typedef struct ArCell</p><p><b>　　{</b></p><p>　　int adj; //路徑長度</p><p>　　}ArCell,AdjMatrix[MAX_VERTEX_NUM

69、][MAX_VERTEX_NUM];</p><p>　　typedef struct //圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱、簡介等信息，</p><p><b>　　{</b></p><p>　　char name[30];</p><p><b>　　int num;</b>&l

70、t;/p><p>　　char introduction[200];//簡介</p><p>　　}infotype;</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　infotype vexs[MAX_VERTEX_NUM];//景點(diǎn)&l

71、t;/p><p>　　AdjMatrix arcs;//路徑數(shù)組</p><p>　　int vexnum,arcnum;//景點(diǎn)數(shù)，路徑長度記錄</p><p><b>　　}MGraph;</b></p><p>　　MGraph b;//全局變量 </p><p>　　void cmd(void

72、);//在主函數(shù)中用來調(diào)用其他應(yīng)用子函數(shù)的函數(shù)聲明</p><p>　　MGraph InitGraph(void);//用來構(gòu)造學(xué)校地圖的子函數(shù) 返回MGraph類型</p><p>　　void Menu(void);//菜單函數(shù)；</p><p>　　void Browser(MGraph *G);//調(diào)用MGraph類型的地址，進(jìn)行</p>&

73、lt;p>　　void ShortestPath_DIJ(MGraph * G);//迪杰斯特拉算法求最短路徑的子函數(shù)</p><p>　　void Floyd(MGraph *G);//佛洛伊德算法</p><p>　　void Search(MGraph *G);//尋找要查詢的景點(diǎn)，并輸出該景點(diǎn)的信息</p><p>　　void browse_view

74、_distribute();//查看景點(diǎn)分布圖</p><p>　　void tou(MGraph *G);//景點(diǎn)列表</p><p>　　void panduan();</p><p>　　//void Exit();//退出</p><p>　　int LocateVex(MGraph *G,char* v);//定點(diǎn)位置</p&

75、gt;<p>　　MGraph * CreatUDN(MGraph *G);////初始化圖形，接受用戶輸入</p><p>　　void print(MGraph *G);//打印輸出子函數(shù)</p><p>　　/******************************************************/</p><p>　　voi

76、d main(void)</p><p><b>　　{</b></p><p>　　system("color 1f");//設(shè)置調(diào)試窗口背景和字體顏色</p><p>　　system("mode con: cols=140 lines=130");//設(shè)置調(diào)試窗口的大小</p><

77、;p>　　cmd();//用該函數(shù)來調(diào)用其他需要用到的函數(shù)</p><p><b>　　}</b></p><p>　　/******************************************************/</p><p>　　void cmd(void)//用來調(diào)用其他需要用到的函數(shù)的子函數(shù)</p>

78、<p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　b=InitGraph();//構(gòu)造校園地圖</p><p>　　Browser(&b);//Menu();//調(diào)用菜單函數(shù)</p><p>　　scanf("%d&

79、quot;,&i);</p><p>　　while(i!=4)</p><p><b>　　{</b></p><p><b>　　switch(i)</b></p><p><b>　　{</b></p><p>　　case 1:syste

80、m("cls");/*ShortestPath_DIJ(&b);*/browse_view_distribute();Browser(&b);break;</p><p>　　case 2:system("cls");tou(&b);Floyd(&b);Browser(&b);break;</p><p>　　

81、case 3:system("cls");tou(&b);Search(&b);Browser(&b);break;</p><p>　　case 4:exit(0);break;</p><p>　　default:break;</p><p><b>　　}</b></p><

82、p>　　scanf("%d",&i);</p><p><b>　　}</b></p><p>　　printf("歡迎下次繼續(xù)使用 !\n\n");</p><p><b>　　}</b></p><p>　　//***************

83、****************************************************</p><p>　　MGraph InitGraph(void)//構(gòu)造校園地圖</p><p><b>　　{</b></p><p><b>　　MGraph G;</b></p><p>

84、<b>　　int i,j;</b></p><p>　　G.vexnum=13;//景點(diǎn)數(shù)量</p><p>　　G.arcnum=21;//路徑數(shù)量</p><p>　　for(i=1;i<=G.vexnum;i++)</p><p>　　G.vexs[i].num=i;//對景點(diǎn)進(jìn)行對應(yīng)編號(hào)</p>

85、;<p>　　/*對對應(yīng)的景點(diǎn)編號(hào)進(jìn)行命名，輸入簡介*/</p><p>　　strcpy(G.vexs[3].name,"行政辦公樓");</p><p>　　strcpy(G.vexs[3].introduction,"學(xué)校的行政機(jī)構(gòu)。");</p><p>　　strcpy(G.vexs[6].name,&

86、quot;圖書館");</p><p>　　strcpy(G.vexs[6].introduction,"體積龐大，是學(xué)校的標(biāo)志性建筑，目前還在建設(shè)中。");</p><p>　　strcpy(G.vexs[2].name,"果園");</p><p>　　strcpy(G.vexs[2].introduction,

87、"枝葉茂盛，各種新鮮水果。");</p><p>　　strcpy(G.vexs[1].name,"校門");</p><p>　　strcpy(G.vexs[1].introduction,"學(xué)校的形象，氣勢宏偉。");</p><p>　　strcpy(G.vexs[4].name,"體育運(yùn)動(dòng)

88、區(qū)");</p><p>　　strcpy(G.vexs[4].introduction,"包括有排球場、籃球場、網(wǎng)球場等。");</p><p>　　strcpy(G.vexs[5].name,"教學(xué)區(qū)");</p><p>　　strcpy(G.vexs[5].introduction,"包括左教學(xué)樓、

89、小湖、右教學(xué)樓、實(shí)驗(yàn)樓和醫(yī)務(wù)室等。");</p><p>　　strcpy(G.vexs[10].name,"男生宿舍");</p><p>　　strcpy(G.vexs[10].introduction,"分1、2、7、8棟，供男同學(xué)居住，女生勿進(jìn)。");</p><p>　　strcpy(G.vexs[7].n

90、ame,"琴房");</p><p>　　strcpy(G.vexs[7].introduction,"音樂學(xué)院學(xué)生練琴的地方。");</p><p>　　strcpy(G.vexs[8].name,"足球場");</p><p>　　strcpy(G.vexs[8].introduction,"

91、踢球，跑步，運(yùn)動(dòng)比賽場地。");</p><p>　　strcpy(G.vexs[9].name,"省高速路");</p><p>　　strcpy(G.vexs[9].introduction,"上面是省高速路，下面是人行隧道。");</p><p>　　strcpy(G.vexs[11].name,"食

92、堂");</p><p>　　strcpy(G.vexs[11].introduction,"分1、2、3、4樓，價(jià)格有所不同，根據(jù)自己愛好，隨意點(diǎn)菜。");</p><p>　　strcpy(G.vexs[12].name,"女生宿舍");</p><p>　　strcpy(G.vexs[12].introduct

93、ion,"樓下一“愛心”超市，價(jià)格絕對不便宜。樓上女同學(xué)居住，男生勿進(jìn)。");</p><p>　　strcpy(G.vexs[13].name,"教師村");</p><p>　　strcpy(G.vexs[13].introduction,"老師們的居住地，10多樓高。");</p><p>　　//對

94、有路的各景點(diǎn)之間的路徑長度進(jìn)行設(shè)置,沒路的設(shè)置為無窮大</p><p>　　for(i=1;i<=G.vexnum;i++)</p><p>　　for(j=1;j<=G.vexnum;j++)</p><p>　　G.arcs[i][j].adj=INFINITY;</p><p>　　G.arcs[1][3].adj=100;

95、</p><p>　　G.arcs[1][2].adj=100;</p><p>　　G.arcs[1][5].adj=200;</p><p>　　G.arcs[2][4].adj=100;</p><p>　　G.arcs[2][3].adj=150;</p><p>　　G.arcs[3][5].adj=200;

96、</p><p>　　G.arcs[3][8].adj=300;</p><p>　　G.arcs[4][5].adj=100;</p><p>　　G.arcs[4][7].adj=150;</p><p>　　G.arcs[5][6].adj=100;</p><p>　　G.arcs[6][7].adj=150;

97、</p><p>　　G.arcs[6][8].adj=100;</p><p>　　G.arcs[7][9].adj=50;</p><p>　　G.arcs[8][9].adj=200;</p><p>　　G.arcs[8][13].adj=200;</p><p>　　G.arcs[9][10].adj=200

98、;</p><p>　　G.arcs[9][11].adj=150;</p><p>　　G.arcs[9][12].adj=200;</p><p>　　G.arcs[10][11].adj=100;</p><p>　　G.arcs[11][12].adj=150;</p><p>　　G.arcs[12][13]

99、.adj=150;</p><p>　　//無向圖的路徑是相互的</p><p>　　for(i=1;i<=G.vexnum;i++)</p><p>　　for(j=1;j<=G.vexnum;j++)</p><p>　　G.arcs[j][i].adj=G.arcs[i][j].adj;</p><p&g

100、t;<b>　　return G;</b></p><p>　　}//InitGraph end</p><p>　　//*******************************************************************</p><p>　　/*//菜單函數(shù)，打印出導(dǎo)游項(xiàng)目菜單</p><

101、p>　　void Menu()</p><p><b>　　{ </b></p><p>　　printf("\n 瓊州學(xué)院校園導(dǎo)游圖\n");</p><p>　　printf(" ┏

102、━━┳━━━━━━━━━━━━━━━━━━┓\n");</p><p>　　printf(" ┃編號(hào)┃ 實(shí) 現(xiàn) 的 功 能 ┃\n");</p><p>　　printf(" ┣━━╋━━━━━━━━━━━━━━

103、━━━━┫\n");</p><p>　　printf(" ┃ 1 ┃ 查 看 景 點(diǎn) 分 布 圖 ┃\n");</p><p>　　printf(" ┣━━╋━━━━━━━━━━━━━━━━━━┫\n");&l

104、t;/p><p>　　printf(" ┃ 2 ┃ 查 找 兩 景 點(diǎn) 間 最 短 距 離 ┃\n");</p><p>　　printf(" ┣━━╋━━━━━━━━━━━━━━━━━━┫\n");</p><p>　

105、　printf(" ┃ 3 ┃ 查 看 景 點(diǎn) 信 息 ┃\n");</p><p>　　printf(" ┣━━╋━━━━━━━━━━━━━━━━━━┫\n");</p><p>　　printf("

106、 ┃ 4 ┃ 退 出 系 統(tǒng) ┃\n");</p><p>　　printf(" ┗━━┻━━━━━━━━━━━━━━━━━━┛\n");</p><p>　　printf("輸入你的操作編號(hào)：")

107、;</p><p><b>　　}*/</b></p><p>　　//*******************************************************************</p><p>　　//輸出所有景點(diǎn)信息</p><p>　　void Browser(MGraph *G)<

108、;/p><p><b>　　{</b></p><p><b>　　int v;</b></p><p>　　printf("┏━━┳━━━━━━┓\n");</p><p>　　printf("┃編號(hào)┃景點(diǎn)名稱 ┃\n");</p><

109、p>　　for(v=1;v<=G->vexnum;v++){</p><p>　　printf("┃%-4d┃%-12s┃",G->vexs[v].num,G->vexs[v].name);</p><p>　　switch(v+2){</p><p>　　case 4:printf("

110、 瓊州學(xué)院校園導(dǎo)游圖\n");break;</p><p>　　case 5:printf(" ┏━━┳━━━━━━━━━━━━━━━━┓\n");break;</p><p>　　case 6:printf(" ┃編號(hào)┃ 實(shí) 現(xiàn) 的 功 能 ┃\n");break;</p>&l

111、t;p>　　case 7:printf(" ┣━━╋━━━━━━━━━━━━━━━━┫\n");break;</p><p>　　case 8:printf(" ┃ 1 ┃ 查 看 景 點(diǎn) 分 布 圖 ┃\n");break;</p><p>　　case 9:printf(" ┣━━╋━━━━━━━

112、━━━━━━━━━┫\n");break;</p><p>　　case 10:printf(" ┃ 2 ┃ 查 找 兩 景 點(diǎn) 間 最 短 距 離 ┃\n");break;</p><p>　　case 11:printf(" ┣━━╋━━━━━━━━━━━━━━━━┫\n");break;</p><p&

113、gt;　　case 12:printf(" ┃ 3 ┃ 查 看 景 點(diǎn) 信 息 ┃\n");break;</p><p>　　case 13:printf(" ┣━━╋━━━━━━━━━━━━━━━━┫\n");break;</p><p>　　case 14:printf(" ┃ 4 ┃ 退 出

114、系 統(tǒng) ┃\n");break;</p><p>　　case 15:printf(" ┗━━┻━━━━━━━━━━━━━━━━┛\n");break;</p><p>　　default:printf("\n");break;</p><p><b>　　}}&l

115、t;/b></p><p>　　printf("┗━━┻━━━━━━┛\n");</p><p>　　printf("輸入你的操作編號(hào)：");</p><p><b>　　}</b></p><p>　　//**********************************

116、*********************************</p><p>　　/*// 迪杰斯特拉算法來計(jì)算出起點(diǎn)到各個(gè)頂點(diǎn)之間的最短路徑,v0為起點(diǎn)</p><p>　　void ShortestPath_DIJ(MGraph * G)</p><p><b>　　{</b></p><p>　　int v,

117、w,i,min,t=0,x,flag=1,v0;</p><p>　　int final[20], D[20], p[20][20];</p><p>　　while(flag)</p><p><b>　　{</b></p><p>　　printf("請輸入一個(gè)起始景點(diǎn)編號(hào):");</p&g

118、t;<p>　　scanf("%d",&v0);</p><p>　　if(v0<=0||v0>G->vexnum)</p><p><b>　　{</b></p><p>　　printf("景點(diǎn)編號(hào)不存在!請重新輸入景點(diǎn)編號(hào):");</p><

119、;p>　　scanf("%d",&v0);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　if(v0>0&&v0<=G->vexnum)</p><p><b>

120、　　flag=0;</b></p><p><b>　　}</b></p><p>　　for(v=1;v<=G->vexnum;v++)</p><p><b>　　{</b></p><p>　　final[v]=0;</p><p>　　D[v]

121、=G->arcs[v0][v].adj;</p><p>　　for(w=1;w<=G->vexnum;w++)</p><p>　　p[v][w]=0;</p><p>　　if(D[v]<INFINITY)</p><p><b>　　{</b></p><p>　　p

122、[v][v0]=1;p[v][v]=1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　D[v0]=0;final[v0]=1;</p><p>　　for(i=1;i<=G->vexnum;i++)</p><p

123、><b>　　{</b></p><p>　　min=INFINITY;</p><p>　　for(w=1;w<=G->vexnum;w++)</p><p>　　if(!final[w])</p><p>　　if(D[w]<min){v=w;min=D[w];}</p><

124、;p>　　final[v]=1;</p><p>　　for(w=1;w<=G->vexnum;w++)</p><p>　　if(!final[w]&&(min+G->arcs[v][w].adj<D[w]))</p><p><b>　　{</b></p><p>　　D

125、[w]=min+G->arcs[v][w].adj;</p><p>　　for(x=1;x<=G->vexnum;x++) </p><p>　　p[w][x]=p[v][x];</p><p>　　p[w][w]=1;</p><p><b>　　}</b></p><p>

126、<b>　　}</b></p><p>　　for(v=1;v<=G->vexnum;v++)</p><p><b>　　{</b></p><p>　　if(v0!=v) printf("%s",G->vexs[v0].name);</p><p>　　fo

127、r(w=v0;w>0;w--)</p><p><b>　　{</b></p><p>　　p[v][v0-v]=0;</p><p>　　if(p[v][w]&&w!=v0) printf("-->%s",G->vexs[w].name);</p><p><

128、;b>　　t++;</b></p><p>　　printf("yyyy");</p><p><b>　　}</b></p><p>　　for(w=v0-1;w<=G->vexnum;w++)</p><p><b>　　{</b></p&

129、gt;<p>　　if(p[v][w]&&w!=v0) printf("-->%s",G->vexs[w].name);</p><p><b>　　t++;</b></p><p>　　printf("xxxx");</p><p><b>　　}&

130、lt;/b></p><p>　　if(t>G->vexnum-1&&v0!=v)printf(" 總路線長%dm\n\n",D[v]);</p><p><b>　　}</b></p><p>　　}//ShortestPath_DIJ end*/</p>&l

131、t;p>　　//*******************************************************************</p><p>　　void Floyd(MGraph *G)</p><p><b>　　{</b></p><p>　　int v,u,i,w,k,j,flag=1,p[14][14]