1、重慶科技學院本科生課程設計 摘要重慶科技學院課程設計報告 院（系）:_電氣與信息工程學院 專業班級: 計科普0902 學生姓名: 周 楊 學 號: 2009441622 設計地點（單位）_計算機基礎自主學習中心I306_設計題目:_校園導游咨詢_ 完成日期： 2011 年 1 月 14 日 指導教師評語: _ _ _ 成績（五級記分制）:_ _ 指導教師（簽字）:_ _ 重慶科技學院課程設計任務書設計題目：校園導游咨詢學生姓名周 楊課程名稱數據結構課程設計專業班級計科2009-02地 點計算機基礎自主學習中心起止時間2011.01.4-2011.01.14設計內容及要求基本要求:（1）設計你的

2、學校的校園平面圖，所含景點不少于10個。以圖中頂點表示學校各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關信息。（2）為來訪客人提供圖中任意景點的問路查詢，即查詢任意兩個景點之間的一條最短的簡單路徑。 （3）為來訪客人提供圖中任意景點相關信息的查詢。測試數據：由讀者根據實際情況指定。實現提示：一般情況下，校園的道路是雙向通行的，可設校園平面圖是一個無向網。頂點和邊均含有相關信息。擴展要求：（1）提供圖中任意景點問路查詢，即求任意兩個景點之間的所有路徑。（2）擴充道路信息，如道路類別（車道、人行道等）、沿途景色等級，以至可按客人所需分別查詢人行路徑或車行路徑或觀景路徑等設

3、計參數1、 自己編寫程序，校園初始數據以文本文件保存，文件格式根據需要自行定義。對應的地圖初始化從文件中讀出數據進行初始化。2、 查詢的結果應提供屏幕和文件兩種方式。3、 有基礎的同學盡量實現界面的可視化操作和動態顯示。進度要求2011.1.4 星期二（上午教師指導，下午學生獨立完成）、完成任務的講解、并接受課程設計任務，選定課程設計的題目2011.1.5 星期三（上午教師指導，下午學生獨立完成）、了解任務的算法、并畫出算法的程序流程圖2011.1.6 星期四（上午教師指導，下午學生獨立完成）、對任務的關鍵技術進行驗證、并確定解決辦法2011.1.7 星期五（上午教師指導，下午學生獨立完成）、

4、編制任務的程序2011.1.10 星期一（上午教師指導，下午學生獨立完成）、編制任務的程序2011.1.11 星期二（上午教師指導，下午學生獨立完成）、對程序的調試，并試運行。2011.1.12 星期三（上午教師指導，下午學生獨立完成）、整理課程設計過程中的各個參數、并進行總結，提出改進意見2011.1.13 星期四（上午教師指導，下午學生獨立完成）、編寫課程設計報告、準備答辨2011.1.14 星期五（上午答辨）、進行答辨驗收工作。參考資料1嚴蔚敏 吳偉民 著， 數據結構（C語言版），清華大學出版社，2007.42. Richard F.Gilberg Behrouz A.Forouzan,

5、 Data Structures A Pseudocode Approach with C，second edition, Thomson, 2005.13. 李春葆 著，數據結構教程，清華大學出版社，2005.1其它說明.本表應在每次實施前一周由負責教師填寫二份，院系審批后交院系辦備案，一份由負責教師留用。.若填寫內容較多可另紙附后。3.一題多名學生共用的，在設計內容、參數、要求等方面應有所區別。教研室主任： 指導教師：向毅、陳劉奎、熊茜 2010年 12 月 20日重慶科技學院本科生課程設計 摘要重慶科技學院本科生課程設計 摘要重慶科技學院本科生課程設計 摘要摘要現代快節奏的生活使得都市人

6、越來越渴望親近自然，因此外出旅游現在被越來越多的都市人所看中，所以如何快速方便的找到我們想要的旅游景點的信息和最短路徑就成了一個很重要的問題。本設計基于圖的結構，創建一個無向圖，針對游客的實際需求，將重慶科技學院的景點編號、名稱、介紹等信息放入到圖的頂點當中并保存在景點文本文件當中，將兩個景點的編號和它們之間的距離當作權值也保存到權值文本文件當中，利用迪杰斯特拉算法來求從一個景點到另一個景點的最短距離，利用strcmp();函數來查找景點，并顯示出它的信息，從而解決了要查找景點信息和景點之間的最短路徑的問題，最后按照顯示屏上的提示進行相關的操作。關鍵詞：無向圖、查找信息、最短距離、校園導游咨詢

