基于無(wú)向圖的校園導(dǎo)游系統(tǒng)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

1、重慶科技學(xué)院本科生課程設(shè)計(jì) 摘要重慶科技學(xué)院課程設(shè)計(jì)報(bào)告 院（系）:_電氣與信息工程學(xué)院 專業(yè)班級(jí): 計(jì)科普0902 設(shè)計(jì)地點(diǎn)（單位）_計(jì)算機(jī)基礎(chǔ)自主學(xué)習(xí)中心i306_設(shè)計(jì)題目:_校園導(dǎo)游咨詢_重慶科技學(xué)院課程設(shè)計(jì)任務(wù)書設(shè)計(jì)題目：校園導(dǎo)游咨詢學(xué)生姓名課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)專業(yè)班級(jí)計(jì)科2009-02地 點(diǎn)計(jì)算機(jī)基礎(chǔ)自主學(xué)習(xí)中心起止時(shí)間設(shè)計(jì)內(nèi)容及要求基本要求:（1）設(shè)計(jì)你的學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)。以圖中頂點(diǎn)表示學(xué)校各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度等相關(guān)信息。（2）為來(lái)訪客人提供圖中任意景點(diǎn)的問(wèn)路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑。

2、（3）為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。測(cè)試數(shù)據(jù)：由讀者根據(jù)實(shí)際情況指定。實(shí)現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個(gè)無(wú)向網(wǎng)。頂點(diǎn)和邊均含有相關(guān)信息。擴(kuò)展要求：（1）提供圖中任意景點(diǎn)問(wèn)路查詢，即求任意兩個(gè)景點(diǎn)之間的所有路徑。（2）擴(kuò)充道路信息，如道路類別（車道、人行道等）、沿途景色等級(jí)，以至可按客人所需分別查詢?nèi)诵新窂交蜍囆新窂交蛴^景路徑等設(shè)計(jì)參數(shù)1、 自己編寫程序，校園初始數(shù)據(jù)以文本文件保存，文件格式根據(jù)需要自行定義。對(duì)應(yīng)的地圖初始化從文件中讀出數(shù)據(jù)進(jìn)行初始化。2、 查詢的結(jié)果應(yīng)提供屏幕和文件兩種方式。3、 有基礎(chǔ)的同學(xué)盡量實(shí)現(xiàn)界面的可視化操作和動(dòng)態(tài)顯示。進(jìn)度要

3、求2011.1.4 星期二（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、完成任務(wù)的講解、并接受課程設(shè)計(jì)任務(wù)，選定課程設(shè)計(jì)的題目2011.1.5 星期三（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、了解任務(wù)的算法、并畫出算法的程序流程圖2011.1.6 星期四（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、對(duì)任務(wù)的關(guān)鍵技術(shù)進(jìn)行驗(yàn)證、并確定解決辦法2011.1.7 星期五（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、編制任務(wù)的程序2011.1.10 星期一（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、編制任務(wù)的程序2011.1.11 星期二（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、對(duì)程序的調(diào)試，并試運(yùn)行。2011.1.12 星期三（上午教師指導(dǎo)，下午學(xué)生

4、獨(dú)立完成）、整理課程設(shè)計(jì)過(guò)程中的各個(gè)參數(shù)、并進(jìn)行總結(jié)，提出改進(jìn)意見2011.1.13 星期四（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、編寫課程設(shè)計(jì)報(bào)告、準(zhǔn)備答辨2011.1.14 星期五（上午答辨）、進(jìn)行答辨驗(yàn)收工作。參考資料1嚴(yán)蔚敏 吳偉民 著， 數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版），清華大學(xué)出版社，2007.42. richard f.gilberg behrouz a.forouzan, data structures a pseudocode approach with c，second edition, thomson, 2005.13. 李春葆 著，數(shù)據(jù)結(jié)構(gòu)教程，清華大學(xué)出版社，2005.1其它說(shuō)明.本

