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

1、榆 林 學(xué) 院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 題 目 城市交通咨詢系統(tǒng) 作 者 楊朝 專 業(yè) 信息管理與信息系統(tǒng) 學(xué) 號(hào) 1514210121 指導(dǎo)老師 張慧 答辯時(shí)間 2016.12.18 目錄1.系統(tǒng)需求分析11.1用戶需求分析11.2功能需求分析21.3數(shù)據(jù)需求分析21.4 小結(jié)32.系統(tǒng)設(shè)計(jì)32.1系統(tǒng)設(shè)計(jì)功能32.2每個(gè)模塊的具體功能。42.2.1采用C語(yǔ)言定義相關(guān)數(shù)據(jù)類型42.2.2建立鄰接矩陣交通網(wǎng)絡(luò)：42.2.3查詢指定城市到其他城市自己建的最短路程：62.2.4查詢?nèi)我鈨蓚€(gè)城市之間的一條最短路徑：72.3主函數(shù)的調(diào)用關(guān)系圖83.系統(tǒng)測(cè)試93.1操作說(shuō)明93.2測(cè)試數(shù)據(jù)103.2.1用戶

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

3、.功能需求分析3.數(shù)據(jù)需求分析1.1用戶需求分析現(xiàn)如今網(wǎng)絡(luò)非常發(fā)達(dá)，無(wú)論人們出差，旅游或者做其他的出行之時(shí)，都會(huì)想到道路問(wèn)題，切不僅僅關(guān)心的是交通費(fèi)用，而且對(duì)于里程和所需要的時(shí)間等的問(wèn)題也是同樣的關(guān)心，在此系統(tǒng)中，完全面向用戶，可以用一個(gè)圖結(jié)構(gòu)來(lái)表示交通網(wǎng)絡(luò)系統(tǒng)，利用計(jì)算機(jī)建立一個(gè)交通咨詢系統(tǒng)。且在圖中，頂點(diǎn)表示城市，邊表示城市之間的交通關(guān)系。設(shè)計(jì)一個(gè)交通咨詢系統(tǒng)，能夠讓旅客咨詢從任一城市頂點(diǎn)到達(dá)另外一個(gè)城市之間頂點(diǎn)的最短路徑問(wèn)題（最短里程問(wèn)題）。當(dāng)要查詢某兩個(gè)城市之間的最短交通路線或者其中一個(gè)城市到達(dá)其余城市的最短路線時(shí)，是一個(gè)很繁瑣的過(guò)程。根據(jù)用戶自己的需求，可以自定義地圖，此程序就是主要

4、以滿足用戶自己的環(huán)境與實(shí)際情況，在難以計(jì)算路程時(shí)，可將地圖輸入進(jìn)行計(jì)算，系統(tǒng)將會(huì)為用戶提供所用路徑最短的出現(xiàn)路線，更好的滿足用戶需求。以下是針對(duì)咨詢用戶說(shuō)明其最基本的模塊功能。（1） 進(jìn)入程序后，用戶可自己設(shè)置城市的個(gè)數(shù)，以及所有城市之間總共的路徑，且分別用頂點(diǎn)和邊表示城市與路徑（2） 用戶根據(jù)自己設(shè)置的城市個(gè)數(shù)和路徑數(shù)，具體輸入每個(gè)路徑的起始點(diǎn)以及每條路徑的長(zhǎng)度。（3）進(jìn)入菜單選擇界面（4）選擇2，系統(tǒng)為用戶進(jìn)行提供任意城市的交通查詢,即查詢?nèi)我鈨蓚€(gè)城市之間的一條最短路徑。（5）選擇1，系統(tǒng)為用戶提供指定城市的交通查詢，即查詢指定城市到其他城市之間的最短路徑。如若輸入頂點(diǎn)超出范圍顯示錯(cuò)誤，系