7、重慶科技學院本科生課程設計 目錄目錄摘要I1 設計內容和要求11.1設計內容11.1設計要求12 概要設計22.1 程序的模塊圖22.2 主函數的概要設計32.3 查找介紹函數的概要設計32.4 查找最短路徑函數的概要設計32.5 退出函數的概要設計33 詳細設計43.1 程序的流程圖43.2 主函數的詳細設計53.3 查找介紹函數的詳細設計53.4 查找最短路徑函數的詳細設計63.5 退出函數的詳細設計83.6 數據結構的詳細設計84 軟件測試104.1 菜單的測試104.2 查找景點簡介的測試104.3 查找兩個景點之間的最短距離的測試114.4 退出的測試115 軟件使用說明126 致謝

8、137 參考文獻148 附錄15重慶科技學院本科生課程設計 設計內容和要求1 設計內容和要求1.1設計內容依據課程設計的要求，利用一個無向圖的結構，將景點當作圖的頂點，將景點之間的距離當作權值來儲存，然后根據游客自己的需求，按照顯示屏上的提示來進行查找景點介紹，查找兩個景點之間的最短距離，退出程序等基本操作。1.1設計要求本軟件為校園導游咨詢系統，根據游客的實際需求而設計，首先創建一個無向圖，然后從文件當中讀取所有景點的編號、名稱、介紹和兩點之間的權值，并將它們寫入到無向圖當中。功能主要包括查找已知景點的信息，查找從一個景點到另一個景點的最短路徑，退出等基本操作。軟件的界面要求使用VC+6.0

9、的運行環境。軟件的數據庫包括校園景點的編號、名稱、介紹和兩個景點之間的距離（權值），首先要定義頂點的數據類型結構體，里面包括景點的編號、名稱、介紹，然后定義一個鄰接矩陣結構體來儲存邊的信息，最后定義一個無向圖類型的結構體來儲存頂點的信息，邊的信息，頂點的個數，邊的個數。最后游客按照顯示屏上的提示來進行相關的操作。1重慶科技學院本科生課程設計 概要設計2 概要設計2.1 程序的模塊圖本軟件的算法依據無向圖的操作通過查找函數查找景點的信息，通過迪杰斯特拉函數來查找最短距離，開始時首先從文件當中讀取景點的編號、名稱、介紹和兩個景點之間的距離即權值，然后將其加入到圖當中，再調用查找函數查找景點的信息，

10、調用迪杰斯特拉函數來查找最短距離，調用退出函數實現退出功能，其模塊圖如圖2.5所示：開始文件讀取加入圖退出最短距離查找信息屏幕顯示屏幕顯示圖2.5模塊圖2.2 主函數的概要設計基于程序的操作要求，對于主函數的設計首先是顯示一個可視化的操作界面提醒游客進行相關的操作和提示游客其可供選擇的景點的名稱，便于其在后面的操作過程當中能夠快速方便的找到其需要查找的景點的名稱。而后就是一個switch（）；的選擇函數，提供查找景點信息，查找兩個景點之間的最短距離和退出的相關的選擇操作而后進入到每一個操作界面當中，從而實現所需要的功能。2.3 查找介紹函數的概要設計當游客選擇了要查找景點的信息的介紹這一項功能

11、的時候，就會進入到查找的界面，對于查找景點信息就是利用strcmp（）；函數，當游客輸入景點的名稱的時候看其是否與文件當中的數據相匹配，如果有則輸出它的介紹，如果沒有則輸出錯誤的提示提醒游客進行相關的操作來進入到正確的操作過程當中。2.4 查找最短路徑函數的概要設計對于查找最短路徑的這一項功能，則是利用迪杰斯特拉函數(1)假設用帶權的鄰接矩陣arcs來表示帶權的有向圖，arcsij表示弧（vi,vj）上的權值。若(vi,vj)不存在，則置arcsij為無窮大。S為已找到從v出發的最短路徑的終點集合，它的初始狀態為空集。那么，從v出發到圖上其余各個定點vi可能到達的最短路徑長度的初始值為：Di