5、表應(yīng)在每次實(shí)施前一周由負(fù)責(zé)教師填寫二份，院系審批后交院系辦備案，一份由負(fù)責(zé)教師留用。.若填寫內(nèi)容較多可另紙附后。3.一題多名學(xué)生共用的，在設(shè)計(jì)內(nèi)容、參數(shù)、要求等方面應(yīng)有所區(qū)別。教研室主任： 指導(dǎo)教師：向毅、陳劉奎、熊茜 2010年 12 月 20日重慶科技學(xué)院本科生課程設(shè)計(jì) 摘要重慶科技學(xué)院本科生課程設(shè)計(jì) 摘要重慶科技學(xué)院本科生課程設(shè)計(jì) 摘要摘要現(xiàn)代快節(jié)奏的生活使得都市人越來(lái)越渴望親近自然，因此外出旅游現(xiàn)在被越來(lái)越多的都市人所看中，所以如何快速方便的找到我們想要的旅游景點(diǎn)的信息和最短路徑就成了一個(gè)很重要的問(wèn)題。本設(shè)計(jì)基于圖的結(jié)構(gòu)，創(chuàng)建一個(gè)無(wú)向圖，針對(duì)游客的實(shí)際需求，將重慶科技學(xué)院的景點(diǎn)編號(hào)、名

6、稱、介紹等信息放入到圖的頂點(diǎn)當(dāng)中并保存在景點(diǎn)文本文件當(dāng)中，將兩個(gè)景點(diǎn)的編號(hào)和它們之間的距離當(dāng)作權(quán)值也保存到權(quán)值文本文件當(dāng)中，利用迪杰斯特拉算法來(lái)求從一個(gè)景點(diǎn)到另一個(gè)景點(diǎn)的最短距離，利用strcmp();函數(shù)來(lái)查找景點(diǎn)，并顯示出它的信息，從而解決了要查找景點(diǎn)信息和景點(diǎn)之間的最短路徑的問(wèn)題，最后按照顯示屏上的提示進(jìn)行相關(guān)的操作。關(guān)鍵詞：無(wú)向圖、查找信息、最短距離、校園導(dǎo)游咨詢重慶科技學(xué)院本科生課程設(shè)計(jì) 目錄目錄摘要i1 設(shè)計(jì)內(nèi)容和要求11.1設(shè)計(jì)內(nèi)容11.1設(shè)計(jì)要求12 概要設(shè)計(jì)22.1 程序的模塊圖22.2 主函數(shù)的概要設(shè)計(jì)32.3 查找介紹函數(shù)的概要設(shè)計(jì)32.4 查找最短路徑函數(shù)的概要設(shè)計(jì)32

7、.5 退出函數(shù)的概要設(shè)計(jì)33 詳細(xì)設(shè)計(jì)43.1 程序的流程圖43.2 主函數(shù)的詳細(xì)設(shè)計(jì)53.3 查找介紹函數(shù)的詳細(xì)設(shè)計(jì)53.4 查找最短路徑函數(shù)的詳細(xì)設(shè)計(jì)63.5 退出函數(shù)的詳細(xì)設(shè)計(jì)83.6 數(shù)據(jù)結(jié)構(gòu)的詳細(xì)設(shè)計(jì)84 軟件測(cè)試104.1 菜單的測(cè)試104.2 查找景點(diǎn)簡(jiǎn)介的測(cè)試104.3 查找兩個(gè)景點(diǎn)之間的最短距離的測(cè)試114.4 退出的測(cè)試115 軟件使用說(shuō)明126 致謝137 參考文獻(xiàn)148 附錄15重慶科技學(xué)院本科生課程設(shè)計(jì) 設(shè)計(jì)內(nèi)容和要求1 設(shè)計(jì)內(nèi)容和要求1.1設(shè)計(jì)內(nèi)容依據(jù)課程設(shè)計(jì)的要求，利用一個(gè)無(wú)向圖的結(jié)構(gòu)，將景點(diǎn)當(dāng)作圖的頂點(diǎn)，將景點(diǎn)之間的距離當(dāng)作權(quán)值來(lái)儲(chǔ)存，然后根據(jù)游客自己的需求，按