5、統(tǒng)回到菜單重新選擇（6）選擇0，系統(tǒng)推出程序。1.2功能需求分析城市交通咨詢系統(tǒng)總體的設(shè)計(jì)目標(biāo)：用數(shù)據(jù)結(jié)構(gòu)中的鄰接矩陣作數(shù)據(jù)結(jié)構(gòu)，并結(jié)合數(shù)據(jù)結(jié)構(gòu)有向圖的最短路徑計(jì)算方法，結(jié)合相應(yīng)的數(shù)據(jù)算法以及c語(yǔ)言的相關(guān)知識(shí)，編寫(xiě)一個(gè)良好的，具有可操作性的，以及能方便用戶的使用，包括自定義地圖，路徑與城市個(gè)數(shù)可結(jié)合實(shí)際情況而言，相對(duì)操作，簡(jiǎn)便易懂并無(wú)難度。系統(tǒng)在菜單可根據(jù)命令進(jìn)行相應(yīng)的操作，已滿足用戶的需求。城市交通系統(tǒng)基本功能根據(jù)以上分析，此系統(tǒng)具備以下功能：（1） 用戶進(jìn)入后的地圖創(chuàng)建界面（明確地圖中城市的個(gè)數(shù)以及路徑的個(gè)數(shù)）（2） 地圖完善界面（用戶自己輸入地圖中相關(guān)路徑的起始點(diǎn)以及路徑長(zhǎng)度）（3） 菜

6、單界面包含兩條命令（4） 命令1求一個(gè)城市到所有城市的最短距離（5） 命令2求任意的兩個(gè)城市之間的最短距離（6） 回復(fù)命令0可推出程序。1.3數(shù)據(jù)需求分析 用鄰接矩陣建立交通網(wǎng)絡(luò)模塊VertexType vexsMVNum;/頂點(diǎn)數(shù)組，類型假定為char Adjmatrix arcsMVNumMVNum;/鄰接矩陣，類型假定為int型建立鄰接矩陣，用函數(shù)void CreateMGraph(MGraph * G,int n,int e) /采用鄰接矩陣表示法構(gòu)造有向圖G，n、e表示圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù) 用迪杰斯特拉算法計(jì)算某頂點(diǎn)到其余頂點(diǎn)的最短路徑用函數(shù)void Dijkstra (MGraph

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

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

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

10、MAXMAX;MGraph; . 2定義一個(gè)Dijkstra函數(shù)void Dijkstra(MGraph *G,int v,int n);3定義一個(gè)Floyd函數(shù)void Floyd(MGraph *G,int n);2.2.2建立鄰接矩陣交通網(wǎng)絡(luò)：開(kāi)始 輸入頂點(diǎn)和邊數(shù)n,e輸入i,j,wk=e,k+YN結(jié)束 圖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)成有向圖 int i,j,

11、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(有向圖的存儲(chǔ)結(jié)構(gòu)建立完畢!n);其中vexsMAX保存頂點(diǎn)信息，arcsMAXMAX用于保存邊與邊之間的信息。在構(gòu)建時(shí)通過(guò)輸入的邊數(shù)i，j作為矩陣的行、列確定頂點(diǎn)的出度和入度。用鄰接矩陣方法存儲(chǔ)圖。2.2.3查詢指定城市到其他城市自己建的最短路程：開(kāi)始輸入頂點(diǎn)v輸出路徑,距離結(jié)束狄克斯特拉算法圖2-3應(yīng)用狄克斯特拉算法來(lái)具體實(shí)現(xiàn)這一步的需求。基本思想：設(shè)G（V

12、,E）是一個(gè)帶權(quán)有向圖，把圖中的頂點(diǎn)集合V分成兩組，第一組為已經(jīng)求出的最短路徑的頂點(diǎn)集合（用S表示，初始時(shí)S中只有一個(gè)原點(diǎn)，以后每求得一條最短路徑就加入的集合S中，知道全部頂點(diǎn)都加入到集合中），第二組，為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)就如S中。如果兩個(gè)頂點(diǎn)之間有權(quán)值，并且各個(gè)路徑的權(quán)值不同，就把最小的作為頂點(diǎn)與頂點(diǎn)的最短距離。k yuv x z 圖2-4如圖所示 若x+yk=u。同理若x+yu，D v1=0;Sv1=1; /原點(diǎn)編號(hào)放入s中 for(i=2;in;i+) min=IDF; for(w=1;w=n;w+) if(!Sw&D w

13、min) v=w;min=D w; Sv=1; /修改頂點(diǎn)u放入s中 for(w=1;warcsvwarcsvw; P w=v; 2.2.4查詢?nèi)我鈨蓚€(gè)城市之間的一條最短路徑：其具體的流程圖如圖2-5所示：調(diào)用弗洛伊德算法結(jié)束輸出路徑,距離輸入起點(diǎn)v，終點(diǎn)w開(kāi)始 圖2-5此過(guò)程需要應(yīng)用弗洛伊德算法來(lái)具體實(shí)現(xiàn)。用鄰接矩陣保存圖存儲(chǔ)后，另外需要存一個(gè)二維數(shù)組A存放當(dāng)前頂點(diǎn)之間的最短路徑長(zhǎng)度。分量Aij表示當(dāng)前頂點(diǎn)i到j(luò)的最短路徑長(zhǎng)度。弗洛伊德算法的基本思維是遞推產(chǎn)生一個(gè)矩陣序列A0，A1，A2，.Ak， An，其中Akij表示從頂點(diǎn)到vi到頂點(diǎn)vj的路徑上所經(jīng)過(guò)的頂點(diǎn)編號(hào)不大于k的最短路徑長(zhǎng)度。A

