1、WORD格式瓊州學院電子信息工程學院課程設計報告課程名稱："數據構造"課程設計設計題目：校園導游咨詢專業：軟件工程班級：2021軟件工程學生*：學號：起止日期：指導教師：指導教師評語：最終成績：指導教師簽名：年月日成項目權重成績績1、設計過程中的學習態度0.2評2、課程設計的質量及辯論0.5定3、設計報告書標準程度0.34、總成績專業資料整理WORD格式瓊州學院本科生課程設計本卷須知本卷須知一、設計目的"數據構造" 是一門實踐性較強的軟件根底課，為了學好這門課程，必須在掌握理論知識的同時， 加強上機實踐。 本課程設計的目的就是要到達理論與實際應用相結合，

2、使同學們能夠根據數據對象的特性， 學會數據組織的方法， 能把現實世界中的實際問題在計算機內部表示出來，并培養根本的、良好的程序設計技能。二、設計要求1通過這次課程設計，要求在數據構造的邏輯特性和物理表示、數據構造的選擇應用、算法的設計及其實現等方面加深課程根本內容的理解。 同時，在程序設計方法以及上機操作等根本技能和科學作風方面受到比較系統和嚴格的訓練。2學生必須仔細研讀"數據構造"課程設計要求，以學生自學為主、指導教師指導為輔，獨立完成課程設計的任務，有問題及時主動與指導教師溝通。3本次課程設計按照教學要求需要在本學期15 周前完成，學生要發揮自主學習的能力，充分利用時間

3、， 安排好課程設計的時間方案，并在課程設計過程中不斷檢測自己的方案完成情況，及時向指導教師匯報。4編程語言： C 語言。三、課程設計說明書的格式要求設計文檔的撰寫必須提前進展，以保證使文檔與程序同步提交。1設計題目2運行環境軟、硬件環境3算法的需求分析4算法概要設計5算法詳細設計6算法的測試7運行結果分析8收獲及體會四、問題分析、設計和測試過程要標準化1需求分析：將題目中要求的功能進展表達分析。2概要設計：算法的設計說明， 描述解決此問題的數據存儲構造， 有些題目已經指定了數據存儲的，按照指定的設計 ，描述算法建議使用流程圖，進展算法分析指明關鍵語句的時間復雜度。3詳細設計：即各個算法的具體實

4、現步驟，每個題目要有相應的源程序，其中每個功能模塊采用不同的函數實現。源程序要標準編寫：構造要清晰，注釋要清楚。重點函數的重點變量和重點功能局部要加上清楚的程序注釋。4調試和測試：給出實現功能的一組或多組測試數據，程序調試后，將按照此測試數據進展測試的結果列出來 。在調試過程中遇到的問題和解決方法也要記錄下來。程序要能夠正常運行，還要有根本的容錯功能。盡量防止出現操作錯誤時出現死循環。5改進措施：對有些題目提出算法改進方案，比較不同算法的優缺點。五、對指導教師的要求指導教師要關心學生的課程設計進展， 認真答疑。 對課程設計報告的撰寫要給予充分的指導，報告中切忌出現大篇源代碼，應嚴格要求學生將主

5、要篇幅放在“原理實現上，即如何用框圖表達設計和實施思想。課程設計報告要用紅筆批閱，最終成績以優、良、中、及格與不及格分等計算。專業資料整理WORD格式II-專業資料整理WORD格式瓊州學院本科生課程設計目錄目錄摘要 .11設計內容和要求 .- 2 -1.1設計內容 .- 2 -1.1設計要求 .- 2 -2概要設計 .22.1程序的模塊圖 .22.2主函數的概要設計 .32.3查找介紹函數的概要設計 .32.4查找最短路徑函數的概要設計 .32.5景點分布圖的概要設計 .32.6退出函數的概要設計 .33詳細設計 .53.1程序的流程圖 .53.2主函數的詳細設計 .63.3查找介紹函數的詳細