8、照顯示屏上的提示來(lái)進(jìn)行查找景點(diǎn)介紹，查找兩個(gè)景點(diǎn)之間的最短距離，退出程序等基本操作。1.1設(shè)計(jì)要求本軟件為校園導(dǎo)游咨詢系統(tǒng)，根據(jù)游客的實(shí)際需求而設(shè)計(jì)，首先創(chuàng)建一個(gè)無(wú)向圖，然后從文件當(dāng)中讀取所有景點(diǎn)的編號(hào)、名稱、介紹和兩點(diǎn)之間的權(quán)值，并將它們寫入到無(wú)向圖當(dāng)中。功能主要包括查找已知景點(diǎn)的信息，查找從一個(gè)景點(diǎn)到另一個(gè)景點(diǎn)的最短路徑，退出等基本操作。軟件的界面要求使用vc+6.0的運(yùn)行環(huán)境。軟件的數(shù)據(jù)庫(kù)包括校園景點(diǎn)的編號(hào)、名稱、介紹和兩個(gè)景點(diǎn)之間的距離（權(quán)值），首先要定義頂點(diǎn)的數(shù)據(jù)類型結(jié)構(gòu)體，里面包括景點(diǎn)的編號(hào)、名稱、介紹，然后定義一個(gè)鄰接矩陣結(jié)構(gòu)體來(lái)儲(chǔ)存邊的信息，最后定義一個(gè)無(wú)向圖類型的結(jié)構(gòu)體來(lái)儲(chǔ)存

9、頂點(diǎn)的信息，邊的信息，頂點(diǎn)的個(gè)數(shù)，邊的個(gè)數(shù)。最后游客按照顯示屏上的提示來(lái)進(jìn)行相關(guān)的操作。1重慶科技學(xué)院本科生課程設(shè)計(jì) 概要設(shè)計(jì)2 概要設(shè)計(jì)2.1 程序的模塊圖本軟件的算法依據(jù)無(wú)向圖的操作通過(guò)查找函數(shù)查找景點(diǎn)的信息，通過(guò)迪杰斯特拉函數(shù)來(lái)查找最短距離，開始時(shí)首先從文件當(dāng)中讀取景點(diǎn)的編號(hào)、名稱、介紹和兩個(gè)景點(diǎn)之間的距離即權(quán)值，然后將其加入到圖當(dāng)中，再調(diào)用查找函數(shù)查找景點(diǎn)的信息，調(diào)用迪杰斯特拉函數(shù)來(lái)查找最短距離，調(diào)用退出函數(shù)實(shí)現(xiàn)退出功能，其模塊圖如圖2.5所示：開始文件讀取加入圖退出最短距離查找信息屏幕顯示屏幕顯示圖2.5模塊圖2.2 主函數(shù)的概要設(shè)計(jì)基于程序的操作要求，對(duì)于主函數(shù)的設(shè)計(jì)首先是顯示一個(gè)

10、可視化的操作界面提醒游客進(jìn)行相關(guān)的操作和提示游客其可供選擇的景點(diǎn)的名稱，便于其在后面的操作過(guò)程當(dāng)中能夠快速方便的找到其需要查找的景點(diǎn)的名稱。而后就是一個(gè)switch（）；的選擇函數(shù)，提供查找景點(diǎn)信息，查找兩個(gè)景點(diǎn)之間的最短距離和退出的相關(guān)的選擇操作而后進(jìn)入到每一個(gè)操作界面當(dāng)中，從而實(shí)現(xiàn)所需要的功能。2.3 查找介紹函數(shù)的概要設(shè)計(jì)當(dāng)游客選擇了要查找景點(diǎn)的信息的介紹這一項(xiàng)功能的時(shí)候，就會(huì)進(jìn)入到查找的界面，對(duì)于查找景點(diǎn)信息就是利用strcmp（）；函數(shù)，當(dāng)游客輸入景點(diǎn)的名稱的時(shí)候看其是否與文件當(dāng)中的數(shù)據(jù)相匹配，如果有則輸出它的介紹，如果沒(méi)有則輸出錯(cuò)誤的提示提醒游客進(jìn)行相關(guān)的操作來(lái)進(jìn)入到正確的操作過(guò)程

11、當(dāng)中。2.4 查找最短路徑函數(shù)的概要設(shè)計(jì)對(duì)于查找最短路徑的這一項(xiàng)功能，則是利用迪杰斯特拉函數(shù)(1)假設(shè)用帶權(quán)的鄰接矩陣arcs來(lái)表示帶權(quán)的有向圖，arcsij表示弧（vi,vj）上的權(quán)值。若(vi,vj)不存在，則置arcsij為無(wú)窮大。s為已找到從v出發(fā)的最短路徑的終點(diǎn)集合，它的初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各個(gè)定點(diǎn)vi可能到達(dá)的最短路徑長(zhǎng)度的初始值為：di = arcsvi;(2)選擇vj,使得dj = mindi | vi v svj就是當(dāng)前求得的一條從v出發(fā)的最短路徑的終點(diǎn)。令s = s j;(3)修改從v出發(fā)到集合v s 上任意頂點(diǎn)vk可到達(dá)的最短路徑的長(zhǎng)度。如果dj +

