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

重慶科技學(xué)院本科生課程設(shè)計 摘要重慶科技學(xué)院課程設(shè)計報告 院（系）:_電氣與信息工程學(xué)院 專業(yè)班級: 計科普0902 設(shè)計地點(diǎn)（單位）_計算機(jī)基礎(chǔ)自主學(xué)習(xí)中心I306_設(shè)計題目:_校園導(dǎo)游咨詢_重慶科技學(xué)院課程設(shè)計任務(wù)書設(shè)計題目：校園導(dǎo)游咨詢學(xué)生姓名課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計專業(yè)班級計科2009-02地 點(diǎn)計算機(jī)基礎(chǔ)自主學(xué)習(xí)中心起止時間設(shè)計內(nèi)容及要求基本要求:（1）設(shè)計你的學(xué)校的校園平面圖，所含景點(diǎn)不少于10個。以圖中頂點(diǎn)表示學(xué)校各景點(diǎn)，存放景點(diǎn)名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。（2）為來訪客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€景點(diǎn)之間的一條最短的簡單路徑。 （3）為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。測試數(shù)據(jù)：由讀者根據(jù)實(shí)際情況指定。實(shí)現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個無向網(wǎng)。頂點(diǎn)和邊均含有相關(guān)信息。擴(kuò)展要求：（1）提供圖中任意景點(diǎn)問路查詢，即求任意兩個景點(diǎn)之間的所有路徑。（2）擴(kuò)充道路信息，如道路類別（車道、人行道等）、沿途景色等級，以至可按客人所需分別查詢?nèi)诵新窂交蜍囆新窂交蛴^景路徑等設(shè)計參數(shù)1、 自己編寫程序，校園初始數(shù)據(jù)以文本文件保存，文件格式根據(jù)需要自行定義。對應(yīng)的地圖初始化從文件中讀出數(shù)據(jù)進(jìn)行初始化。2、 查詢的結(jié)果應(yīng)提供屏幕和文件兩種方式。3、 有基礎(chǔ)的同學(xué)盡量實(shí)現(xiàn)界面的可視化操作和動態(tài)顯示。進(jìn)度要求2011.1.4 星期二（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、完成任務(wù)的講解、并接受課程設(shè)計任務(wù)，選定課程設(shè)計的題目2011.1.5 星期三（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、了解任務(wù)的算法、并畫出算法的程序流程圖2011.1.6 星期四（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、對任務(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ú)立完成）、對程序的調(diào)試，并試運(yùn)行。2011.1.12 星期三（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、整理課程設(shè)計過程中的各個參數(shù)、并進(jìn)行總結(jié)，提出改進(jìn)意見2011.1.13 星期四（上午教師指導(dǎo)，下午學(xué)生獨(dú)立完成）、編寫課程設(shè)計報告、準(zhǔn)備答辨2011.1.14 星期五（上午答辨）、進(jìn)行答辨驗(yàn)收工作。參考資料1嚴(yán)蔚敏 吳偉民 著， 數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(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其它說明.本表應(yīng)在每次實(shí)施前一周由負(fù)責(zé)教師填寫二份，院系審批后交院系辦備案，一份由負(fù)責(zé)教師留用。.若填寫內(nèi)容較多可另紙附后。3.一題多名學(xué)生共用的，在設(shè)計內(nèi)容、參數(shù)、要求等方面應(yīng)有所區(qū)別。教研室主任： 指導(dǎo)教師：向毅、陳劉奎、熊茜 2010年 12 月 20日重慶科技學(xué)院本科生課程設(shè)計 摘要重慶科技學(xué)院本科生課程設(shè)計 摘要重慶科技學(xué)院本科生課程設(shè)計 摘要摘要現(xiàn)代快節(jié)奏的生活使得都市人越來越渴望親近自然，因此外出旅游現(xiàn)在被越來越多的都市人所看中，所以如何快速方便的找到我們想要的旅游景點(diǎn)的信息和最短路徑就成了一個很重要的問題。本設(shè)計基于圖的結(jié)構(gòu)，創(chuàng)建一個無向圖，針對游客的實(shí)際需求，將重慶科技學(xué)院的景點(diǎn)編號、名稱、介紹等信息放入到圖的頂點(diǎn)當(dāng)中并保存在景點(diǎn)文本文件當(dāng)中，將兩個景點(diǎn)的編號和它們之間的距離當(dāng)作權(quán)值也保存到權(quán)值文本文件當(dāng)中，利用迪杰斯特拉算法來求從一個景點(diǎn)到另一個景點(diǎn)的最短距離，利用strcmp();函數(shù)來查找景點(diǎn)，并顯示出它的信息，從而解決了要查找景點(diǎn)信息和景點(diǎn)之間的最短路徑的問題，最后按照顯示屏上的提示進(jìn)行相關(guān)的操作。關(guān)鍵詞：無向圖、查找信息、最短距離、校園導(dǎo)游咨詢重慶科技學(xué)院本科生課程設(shè)計 目錄目錄摘要I1 設(shè)計內(nèi)容和要求11.1設(shè)計內(nèi)容11.1設(shè)計要求12 概要設(shè)計22.1 程序的模塊圖22.2 主函數(shù)的概要設(shè)計32.3 查找介紹函數(shù)的概要設(shè)計32.4 查找最短路徑函數(shù)的概要設(shè)計32.5 退出函數(shù)的概要設(shè)計33 詳細(xì)設(shè)計43.1 程序的流程圖43.2 主函數(shù)的詳細(xì)設(shè)計53.3 查找介紹函數(shù)的詳細(xì)設(shè)計53.4 查找最短路徑函數(shù)的詳細(xì)設(shè)計63.5 退出函數(shù)的詳細(xì)設(shè)計83.6 數(shù)據(jù)結(jié)構(gòu)的詳細(xì)設(shè)計84 軟件測試104.1 菜單的測試104.2 查找景點(diǎn)簡介的測試104.3 查找兩個景點(diǎn)之間的最短距離的測試114.4 退出的測試115 軟件使用說明126 致謝137 參考文獻(xiàn)148 附錄15重慶科技學(xué)院本科生課程設(shè)計 設(shè)計內(nèi)容和要求1 設(shè)計內(nèi)容和要求1.1設(shè)計內(nèi)容依據(jù)課程設(shè)計的要求，利用一個無向圖的結(jié)構(gòu)，將景點(diǎn)當(dāng)作圖的頂點(diǎn)，將景點(diǎn)之間的距離當(dāng)作權(quán)值來儲存，然后根據(jù)游客自己的需求，按照顯示屏上的提示來進(jìn)行查找景點(diǎn)介紹，查找兩個景點(diǎn)之間的最短距離，退出程序等基本操作。1.1設(shè)計要求本軟件為校園導(dǎo)游咨詢系統(tǒng)，根據(jù)游客的實(shí)際需求而設(shè)計，首先創(chuàng)建一個無向圖，然后從文件當(dāng)中讀取所有景點(diǎn)的編號、名稱、介紹和兩點(diǎn)之間的權(quán)值，并將它們寫入到無向圖當(dāng)中。功能主要包括查找已知景點(diǎn)的信息，查找從一個景點(diǎn)到另一個景點(diǎn)的最短路徑，退出等基本操作。軟件的界面要求使用VC+6.0的運(yùn)行環(huán)境。軟件的數(shù)據(jù)庫包括校園景點(diǎn)的編號、名稱、介紹和兩個景點(diǎn)之間的距離（權(quán)值），首先要定義頂點(diǎn)的數(shù)據(jù)類型結(jié)構(gòu)體，里面包括景點(diǎn)的編號、名稱、介紹，然后定義一個鄰接矩陣結(jié)構(gòu)體來儲存邊的信息，最后定義一個無向圖類型的結(jié)構(gòu)體來儲存頂點(diǎn)的信息，邊的信息，頂點(diǎn)的個數(shù)，邊的個數(shù)。最后游客按照顯示屏上的提示來進(jìn)行相關(guān)的操作。1重慶科技學(xué)院本科生課程設(shè)計 概要設(shè)計2 概要設(shè)計2.1 程序的模塊圖本軟件的算法依據(jù)無向圖的操作通過查找函數(shù)查找景點(diǎn)的信息，通過迪杰斯特拉函數(shù)來查找最短距離，開始時首先從文件當(dāng)中讀取景點(diǎn)的編號、名稱、介紹和兩個景點(diǎn)之間的距離即權(quán)值，然后將其加入到圖當(dāng)中，再調(diào)用查找函數(shù)查找景點(diǎn)的信息，調(diào)用迪杰斯特拉函數(shù)來查找最短距離，調(diào)用退出函數(shù)實(shí)現(xiàn)退出功能，其模塊圖如圖2.5所示：開始文件讀取加入圖退出最短距離查找信息屏幕顯示屏幕顯示圖2.5模塊圖2.2 主函數(shù)的概要設(shè)計基于程序的操作要求，對于主函數(shù)的設(shè)計首先是顯示一個可視化的操作界面提醒游客進(jìn)行相關(guān)的操作和提示游客其可供選擇的景點(diǎn)的名稱，便于其在后面的操作過程當(dāng)中能夠快速方便的找到其需要查找的景點(diǎn)的名稱。而后就是一個switch（）；的選擇函數(shù)，提供查找景點(diǎn)信息，查找兩個景點(diǎn)之間的最短距離和退出的相關(guān)的選擇操作而后進(jìn)入到每一個操作界面當(dāng)中，從而實(shí)現(xiàn)所需要的功能。2.3 查找介紹函數(shù)的概要設(shè)計當(dāng)游客選擇了要查找景點(diǎn)的信息的介紹這一項功能的時候，就會進(jìn)入到查找的界面，對于查找景點(diǎn)信息就是利用strcmp（）；函數(shù)，當(dāng)游客輸入景點(diǎn)的名稱的時候看其是否與文件當(dāng)中的數(shù)據(jù)相匹配，如果有則輸出它的介紹，如果沒有則輸出錯誤的提示提醒游客進(jìn)行相關(guān)的操作來進(jìn)入到正確的操作過程當(dāng)中。2.4 查找最短路徑函數(shù)的概要設(shè)計對于查找最短路徑的這一項功能，則是利用迪杰斯特拉函數(shù)(1)假設(shè)用帶權(quán)的鄰接矩陣arcs來表示帶權(quán)的有向圖，arcsij表示弧（vi,vj）上的權(quán)值。若(vi,vj)不存在，則置arcsij為無窮大。S為已找到從v出發(fā)的最短路徑的終點(diǎn)集合，它的初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各個定點(diǎn)vi可能到達(dá)的最短路徑長度的初始值為：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á)的最短路徑的長度。如果Dj + arcsjk Dk則修改Dk為Dk = Dj+arcsjk;(4)重復(fù)操作(2)、(3)共n 1 次，由此求得從v到圖上其余各個頂點(diǎn)的最短路徑是依路徑長度遞增的序列。從而求得了從一個景點(diǎn)到另一個景點(diǎn)的最短路徑的問題。2.5 退出函數(shù)的概要設(shè)計關(guān)于退出函數(shù)，則是當(dāng)游客執(zhí)行完了他想要進(jìn)行的操作過后選擇退出的功能的時候就調(diào)用退出函數(shù)exit(0);跳入到退出界面實(shí)現(xiàn)退出的功能。3重慶科技學(xué)院本科生課程設(shè)計 詳細(xì)設(shè)計3 詳細(xì)設(shè)計3.1 程序的流程圖當(dāng)我們想要更加實(shí)際的了解一個程序的算法過程的時候，我們就要依據(jù)程序的流程圖來給我們一個比較實(shí)際的過程，從流程圖當(dāng)中能夠更加清楚整個程序?qū)崿F(xiàn)的過程是怎樣的。其流程圖如圖3.1所示：start讀取文件信息創(chuàng)建無向圖寫入無向圖中Case ICase PCase Q查找信息end最短路徑TTFF圖3.1流程圖3.2 主函數(shù)的詳細(xì)設(shè)計主函數(shù)是一個程序的主體，當(dāng)我們要進(jìn)行我們所需要的操作的時候我們就要根據(jù)主函數(shù)中的顯示信息和它給我們的相關(guān)的提示信息來進(jìn)行所需要的操作，因此在這次的程序?qū)崿F(xiàn)的過程當(dāng)中，首先調(diào)用CreateUDN(G);函數(shù)創(chuàng)建一個無向圖，然后利用一個for();循環(huán)語句for(int k = 0; k G.vexnum; k+)if(k - 5 = 0)coutendl;couttG.;elsecouttG.;將景點(diǎn)的名稱打印在顯示屏上，最后是一個switch();的選擇語句，提示游客根據(jù)選擇來進(jìn)入到相關(guān)的操作界面實(shí)現(xiàn)程序的基本功能。3.3 查找介紹函數(shù)的詳細(xì)設(shè)計當(dāng)游客選擇了要查找景點(diǎn)的信息的介紹這一項功能的時候，程序就會調(diào)用DisIntroduction(G);函數(shù)進(jìn)入到查找景點(diǎn)的介紹的界面，當(dāng)游客輸入了需要查找的景點(diǎn)的名稱的時候，程序利用for();循環(huán)語句來查找是否有這個景點(diǎn)for(int i=0;iG.vexnum;i+)int m = strcmp(G.,n1);if(m=0)v1=i;count1=count1+1;，找到將它的編號返回，并輸出它的介紹，沒有找到這輸出錯誤提示，提醒游客進(jìn)行相關(guān)的操作進(jìn)入正確的操作過程當(dāng)中。3.4 查找最短路徑函數(shù)的詳細(xì)設(shè)計當(dāng)游客選擇了要查找兩個景點(diǎn)之間的最短距離這一項功能的時候，程序就會調(diào)用DisPath(G)；函數(shù)進(jìn)入到查找兩個景點(diǎn)之間的最短距離的操作界面當(dāng)中，當(dāng)游客輸入了兩個景點(diǎn)的名稱過后，程序會調(diào)用strcmp();函數(shù)查看是否有這兩個景點(diǎn)，如果有則返回他們各自的編號，并調(diào)用ShortPath_DIJ(G,v1,v2);函數(shù)進(jìn)入到查找最短路徑問題的程序當(dāng)中。for(v=0;vG.vexnum;v+)/各對節(jié)點(diǎn)之間初始已知路徑及距離finalv=FALSE;/從V出發(fā)的最短路徑的空集合Dv=G.arcsv0v;/從V出發(fā)到圖上其余各個定點(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+)/對Pathij進(jìn)行初始化，使其值全部為1000，便于后期的判斷for(j=0;jG.vexnum;j+)Pathij=1000;for(i=0;iG.vexnum;i+)/對數(shù)組進(jìn)行初始化，以便對Pathij進(jìn)行描述ai=1;for(v=0;vG.vexnum;v+)/各條路線的初始節(jié)點(diǎn)為v0Pathv0=v0;/開始主循環(huán)，每次求解得到v0到某個v頂點(diǎn)的最短路徑，并加入到S集合中for(i=1;iG.vexnum;i+)/其余G.vexnum - 1個頂點(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=1;while(Pathvk0!=1000)/如果上述條件成立，Pathw路徑需要改變，因?yàn)閺膙0到w的路徑顯然經(jīng)過了v0和v之間的所有的點(diǎn)（包括v）Pathwk0=Pathvk0;k0+;aw+;cout兩個景點(diǎn)之間的最短路徑為:t;int k=0;while(Pathv2k!=1000)int m=Pathv2k;coutG.t;k+;coutendl;cout兩個景點(diǎn)之間的最短距離為: Dv2Mendl;cout請選擇要進(jìn)行的操作(I:查詢景點(diǎn)信息，P:查詢兩個景點(diǎn)之間的最短路徑，Q:退出)endl;(1)假設(shè)用帶權(quán)的鄰接矩陣arcs來表示帶權(quán)的有向圖，arcsij表示?。╲i,vj）上的權(quán)值。若(vi,vj)不存在，則置arcsij為無窮大。S為已找到從v出發(fā)的最短路徑的終點(diǎn)集合，它的初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各個定點(diǎn)vi可能到達(dá)的最短路徑長度的初始值為：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á)的最短路徑的長度。如果Dj + arcsjk Dk則修改Dk為Dk = Dj+arcsjk;(4)重復(fù)操作(2)、(3)共n 1 次，由此求得從v到圖上其余各個頂點(diǎn)的最短路徑是依路徑長度遞增的序列。從而求得了從一個景點(diǎn)到另一個景點(diǎn)的最短路徑的問題。3.5 退出函數(shù)的詳細(xì)設(shè)計對于退出函數(shù)，當(dāng)游客選擇了退出這一個操作的時候，程序就會調(diào)用Exit();函數(shù)從而進(jìn)入到退出函數(shù)的界面void Exit() /退出cout歡迎下次繼續(xù)使用!endl;exit(0);程序會提示游客感謝使用，歡迎下次繼續(xù)使用的提示語，然后調(diào)用exit(0);函數(shù)實(shí)現(xiàn)退出主函數(shù)的功能。3.6 數(shù)據(jù)結(jié)構(gòu)的詳細(xì)設(shè)計本軟件的數(shù)據(jù)結(jié)構(gòu)包括3個部分：1. 鄰接矩陣typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;定義一個鄰接矩陣，用鄰接矩陣來定義和儲存邊的相關(guān)信息。2. 頂點(diǎn)的結(jié)構(gòu)體typedef struct Vertex/定義圖中頂點(diǎn)的數(shù)據(jù)類型int num;/景點(diǎn)編號char name14;/景點(diǎn)名稱char introduction100;/景點(diǎn)介紹Vertex;定義一個頂點(diǎn)的結(jié)構(gòu)體，用來儲存景點(diǎn)的編號、景點(diǎn)得名稱和景點(diǎn)的介紹等關(guān)于景點(diǎn)的信息。3.無向圖的結(jié)構(gòu)體typedef struct /定義圖的數(shù)據(jù)類型Vertex vexsMAX_VERTEX_NUM;/頂點(diǎn)的結(jié)構(gòu)體AdjMatrix arcs;/邊的鄰接矩陣int vexnum,arcnum;/頂點(diǎn)的個數(shù)，邊的個數(shù)MGraph;定義一個圖的結(jié)構(gòu)體，用來儲存頂點(diǎn)的信息、邊的信息、頂點(diǎn)的個數(shù)和邊的個數(shù)等相關(guān)的信息便于我們以后在用的時候能夠方便快捷的調(diào)用。定義好這些結(jié)構(gòu)體后，當(dāng)我們以后需要調(diào)用的時候，我們就能夠方便快捷的調(diào)用這些結(jié)構(gòu)體，從而使得我們在運(yùn)行程序的時候能夠更加的快速能夠提高我們的程序的運(yùn)行效率，大大的節(jié)省了我們的時間還使得程序變得更加的簡單。9重慶科技學(xué)院本科生課程設(shè)計 軟件測試4 軟件測試4.1 菜單的測試對于菜單函數(shù)的測試，首先菜單是一個可示化的界面，它能夠提示游客依據(jù)顯示屏上出現(xiàn)的提示來進(jìn)行相關(guān)的操作，查看所有的景點(diǎn)從而方便游客進(jìn)行相關(guān)的操作，因而我們在運(yùn)行程序的時候首先就會進(jìn)入到菜單函數(shù)當(dāng)中，經(jīng)過測試其能夠?qū)崿F(xiàn)我們所要實(shí)現(xiàn)得基本功能，其效果圖如圖4.1所示：圖4.1菜單4.2 查找景點(diǎn)簡介的測試對于查找景點(diǎn)的介紹的測試，首先依據(jù)顯示屏上的提示首先輸入要進(jìn)行的操作輸入i進(jìn)入查找景點(diǎn)信息的操作界面，然后輸入需要查找的景點(diǎn)的名稱即可顯示出景點(diǎn)的介紹信息，經(jīng)過測試可以得出其沒有什么錯誤，程序能夠按照我的要求實(shí)現(xiàn)它的功能，其效果圖如圖4.2所示：圖4.2查找景點(diǎn)信息4.3 查找兩個景點(diǎn)之間的最短距離的測試同查找景點(diǎn)的信息一樣，對于查找景點(diǎn)之間的最短距離的測試，我們就要依據(jù)提示輸入p進(jìn)入到查詢最短路徑的界面，依次輸入所需要查找的兩個景點(diǎn)就會顯示出怎樣到達(dá)這兩個景點(diǎn)并顯示出它們之間的最短路徑，經(jīng)過測試可見程序能夠按照我的要求來實(shí)現(xiàn)其所需要的功能，其效果圖如圖4.3所示：圖4.3查找兩個景點(diǎn)之間的最短距離4.4 退出的測試原理同上，對于退出函數(shù)的測試，我需要依據(jù)顯示屏上的提示，首先需要輸入q進(jìn)入到退出的界面，系統(tǒng)就會直接調(diào)用退出的函數(shù)，顯示出“歡迎下次繼續(xù)使用！”的話讓后按任意鍵就退出了系統(tǒng)，其效果圖如圖4.4所示：圖4.4退出界面115 軟件使用說明對于軟件的使用，對于第一次使用軟件的游客來說，要讓他們在第一次用的時候就能夠快速輕松的掌握軟件的用法，因此在程序一開始運(yùn)行的時候，我們要進(jìn)行如下的操作：（1）首先我會給游客提供一個可視化的菜單操作界面，在顯示屏上提示用戶其可以進(jìn)行的操作和他能夠查詢的景點(diǎn)的名稱。（2）用戶輸入了“i”后，進(jìn)入到查詢景點(diǎn)簡介的界面，當(dāng)用戶輸入了想要查找的景點(diǎn)的名稱過后就會顯示出這個景點(diǎn)的介紹來。（3）當(dāng)用戶輸入了“p”后，進(jìn)入到查詢最短路徑的界面，然后依據(jù)提示用戶依次輸入兩個景點(diǎn)的名稱，程序就會將這兩個景點(diǎn)的最短路徑給我們表示出來并顯示出最短路徑是多少。（4）當(dāng)用戶輸入了“q”后，進(jìn)入到退出界面，這是系統(tǒng)就會提示用戶程序?qū)⒁\(yùn)行結(jié)束，歡迎下次繼續(xù)使用的提示語，最后按下任意鍵程序結(jié)束。重慶科技學(xué)院本科生課程設(shè)計 致謝6 致謝在本次的實(shí)驗(yàn)過程當(dāng)中，雖然有各種各樣的問題在困擾著我，但是好在我的身邊總會有人在這個時候出現(xiàn)為我解決這些問題，而他們就是我的老師和同學(xué)們，一個人做事的時候總是會遇到問題的，有問題并不可怕只要我們相信我們不是一個人在戰(zhàn)斗而是有很多的同學(xué)和老師與我們站在一起的這樣我們就能夠戰(zhàn)勝各種困難，感謝我的老師和我的同學(xué)們。是他們在我遇到問題的時候給我指明了解決的方法，從而克服了一個又一個的問題最終解決了所有的問題實(shí)現(xiàn)了程序所需要的功能，感謝我的同學(xué)們，不論是上課還是下課，只要是遇到了困難找到他們的時候只要是能夠解決的他們會義不容辭的獻(xiàn)出自己的力量。感謝老師們的諄諄教誨，他們不辭辛勞為了我們能夠順利的解決問題無時無刻不在我們的身邊，當(dāng)我們一遇到問題的時候他就會出現(xiàn)，從沒有半點(diǎn)怨言。最后還要感謝學(xué)校感謝給我們提供了良好的實(shí)驗(yàn)環(huán)境，使我們能夠安心輕松的在好的額環(huán)境當(dāng)中完成我們的實(shí)驗(yàn)。 簽名 周 楊 日期 2011年1月13日14重慶科技學(xué)院本科生課程設(shè)計 參考文獻(xiàn)7 參考文獻(xiàn)【1】 數(shù)據(jù)結(jié)構(gòu)(C語言版) 嚴(yán)蔚敏 吳偉民 編著 清華大學(xué)出版社 2002【2】 C程序設(shè)計經(jīng)典教程，美Deitel,H.M.，美Deitel,P.J.著，清華大學(xué)出版社 2006【3】 Windows程序設(shè)計，美 Charles Petzold 著，北京大學(xué)出版社 2004【4】 Data Structures：A Pseudecode（Approach with C）美Richard F.Gilberg，美Behrouz A.Forouzan著15重慶科技學(xué)院本科生課程設(shè)計 附錄8 附錄main.cpp#include#include#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請選擇要進(jìn)行的操作(I:查詢景點(diǎn)信息，P:查詢兩個景點(diǎn)之間的最短路徑，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)建一個圖ifstream in_file(view.txt,ios: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;kijw;G.arcsij=w;G.arcsji=G.arcsij;DisIntroduction.hvoid DisIntroduction(MGraph G)/提供景點(diǎn)的信息char n120;int v1;cout請輸入所要查詢的景點(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請選擇要進(jìn)行的操作(I:查詢景點(diǎn)信息，P:查詢兩個景點(diǎn)之間的最短路徑，Q:退出)endl;else cout該景點(diǎn)的簡介為:tG.roductionendl;cout請選擇要進(jìn)行的操作(I:查詢景點(diǎn)信息，P:查詢兩個景點(diǎn)之間的最短路徑，Q:退出)endl;DisPath.hvoid DisPath(MGraph G)/查詢?nèi)我鈨蓚€景點(diǎn)之間的一條最短的簡單路徑int v1,v2;char n120,n220;cout請輸入要查詢的最短路徑的兩個頂點(diǎn)名稱:n1n2;int count=0;for(int i=0;iG.vexnum;i+)int m1= strcmp(G.,n1);int m2= strcmp(G.,n2);if(m1=0)v1=i;count+;else if(m2=0)v2=i;count+;if(count!=2)cout您輸入的名稱有誤!endl;cout請選擇要進(jìn)行的操作(I:查詢景點(diǎn)信息，P:查詢兩個景點(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#include 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