12、= arcsvi;(2)選擇vj,使得Dj = MinDi | vi V Svj就是當前求得的一條從v出發的最短路徑的終點。令S = S j;(3)修改從v出發到集合V S 上任意頂點vk可到達的最短路徑的長度。如果Dj + arcsjk < Dk則修改Dk為Dk = Dj+arcsjk;(4)重復操作(2)、(3)共n 1 次，由此求得從v到圖上其余各個頂點的最短路徑是依路徑長度遞增的序列。從而求得了從一個景點到另一個景點的最短路徑的問題。2.5 退出函數的概要設計關于退出函數，則是當游客執行完了他想要進行的操作過后選擇退出的功能的時候就調用退出函數exit(0);跳入到退出界面實現退

13、出的功能。3重慶科技學院本科生課程設計 詳細設計3 詳細設計3.1 程序的流程圖當我們想要更加實際的了解一個程序的算法過程的時候，我們就要依據程序的流程圖來給我們一個比較實際的過程，從流程圖當中能夠更加清楚整個程序實現的過程是怎樣的。其流程圖如圖3.1所示：start讀取文件信息創建無向圖寫入無向圖中Case ICase PCase Q查找信息end最短路徑TTFF圖3.1流程圖3.2 主函數的詳細設計主函數是一個程序的主體，當我們要進行我們所需要的操作的時候我們就要根據主函數中的顯示信息和它給我們的相關的提示信息來進行所需要的操作，因此在這次的程序實現的過程當中，首先調用CreateUDN(

14、G);函數創建一個無向圖，然后利用一個for();循環語句for(int k = 0; k < G.vexnum; k+)if(k - 5 = 0)cout<<endl;cout<<""<<'t'<<G.;elsecout<<""<<'t'<<G.;將景點的名稱打印在顯示屏上，最后是一個switch();的選擇語句，提示游客根據選擇來進入到相關的操作界面實現程序的基本功能。3.3 查找介紹函數的

15、詳細設計當游客選擇了要查找景點的信息的介紹這一項功能的時候，程序就會調用DisIntroduction(G);函數進入到查找景點的介紹的界面，當游客輸入了需要查找的景點的名稱的時候，程序利用for();循環語句來查找是否有這個景點for(int i=0;i<G.vexnum;i+)int m = strcmp(G.,n1);if(m=0)v1=i;count1=count1+1;，找到將它的編號返回，并輸出它的介紹，沒有找到這輸出錯誤提示，提醒游客進行相關的操作進入正確的操作過程當中。3.4 查找最短路徑函數的詳細設計當游客選擇了要查找兩個景點之間的最短距離這一項功能

16、的時候，程序就會調用DisPath(G)；函數進入到查找兩個景點之間的最短距離的操作界面當中，當游客輸入了兩個景點的名稱過后，程序會調用strcmp();函數查看是否有這兩個景點，如果有則返回他們各自的編號，并調用ShortPath_DIJ(G,v1,v2);函數進入到查找最短路徑問題的程序當中。for(v=0;v<G.vexnum;v+)/各對節點之間初始已知路徑及距離finalv=FALSE;/從V出發的最短路徑的空集合Dv=G.arcsv0v;/從V出發到圖上其余各個定點v0可能到達的最短路徑的初始值for(w=0;w<G.vexnum;w+)Pvw=FALSE;/設空路徑i