12、arcsjk dk則修改dk為dk = dj+arcsjk;(4)重復(fù)操作(2)、(3)共n 1 次，由此求得從v到圖上其余各個(gè)頂點(diǎn)的最短路徑是依路徑長(zhǎng)度遞增的序列。從而求得了從一個(gè)景點(diǎn)到另一個(gè)景點(diǎn)的最短路徑的問(wèn)題。2.5 退出函數(shù)的概要設(shè)計(jì)關(guān)于退出函數(shù)，則是當(dāng)游客執(zhí)行完了他想要進(jìn)行的操作過(guò)后選擇退出的功能的時(shí)候就調(diào)用退出函數(shù)exit(0);跳入到退出界面實(shí)現(xiàn)退出的功能。3重慶科技學(xué)院本科生課程設(shè)計(jì) 詳細(xì)設(shè)計(jì)3 詳細(xì)設(shè)計(jì)3.1 程序的流程圖當(dāng)我們想要更加實(shí)際的了解一個(gè)程序的算法過(guò)程的時(shí)候，我們就要依據(jù)程序的流程圖來(lái)給我們一個(gè)比較實(shí)際的過(guò)程，從流程圖當(dāng)中能夠更加清楚整個(gè)程序?qū)崿F(xiàn)的過(guò)程是怎樣的。其

13、流程圖如圖3.1所示：start讀取文件信息創(chuàng)建無(wú)向圖寫入無(wú)向圖中case icase pcase q查找信息end最短路徑ttff圖3.1流程圖3.2 主函數(shù)的詳細(xì)設(shè)計(jì)主函數(shù)是一個(gè)程序的主體，當(dāng)我們要進(jìn)行我們所需要的操作的時(shí)候我們就要根據(jù)主函數(shù)中的顯示信息和它給我們的相關(guān)的提示信息來(lái)進(jìn)行所需要的操作，因此在這次的程序?qū)崿F(xiàn)的過(guò)程當(dāng)中，首先調(diào)用createudn(g);函數(shù)創(chuàng)建一個(gè)無(wú)向圖，然后利用一個(gè)for();循環(huán)語(yǔ)句for(int k = 0; k g.vexnum; k+)if(k - 5 = 0)coutendl;couttg.;elsecouttg.vexsk.na

14、me;將景點(diǎn)的名稱打印在顯示屏上，最后是一個(gè)switch();的選擇語(yǔ)句，提示游客根據(jù)選擇來(lái)進(jìn)入到相關(guān)的操作界面實(shí)現(xiàn)程序的基本功能。3.3 查找介紹函數(shù)的詳細(xì)設(shè)計(jì)當(dāng)游客選擇了要查找景點(diǎn)的信息的介紹這一項(xiàng)功能的時(shí)候，程序就會(huì)調(diào)用disintroduction(g);函數(shù)進(jìn)入到查找景點(diǎn)的介紹的界面，當(dāng)游客輸入了需要查找的景點(diǎn)的名稱的時(shí)候，程序利用for();循環(huán)語(yǔ)句來(lái)查找是否有這個(gè)景點(diǎn)for(int i=0;ig.vexnum;i+)int m = strcmp(g.,n1);if(m=0)v1=i;count1=count1+1;，找到將它的編號(hào)返回，并輸出它的介紹，沒(méi)有找到

15、這輸出錯(cuò)誤提示，提醒游客進(jìn)行相關(guān)的操作進(jìn)入正確的操作過(guò)程當(dāng)中。3.4 查找最短路徑函數(shù)的詳細(xì)設(shè)計(jì)當(dāng)游客選擇了要查找兩個(gè)景點(diǎn)之間的最短距離這一項(xiàng)功能的時(shí)候，程序就會(huì)調(diào)用dispath(g)；函數(shù)進(jìn)入到查找兩個(gè)景點(diǎn)之間的最短距離的操作界面當(dāng)中，當(dāng)游客輸入了兩個(gè)景點(diǎn)的名稱過(guò)后，程序會(huì)調(diào)用strcmp();函數(shù)查看是否有這兩個(gè)景點(diǎn)，如果有則返回他們各自的編號(hào)，并調(diào)用shortpath_dij(g,v1,v2);函數(shù)進(jìn)入到查找最短路徑問(wèn)題的程序當(dāng)中。for(v=0;vg.vexnum;v+)/各對(duì)節(jié)點(diǎn)之間初始已知路徑及距離finalv=false;/從v出發(fā)的最短路徑的空集合dv=g.arcsv0v;/

