數(shù)據(jù)結(jié)構(gòu)課程設(shè)計城市交通咨詢系統(tǒng)Word版

1、傳播優(yōu)秀word版文檔 ，希望對您有幫助，可雙擊去除！榆 林 學(xué) 院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 題 目 城市交通咨詢系統(tǒng) 作 者 楊朝 專 業(yè) 信息管理與信息系統(tǒng) 學(xué) 號 1514210121 指導(dǎo)老師 張慧 答辯時間 2016.12.18 目錄目錄11系統(tǒng)需求分析21.1用戶需求分析21.2功能需求分析31.3數(shù)據(jù)需求分析31.4 小結(jié)32系統(tǒng)設(shè)計42.1系統(tǒng)設(shè)計思路42.2系統(tǒng)設(shè)計功能42.3每個模塊的具體能52.4主函數(shù)的調(diào)用關(guān)圖103系統(tǒng)測試113.1操作說明113.2測試數(shù)據(jù)113.2.1用戶進入界面113.2.2具體功能的實現(xiàn)123.2.3選擇0結(jié)束程序144總結(jié)145致謝146附錄15

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

3、想到道路問題，切不僅僅關(guān)心的是交通費用，而且對于里程和所需要的時間等的問題也是同樣的關(guān)心，在此系統(tǒng)中，完全面向用戶，可以用一個圖結(jié)構(gòu)來表示交通網(wǎng)絡(luò)系統(tǒng)，利用計算機建立一個交通咨詢系統(tǒng)。且在圖中，頂點表示城市，邊表示城市之間的交通關(guān)系。設(shè)計一個交通咨詢系統(tǒng)，能夠讓旅客咨詢從任一城市頂點到達另外一個城市之間頂點的最短路徑問題（最短里程問題）。當(dāng)要查詢某兩個城市之間的最短交通路線或者其中一個城市到達其余城市的最短路線時，是一個很繁瑣的過程。 根據(jù)用戶自己的需求，可以自定義地圖，此程序就是主要以滿足用戶自己的環(huán)境與實際情況，在難以計算路程時，可將地圖輸入進行計算，系統(tǒng)將會為用戶提供所用路徑最短的出現(xiàn)路

4、線，更好的滿足用戶需求。以下是針對咨詢用戶說明其最基本的模塊功能。 （1） 進入程序后，用戶可自己設(shè)置城市的個數(shù)，以及所有城市之間總共的路徑，且分別用頂點和邊表示城市與路徑（2） 用戶根據(jù)自己設(shè)置的城市個數(shù)和路徑數(shù)，具體輸入每個路徑的起始點以及每條路徑的長度。（3）進入菜單選擇界面（4）選擇2，系統(tǒng)為用戶進行提供任意城市的交通查詢,即查詢?nèi)我鈨蓚€城市之間的一條最短路徑。（5）選擇1，系統(tǒng)為用戶提供指定城市的交通查詢，即查詢指定城市到其他城市之間的最短路徑。如若輸入頂點超出范圍顯示錯誤，系統(tǒng)回到菜單重新選擇（6）選擇0，系統(tǒng)推出程序。1.2功能需求分析城市交通咨詢系統(tǒng)總體的設(shè)計目標(biāo)：用數(shù)據(jù)結(jié)構(gòu)中

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

6、兩個城市之間的最短距離（6） 回復(fù)命令0可推出程序。1.3數(shù)據(jù)需求分析  用鄰接矩陣建立交通網(wǎng)絡(luò)模塊vertextype vexsmvnum;/頂點數(shù)組，類型假定為char adjmatrix arcsmvnummvnum;/鄰接矩陣，類型假定為int型建立鄰接矩陣，用函數(shù)void createmgraph(mgraph * g,int n,int e) /采用鄰接矩陣表示法構(gòu)造有向圖g，n、e表示圖的當(dāng)前頂點數(shù)和邊數(shù)  用迪杰斯特拉算法計算某頂點到其余頂點的最短路徑用函數(shù)void dijkstra (mgraph * g,int n,int e) 來定義此函數(shù)采用鄰接矩陣

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

8、，確定什么功能有實現(xiàn)必要，什么功能可有可無。在這樣的基礎(chǔ)之下使得思路更加清晰。2.系統(tǒng)設(shè)計  2.1系統(tǒng)設(shè)計思路 本程序首先是用戶編輯界面，用戶根據(jù)自己的需求編寫地圖，從而加入頂點的數(shù)組之中，創(chuàng)建的地圖用鄰接矩陣存儲，在從主函數(shù)之中進行調(diào)用，實現(xiàn)對兩個算法的調(diào)用。用戶在輸入頂點以及邊的信息都會存儲，在存儲成功之后會提示用戶存儲成功，之后進入到菜單界面，菜單界面提供兩種選擇口令，分別可以調(diào)運dijkstra和floyd算法，調(diào)用之后輸入相應(yīng)的口令以及要查詢的城市編號，算法會根據(jù)鄰接矩陣存儲的地圖進行計算，求出最短路徑。在以后使用完系統(tǒng)后，可輸入口令0，系統(tǒng)會結(jié)束一切運算，退出