17、f(Dv<MAXNUM)Pvv0=TRUE;Pvv=TRUE;Dv0=0;finalv0=TRUE;int a20;for(i=0;i<G.vexnum;i+)/對Pathij進行初始化，使其值全部為1000，便于后期的判斷for(j=0;j<G.vexnum;j+)Pathij=1000;for(i=0;i<G.vexnum;i+)/對數組進行初始化，以便對Pathij進行描述ai=1;for(v=0;v<G.vexnum;v+)/各條路線的初始節點為v0Pathv0=v0;/開始主循環，每次求解得到v0到某個v頂點的最短路徑，并加入到S集合中for(i=1;i

18、<G.vexnum;i+)/其余G.vexnum - 1個頂點m=MAXNUM;/當前所知的離v0最近的距離for(w=0;w<G.vexnum;w+)if(!finalw)/w頂點在V-S中if(Dw<m)/w頂點離v0頂點更近v=w;m=Dw;Pathvav=v;/離v0頂點最近的v加入s集合finalv=TRUE;for(w=0;w<G.vexnum;w+)/更新當前最短路徑及距離if(!finalw)&&(m+G.arcsvw<Dw)Dw=m+G.arcsvw;/修改當前的最短路徑的值int k0=1;aw=1;while(Pathvk0!

19、=1000)/如果上述條件成立，Pathw路徑需要改變，因為從v0到w的路徑顯然經過了v0和v之間的所有的點（包括v）Pathwk0=Pathvk0;k0+;aw+;cout<<"兩個景點之間的最短路徑為:"<<'t'int k=0;while(Pathv2k!=1000)int m=Pathv2k;cout<<G.<<'t'k+;cout<<endl;cout<<"兩個景點之間的最短距離為: "<<Dv2<<

20、;"M"<<endl;cout<<"請選擇要進行的操作(I:查詢景點信息，P:查詢兩個景點之間的最短路徑，Q:退出)"<<endl;(1)假設用帶權的鄰接矩陣arcs來表示帶權的有向圖，arcsij表示弧（vi,vj）上的權值。若(vi,vj)不存在，則置arcsij為無窮大。S為已找到從v出發的最短路徑的終點集合，它的初始狀態為空集。那么，從v出發到圖上其余各個定點vi可能到達的最短路徑長度的初始值為：Di = arcsvi;(2)選擇vj,使得Dj = MinDi | vi V Svj就是當前求得的一條從v出發的最

21、短路徑的終點。令S = S j;(3)修改從v出發到集合V S 上任意頂點vk可到達的最短路徑的長度。如果Dj + arcsjk < Dk則修改Dk為Dk = Dj+arcsjk;(4)重復操作(2)、(3)共n 1 次，由此求得從v到圖上其余各個頂點的最短路徑是依路徑長度遞增的序列。從而求得了從一個景點到另一個景點的最短路徑的問題。3.5 退出函數的詳細設計對于退出函數，當游客選擇了退出這一個操作的時候，程序就會調用Exit();函數從而進入到退出函數的界面void Exit() /退出cout<<"歡迎下次繼續使用!"<<endl;exit

22、(0);程序會提示游客感謝使用，歡迎下次繼續使用的提示語，然后調用exit(0);函數實現退出主函數的功能。3.6 數據結構的詳細設計本軟件的數據結構包括3個部分：1. 鄰接矩陣typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;定義一個鄰接矩陣，用鄰接矩陣來定義和儲存邊的相關信息。2. 頂點的結構體typedef struct Vertex/定義圖中頂點的數據類型int num;/景點編號char name14;/景點名稱char introduction100;/景點介紹Vertex;定義一個頂點的結構體，用來儲存景點的編號、景點得名稱和景點

23、的介紹等關于景點的信息。3.無向圖的結構體typedef struct /定義圖的數據類型Vertex vexsMAX_VERTEX_NUM;/頂點的結構體AdjMatrix arcs;/邊的鄰接矩陣int vexnum,arcnum;/頂點的個數，邊的個數MGraph;定義一個圖的結構體，用來儲存頂點的信息、邊的信息、頂點的個數和邊的個數等相關的信息便于我們以后在用的時候能夠方便快捷的調用。定義好這些結構體后，當我們以后需要調用的時候，我們就能夠方便快捷的調用這些結構體，從而使得我們在運行程序的時候能夠更加的快速能夠提高我們的程序的運行效率，大大的節省了我們的時間還使得程序變得更加的簡單。9

