1、數據結構課程設計報告榆 林 學 院數據結構課程設計報告 題 目 城市交通咨詢系統 作 者 楊朝 專 業 信息管理與信息系統 學 號 1514210121 指導老師 張慧 答辯時間 2016.12.18 目錄目錄11系統需求分析21.1用戶需求分析21.2功能需求分析31.3數據需求分析31.4 小結32系統設計42.1系統設計思路42.2系統設計功能42.3每個模塊的具體能52.4主函數的調用關圖103系統測試113.1操作說明113.2測試數據113.2.1用戶進入界面113.2.2具體功能的實現123.2.3選擇0結束程序144總結145致謝146附錄151.系統需求分析描述：現如今網絡非

2、常發達，無論人們出差，旅游或者做其他的出行之時，都會想到道路問題，切不僅僅關心的是交通費用，而且對于里程和所需要的時間等的問題也是同樣的關心，在此系統中，完全面向用戶，可以用一個圖結構來表示交通網絡系統，利用計算機建立一個交通咨詢系統。且在圖中，頂點表示城市，邊表示城市之間的交通關系。設計一個交通咨詢系統，能夠讓旅客咨詢從任一城市頂點到達另外一個城市之間頂點的最短路徑問題（最短里程問題）。對系統分析，主要從以下幾個方面進行分析。1.用戶需求分析2.功能需求分析3.數據需求分析1.1 用戶需求分析 現如今網絡非常發達，無論人們出差，旅游或者做其他的出行之時，都會想到道路問題，切不僅僅關心的是交通

3、費用，而且對于里程和所需要的時間等的問題也是同樣的關心，在此系統中，完全面向用戶，可以用一個圖結構來表示交通網絡系統，利用計算機建立一個交通咨詢系統。且在圖中，頂點表示城市，邊表示城市之間的交通關系。設計一個交通咨詢系統，能夠讓旅客咨詢從任一城市頂點到達另外一個城市之間頂點的最短路徑問題（最短里程問題）。當要查詢某兩個城市之間的最短交通路線或者其中一個城市到達其余城市的最短路線時，是一個很繁瑣的過程。 根據用戶自己的需求，可以自定義地圖，此程序就是主要以滿足用戶自己的環境與實際情況，在難以計算路程時，可將地圖輸入進行計算，系統將會為用戶提供所用路徑最短的出現路線，更好的滿足用戶需求。以下是針對

4、咨詢用戶說明其最基本的模塊功能。 （1） 進入程序后，用戶可自己設置城市的個數，以及所有城市之間總共的路徑，且分別用頂點和邊表示城市與路徑（2） 用戶根據自己設置的城市個數和路徑數，具體輸入每個路徑的起始點以及每條路徑的長度。（3）進入菜單選擇界面（4）選擇2，系統為用戶進行提供任意城市的交通查詢,即查詢任意兩個城市之間的一條最短路徑。（5）選擇1，系統為用戶提供指定城市的交通查詢，即查詢指定城市到其他城市之間的最短路徑。如若輸入頂點超出范圍顯示錯誤，系統回到菜單重新選擇（6）選擇0，系統推出程序。1.2功能需求分析城市交通咨詢系統總體的設計目標：用數據結構中的鄰接矩陣作數據結構，并結合數據結

5、構有向圖的最短路徑計算方法，結合相應的數據算法以及c語言的相關知識，編寫一個良好的，具有可操作性的，以及能方便用戶的使用，包括自定義地圖，路徑與城市個數可結合實際情況而言，相對操作，簡便易懂并無難度。系統在菜單可根據命令進行相應的操作，已滿足用戶的需求。  1.2.1城市交通系統基本功能根據以上分析，此系統具備以下功能：（1） 用戶進入后的地圖創建界面（明確地圖中城市的個數以及路徑的個數）（2） 地圖完善界面（用戶自己輸入地圖中相關路徑的起始點以及路徑長度）（3） 菜單界面包含兩條命令（4） 命令1求一個城市到所有城市的最短距離（5） 命令2求任意的兩個城市之間的最短距離（6） 回復

6、命令0可推出程序。1.3數據需求分析  用鄰接矩陣建立交通網絡模塊VertexType vexsMVNum;/頂點數組，類型假定為char Adjmatrix arcsMVNumMVNum;/鄰接矩陣，類型假定為int型建立鄰接矩陣，用函數void CreateMGraph(MGraph * G,int n,int e) /采用鄰接矩陣表示法構造有向圖G，n、e表示圖的當前頂點數和邊數  用迪杰斯特拉算法計算某頂點到其余頂點的最短路徑用函數void Dijkstra (MGraph * G,int n,int e) 來定義此函數采用鄰接矩陣表示法構造有向圖G，n、e表示圖的