16、從v出發(fā)到圖上其余各個(gè)定點(diǎn)v0可能到達(dá)的最短路徑的初始值for(w=0;wg.vexnum;w+)pvw=false;/設(shè)空路徑if(dvmaxnum)pvv0=true;pvv=true;dv0=0;finalv0=true;int a20;for(i=0;ig.vexnum;i+)/對(duì)pathij進(jìn)行初始化，使其值全部為1000，便于后期的判斷for(j=0;jg.vexnum;j+)pathij=1000;for(i=0;ig.vexnum;i+)/對(duì)數(shù)組進(jìn)行初始化，以便對(duì)pathij進(jìn)行描述ai=1;for(v=0;vg.vexnum;v+)/各條路線的初始節(jié)點(diǎn)為v0pathv0=v0

17、;/開始主循環(huán)，每次求解得到v0到某個(gè)v頂點(diǎn)的最短路徑，并加入到s集合中for(i=1;ig.vexnum;i+)/其余g.vexnum - 1個(gè)頂點(diǎn)m=maxnum;/當(dāng)前所知的離v0最近的距離for(w=0;wg.vexnum;w+)if(!finalw)/w頂點(diǎn)在v-s中if(dwm)/w頂點(diǎn)離v0頂點(diǎn)更近v=w;m=dw;pathvav=v;/離v0頂點(diǎn)最近的v加入s集合finalv=true;for(w=0;wg.vexnum;w+)/更新當(dāng)前最短路徑及距離if(!finalw)&(m+g.arcsvwdw)dw=m+g.arcsvw;/修改當(dāng)前的最短路徑的值int k0=1;aw=

18、1;while(pathvk0!=1000)/如果上述條件成立，pathw路徑需要改變，因?yàn)閺膙0到w的路徑顯然經(jīng)過(guò)了v0和v之間的所有的點(diǎn)（包括v）pathwk0=pathvk0;k0+;aw+;cout兩個(gè)景點(diǎn)之間的最短路徑為:t;int k=0;while(pathv2k!=1000)int m=pathv2k;coutg.t;k+;coutendl;cout兩個(gè)景點(diǎn)之間的最短距離為: dv2mendl;cout請(qǐng)選擇要進(jìn)行的操作(i:查詢景點(diǎn)信息，p:查詢兩個(gè)景點(diǎn)之間的最短路徑，q:退出)endl;(1)假設(shè)用帶權(quán)的鄰接矩陣arcs來(lái)表示帶權(quán)的有向圖，arcsij表

19、示弧（vi,vj）上的權(quán)值。若(vi,vj)不存在，則置arcsij為無(wú)窮大。s為已找到從v出發(fā)的最短路徑的終點(diǎn)集合，它的初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各個(gè)定點(diǎn)vi可能到達(dá)的最短路徑長(zhǎng)度的初始值為：di = arcsvi;(2)選擇vj,使得dj = mindi | vi v svj就是當(dāng)前求得的一條從v出發(fā)的最短路徑的終點(diǎn)。令s = s j;(3)修改從v出發(fā)到集合v s 上任意頂點(diǎn)vk可到達(dá)的最短路徑的長(zhǎng)度。如果dj + arcsjk dk則修改dk為dk = dj+arcsjk;(4)重復(fù)操作(2)、(3)共n 1 次，由此求得從v到圖上其余各個(gè)頂點(diǎn)的最短路徑是依路徑長(zhǎng)度遞增的

20、序列。從而求得了從一個(gè)景點(diǎn)到另一個(gè)景點(diǎn)的最短路徑的問(wèn)題。3.5 退出函數(shù)的詳細(xì)設(shè)計(jì)對(duì)于退出函數(shù)，當(dāng)游客選擇了退出這一個(gè)操作的時(shí)候，程序就會(huì)調(diào)用exit();函數(shù)從而進(jìn)入到退出函數(shù)的界面void exit() /退出cout歡迎下次繼續(xù)使用!endl;exit(0);程序會(huì)提示游客感謝使用，歡迎下次繼續(xù)使用的提示語(yǔ)，然后調(diào)用exit(0);函數(shù)實(shí)現(xiàn)退出主函數(shù)的功能。3.6 數(shù)據(jù)結(jié)構(gòu)的詳細(xì)設(shè)計(jì)本軟件的數(shù)據(jù)結(jié)構(gòu)包括3個(gè)部分：1. 鄰接矩陣typedef int adjmatrixmax_vertex_nummax_vertex_num;定義一個(gè)鄰接矩陣，用鄰接矩陣來(lái)定義和儲(chǔ)存邊的相關(guān)信息。2. 頂點(diǎn)