24、重慶科技學院本科生課程設計 軟件測試4 軟件測試4.1 菜單的測試對于菜單函數的測試，首先菜單是一個可示化的界面，它能夠提示游客依據顯示屏上出現的提示來進行相關的操作，查看所有的景點從而方便游客進行相關的操作，因而我們在運行程序的時候首先就會進入到菜單函數當中，經過測試其能夠實現我們所要實現得基本功能，其效果圖如圖4.1所示：圖4.1菜單4.2 查找景點簡介的測試對于查找景點的介紹的測試，首先依據顯示屏上的提示首先輸入要進行的操作輸入i進入查找景點信息的操作界面，然后輸入需要查找的景點的名稱即可顯示出景點的介紹信息，經過測試可以得出其沒有什么錯誤，程序能夠按照我的要求實現它的功能，其效果圖如圖

25、4.2所示：圖4.2查找景點信息4.3 查找兩個景點之間的最短距離的測試同查找景點的信息一樣，對于查找景點之間的最短距離的測試，我們就要依據提示輸入p進入到查詢最短路徑的界面，依次輸入所需要查找的兩個景點就會顯示出怎樣到達這兩個景點并顯示出它們之間的最短路徑，經過測試可見程序能夠按照我的要求來實現其所需要的功能，其效果圖如圖4.3所示：圖4.3查找兩個景點之間的最短距離4.4 退出的測試原理同上，對于退出函數的測試，我需要依據顯示屏上的提示，首先需要輸入q進入到退出的界面，系統就會直接調用退出的函數，顯示出“歡迎下次繼續使用！”的話讓后按任意鍵就退出了系統，其效果圖如圖4.4所示：圖4.4退出

26、界面115 軟件使用說明對于軟件的使用，對于第一次使用軟件的游客來說，要讓他們在第一次用的時候就能夠快速輕松的掌握軟件的用法，因此在程序一開始運行的時候，我們要進行如下的操作：（1）首先我會給游客提供一個可視化的菜單操作界面，在顯示屏上提示用戶其可以進行的操作和他能夠查詢的景點的名稱。（2）用戶輸入了“i”后，進入到查詢景點簡介的界面，當用戶輸入了想要查找的景點的名稱過后就會顯示出這個景點的介紹來。（3）當用戶輸入了“p”后，進入到查詢最短路徑的界面，然后依據提示用戶依次輸入兩個景點的名稱，程序就會將這兩個景點的最短路徑給我們表示出來并顯示出最短路徑是多少。（4）當用戶輸入了“q”后，進入到退

27、出界面，這是系統就會提示用戶程序將要運行結束，歡迎下次繼續使用的提示語，最后按下任意鍵程序結束。重慶科技學院本科生課程設計 致謝6 致謝在本次的實驗過程當中，雖然有各種各樣的問題在困擾著我，但是好在我的身邊總會有人在這個時候出現為我解決這些問題，而他們就是我的老師和同學們，一個人做事的時候總是會遇到問題的，有問題并不可怕只要我們相信我們不是一個人在戰斗而是有很多的同學和老師與我們站在一起的這樣我們就能夠戰勝各種困難，感謝我的老師和我的同學們。是他們在我遇到問題的時候給我指明了解決的方法，從而克服了一個又一個的問題最終解決了所有的問題實現了程序所需要的功能，感謝我的同學們，不論是上課還是下課，只

28、要是遇到了困難找到他們的時候只要是能夠解決的他們會義不容辭的獻出自己的力量。感謝老師們的諄諄教誨，他們不辭辛勞為了我們能夠順利的解決問題無時無刻不在我們的身邊，當我們一遇到問題的時候他就會出現，從沒有半點怨言。最后還要感謝學校感謝給我們提供了良好的實驗環境，使我們能夠安心輕松的在好的額環境當中完成我們的實驗。 簽名 周 楊 日期 2011年1月13日14重慶科技學院本科生課程設計 參考文獻7 參考文獻【1】 數據結構(C語言版) 嚴蔚敏 吳偉民 編著 清華大學出版社 2002【2】 C程序設計經典教程，美Deitel,H.M.，美Deitel,P.J.著，清華大學出版社 2006【3】 Win