6、設計 .63.4查找最短路徑函數的詳細設計 .73.5景點分布圖的詳細設計 .83.6退出函數的詳細設計 .93.7數據構造的詳細設計 .94軟件測試 .104.1菜單的測試 .104.2查找景點簡介的測試 .114.3查找兩個景點之間的最短距離的測試. 124.4查看景點分布圖的測試 .134.5退出的測試 .145軟件使用說明 .156參考文獻 .167附錄 .177.1系統完整代碼 .17專業資料整理WORD格式瓊州學院本科生課程設計摘要摘要現代快節奏的生活使得都市人越來越渴望親近自然，因此外出旅游現在被越來越多的都市人所看中， 所以如何快速方便的找到我們想要的旅游景點的信息和最短路徑就

7、成了一個很重要的問題。本設計基于圖的構造，創立一個無向圖，針對游客的實際需求，將瓊州學院的景點編號、名稱、介紹等信息放入到圖的頂點當中并保存在景點文本文件當中，將兩個景點的編號和它們之間的距離當作權值也保存到權值文本文件當中，利用迪杰斯特拉算法來求從一個景點到另一個景點的最短距離，利用Search( );函數來查找景點， 并顯示出它的信息， 從而解決了要查找景點信息和景點之間的最短路徑的問題，最后按照顯示屏上的提示進展相關的操作。關鍵詞：分布圖、查找信息、最短距離、校園導游咨詢專業資料整理WORD格式1專業資料整理WORD格式瓊州學院本科生課程設計設計內容和要求1 設計內容和要求1.1 設計內

8、容依據課程設計的要求，利用一個無向圖的構造，將景點當作圖的頂點，將景點之間的距離當作權值來儲存，然后根據游客自己的需求， 按照顯示屏上的提示來進展查找景點介紹，查找兩個景點之間的最短距離，退出程序等根本操作。1.1 設計要求本軟件為校園導游咨詢系統，根據游客的實際需求而設計，首先創立一個無向圖，然后從文件當中讀取所有景點的編號、名稱、介紹和兩點之間的權值，并將它們寫入到無向圖當中。 功能主要包括查找景點的信息，查找從一個景點到另一個景點的最短路徑，退出等根本操作。軟件的界面要求使用VC+6.0 的運行環境。軟件的數據庫包括校園景點的編號、名稱、介紹和兩個景點之間的距離權值，首先要定義頂點的數據

9、類型構造體，里面包括景點的編號、名稱、介紹，然后定義一個鄰接矩陣構造體來儲存邊的信息，最后定義一個無向圖類型的構造體來儲存頂點的信息，邊的信息，頂點的個數，邊的條數。最后游客按照顯示屏上的提示來進展相關的操作。專業資料整理WORD格式2專業資料整理WORD格式瓊州學院本科生課程設計概要設計2 概要設計2.1程序的模塊圖本軟件的算法依據無向圖的操作通過查找函數查找景點的信息，通過費洛伊德函數來查找最短距離， 開場時首先從文件當中讀取景點的編號、名稱、介紹和兩個景點之間的距離即權值， 然后將其參加到圖當中， 再調用查找函數查找景點的信息，調用費洛伊德函數來查找最短距離，調用退出函數實現退出功能，

10、其模塊圖如圖 2.5 所示：開場加入圖分查最退布找短出圖信距息離屏屏屏幕幕幕顯顯顯示示示圖 2.5 模塊圖專業資料整理WORD格式3專業資料整理WORD格式瓊州學院本科生課程設計概要設計2.2主函數的概要設計基于程序的操作要求， 對于主函數的設計首先是顯示一個可視化的操作界面提醒游客進展相關的操作和提示游客其可供選擇的景點的名稱， 便于其在后面的操作過程當中能夠快速方便的找到其需要查找的景點的名稱。而后就是一個 switch ；的選擇函數，提供查找景點信息，查找兩個景點之間的最短距離和退出的相關的選擇操作而后進入到每一個操作界面當中，從而實現所需要的功能。2.3查找介紹函數的概要設計當游客選擇