21、的結(jié)構(gòu)體typedef struct vertex/定義圖中頂點(diǎn)的數(shù)據(jù)類型int num;/景點(diǎn)編號(hào)char name14;/景點(diǎn)名稱char introduction100;/景點(diǎn)介紹vertex;定義一個(gè)頂點(diǎn)的結(jié)構(gòu)體，用來(lái)儲(chǔ)存景點(diǎn)的編號(hào)、景點(diǎn)得名稱和景點(diǎn)的介紹等關(guān)于景點(diǎn)的信息。3.無(wú)向圖的結(jié)構(gòu)體typedef struct /定義圖的數(shù)據(jù)類型vertex vexsmax_vertex_num;/頂點(diǎn)的結(jié)構(gòu)體adjmatrix arcs;/邊的鄰接矩陣int vexnum,arcnum;/頂點(diǎn)的個(gè)數(shù)，邊的個(gè)數(shù)mgraph;定義一個(gè)圖的結(jié)構(gòu)體，用來(lái)儲(chǔ)存頂點(diǎn)的信息、邊的信息、頂點(diǎn)的個(gè)數(shù)和邊的個(gè)數(shù)

22、等相關(guān)的信息便于我們以后在用的時(shí)候能夠方便快捷的調(diào)用。定義好這些結(jié)構(gòu)體后，當(dāng)我們以后需要調(diào)用的時(shí)候，我們就能夠方便快捷的調(diào)用這些結(jié)構(gòu)體，從而使得我們?cè)谶\(yùn)行程序的時(shí)候能夠更加的快速能夠提高我們的程序的運(yùn)行效率，大大的節(jié)省了我們的時(shí)間還使得程序變得更加的簡(jiǎn)單。9重慶科技學(xué)院本科生課程設(shè)計(jì) 軟件測(cè)試4 軟件測(cè)試4.1 菜單的測(cè)試對(duì)于菜單函數(shù)的測(cè)試，首先菜單是一個(gè)可示化的界面，它能夠提示游客依據(jù)顯示屏上出現(xiàn)的提示來(lái)進(jìn)行相關(guān)的操作，查看所有的景點(diǎn)從而方便游客進(jìn)行相關(guān)的操作，因而我們?cè)谶\(yùn)行程序的時(shí)候首先就會(huì)進(jìn)入到菜單函數(shù)當(dāng)中，經(jīng)過(guò)測(cè)試其能夠?qū)崿F(xiàn)我們所要實(shí)現(xiàn)得基本功能，其效果圖如圖4.1所示：圖4.1菜單4

23、.2 查找景點(diǎn)簡(jiǎn)介的測(cè)試對(duì)于查找景點(diǎn)的介紹的測(cè)試，首先依據(jù)顯示屏上的提示首先輸入要進(jìn)行的操作輸入i進(jìn)入查找景點(diǎn)信息的操作界面，然后輸入需要查找的景點(diǎn)的名稱即可顯示出景點(diǎn)的介紹信息，經(jīng)過(guò)測(cè)試可以得出其沒(méi)有什么錯(cuò)誤，程序能夠按照我的要求實(shí)現(xiàn)它的功能，其效果圖如圖4.2所示：圖4.2查找景點(diǎn)信息4.3 查找兩個(gè)景點(diǎn)之間的最短距離的測(cè)試同查找景點(diǎn)的信息一樣，對(duì)于查找景點(diǎn)之間的最短距離的測(cè)試，我們就要依據(jù)提示輸入p進(jìn)入到查詢最短路徑的界面，依次輸入所需要查找的兩個(gè)景點(diǎn)就會(huì)顯示出怎樣到達(dá)這兩個(gè)景點(diǎn)并顯示出它們之間的最短路徑，經(jīng)過(guò)測(cè)試可見程序能夠按照我的要求來(lái)實(shí)現(xiàn)其所需要的功能，其效果圖如圖4.3所示：圖4