7、當前頂點數和邊數  用弗洛伊德算法求任意一對頂點的最短路徑 用函數 void Floyd(MGraph *G,int n) 來定義。利用費洛伊德算法，求出最短路徑。1.4 小結 從各種需求方面下手改編代碼，并不斷調試，讓界面更加友好。不斷地嘗試上，在各種問題上不斷突破，慢慢的完善代碼，等最大限度的滿足用戶需求。這幾天短時間的課程設計也讓我認識到了自己在這門課程上還面臨著許許多多的問題，為以后的具體實踐明確了努力方向。同時，城市交通咨詢系統的實現，為用戶更好的解決了再實際出行時遇到的路徑問題，最初的設計也為代碼敲定了編寫方向。再三考慮后確定了系統的功能，確定什么功能有實現必要，什么功能

8、可有可無。在這樣的基礎之下使得思路更加清晰。2.系統設計  2.1系統設計思路 本程序首先是用戶編輯界面，用戶根據自己的需求編寫地圖，從而加入頂點的數組之中，創建的地圖用鄰接矩陣存儲，在從主函數之中進行調用，實現對兩個算法的調用。用戶在輸入頂點以及邊的信息都會存儲，在存儲成功之后會提示用戶存儲成功，之后進入到菜單界面，菜單界面提供兩種選擇口令，分別可以調運Dijkstra和Floyd算法，調用之后輸入相應的口令以及要查詢的城市編號，算法會根據鄰接矩陣存儲的地圖進行計算，求出最短路徑。在以后使用完系統后，可輸入口令0，系統會結束一切運算，退出程序。  2.2系統設計

9、功能菜單界面的主要功能有兩個:（1）、求一個城市到所有城市的最短距離（2）、求任意的兩個城市之間的最短距離城市交通咨詢系統主要有三個模塊分別為：（1）、鄰接矩陣的輸入與存儲構建交通網絡（2）、任意兩個城市的最短距離查詢（3）、兩個指定城市的最短距離查詢主界面的模塊概念圖如下：用戶進入系統交通網絡構建結果，退出系統任意兩個城市的 最短距離查詢兩個指定城市的最短距離查詢 圖 2.1  2.3每個模塊的具體功能。（1）、采用C語言定義相關數據類型1定義一個，用來存儲頂點信息。typedef struct VertexType vexsMAX; Adjmatrix arcsMAXMAX;MG

10、raph; . 2定義一個Dijkstra函數void Dijkstra(MGraph *G,int v,int n);3定義一個Floyd函數void Floyd(MGraph *G,int n);（2）、建立鄰接矩陣交通網絡：N結束k<=e,k+開始 輸入頂點和邊數n,e輸入i,j,w Y 圖2.2鄰接矩陣構造圖結構函數數據類型定義：typedef struct VertexType vexsMAX; Adjmatrix arcsMAXMAX;MGraph;void CreateMGraph(MGraph *G,int n,int e)/鄰接矩陣構成有向圖 int i,j,k,w;

11、for(i=1;i<=n;i+) G->vexsi=(char)i; for(i=1;i<=n;i+) for(j=1;j<=n;j+) G->arcsij=IDF; printf("輸入%d條邊的i,j及w: n",e); for(k=1;k<=e;k+) scanf("%d,%d,%d",&i,&j,&w); G->arcsij=w; printf("有向圖的存儲結構建立完畢!n");其中vexsMAX保存頂點信息，arcsMAXMAX用于保存邊與邊之間的信息。在構

12、建時通過輸入的邊數i，j作為矩陣的行、列確定頂點的出度和入度。用鄰接矩陣方法存儲圖。（3）、查詢指定城市到其他城市自己建的最短路程：開始 輸入頂點v狄克斯特拉算法輸出路徑,距離結束 圖2.3應用狄克斯特拉算法來具體實現這一步的需求。基本思想：設G（V,E）是一個帶權有向圖，把圖中的頂點集合V分成兩組，第一組為已經求出的最短路徑的頂點集合（用S表示，初始時S中只有一個原點，以后每求得一條最短路徑就加入的集合S中，知道全部頂點都加入到集合中），第二組，為其余未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點就如S中。如果兩個頂點之間有權值，并且各個路徑的權值不同，就把

