1、課 程 設 計 報 告課程名稱課程名稱 數據結構課程設計數據結構課程設計 課題名稱課題名稱 交通咨詢系統交通咨詢系統 專專 業業 通信工程通信工程 班班 級級 通信通信 1001 班班 學學 號號 姓姓 名名 指導教師指導教師 田娟秀田娟秀 胡瑛胡瑛 曹燚曹燚 2012 年年 7 月月 6 日日2湖南工程學院課 程 設 計 任 務 書課程名稱 數據結構 課 題 交通咨詢系統 專業班級 通信 1001 班 學生姓名 學 號 指導老師 田娟秀 胡瑛 曹燚 審 批 田娟秀 任務書下達日期 2012 年 7 月 1 日任務完成日期 2012 年 7 月 6 日31.11.1 任務書任務書課題六：交通咨

2、詢系統：在交通網絡非常發達的今天，人們出差、旅游或做其他出行時，不僅關心節省交通費用，而且對里程和所需時間等問題也很感興趣。對于這樣一個人們關心的問題，可用一個圖結構來表示交通網絡系統，利用計算機建立一個交通咨詢系統。圖中頂點表示城市，邊表示城市之間的交通關系。設計一個交通咨詢系統，能讓旅客咨詢從任一個城市頂點到達另外一個城市頂點之間的最短路徑（里程）的問題。 要求完成以下功能：(a) 以圖中頂點表示湖南省各市(至少包括 8 個以上的城市)，存放城市名稱、代號、簡介等信息，以邊表示路徑，存放路徑長度等有關信息，先建立交通網絡圖的存儲結構；(b) 為用戶提供圖中任何城市有關信息的查詢；(c) 為

3、用戶提供任意城市的交通查詢,即查詢任意兩個城市之間的一條最短路徑。(d) 為用戶提供指定城市的交通查詢，即查詢指定城市到其他城市之間的最短路徑。選做內容：（1）提供圖的編輯功能：增、刪城市；增刪路徑；修改已有信息等；（2）交通圖的仿真界面。1.21.2 選題方案：選題方案：所選題目根據學號確定，學號模 6 加 1，即（學號%6+1） 。如你的學號為 9，則所選題目號為：9%6+1（題目 4） 。注意，所有的課題都要求用圖形方式演示步驟和結果。同學們可以自己針對數據結構課程中所講算法來設計一個演示過程的算法。1.31.3 設計要求：設計要求：1.3.11.3.1 課程設計報告規范課程設計報告規范

4、（1）需求分析a.程序的功能。b.輸入輸出的要求。（2）概要設計4a.程序由哪些模塊組成以及模塊之間的層次結構、各模塊的調用關系；每個模塊的功能。b.課題涉及的數據結構和數據庫結構；即要存儲什么數據，這些數據是什么樣的結構，它們之間有什么關系等。（3）詳細設計a.采用 C 語言定義相關的數據類型。b寫出各模塊的類 C 碼算法。c.畫出各函數的調用關系圖、主要函數的流程圖。（4）調試分析以及設計體會a.測試數據：準備典型的測試數據和測試方案，包括正確的輸入及輸出結果和含有錯誤的輸入及輸出結果。b.程序調試中遇到的問題以及解決問題的方法。c.課程設計過程經驗教訓、心得體會。（5）使用說明用戶使用手

5、冊：說明如何使用你編寫的程序，詳細列出每一步的操作步驟。（6）書寫格式a.設計報告要求用 A4 紙打印成冊：b.一級標題用 3 號黑體,二級標題用四號宋體加粗,正文用小四號宋體;行距為22。（7）附錄源程序清單（帶注釋）1.3.21.3.2 考核方式考核方式指導老師負責驗收程序的運行結果，并結合學生的工作態度、實際動手能力、創新精神和設計報告等進行綜合考評，并按優秀、良好、中等、及格和不及格五個等級給出每位同學的課程設計成績。具體考核標準包含以下幾個部分：（1）平時出勤 （占 10%）（2）系統需求分析、功能設計、數據結構設計及程序總體結構合理與否（占10%）（3）程序能否完整、準確地運行，個

6、人能否獨立、熟練地調試程序（占 40%）（4）設計報告（占 30%）注意：不得抄襲他人的報告（或給他人抄襲） ，一旦發現，成績為零分。5（5）獨立完成情況（占 10%） 。1.3.31.3.3 課程驗收要求課程驗收要求（1）運行所設計的系統。（2）回答有關問題。（3）提交課程設計報告。（4）提交軟盤（源程序、設計報告文檔） 。（5）依內容的創新程度，完善程序情況及對程序講解情況打分。2 2 進度安排進度安排第 20 周：星期一 8：0012：00 上課 星期一 14：3018：30 上機星期二 14：3018：30 上機 星期三 8：0012：00 上機 附：課程設計報告裝訂順序：封面、任務書