24、.3查找兩個(gè)景點(diǎn)之間的最短距離4.4 退出的測(cè)試原理同上，對(duì)于退出函數(shù)的測(cè)試，我需要依據(jù)顯示屏上的提示，首先需要輸入q進(jìn)入到退出的界面，系統(tǒng)就會(huì)直接調(diào)用退出的函數(shù)，顯示出“歡迎下次繼續(xù)使用！”的話讓后按任意鍵就退出了系統(tǒng)，其效果圖如圖4.4所示：圖4.4退出界面115 軟件使用說(shuō)明對(duì)于軟件的使用，對(duì)于第一次使用軟件的游客來(lái)說(shuō)，要讓他們?cè)诘谝淮斡玫臅r(shí)候就能夠快速輕松的掌握軟件的用法，因此在程序一開始運(yùn)行的時(shí)候，我們要進(jìn)行如下的操作：（1）首先我會(huì)給游客提供一個(gè)可視化的菜單操作界面，在顯示屏上提示用戶其可以進(jìn)行的操作和他能夠查詢的景點(diǎn)的名稱。（2）用戶輸入了“i”后，進(jìn)入到查詢景點(diǎn)簡(jiǎn)介的界面，當(dāng)用

25、戶輸入了想要查找的景點(diǎn)的名稱過(guò)后就會(huì)顯示出這個(gè)景點(diǎn)的介紹來(lái)。（3）當(dāng)用戶輸入了“p”后，進(jìn)入到查詢最短路徑的界面，然后依據(jù)提示用戶依次輸入兩個(gè)景點(diǎn)的名稱，程序就會(huì)將這兩個(gè)景點(diǎn)的最短路徑給我們表示出來(lái)并顯示出最短路徑是多少。（4）當(dāng)用戶輸入了“q”后，進(jìn)入到退出界面，這是系統(tǒng)就會(huì)提示用戶程序?qū)⒁\(yùn)行結(jié)束，歡迎下次繼續(xù)使用的提示語(yǔ)，最后按下任意鍵程序結(jié)束。重慶科技學(xué)院本科生課程設(shè)計(jì) 致謝6 致謝在本次的實(shí)驗(yàn)過(guò)程當(dāng)中，雖然有各種各樣的問(wèn)題在困擾著我，但是好在我的身邊總會(huì)有人在這個(gè)時(shí)候出現(xiàn)為我解決這些問(wèn)題，而他們就是我的老師和同學(xué)們，一個(gè)人做事的時(shí)候總是會(huì)遇到問(wèn)題的，有問(wèn)題并不可怕只要我們相信我們不是

26、一個(gè)人在戰(zhàn)斗而是有很多的同學(xué)和老師與我們站在一起的這樣我們就能夠戰(zhàn)勝各種困難，感謝我的老師和我的同學(xué)們。是他們?cè)谖矣龅絾?wèn)題的時(shí)候給我指明了解決的方法，從而克服了一個(gè)又一個(gè)的問(wèn)題最終解決了所有的問(wèn)題實(shí)現(xiàn)了程序所需要的功能，感謝我的同學(xué)們，不論是上課還是下課，只要是遇到了困難找到他們的時(shí)候只要是能夠解決的他們會(huì)義不容辭的獻(xiàn)出自己的力量。感謝老師們的諄諄教誨，他們不辭辛勞為了我們能夠順利的解決問(wèn)題無(wú)時(shí)無(wú)刻不在我們的身邊，當(dāng)我們一遇到問(wèn)題的時(shí)候他就會(huì)出現(xiàn)，從沒(méi)有半點(diǎn)怨言。最后還要感謝學(xué)校感謝給我們提供了良好的實(shí)驗(yàn)環(huán)境，使我們能夠安心輕松的在好的額環(huán)境當(dāng)中完成我們的實(shí)驗(yàn)。 簽名 周 楊 日期 2011年

27、1月13日14重慶科技學(xué)院本科生課程設(shè)計(jì) 參考文獻(xiàn)7 參考文獻(xiàn)【1】 數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版) 嚴(yán)蔚敏 吳偉民 編著 清華大學(xué)出版社 2002【2】 c程序設(shè)計(jì)經(jīng)典教程，美deitel,h.m.，美deitel,p.j.著，清華大學(xué)出版社 2006【3】 windows程序設(shè)計(jì)，美 charles petzold 著，北京大學(xué)出版社 2004【4】 data structures：a pseudecode（approach with c）美richard f.gilberg，美behrouz a.forouzan著15重慶科技學(xué)院本科生課程設(shè)計(jì) 附錄8 附錄main.cpp#include#inc