11、了要查找景點的信息的介紹這一項功能的時候，就會進入到查找的界面，對于查找景點信息就是利用 Search( ); 函數，當游客輸入景點的名稱的時候看其是否與文件當中的數據相匹配， 如果有那么輸出它的介紹， 如果沒有那么輸出錯誤的提示提醒游客進展相關的操作來進入到正確的操作過程當中。2.4查找最短路徑函數的概要設計對于查找最短路徑的這一項功能，可以利用迪杰斯特拉算法，但我是用的費洛伊德算法，相對來說步驟跟簡單一點。后面有詳細介紹。2.5景點分布圖的概要設計先手稿繪制所有景點的分布，利用printf；函數打印分布圖的框架構造。各景點之間用線條，通過分布圖能全面的對校園各景點有個方位感。2.6退出函數

12、的概要設計關于退出函數， 那么是當游客執行完了他想要進展的操作過后選擇退出的功能的時候就調用退出函數 exit(0); 跳入到退出界面實現退出的功能。專業資料整理WORD格式4專業資料整理WORD格式瓊州學院本科生課程設計詳細設計3 詳細設計3.1程序的流程圖當我們想要更加實際的了解一個程序的算法過程的時候，我們就要依據程序的流程圖來給我們一個比較實際的過程， 從流程圖當中能夠更加清楚整個程序實現的過程是怎樣的。其流程圖如圖 3.1 所示：start創立無向圖寫入無向圖中Case 3查找信息TFCase 2最短路徑FTCase 1分布圖FTCase 4end圖 3.1 流程圖專業資料整理WOR

13、D格式5專業資料整理WORD格式瓊州學院本科生課程設計詳細設計3.2主函數的詳細設計主函數是一個程序的主體， 當我們要進展我們所需要的操作的時候我們就要根據主函數中的顯示信息和它給我們的相關的提示信息來進展所需要的操作，因此在這次的程序實現的過程當中，調用 Browser(); 提示游客根據 switch(); 的選擇語句，選擇來進入到相關的操作界面實現程序的根本功能。 ，3.3查找介紹函數的詳細設計當游客選擇了要查找景點的信息的介紹這一項功能的時候，程序就會調用Search( ); 函數進入到查找景點的介紹的界面，當游客輸入了需要查找的景點的編號的時候，程序通過構造體，自動匹配相應的信息，查