9、程序。  2.2系統(tǒng)設(shè)計功能菜單界面的主要功能有兩個:（1）、求一個城市到所有城市的最短距離（2）、求任意的兩個城市之間的最短距離城市交通咨詢系統(tǒng)主要有三個模塊分別為：（1）、鄰接矩陣的輸入與存儲構(gòu)建交通網(wǎng)絡(luò)（2）、任意兩個城市的最短距離查詢（3）、兩個指定城市的最短距離查詢主界面的模塊概念圖如下：用戶進入系統(tǒng)交通網(wǎng)絡(luò)構(gòu)建結(jié)果，退出系統(tǒng)任意兩個城市的 最短距離查詢兩個指定城市的最短距離查詢 圖 2.1  2.3每個模塊的具體功能。（1）、采用c語言定義相關(guān)數(shù)據(jù)類型1定義一個，用來存儲頂點信息。typedef struct vertextype vexsmax; adjmat

10、rix arcsmaxmax;mgraph; . 2定義一個dijkstra函數(shù)void dijkstra(mgraph *g,int v,int n);3定義一個floyd函數(shù)void floyd(mgraph *g,int n);（2）、建立鄰接矩陣交通網(wǎng)絡(luò)：n結(jié)束k<=e,k+開始 輸入頂點和邊數(shù)n,e輸入i,j,w y 圖2.2鄰接矩陣構(gòu)造圖結(jié)構(gòu)函數(shù)數(shù)據(jù)類型定義：typedef struct vertextype vexsmax; adjmatrix arcsmaxmax;mgraph;void createmgraph(mgraph *g,int n,int e)/鄰接矩陣構(gòu)成

11、有向圖 int i,j,k,w; 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("有向圖的存儲結(jié)構(gòu)建立完畢!n");其中vexsmax保存頂點信息，arcsmaxm

12、ax用于保存邊與邊之間的信息。在構(gòu)建時通過輸入的邊數(shù)i，j作為矩陣的行、列確定頂點的出度和入度。用鄰接矩陣方法存儲圖。（3）、查詢指定城市到其他城市自己建的最短路程：開始 輸入頂點v狄克斯特拉算法輸出路徑,距離結(jié)束 圖2.3應(yīng)用狄克斯特拉算法來具體實現(xiàn)這一步的需求?；舅枷耄涸O(shè)g（v,e）是一個帶權(quán)有向圖，把圖中的頂點集合v分成兩組，第一組為已經(jīng)求出的最短路徑的頂點集合（用s表示，初始時s中只有一個原點，以后每求得一條最短路徑就加入的集合s中，知道全部頂點都加入到集合中），第二組，為其余未確定最短路徑的頂點集合（用u表示），按最短路徑長度的遞增次序依次把第二組的頂點就如s中。如果兩個頂點之間有

13、權(quán)值，并且各個路徑的權(quán)值不同，就把最小的作為頂點與頂點的最短距離。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

14、 w) d w=d v+g->arcsvw; p w=v; （4）、查詢?nèi)我鈨蓚€城市之間的一條最短路徑：開始輸入起點v，終點w調(diào)用弗洛伊德算法輸出路徑,距離結(jié)束 圖2.5此過程需要應(yīng)用弗洛伊德算法來具體實現(xiàn)。用鄰接矩陣保存圖存儲后，另外需要存一個二維數(shù)組a存放當(dāng)前頂點之間的最短路徑長度。分量aij表示當(dāng)前頂點i到j(luò)的最短路徑長度。弗洛伊德算法的基本思維是遞推產(chǎn)生一個矩陣序列a0，a1，a2，.ak， an，其中akij表示從頂點到vi到頂點vj的路徑上所經(jīng)過的頂點編號不大于k的最短路徑長度。aij=costija(k+1)ij=minakij,aki+1k+1+akk+1j 弗洛伊德主要

15、算法，若akij已求出，頂點i到頂點k+1的路徑長度為akik+1，頂點路徑長度為akij，頂點k+1到頂點j的路徑長度為akk+1j，如果此時 akik+1+akk+1j< akij,則將原來的頂點i到頂點j的路徑改為頂點，否則不需要修改頂點i到j(luò)的路徑。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