13、最小的作為頂點與頂點的最短距離。k yuv x z 圖2.4如圖所示 若x+y<z，則最短的路徑就是v=>k=>u。同理若x+y<z，則最短的路徑就是v=>u，D v1=0;Sv1=1; /原點編號放入s中 for(i=2;i<n;i+) min=IDF; for(w=1;w<=n;w+) if(!Sw&&D w<min) v=w;min=D w; Sv=1; /修改頂點u放入s中 for(w=1;w<=n;w+) if(!Sw&&(D v+G->arcsvw<D w) D w=D v+G->

14、;arcsvw; P w=v; （4）、查詢任意兩個城市之間的一條最短路徑：開始輸入起點v，終點w調用弗洛伊德算法輸出路徑,距離結束 圖2.5此過程需要應用弗洛伊德算法來具體實現。用鄰接矩陣保存圖存儲后，另外需要存一個二維數組A存放當前頂點之間的最短路徑長度。分量Aij表示當前頂點i到j的最短路徑長度。弗洛伊德算法的基本思維是遞推產生一個矩陣序列A0，A1，A2，.Ak， An，其中Akij表示從頂點到vi到頂點vj的路徑上所經過的頂點編號不大于k的最短路徑長度。Aij=costijA(k+1)ij=minAkij,Aki+1k+1+Akk+1j 弗洛伊德主要算法，若Akij已求出，頂點i到頂

15、點k+1的路徑長度為Akik+1，頂點路徑長度為Akij，頂點k+1到頂點j的路徑長度為Akk+1j，如果此時 Akik+1+Akk+1j< Akij,則將原來的頂點i到頂點j的路徑改為頂點，否則不需要修改頂點i到j的路徑。k+1ij Aki,k+1 Akk+1,j Aki,j 圖2.6若Akik+1+Akk+1 j< Akij,修改路徑 過程： for(k=1;k<=n;k+) for(i=1;i<=n;i+)for(j=1;j<=n;j+) if(Dik+Dkj<Dij)Dij=Dik+Dkj; /修改長度Pij=Pik;  2.4主函數的調用

16、關系圖 開始輸入參數選擇查詢 信息 0 1 2弗洛伊德狄克斯特退出輸出結果輸出結果結束3.系統測試  3.1操作說明雙擊“城市交通咨詢系統.exe”，根據屏幕菜單提示信息，選擇任意可選項進行相關操作。根據提示開始輸入城市個數以及路徑總個數。之后開始建立地圖，建立成功后根據菜單界面選擇功能。  3.2測試數據輸入測試數據可以對程序進行如下的圖的數據進行數據測試。21 8 4 6 543 6 7下面運行程序檢查輸入，輸出結果。  3.2.1用戶進入界面：（1）、輸入城市個數與路徑個數（2）輸入具體的頂點以及邊的個數：地圖輸入完成，有向圖存儲結構建立完成。 

17、3.2.2、具體功能的實現 1、求一個城市到所有城市之間的最短距離。查詢一個頂點到其他頂點的最短路徑。如下圖。經過手工計算：1=>1 長度=0，1=>2 長度=8，1=>3 長度=8+6=14，1=>4 長度=8+5=13；和下圖完全一致為保證結果正確換一個頂點進行：如頂點2到其他的距離經過手工計算：2=>1 長度=6+4=10，2=>2 長度=0，2=>3 長度=6，2=>4 長度=5；和下圖完全一致2、求任意的兩個城市之間的最短距離例1到3之間的最短距離，經過計算可得最短距離為1=>2=>3，且路徑為14，與下圖結果相同。為保證結

18、果正確換一個頂點進行：如頂點2到4之間的最短路徑以及距離經過計算可得2到4的最短路徑是2=>4,且最短路徑為5  3.2.3、選擇0結束程序 4.總結通過這次數據結構課程設計，我對數據結構這門課程有了更深一步的了解，使我對數據結構這門課程掌握以及運用更加靈活。同時也讓我發現了自己在這門課上的不足與缺陷，同時也明確了自己在以后的類似課程中的具體學習方法。這次在應用中，我發現了自己的很多不足，在編寫城市交通咨詢系統的過程中，自己C語言方面的只是掌握太少，很多功能需求只能退而求其次，一次又一次的更改，一次又一次的失敗，也終于是在最后也完成了自己的要求，同時我也知道了平時用功學習的重要

19、性。尤其是在日常學習之中，對于單一的只是點也許掌握的還不錯，但是自己動手太少，實踐經驗嚴重不足，且面臨課程設計之時，要求多方面的只是結和編碼，對于我而言還是有很大的難度的。如此次對于鄰接矩陣的存儲于讀取，以及最短路徑算法的實現，兩個及其重要的算法，狄克斯特拉算法和佛洛依德算法，在具體的應用上還是有很多不足。通過此次課程設計，我也明白了對于一個完成的程序而言，想要完成它最重要的代碼，最初，也是最為重要的一個部分就是算法思想，以及具體程序功能規劃，只有最重要的地基部分完美實現，才可以進行接下來的具體代碼編程，以及更多細節上的完美。通過這次的課程設計我有懂得了好多數據結構的知識，以前上課沒有聽的，不

20、知道的，這次都有所了解了，像有向圖的構建，弗洛伊德算法，迪克斯特拉算法。這些知識從曾經的聽說到現在的了解，進了一大步。不但如此，這次的課設也是我感覺到了數據結構的強大與神奇。漸漸的愛上他了。不僅讓我了解了數據結構更加深了對它與C語言的聯系的理解。因為自己的不學習，導致這次的課設變得如此的艱難。且因為自己生病住院也更是浪費了很大的時間，對于我自己做課程設計的時間就少的可憐，這也無疑是對我更大的挑戰。在臨近答辯，我的代碼才基本完成，夜以繼日的努力也終于是讓我完成5.致謝本次課程設計我遇到了極大的問題，不管是時間方面還是內容方面，自己都顯得慌亂過，我能夠完成本次課程設計也完全感謝舍友的支持與幫助，在

21、難點上能夠對我進行幫助。尤其感謝我的知道老師張老師。感謝她在百忙之中抽出時間來為我解答疑惑，解決問題，她對我此次的課程設計有極大的幫助。再次感謝張老師。課程設計馬上結束，同時也謝謝所有的負責老師，謝謝她們這幾天對我們的付出，老師辛苦了。  6.附錄#include<stdio.h> #include<stdlib.h> #define MVNum 100/最大頂點數 #define Maxint 32767 enum booleanFALSE,TRUE; typedef char VertexType; typedef int Adjmatrix; typed

22、ef struct VertexType vexsMVNum;/頂點數組，類型假定為char Adjmatrix arcsMVNumMVNum;/鄰接矩陣，類型假定為int型 MGraph; int D1MVNum,P1MVNum; int DMVNumMVNum,PMVNumMVNum; /*建立有向圖的儲存結構*/ void CreateMGraph(MGraph * G,int n,int e) /采用鄰接矩陣表示法構造有向圖G，n、e表示圖的當前頂點數和邊數 int i,j,k,w; for(i=1;i<=n;i+)/輸入頂點信息 G->vexsi=(char)i; for

23、(i=1;i<=n;i+) for(j=1;j<=n;j+) G->arcsij=Maxint;/初始化鄰接矩陣 printf(" = 輸入%d條邊人i（起點）、j（終點）及w（路徑長度）：n",e); for(k=1;k<=e;k+)/讀入e條邊，建立鄰接矩陣 printf(" =");scanf("%d,%d,%d",&i,&j,&w);G->arcsij=w; printf(" = 有向圖人存儲結構建立完畢！ =n"); /*迪杰斯特拉算法*/ void

24、Dijkstra(MGraph *G,int v1,int n) /利用迪杰斯特拉算法，求出有向圖G的v1頂點到其他頂點v 的最短路徑Pv及權Dv int D2MVNum,P2MVNum; int v,i,w,min; enum boolean SMVNum; for(v=1;v<=n;v+)/初始化S和D Sv=FALSE;/置空最短路徑終點集 D2v=G->arcsv1v;/置初始的最短路徑值 if(D2v<Maxint) P2v=v1;/v1是v的前趨（雙親） else P2v=0;/v無前趨（雙親） D2v1=0;Sv1=TRUE;/S集初始時只有源點，距離為0 fo

25、r(i=2;i<n;i+)/其余n-1個頂點 min=Maxint; for(w=1;w<=n;w+) if(!Sw && D2w<min) v=w;min=D2w; /w頂點離v1頂點更近 Sv=TRUE; for(w=1;w<=n;w+)/更新當前最短路徑及距離 if(!Sw&&(D2v+G->arcsvw<D2w) D2w=D2v+G->arcsvw; P2w=v; printf(" = 路徑長度，路徑 =n"); for(i=1;i<=n;i+) printf(" = %5d&

26、quot;,D2i); printf("%5d",i); v=P2i; while(v!=0) printf("<-%d",v); v=P2v; printf("n"); /*費洛伊德算法*/ void Floyd(MGraph *G,int n) /利用費洛伊德算法，求出最短路徑 int i,j,k; for(i=1;i<=n;i+) for(j=1;j<=n;j+) if(G->arcsij!=Maxint) Pij=j; else Pij=0; Dij=G->arcsij; for(k=1;k<=n;k+) for(i=1;i<=n;i+) for(j=1;j<=n;j+) if(Dik+Dkj<Dij) Dij=Dik+Dkj; Pij=Pik; void main() printf(" *歡迎使用城市交通咨詢系統*n"); printf("n");printf(" =n");MGraph *G; int n,e,v,w,k; int xz=1; G=(MGraph *)malloc(sizeof(MGraph); printf(" = 輸入城市個數和路徑個數n，e： ");