7、、目錄、正文、評分表、附件（A4 大小的圖紙及程序清單） 。 正文的格式:一級標題用 3 號黑體,二級標題用四號宋體加粗,正文用小四號宋體;行距為 22。正文的內容:一、課題的主要功能；二、課題的功能模塊的劃分（要求畫出模塊圖） ；三、主要功能的實現（至少要有一個主要模塊的流程圖） ；四、程序調試；五、總結；六、附件（所有程序的原代碼，要求對程序寫出必要的注釋） 。正文總字數要求在 5000 字以上（不含程序原代碼） 。 6 目 錄一一 需求分析需求分析.71.1 程序的功能.71.2 輸入輸出的要求.7二概要設計二概要設計.82.1 程序的模塊組成.82.2 每個模塊的功能.82.3 存儲數

8、據及其關系.10三詳細設計三詳細設計.103.1 采用 C 語言定義相關類型.103.2 寫出各模塊的類 C 碼算法.113.3 調用關系圖.14四調試分析以及心得體會四調試分析以及心得體會.154.1 測試數據.154.2 心得體會 .17五五 使用說明使用說明.18六六 附錄附錄.19七評分表七評分表.247一 需求分析1.11.1 程序的功能程序的功能在交通網絡非常發達的今天，人們出差、旅游或做其他出行時，不僅關心節省交通費用，而且對里程和所需時間等問題也很感興趣。對于這樣一個人們關心的問題，可用一個圖結構來表示交通網絡系統，利用計算機建立一個交通咨詢系統。圖中頂點表示城市，邊表示城市之

9、間的交通關系。設計一個交通咨詢系統，能讓旅客咨詢從任一個城市頂點到達另外一個城市頂點之間的最短路徑（里程）的問題。 要求完成以下功能(a) 以圖中頂點表示湖南省各市(至少包括 8 個以上的城市)，存放城市名稱、代號、簡介等信息，以邊表示路徑，存放路徑長度等有關信息，先建立交通網絡圖的存儲結構；(b) 為用戶提供圖中任何城市有關信息的查詢；(c) 為用戶提供任意城市的交通查詢,即查詢任意兩個城市之間的一條最短路徑。(d) 為用戶提供指定城市的交通查詢，即查詢指定城市到其他城市之間的最短路徑。選做內容：（1）提供圖的編輯功能：增、刪城市；增刪路徑；修改已有信息等；（2）交通圖的仿真界面。1.21.

10、2 輸入輸出的要求輸入輸出的要求在用戶剛進入主界面后，系統就會提示輸入建立交通網絡的儲存結構，輸入頂點個數和和邊數，隨后會有系統進行提示輸入頂點信息以及他們的權值，即 I,j 和 w，依次根據邊的信息個數進行輸入。隨之進行的是查詢頁面，輸入選擇按鈕進行功能查詢選擇。如，選擇 1：表示的是查詢任意兩個城市之間的一條最短路徑，選擇 2：表示的是查詢指定城市到其他城市之間的最短路徑，選擇 0：表示你將要退出程序查詢系統。二概要設計2.12.1 程序的模塊組成程序的模塊組成本程序主要有三個模塊組成，他們分別是：鄰接矩陣建立有向圖，查詢任意8兩個城市之間的一條最短路徑，查詢指定城市到其他城市之間的最短路

11、徑。三個模塊的概圖：任意兩個城市的 最短距離查詢兩個指定城市的最短距離查詢 圖 2.12.22.2 每個模塊的功能每個模塊的功能鄰接矩陣建立交通網絡 Y用戶進入系統交通網絡構建結果，退出系統開始輸入 n,e輸入 i,j,wk=e,k+結束N9 圖 2.2.1查詢指定城市到其他城市之間的最短路徑 圖 2.2.2 查詢任意兩個城市之間的一條最短路徑：開始輸入頂點 v狄克斯特拉算法輸出路徑,距離結束開始輸入起點v，終點 w輸出路徑,距離結束10 圖 2.2.32.32.3 存儲數據及其關系存儲數據及其關系比如下列五個數據之間的存儲及其關系12453 圖 2.3上圖說明：上圖各個節點之間會有一條或者兩