28、lude#include#include graphadt.husing namespace std;void main()mgraph g;createudn(g);int i = 0;char choice10;coutt*歡迎使用重慶科技學(xué)院校園導(dǎo)游程序*endl;coutt_endl;coutt*景點(diǎn)名稱*endl;for(int k = 0; k g.vexnum; k+)if(k - 5 = 0)coutendl;couttg.;elsecouttg.;coutnt_nendl;cout請(qǐng)選擇要進(jìn)行的操作(i:查詢景點(diǎn)信息，p:查詢兩個(gè)景點(diǎn)之

29、間的最短路徑，q:退出)choicei;switch(choicei)case i:case i:disintroduction(g);break;case p:case p:dispath(g);break;case q:case q:exit();break;creatudn.h#include#include#include#define maxnum 10000#define vertex 10#define edges 13using namespace std;void createudn(mgraph &g)/創(chuàng)建一個(gè)圖ifstream in_file(view.txt,ios:

30、in);/從view.txt中讀入景點(diǎn)的相關(guān)信息if(!in_file)exit(-1);int i,j,k,w;g.vexnum = vertex;g.arcnum = edges;for(i=0;ig.vexsi.numg.g.roduction;for(i=0;ig.vexnum;i+)/初始化矩陣for(j=0;jg.vexnum;j+)g.arcsij=maxnum;ifstream weight_file(weight.txt,ios:in);/從weight.txt中讀入權(quán)重的值if(!weight_file)exit(-1);for(k=0

31、;kijw;g.arcsij=w;g.arcsji=g.arcsij;disintroduction.hvoid disintroduction(mgraph g)/提供景點(diǎn)的信息char n120;int v1;cout請(qǐng)輸入所要查詢的景點(diǎn)的名稱:n1;int count1=0;for(int i=0;ig.vexnum;i+)int m = strcmp(g.,n1);if(m=0)v1=i;count1=count1+1;if(count1!=1)cout您輸入的名稱有誤!endl;cout請(qǐng)選擇要進(jìn)行的操作(i:查詢景點(diǎn)信息，p:查詢兩個(gè)景點(diǎn)之間的最短路徑，q:退出

32、)endl;else cout該景點(diǎn)的簡(jiǎn)介為:tg.roductionendl;cout請(qǐng)選擇要進(jìn)行的操作(i:查詢景點(diǎn)信息，p:查詢兩個(gè)景點(diǎn)之間的最短路徑，q:退出)endl;dispath.hvoid dispath(mgraph g)/查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑int v1,v2;char n120,n220;cout請(qǐng)輸入要查詢的最短路徑的兩個(gè)頂點(diǎn)名稱:n1n2;int count=0;for(int i=0;ig.vexnum;i+)int m1= strcmp(g.,n1);int m2= strcmp(g.

33、,n2);if(m1=0)v1=i;count+;else if(m2=0)v2=i;count+;if(count!=2)cout您輸入的名稱有誤!endl;cout請(qǐng)選擇要進(jìn)行的操作(i:查詢景點(diǎn)信息，p:查詢兩個(gè)景點(diǎn)之間的最短路徑，q:退出)endl;shortpath_dij(g,v1,v2);exit.hvoid exit() /退出cout歡迎下次繼續(xù)使用!endl;exit(0);graphadt.h#include graphtypedef.h#include createudn.h#include shortpath.h#include disintroduction.h#i

34、nclude dispath.h#include exit.hgraphtypedef.h#define max_vertex_num 10typedef int adjmatrixmax_vertex_nummax_vertex_num;typedef struct vertex/定義圖中頂點(diǎn)的數(shù)據(jù)類型int num;char name14;char introduction100;vertex;typedef struct /定義圖的數(shù)據(jù)類型vertex vexsmax_vertex_num;adjmatrix arcs;int vexnum,arcnum;mgraph;void createudn(mgraph &g);void shortpath_dij(mgraph g,int v0,int v2);void disintroduction(mgraph g);void dispath(mgraph g);void exit();shortpath.h#inclu