14、ij=costijA(k+1)ij=minAkij,Aki+1k+1+Akk+1j弗洛伊德主要算法，若Akij已求出，頂點(diǎn)i到頂點(diǎn)k+1的路徑長(zhǎng)度為Akik+1，頂點(diǎn)路徑長(zhǎng)度為Akij，頂點(diǎn)k+1到頂點(diǎn)j的路徑長(zhǎng)度為Akk+1j，如果此時(shí)Akik+1+Akk+1j Akij,則將原來(lái)的頂點(diǎn)i到頂點(diǎn)j的路徑改為頂點(diǎn)，否則不需要修改頂點(diǎn)i到j(luò)的路徑。k+1ij Aki,k+1 Akk+1,j Aki,j 圖2-6若Akik+1+Akk+1 j Akij,修改路徑 過(guò)程： for(k=1;k=n;k+) for(i=1;i=n;i+)for(j=1;j=n;j+) if(Dik+Dkj1 長(zhǎng)度=0，

15、1=2 長(zhǎng)度=8，1=3 長(zhǎng)度=8+6=14，1=4 長(zhǎng)度=8+5=13；和下圖完全一致圖3-4為保證結(jié)果正確換一個(gè)頂點(diǎn)進(jìn)行：如頂點(diǎn)2到其他的距離經(jīng)過(guò)手工計(jì)算：2=1 長(zhǎng)度=6+4=10，2=2 長(zhǎng)度=0，2=3 長(zhǎng)度=6，2=4 長(zhǎng)度=5；和下圖完全一致圖3-52、求任意的兩個(gè)城市之間的最短距離例1到3之間的最短距離，經(jīng)過(guò)計(jì)算可得最短距離為1=2=3，且路徑為14，與下圖結(jié)果相同。圖3-6為保證結(jié)果正確換一個(gè)頂點(diǎn)進(jìn)行：如頂點(diǎn)2到4之間的最短路徑以及距離經(jīng)過(guò)計(jì)算可得2到4的最短路徑是2=4,且最短路徑為5圖3-73.2.3、結(jié)束程序當(dāng)用戶輸入命令0時(shí)，結(jié)束程序圖3-8 4.總結(jié)通過(guò)這次數(shù)據(jù)結(jié)構(gòu)

16、課程設(shè)計(jì)，我對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程有了更深一步的了解，使我對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程掌握以及運(yùn)用更加靈活。同時(shí)也讓我發(fā)現(xiàn)了自己在這門課上的不足與缺陷，同時(shí)也明確了自己在以后的類似課程中的具體學(xué)習(xí)方法。這次在應(yīng)用中，我發(fā)現(xiàn)了自己的很多不足，在編寫(xiě)城市交通咨詢系統(tǒng)的過(guò)程中，自己C語(yǔ)言方面的只是掌握太少，很多功能需求只能退而求其次，一次又一次的更改，一次又一次的失敗，也終于是在最后也完成了自己的要求，同時(shí)我也知道了平時(shí)用功學(xué)習(xí)的重要性。尤其是在日常學(xué)習(xí)之中，對(duì)于單一的只是點(diǎn)也許掌握的還不錯(cuò)，但是自己動(dòng)手太少，實(shí)踐經(jīng)驗(yàn)嚴(yán)重不足，且面臨課程設(shè)計(jì)之時(shí)，要求多方面的只是結(jié)和編碼，對(duì)于我而言還是有很大的難度的。如此次對(duì)于

17、鄰接矩陣的存儲(chǔ)于讀取，以及最短路徑算法的實(shí)現(xiàn)，兩個(gè)及其重要的算法，狄克斯特拉算法和佛洛依德算法，在具體的應(yīng)用上還是有很多不足。通過(guò)此次課程設(shè)計(jì)，我也明白了對(duì)于一個(gè)完成的程序而言，想要完成它最重要的代碼，最初，也是最為重要的一個(gè)部分就是算法思想，以及具體程序功能規(guī)劃，只有最重要的地基部分完美實(shí)現(xiàn)，才可以進(jìn)行接下來(lái)的具體代碼編程，以及更多細(xì)節(jié)上的完美。通過(guò)這次的課程設(shè)計(jì)我有懂得了好多數(shù)據(jù)結(jié)構(gòu)的知識(shí)，以前上課沒(méi)有聽(tīng)的，不知道的，這次都有所了解了，像有向圖的構(gòu)建，弗洛伊德算法，迪克斯特拉算法。這些知識(shí)從曾經(jīng)的聽(tīng)說(shuō)到現(xiàn)在的了解，進(jìn)了一大步。不但如此，這次的課設(shè)也是我感覺(jué)到了數(shù)據(jù)結(jié)構(gòu)的強(qiáng)大與神奇。漸漸的愛(ài)

18、上他了。不僅讓我了解了數(shù)據(jù)結(jié)構(gòu)更加深了對(duì)它與C語(yǔ)言的聯(lián)系的理解。因?yàn)樽约旱牟粚W(xué)習(xí)，導(dǎo)致這次的課設(shè)變得如此的艱難。且因?yàn)樽约荷∽≡阂哺抢速M(fèi)了很大的時(shí)間，對(duì)于我自己做課程設(shè)計(jì)的時(shí)間就少的可憐，這也無(wú)疑是對(duì)我更大的挑戰(zhàn)。在臨近答辯，我的代碼才基本完成，夜以繼日的努力也終于是讓我完成5.致謝本次課程設(shè)計(jì)我遇到了極大的問(wèn)題，不管是時(shí)間方面還是內(nèi)容方面，自己都顯得慌亂過(guò)，我能夠完成本次課程設(shè)計(jì)也完全感謝舍友的支持與幫助，在難點(diǎn)上能夠?qū)ξ疫M(jìn)行幫助。尤其感謝我的知道老師張老師。感謝她在百忙之中抽出時(shí)間來(lái)為我解答疑惑，解決問(wèn)題，她對(duì)我此次的課程設(shè)計(jì)有極大的幫助。再次感謝張老師。課程設(shè)計(jì)馬上結(jié)束，同時(shí)也謝謝所