16、;  2.4主函數(shù)的調(diào)用關(guān)系圖 開始輸入?yún)?shù)選擇查詢 信息 0 1 2弗洛伊德狄克斯特退出輸出結(jié)果輸出結(jié)果結(jié)束3.系統(tǒng)測試  3.1操作說明雙擊“城市交通咨詢系統(tǒng).exe”，根據(jù)屏幕菜單提示信息，選擇任意可選項進行相關(guān)操作。根據(jù)提示開始輸入城市個數(shù)以及路徑總個數(shù)。之后開始建立地圖，建立成功后根據(jù)菜單界面選擇功能。  3.2測試數(shù)據(jù)輸入測試數(shù)據(jù)可以對程序進行如下的圖的數(shù)據(jù)進行數(shù)據(jù)測試。21 8 4 6 543 6 7下面運行程序檢查輸入，輸出結(jié)果。  3.2.1用戶進入界面：（1）、輸入城市個數(shù)與路徑個數(shù)（2）輸入具體的頂點以及邊的個數(shù)：地圖輸入完成，有向

17、圖存儲結(jié)構(gòu)建立完成。  3.2.2、具體功能的實現(xiàn) 1、求一個城市到所有城市之間的最短距離。查詢一個頂點到其他頂點的最短路徑。如下圖。經(jīng)過手工計算：1=>1 長度=0，1=>2 長度=8，1=>3 長度=8+6=14，1=>4 長度=8+5=13；和下圖完全一致為保證結(jié)果正確換一個頂點進行：如頂點2到其他的距離經(jīng)過手工計算：2=>1 長度=6+4=10，2=>2 長度=0，2=>3 長度=6，2=>4 長度=5；和下圖完全一致2、求任意的兩個城市之間的最短距離例1到3之間的最短距離，經(jīng)過計算可得最短距離為1=>2=>3，且路

18、徑為14，與下圖結(jié)果相同。為保證結(jié)果正確換一個頂點進行：如頂點2到4之間的最短路徑以及距離經(jīng)過計算可得2到4的最短路徑是2=>4,且最短路徑為5  3.2.3、選擇0結(jié)束程序 4.總結(jié)通過這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，我對數(shù)據(jù)結(jié)構(gòu)這門課程有了更深一步的了解，使我對數(shù)據(jù)結(jié)構(gòu)這門課程掌握以及運用更加靈活。同時也讓我發(fā)現(xiàn)了自己在這門課上的不足與缺陷，同時也明確了自己在以后的類似課程中的具體學(xué)習(xí)方法。這次在應(yīng)用中，我發(fā)現(xiàn)了自己的很多不足，在編寫城市交通咨詢系統(tǒng)的過程中，自己c語言方面的只是掌握太少，很多功能需求只能退而求其次，一次又一次的更改，一次又一次的失敗，也終于是在最后也完成了自己的要求

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

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

21、設(shè)計也完全感謝舍友的支持與幫助，在難點上能夠?qū)ξ疫M行幫助。尤其感謝我的知道老師張老師。感謝她在百忙之中抽出時間來為我解答疑惑，解決問題，她對我此次的課程設(shè)計有極大的幫助。再次感謝張老師。課程設(shè)計馬上結(jié)束，同時也謝謝所有的負(fù)責(zé)老師，謝謝她們這幾天對我們的付出，老師辛苦了。  6.附錄#include<stdio.h> #include<stdlib.h> #define mvnum 100/最大頂點數(shù) #define maxint 32767 enum booleanfalse,true; typedef char vertextype; typedef int

22、 adjmatrix; typedef struct vertextype vexsmvnum;/頂點數(shù)組，類型假定為char adjmatrix arcsmvnummvnum;/鄰接矩陣，類型假定為int型 mgraph; int d1mvnum,p1mvnum; int dmvnummvnum,pmvnummvnum; /*建立有向圖的儲存結(jié)構(gòu)*/ void createmgraph(mgraph * g,int n,int e) /采用鄰接矩陣表示法構(gòu)造有向圖g，n、e表示圖的當(dāng)前頂點數(shù)和邊數(shù) int i,j,k,w; for(i=1;i<=n;i+)/輸入頂點信息 g->v

23、exsi=(char)i; for(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(" = 有向圖人存儲結(jié)構(gòu)建立完畢！ =n");

24、/*迪杰斯特拉算法*/ void dijkstra(mgraph *g,int v1,int n) /利用迪杰斯特拉算法，求出有向圖g的v1頂點到其他頂點v 的最短路徑pv及權(quán)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;/

25、s集初始時只有源點，距離為0 for(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+)/更新當(dāng)前最短路徑及距離 if(!sw&&(d2v+g->arcsvw<d2w) d2w=d2v+g->arcsvw; p2w=v; printf(" = 路徑長度，路徑 =n"); for(i=1;i<=n;i+) pri

26、ntf(" = %5d",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->arc

27、sij; 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(" *歡迎使用城市交通咨詢系統(tǒng)*n"); printf("n");printf(" =n");mgraph *g; int n,e,v,w,k; int xz=1; g=(mgraph *)malloc(sizeof(mgraph); printf(" = 輸入城市個數(shù)和路徑個數(shù)n，e： &quo