14、找是否有這個景點。void Search(MGraph *G)int k,flag=1;while(flag)printf("請輸入要查詢的景點編號:");scanf("%d",&k);if(k<=0|k>G->vexnum)printf(" 景點編號不存在 ! 請重新輸入景點編號 :"); scanf("%d",&k);if(k>0&&k<=G->vexnum) flag=0;printf("n n");printf(&quo

15、t;編號景點名稱簡介 n");printf("%-4d%-16s%-62sn",G->vexsk.num,G->,G->roduction);printf(" n"); ，找到將它的編號返回，并輸出它的介紹，沒有找到這輸出錯誤提示，提醒游客進展相關的操作進入正確的操作過程當中。專業資料整理WORD格式6專業資料整理WORD格式瓊州學院本科生課程設計詳細設計3.4查找最短路徑函數的詳細設計當游客選擇了要查找兩個景點之間的最短距離這一項功能的時候，函數進入到查找兩個景點之間的最短距離的操作界面

16、當中， 當游客輸入了兩個景點的名稱過后，程序會判斷是否有這兩個景點，如果有那么返回他們各自的編號，并調用 Floyd( ); 函數進入到查找最短路徑問題的程序當中。void Floyd(MGraph *G)int v,u,i,w,k,j,flag=1,p141414,D1414;for(v=1;v<=G->vexnum;v+)for(w=1;w<=G->vexnum;w+)Dvw=G->arcsvw.adj;for(u=1;u<=G->vexnum;u+)pvwu=0;if(Dvw<INFINITY)pvwv=1;pvww=1;for(u=1;u

17、<=G->vexnum;u+)for(v=1;v<=G->vexnum;v+)for(w=1;w<=G->vexnum;w+)if(Dvu+Duw<Dvw)Dvw=Dvu+Duw;for(i=1;i<=G->vexnum;i+)pvwi=pvui | puwi;while(flag)printf("請輸入出發點和目的地的編號:");scanf("%d%d",&k,&j);if(k<=0 | k>G->vexnum | j<=0 | j>G->vexn

18、um)printf(" 景點編號不存在 ! 請重新輸入出發點和目的地的編號 :"); scanf("%d%d",&k,&j);if(k=j)專業資料整理WORD格式7專業資料整理WORD格式瓊州學院本科生課程設計詳細設計printf("出發點和目的地一樣! 請重新輸入出發點和目的地的編號 :");scanf("%d%d",&k,&j);if(k>0 && k<=G->vexnum && j>0 && j<=

19、G->vexnum)flag=0;printf("n最短游覽路線： %s",G->);if(k>j)for(u=G->vexnum;u>0;u-)if(pkju && k!=u && j!=u)printf("->%s",G->);if(k<j)for(u=1;u<=G->vexnum;u+)if(pkju && k!=u && j!=u)printf("->%s",

20、G->);printf("->%s",G->);printf("總路線長 %dmn",Dkj);有 n 個頂點的有向圖 ,佛洛伊德算法可以求解出每一對頂點之間的最短路徑。假設使用鄰接矩陣 d ( i, j) 來對圖進展存儲 , d ( i, j) 表示 i 到j 之間的距離 ,但是該距離不一定是最短距離。 佛洛伊德算法的根本思想是 :為求頂點 ij 之間的最短距離 ,需要進展 n 次試探。首先將0 參加路徑 ,考慮路徑i 0j 是否存在 ,如果存在 ,那么比較i j 和 i 0 j 的路徑長度 ,

21、取長度短的路徑作為 i j 的路徑 ,記作 (i , j ) 。接著在路徑上再增加一個頂點1 ,比較i 1 j 和 (i ,j )的路徑長度 , 取長度短的路徑作為 (i , j) 。不斷將頂點 2 ,3 , .,n - 1 參加進展試探 , 最后得到的 (i , j ) 必定為 i j 的最短路徑。假設使用數組 dk ( i, j) 表示參加頂點 k 后,最短路徑長度的變化情況 ,使用數組 pk ( i, j) 表示參加頂點 k 后,最短路徑上頂點的變化情況 , 這樣就求得了最短路徑和最短路徑長度。3.5景點分布圖的詳細設計這里不詳細介紹，具體代碼，查看附錄browse_view_distr

22、ibute ( )函數。專業資料整理WORD格式8專業資料整理WORD格式瓊州學院本科生課程設計詳細設計3.6退出函數的詳細設計對于退出函數，當游客選擇了退出這一個操作的時候， 程序就會調用 exit(0); 函數實現退出主函數的功能。最后會提示游客，歡迎下次繼續使用！3.7數據構造的詳細設計本軟件的數據構造包括3 個局部：1. 鄰接矩陣typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; 定義一個鄰接矩陣，用鄰接矩陣來定義和儲存邊的相關信息。2. 頂點的構造體typedef struct Vertex/定義圖中頂點的數據類型int num;/

23、景點編號char name30;/景點名稱char introduction200;/景點介紹Vertex;定義一個頂點的構造體， 用來儲存景點的編號、 景點得名稱和景點的介紹等關于景點的信息。3.無向圖的構造體typedef struct /定義圖的數據類型Vertex vexsMAX_VERTEX_NUM;/ 頂點的構造體AdjMatrix arcs;/ 邊的鄰接矩陣int vexnum,arcnum;/頂點的個數，邊的個數MGraph;定義一個圖的構造體，用來儲存頂點的信息、邊的信息、 頂點的個數和邊的個數等相關的信息便于我們以后在用的時候能夠方便快捷的調用。定義好這些構造體后， 當我們

24、以后需要調用的時候，我們就能夠方便快捷的調用這些構造體，從而使得我們在運行程序的時候能夠更加的快速能夠提高我們的程序的運行效率，大大的節省了我們的時間還使得程序變得更加的簡單。專業資料整理WORD格式9專業資料整理WORD格式瓊州學院本科生課程設計軟件測試4 軟件測試4.1菜單的測試對于菜單函數的測試，首先菜單是一個可示化的界面，它能夠提示游客依據顯示屏上出現的提示來進展相關的操作， 查看所有的景點從而方便游客進展相關的操作，因而我們在運行程序的時候首先就會進入到菜單函數當中， 經過測試其能夠實現我們所要實現得根本功能，其效果圖如圖 4.1 所示：圖 4.1 菜單專業資料整理WORD格式10專

25、業資料整理WORD格式瓊州學院本科生課程設計軟件測試4.2查找景點簡介的測試對于查找景點的介紹的測試， 首先依據顯示屏上的提示首先輸入要進展的操作輸入 3 進入查找景點信息的操作界面， 然后輸入需要查找的景點的名稱即可顯示出景點的介紹信息， 經過測試可以得出其沒有什么錯誤， 程序能夠按照我的要*現它的功能，其效果圖如圖 4.2 所示：圖 4.2 查找景點信息專業資料整理WORD格式11專業資料整理WORD格式瓊州學院本科生課程設計軟件測試4.3查找兩個景點之間的最短距離的測試同查找景點的信息一樣，對于查找景點之間的最短距離的測試，我們就要依據提示輸入 2 進入到查詢最短路徑的界面， 依次輸入所

26、需要查找的兩個景點就會顯示出怎樣到達這兩個景點并顯示出它們之間的最短路徑， 經過測試可見程序能夠按照我的要求來實現其所需要的功能，其效果圖如圖4.3 所示：圖 4.3 查找兩個景點之間的最短距離專業資料整理WORD格式12專業資料整理WORD格式瓊州學院本科生課程設計軟件測試4.4查看景點分布圖的測試對于查看景點分布圖的測試，我需要依據顯示屏上的提示，需要輸入1 進入到分布圖的界面，系統就會直接調用browse_view_distribute();函數，在屏幕上打印出景點的分布圖。圖 4.4 景點分布圖界面專業資料整理WORD格式13專業資料整理WORD格式瓊州學院本科生課程設計軟件測試4.5

27、退出的測試原理同上，對于退出函數的測試，我需要依據顯示屏上的提示，需要輸入 4 進入到退出的界面，系統就會直接調用退出的函數， 顯示出“歡迎下次繼續使用！ 的話，退出了系統，其效果圖如圖 4.4 所示：圖 4.5 退出界面專業資料整理WORD格式14專業資料整理WORD格式瓊州學院本科生課程設計軟件使用說明5 軟件使用說明對于軟件的使用，對于第一次使用軟件的游客來說，要讓他們在第一次用的時候就能夠快速輕松的掌握軟件的用法， 因此在程序一開場運行的時候， 我們要進展如下的操作：1首先我會給游客提供一個可視化的菜單操作界面，在顯示屏上提示用戶其可以進展的操作和他能夠查詢的景點的編號、名稱。2用戶輸

28、入了“ 1后，屏幕上會顯示出所有景點的位置關系平面圖。能夠大致了解景點的分布。3當用戶輸入了“ 2后，進入到查詢任意兩景點間最短路徑的界面，然后提示用戶依次輸入兩個景點的編號， 程序就會將這兩個景點的最短路徑給我們表示出來并顯示出最短路徑是多少。4用戶輸入了“ 3后，進入到查詢景點信息的界面，然后提示用戶輸入景點的編號一次限一個 ，程序就會顯示出這個景點的詳細介紹。5當用戶輸入了“ 4后，進入到退出界面，這時系統就會顯示“歡迎下次繼續使用 ! 的提示語，最后按下任意鍵退出系統。專業資料整理WORD格式15專業資料整理WORD格式*科技學院本科生課程設計參考文獻6 參考文獻【 1】 數據構造 (

29、C 語言版 ) 嚴蔚敏 吳偉民 編著 清華大學 2002【 2】C程序設計經典教程，美Deitel,H.M.， 美 Deitel,P.J.著，清華大學2006【 3】Windows程序設計，美 Charles Petzold著，大學 2004【 4】Data Structures： A Pseudecode Approach with C 美 Richard F.Gilberg， 美 Behrouz A.Forouzan著專業資料整理WORD格式16專業資料整理WORD格式瓊州學院本科生課程設計附錄7 附錄7.1系統完整代碼#define INFINITY10000/*無窮大 */#defin

30、e MAX_VERTEX_NUM40#define MAX 40#include<stdlib.h>#include<stdio.h>#include<conio.h>#include<string.h>#include "Exit.h"typedef struct ArCellint adj;/路徑長度ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct/圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，char name30;int num;char

31、introduction200;/簡介infotype;typedef structinfotype vexsMAX_VERTEX_NUM;/ 景點AdjMatrix arcs;/路徑數組int vexnum,arcnum;/景點數，路徑長度記錄MGraph;MGraph b;/ 全局變量void cmd(void);/在主函數中用來調用其他應用子函數的函數聲明MGraph InitGraph(void);/用來構造學校地圖的子函數返回 MGraph類型void Menu(void);/菜單函數；void Browser(MGraph *G);/調用 MGraph類型的地址，進展void Sh

32、ortestPath_DIJ(MGraph * G);/迪杰斯特拉算法求最短路徑的子函數void Floyd(MGraph *G);/佛洛伊德算法void Search(MGraph *G);/尋找要查詢的景點，并輸出該景點的信息void browse_view_distribute();/查看景點分布圖void tou(MGraph *G);/景點列表void panduan();專業資料整理WORD格式17專業資料整理WORD格式瓊州學院本科生課程設計附錄/void Exit();/退出int LocateVex(MGraph *G,char* v);/定點位置MGraph * Creat

33、UDN(MGraph *G);/初始化圖形，承受用戶輸入void print(MGraph *G);/打印輸出子函數/*/void main(void)system("color 1f");/設置調試窗口背景和字體顏色system("mode con: cols=140 lines=130");/設置調試窗口的大小cmd();/用該函數來調用其他需要用到的函數/*/void cmd(void)/用來調用其他需要用到的函數的子函數int i;b=InitGraph();/構造校園地圖Browser(&b);/Menu();/調用菜單函數scanf(

34、"%d",&i);while(i!=4)switch(i)case1:system("cls");/*ShortestPath_DIJ(&b);*/browse_view_distribute();Browser(&b);break;case 2:system("cls");tou(&b);Floyd(&b);Browser(&b);break; case 3:system("cls");tou(&b);Search(&b);Browser(&

35、b);break; case 4:exit(0);break;default:break;scanf("%d",&i);printf("歡迎下次繼續使用!nn");/*MGraph InitGraph(void)/構造校園地圖MGraph G;int i,j;G.vexnum=13;/ 景點數量G.arcnum=21;/ 路徑數量for(i=1;i<=G.vexnum;i+)G.vexsi.num=i;/對景點進展對應編號專業資料整理WORD格式18專業資料整理WORD格式瓊州學院本科生課程設計附錄/* 對對應的景點編號進展命名，輸入簡介*

36、/strcpy(G.,"行政辦公樓 ");strcpy(G.roduction,"學校的行政機構。 ");strcpy(G.,"圖書館 ");strcpy(G.roduction,"體積龐大，是學校的標志性建筑，目前還在建立中。 ");strcpy(G.,"果園 ");strcpy(G.roduction,"枝葉茂盛，各種新鮮水果。");strcpy(G.vexs

37、1.name,"校門 ");strcpy(G.roduction," 學校的形象，氣勢宏偉。 "); strcpy(G.," 體育運動區 ");strcpy(G.roduction," 包括有排球場、籃球場、網球場等。 "); strcpy(G.," 教學區 ");strcpy(G.roduction,"包括左教學樓、小湖、右教學樓、實驗樓和醫務室等。 ");strcpy(G.vex