19、有的負(fù)責(zé)老師，謝謝她們這幾天對(duì)我們的付出，老師辛苦了。6.附錄#include #include #define MVNum 100/最大頂點(diǎn)數(shù) #define Maxint 32767 enum booleanFALSE,TRUE; typedef char VertexType; typedef int Adjmatrix; typedef struct VertexType vexsMVNum;/頂點(diǎn)數(shù)組，類型假定為char Adjmatrix arcsMVNumMVNum;/鄰接矩陣，類型假定為int型 MGraph; int D1MVNum,P1MVNum; int DMVNumMV

20、Num,PMVNumMVNum; /*建立有向圖的儲(chǔ)存結(jié)構(gòu)*/ void CreateMGraph(MGraph * G,int n,int e) /采用鄰接矩陣表示法構(gòu)造有向圖G，n、e表示圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù) int i,j,k,w; for(i=1;ivexsi=(char)i; for(i=1;i=n;i+) for(j=1;jarcsij=Maxint;/初始化鄰接矩陣 printf( = 輸入%d條邊人i（起點(diǎn)）、j（終點(diǎn)）及w（路徑長(zhǎng)度）：n,e); for(k=1;karcsij=w; printf( = 有向圖人存儲(chǔ)結(jié)構(gòu)建立完畢！ =n); /*迪杰斯特拉算法*/ void Dijkstra(MGraph *G,int v1,int n) /利用迪杰斯特拉算法，求出有向圖G的v1頂點(diǎn)到其他頂點(diǎn)v 的最短路徑Pv及權(quán)Dv int D2MVNum,P2MVNum; int v,i,w,min; enum boolean SMVNum; for(v=1;varcsv1v;/置初始的最短路徑值 if(D2vMaxint) P2v=v1;/v1是v的前趨（雙親） e