29、dows程序設計，美 Charles Petzold 著，北京大學出版社 2004【4】 Data Structures：A Pseudecode（Approach with C）美Richard F.Gilberg，美Behrouz A.Forouzan著15重慶科技學院本科生課程設計 附錄8 附錄main.cpp#include<iostream>#include<fstream>#include<cstring>#include "GraphADT.h"using namespace std;void main()MGraph G;

30、CreateUDN(G);int i = 0;char choice10;cout<<"t*歡迎使用重慶科技學院校園導游程序*"<<endl;cout<<"t_"<<endl;cout<<"t*景點名稱*"<<endl;for(int k = 0; k < G.vexnum; k+)if(k - 5 = 0)cout<<endl;cout<<""<<'t'<<G.vexsk.

31、name;elsecout<<""<<'t'<<G.;cout<<"nt_n"<<endl;cout<<"請選擇要進行的操作(I:查詢景點信息，P:查詢兩個景點之間的最短路徑，Q:退出)"<<endl;while(choicei!='Q')cin>>choicei;switch(choicei)case 'I':case 'i':DisIntroductio

32、n(G);break;case 'P':case 'p':DisPath(G);break;case 'Q':case 'q':Exit();break;CreatUDN.h#include<iostream>#include<fstream>#include<cstring>#define MAXNUM 10000#define Vertex 10#define Edges 13using namespace std;void CreateUDN(MGraph &G)/創建一個圖ifs

33、tream in_file("view.txt",ios:in);/從view.txt中讀入景點的相關信息if(!in_file)exit(-1);int i,j,k,w;G.vexnum = Vertex;G.arcnum = Edges;for(i=0;i<G.vexnum;i+)in_file>>G.vexsi.num>>G.>>G.roduction;for(i=0;i<G.vexnum;i+)/初始化矩陣for(j=0;j<G.vexnum;j+)G.arcsij=MAXN

34、UM;ifstream weight_file("weight.txt",ios:in);/從weight.txt中讀入權重的值if(!weight_file)exit(-1);for(k=0;k<G.arcnum;k+)/講權值帶入矩陣當中weight_file>>i>>j>>w;G.arcsij=w;G.arcsji=G.arcsij;DisIntroduction.hvoid DisIntroduction(MGraph G)/提供景點的信息char n120;int v1;cout<<"請輸入所要查詢的

35、景點的名稱:"<<endl;cin>>n1;int count1=0;for(int i=0;i<G.vexnum;i+)int m = strcmp(G.,n1);if(m=0)v1=i;count1=count1+1;if(count1!=1)cout<<"您輸入的名稱有誤!"<<endl;cout<<"請選擇要進行的操作(I:查詢景點信息，P:查詢兩個景點之間的最短路徑，Q:退出)"<<endl;else cout<<"

36、該景點的簡介為:"<<'t'<<G.roduction<<endl;cout<<"請選擇要進行的操作(I:查詢景點信息，P:查詢兩個景點之間的最短路徑，Q:退出)"<<endl;DisPath.hvoid DisPath(MGraph G)/查詢任意兩個景點之間的一條最短的簡單路徑int v1,v2;char n120,n220;cout<<"請輸入要查詢的最短路徑的兩個頂點名稱:"<<endl;cin>>n1&g

37、t;>n2;int count=0;for(int i=0;i<G.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<<"請選擇要進行的操作(I:查詢景點信息，P:查詢兩個景點之間的最短路徑，Q:退出)"<<endl;ShortP

38、ath_DIJ(G,v1,v2);Exit.hvoid Exit() /退出cout<<"歡迎下次繼續使用!"<<endl;exit(0);GraphADT.h#include "GraphTypeDef.h"#include "CreateUDN.h"#include "ShortPath.h"#include "DisIntroduction.h"#include "DisPath.h"#include "Exit.h"Grap

39、hTypeDef.h#define MAX_VERTEX_NUM 10typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct Vertex/定義圖中頂點的數據類型int num;char name14;char introduction100;Vertex;typedef struct /定義圖的數據類型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#include<iostream>#include<fstream>#include<cstring>#define MAXNUM 10000#