12、條邊，當輸入他們的信息時根據他們的方向進行有向圖的存儲。并且每兩個頂點之間（單向）都會有一個值 w，即權值。如頂點 1 和 2 之間可以設置他的權值是 2，頂點 2 到頂點 5 的權值可以是3，頂點 5 到頂點 2 的權值可以是 4，等等。三詳細設計3.13.1 采用采用 C C 語言定義相關類型語言定義相關類型1定義一個，用來存儲頂點信息。typedef struct VertexType vexsMAX; Adjmatrix arcsMAXMAX;MGraph; . 2定義一個 Dijkstra 函數void Dijkstra(MGraph *G,int v,int n);2定義一個 Fl

13、oyd 函數調用弗洛伊德算法11void Floyd(MGraph *G,int n);3.23.2 寫出各模塊的類寫出各模塊的類 C C 碼算法碼算法鄰接矩陣構造圖結構函數數據類型定義：typedef struct VertexType vexsMAX; Adjmatrix arcsMAXMAX;MGraph;void CreateMGraph(MGraph *G,int n,int e)/鄰接矩陣構成有向圖 int i,j,k,w; for(i=1;ivexsi=(char)i; for(i=1;i=n;i+) for(j=1;jarcsij=IDF; printf(輸入%d 條邊的 i,

14、j 及 w: n,e); for(k=1;karcsij=w; printf(有向圖的存儲結構建立完畢!n);其中 vexsMAX保存頂點信息，arcsMAXMAX用于保存邊與邊之間的信息。在構建時通過輸入的邊數 i，j 作為矩陣的行、列確定頂點的出度和入度。用鄰接矩陣方法存儲圖。12Dijkstra 算法； 基本思想：設 G（V,E）是一個帶權有向圖，把圖中的頂點集合 V 分成兩組，第一組為已經求出的最短路徑的頂點集合（用 S 表示，初始時 S 中只有一個原點，以后每求得一條最短路徑就加入的集合 S 中，知道全部頂點都加入到集合中） ，第二組，為其余未確定最短路徑的頂點集合（用 U 表示）

15、，按最短路徑長度的遞增次序依次把第二組的頂點就如 S 中。如果兩個頂點之間有權值，并且各個路徑的權值不同，就把最小的作為頂點與頂點的最短距離。 y x z 圖 3.3.1如圖所示 若 x+yk=u。同理若 x+yu，D v1=0;Sv1=1; /原點編號放入 s 中 for(i=2;in;i+) min=IDF; for(w=1;w=n;w+) if(!Sw&D wmin) v=w;min=D w; Sv=1; /修改頂點 u 放入 s 中 for(w=1;warcsvwarcsvw; P w=v; 弗洛伊德算法：kvu13用鄰接矩陣保存圖存儲后，另外需要存一個二維數組 A 存放當前頂

16、點之間的最短路徑長度。分量 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 到頂點 k+1 的路徑長度為 Akik+1，頂點路徑長度為 Akij，頂點 k+1 到頂點 j 的路徑長度為 Akk+1j，如果此時 Akik+1+Akk+1j Akij,則將原來的頂點 i 到頂點 j 的路徑

17、改為頂點，否則不需要修改頂點 i 到 j 的路徑。 Aki,k+1 Akk+1,j Aki,j 圖 3.3.2 若 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+Dkj1 長度=0，1=2 長度=3，1=3 長度=3+3=8，1=4 長度=3+6=9；和下圖完全一致圖 4.4.3 3為保證結果正確換一個頂點進行：如圖 4.4.4，計算可知結果正確。 圖 4.4.4 4查詢一個頂點到另一個頂點的最短路徑：如圖 4.4.5，經計算：可知結果正確。 圖 4.4.5 5選擇 0 進行

18、 退出程序的操作。如下圖 4.4.6 圖 4.4.6 174.24.2 心得體會心得體會 “平時不好干，遇事只能看” ，經過這幾天的數據結構的課程設計對這句話這真的別有一番的體會。 “成功只屬于有準備的人” ，真的，這幾天的課程設計讓你不得不想起這句話。俗話說“厚積薄發” ，前期的積累，說不定什么時候就能夠用上。這次就是這樣，前期沒有積累足夠的知識儲備，以至于拿到課程設計的任務書時感覺無所適從，不知道從何下手，真是老虎吃刺猬，無從下口。所以，在第一次上課時就什么都沒有做，就那樣在實驗室里干看著別人在熱熱火火的搞自己的課程設計。于是乎自己只能看書，把自己以前丟失的都補回來。因為自己的不學習，導致

19、這次的課設變得如此的艱難。當別人都已經快答辯了，我的程序還只有那可憐的幾行，無獨有偶，也就是這樣，我一度準備放棄，心想就直接從網上拷貝一個就行了。可是，許三多的一句話敲醒了我，不拋棄，不放棄，對，不能放棄。就這樣。我堅持了下去，開始從各個方面入手，查書，查資料，一句一句的敲，一點一點的寫，不會的問老師，請教同學。終于功夫不負有心人。臨到答辯結束的我趕上了末班車。順利的通過了答辯，抹掉分數的高低吧。還是有小小的成就感的。通過這次的課程設計我有懂得了好多數據結構的知識，以前上課沒有聽的，不知道的，這次都有所了解了，像有向圖的構建，弗洛伊德算法，迪克斯特拉算法。這些知識從曾經的聽說到現在的了解，進了

20、一大步。不但如此，這次的課設也是我感覺到了數據結構的強大與神奇。漸漸的愛上他了。不僅讓我了解了數據結構更加深了對它與 C 語言的聯系的理解。課設已經結束了。真心的感謝我們的田老師，這么大熱的天，當其他老師都在空調房里舒服時，她還是冒著火烈的太陽，趕過來給我們指導。想讓我們學到更多的知識。在這里，深情的說一句：老師，您辛苦了，謝謝您。同樣感謝另外兩個老師的知道。謝謝你們。185使用說明第一步：運行程序。進入主界面。進一步提示輸入圖中的頂點，邊數。第二步：輸入邊之后按回車，進入圖的構建。依次輸入各個邊的的信息，i, j, w 根據自己所設的圖的不同進行設置。第三步：進入程序查詢區域。有選擇 1 或

21、 2 或 0 分別表示你所選擇的查詢不同方式。 （1）選擇 1 表示查詢一個頂點至其他所有頂點的最短路徑。會提示用戶進行查詢定點的選擇。系統將會顯示你要查詢的最短路徑。 （2）選擇 2 表示查詢任意兩個點之間的最短路徑，輸入用戶所要查詢的起點和終點就會顯示你要查詢的最短路徑。19 （3）選擇 0 表示用戶將要退出系統。6附錄#include#include#define MAX 100#define IDF 32767 /最大頂點數typedef char VertexType;typedef int Adjmatrix;typedef struct /設置數組保存頂點信息 VertexTyp

22、e vexsMAX; Adjmatrix arcsMAXMAX;MGraph; int D1MAX,P1MAX;int DMAXMAX,PMAXMAX;void CreateMGraph(MGraph *G,int n,int e); /建立圖的存儲結構void Dijkstra(MGraph *G,int v1,int n); /狄克特求最短路徑void Floyd(MGraph *G,int n); /弗洛伊德算法void main()20 MGraph *G; int m,n,e,v,w,k; int xz=1; G=(MGraph *)malloc(sizeof(MGraph); pr

23、intf( *歡迎進入交通咨詢系統*n); printf(交通網絡圖的存儲結構n); printf(輸入圖中頂點,邊數 n，e: ); scanf(%d %d,&n,&e); CreateMGraph(G,n,e); while(xz!=0) printf( *下一步*n); printf( *查詢城市之間的路徑*n); printf( 1.查詢一個城市到所有城市的最短路徑n); printf( 2.查詢任意的兩個城市之間的最短路徑n); printf(請選擇: 1 or 2:n ); printf( 選擇:0 退出: ); scanf(%d,&xz); if(xz=2

24、) Floyd(G,n); /調用費洛伊德算法 printf(輸入起點,終點：v,w: ); scanf(%d %d,&v,&w); k=Pvw;/k 保存最短路徑長度 if(k=0) printf(頂點%d 到 %d 無路徑!n,v,w); else printf(從頂點%d 到%d 的最短路徑是: %d,v,w,v); while(k!=w) printf(-%d,k);/輸入后繼結點繼續找下一個頂點 k=Pkw; 21 printf(-%d,w); /輸出終點 printf(路徑長度: %dn,Dvw); else if(xz=1) printf(輸入頂點 v: ); scanf(%d,&v); Dijkstra(G,v,n);/調用狄克斯特拉算法 printf(結束求最短路徑,再見! n);void CreateMGraph(MGraph *G,int n,int e)/鄰接矩陣構成有向圖 int i,j,k,w; for(i=1;ivexsi=(char)i; for(i=1;i=n;i+) for(j=1;jarcsij=IDF; printf(輸入%d 條邊的 i,j 及 w: n,e); for(k=1;karcsij=w; printf(有向圖的存儲結構