數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---交通旅游圖的最短路徑問題

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告</p><p>　題 目交通旅游圖的最短路徑問題</p><p>　學(xué)生姓名*****</p><p>　指導(dǎo)教師*****</p><p>　學(xué) 院******</p><p>　專業(yè)班級******</p><p>　完成時(shí)間*****

2、***</p><p><b>　　摘 要</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)主要是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中的計(jì)算機(jī)操作對象以及它們之間的關(guān)系和操作等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)與技術(shù)中是一門綜合性的專業(yè)基礎(chǔ)課，其研究不僅涉及到計(jì)算機(jī)硬件的研究范圍，而且和計(jì)算機(jī)軟件的研究有著更密切的關(guān)系。不論是編譯程序過程還是操作系統(tǒng)都涉及到數(shù)據(jù)元素在存儲器中的分配

3、問題。在計(jì)算機(jī)科學(xué)與技術(shù)中，數(shù)據(jù)結(jié)構(gòu)不僅是一般程序性的基礎(chǔ)，而且也是其他系統(tǒng)程序和大型程序的重要基礎(chǔ)。</p><p>　　在交通網(wǎng)絡(luò)非常發(fā)達(dá)，交通工具和交通方式不斷更新的今天，人們在出差、旅游或做其它出行時(shí)，不僅關(guān)心節(jié)省費(fèi)用，而且對里程和所需時(shí)間等問題也感興趣。對于這樣一個(gè)人們關(guān)心的問題，可用一個(gè)圖結(jié)構(gòu)來表示交通網(wǎng)絡(luò)系統(tǒng)，利用計(jì)算機(jī)建立一個(gè)交通咨詢系統(tǒng)。圖中頂點(diǎn)表示站點(diǎn)之間的交通關(guān)系。這個(gè)交通系統(tǒng)可以回答旅客提

4、出的各種問題。比如任意一個(gè)站點(diǎn)到其他站點(diǎn)的最短路徑，任意兩個(gè)站點(diǎn)之間的最短路徑問題。</p><p>　　本次設(shè)計(jì)的交通咨詢系統(tǒng)主要是運(yùn)用C語言來完成交通圖的存儲、圖中頂點(diǎn)的最短路徑和任意一對頂點(diǎn)間的最短路徑問題。</p><p>　　關(guān)鍵字：數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì) 交通咨詢系統(tǒng)</p><p><b>　　目 錄</b></p>

5、<p><b>　　前言1</b></p><p>　　第一章 設(shè)計(jì)要求2</p><p><b>　　1.1設(shè)計(jì)內(nèi)容2</b></p><p><b>　　1.2設(shè)計(jì)目的3</b></p><p><b>　　1.3設(shè)計(jì)分析4</b&g

6、t;</p><p>　　第二章系統(tǒng)功能模塊的設(shè)計(jì)5</p><p>　　2.1 系統(tǒng)功能分析與設(shè)計(jì)5</p><p>　　2.1.1系統(tǒng)簡介...............................................................................................................

7、...5</p><p>　　2.1.2 系統(tǒng)流程圖.............................................................................................................5</p><p>　　2.2 各功能模塊簡介6</p><p>　　2.2.1結(jié)構(gòu)體的建立6

8、</p><p>　　2.2.2 圖的建立與初始化6</p><p>　　2.2.3 鄰接矩陣的輸出8</p><p>　　2.2.4 顯示函數(shù)..............................................................................................................

9、...8</p><p>　　2.2.5 最短路徑算法.........................................................................................................9</p><p>　　2.2.6主函數(shù)............................................

10、.........................................................................10</p><p>　　第三章 實(shí)踐結(jié)果與調(diào)試..........................................................................................................12<

11、;/p><p>　　3.1運(yùn)行結(jié)果.........................................................................................................................12</p><p>　　3.1.1主界面.......................................

12、............................................................................12</p><p>　　3.1.2查詢站點(diǎn)編號模塊...............................................................................................12</p>

13、;<p>　　3.1.3鄰接矩陣查詢模塊...............................................................................................12</p><p>　　3.1.4最短路徑查詢模塊............................................................

14、...................................13</p><p>　　3.2運(yùn)行調(diào)試及發(fā)現(xiàn)問題.................................................................................................15</p><p>　　3.2.1調(diào)試過程.................

15、..............................................................................................15</p><p>　　3.2.2發(fā)現(xiàn)問題............................................................................................

16、...................15</p><p>　　第四章設(shè)計(jì)總結(jié)與心得............................................................................................................16</p><p>　　附錄：程序源代碼........................

17、...............................................................................18</p><p><b>　　前 言</b></p><p>　　乘汽車旅行的人總希望找出到目的地的盡可能短的行程。如果有一張地圖并在圖上標(biāo)出每對十字路口之間的距離，如何找出這一最短行程？</p>

18、;<p>　　計(jì)算機(jī)網(wǎng)絡(luò)中的路由就是通過互聯(lián)的網(wǎng)絡(luò)把信息從源地址傳輸?shù)侥康牡刂返幕顒?dòng)。為了高效引導(dǎo)數(shù)據(jù)的傳輸，如何找出源和目的地址之間的最優(yōu)路徑？</p><p>　　這些問題中的網(wǎng)絡(luò)（交通網(wǎng)，計(jì)算機(jī)通信網(wǎng)）可以使用一個(gè)帶權(quán)圖來建模，尋找最優(yōu)路的需求可轉(zhuǎn)換為帶權(quán)圖的最短路徑問題。最短路徑問題是圖論研究中的一個(gè)經(jīng)典算法問題， 旨在尋找圖（由結(jié)點(diǎn)和邊組成的）中兩結(jié)點(diǎn)之間的最短路徑。</p>

19、<p>　　問題具體的形式包括：</p><p>　　確定起點(diǎn)的最短路徑問題，即已知起始結(jié)點(diǎn)，求最短路徑的問題。適合使用Dijkstra算法。</p><p>　　確定終點(diǎn)的最短路徑問題，與確定起點(diǎn)的問題相反，該問題是已知終結(jié)結(jié)點(diǎn)，求最短路徑的問題。在無向圖中該問題與確定起點(diǎn)的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問題。</p><

20、;p>　　確定起點(diǎn)終點(diǎn)的最短路徑問題，即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。</p><p>　　全局最短路徑問題，求圖中所有的最短路徑。適合使用Floyd-Warshall算法。</p><p><b>　　第一章 設(shè)計(jì)要求</b></p><p><b>　　1.1 設(shè)計(jì)內(nèi)容</b></p>&

21、lt;p><b>　　一．問題描述：</b></p><p>　　已知某市每條公共路線及沿途所經(jīng)站名，試設(shè)計(jì)一個(gè)問路程序，用戶可以在任一車站通過終端詢問知道：</p><p>　　是否有公共汽車到達(dá)指定的目的地? </p><p>　　若有，告訴乘車路線。如需中途換車，應(yīng)指示再那里換車 </p><p><b

22、>　　二．基本要求：</b></p><p>　　（1）自己提出一個(gè)公共汽車路線圖，可以在網(wǎng)上搜索現(xiàn)實(shí)城市公交路線圖（如長沙市的），至少要有7條公交線路，每條線路至少要有7個(gè)公共汽車站。</p><p>　　（2）數(shù)據(jù)結(jié)構(gòu)：將公共汽車路線圖看成是一個(gè)有向圖，選擇合適的數(shù)據(jù)結(jié)構(gòu)，除了反映頂點(diǎn)(站)之間的鄰接關(guān)系外，還應(yīng)反映途經(jīng)的路線號。注意，兩站之間可能存在往返兩個(gè)方向，每

23、個(gè)方向又可能對應(yīng)多個(gè)路線號。 </p><p>　?。?）算法：按選定的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)相應(yīng)的算法。注意，當(dāng)從乘車站到目的站存在多種乘車路線時(shí)，必須確定路線選取標(biāo)準(zhǔn)。例如，要求換車次數(shù)最少等。 </p><p>　　數(shù)據(jù)結(jié)構(gòu)可以采用鏈接結(jié)構(gòu)：</p><p>　　structNODE</p><p><b>　　{</b>&

24、lt;/p><p>　　char* stname;</p><p>　　struct NODE* link;</p><p><b>　　};</b></p><p>　　struct NODE hdtp[MAX+1]；</p><p>　　數(shù)據(jù)結(jié)構(gòu)也可以采用順序結(jié)構(gòu)：</p><

25、p>　　struct NODE{</p><p>　　int go,back;</p><p><b>　　};</b></p><p>　　struct NODE a[max+1,max+1];</p><p>　　其中，a[I，j].go>0 表示第i條線路上，向站j 去方向的下一站號；a[i，j].ba

26、ck>0表示第i條線路上，站j回來的下一站號。若站j不在第i條線路上，a[i，j].go 和a[i，j].back 均為0。</p><p>　?。?）另外，還需建立兩個(gè)數(shù)組；一個(gè)是線路序號和線路號“值”的對照表；另一個(gè)是站號和站名對照表。</p><p>　?。?）對所采用的算法進(jìn)行算法分析 </p><p><b>　　三. 實(shí)現(xiàn)提示</b

27、></p><p>　　假定頂點(diǎn)編號為1..n，數(shù)據(jù)結(jié)構(gòu)采用連接結(jié)構(gòu)。設(shè)置表頭數(shù)組為head[1..n]，head[i]包含站i的名字和一指針，該指針指向i的所有鄰接頂點(diǎn)組成的單鏈表。單鏈表中的每個(gè)結(jié)點(diǎn)包含3個(gè)域：一個(gè)站號域，兩個(gè)指針域。一個(gè)指針指向i的下一個(gè)鄰接頂點(diǎn)，另一個(gè)指針指向從i到該結(jié)點(diǎn)的所有線路號組成的鏈表。 </p><p>　　struct LINENODE</p

28、><p><b>　　{</b></p><p>　　int lineno;</p><p>　　struct LINENODE* next;</p><p><b>　　};</b></p><p>　　struct STNODE</p><p><

29、;b>　　{</b></p><p><b>　　int stno;</b></p><p>　　struct LINENODE* Link1,*Link2;</p><p><b>　　};</b></p><p>　　如果按途經(jīng)站數(shù)最少的原則來確定乘車路線，實(shí)際上是最短路徑問題

30、，則可以采用Djkstra算法或圖的寬度優(yōu)先搜索算法。在保證站數(shù)最少的前提下，如果存在多種乘車路線，則可以進(jìn)一步挑選換車次數(shù)最少的路線。</p><p><b>　　1.2 設(shè)計(jì)目的</b></p><p>　　一.設(shè)計(jì)思想：用鄰接矩陣來存儲交通網(wǎng)絡(luò)圖的信息，運(yùn)用迪杰斯特拉算法實(shí)現(xiàn)圖上單源最短路徑問題，然后運(yùn)用費(fèi)洛伊德算法實(shí)現(xiàn)圖中任意一對頂點(diǎn)間最短路徑問題，這樣就會(huì)實(shí)

31、現(xiàn)旅客所要咨詢的問題。 </p><p>　　二.設(shè)計(jì)要求：該交通咨詢系統(tǒng)要完成城市網(wǎng)絡(luò)圖的存儲，并要實(shí)現(xiàn)求任意一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑問題，還要實(shí)現(xiàn)任意兩個(gè)車站頂點(diǎn)間的最短路徑問題。故設(shè)計(jì)要分成三部分，一是建立交通網(wǎng)絡(luò)圖的存儲結(jié)構(gòu)；二是解決路徑問題；最后再實(shí)現(xiàn)兩個(gè)車站之間的最短路徑問題。</p><p>　　三.設(shè)計(jì)目的：通過課程設(shè)計(jì)我們不僅可以鞏固已學(xué)到的書本知識，還

32、可以從親自動(dòng)手設(shè)計(jì)這項(xiàng)課程設(shè)計(jì)的過程中發(fā)現(xiàn)問題，并學(xué)會(huì)用自己所學(xué)的知識解決問題。這不僅使我們能學(xué)會(huì)很多書本中學(xué)不到的知識、經(jīng)驗(yàn)，還能提高我們自己的動(dòng)手能力，同時(shí)開發(fā)自身的創(chuàng)新思想，拓展思維。</p><p><b>　　1.3 設(shè)計(jì)分析</b></p><p>　　一．通過對題目的分析知，是要讓我們能夠通過利用所學(xué)的數(shù)據(jù)結(jié)構(gòu)的基本知識和技能來解決程序設(shè)計(jì)問，因此在搞程

33、序設(shè)計(jì)之前先好好的把書復(fù)習(xí)一遍，弄清楚各個(gè)知識之間的聯(lián)系。</p><p>　　二．根據(jù)這些功能和基本要求，可充分運(yùn)用我們所學(xué)的數(shù)據(jù)結(jié)構(gòu)的基本知識和技能去逐步的解決。其中將函數(shù)進(jìn)行模塊化。在數(shù)據(jù)結(jié)構(gòu)中，通過隊(duì)列，棧，圖的聲明來實(shí)現(xiàn)系統(tǒng)的各種功能的存儲各站點(diǎn)之間乘車的時(shí)間，距離，以及最少的中轉(zhuǎn)站。利用結(jié)點(diǎn)來實(shí)現(xiàn)站點(diǎn)之間各種操作，而這些知識點(diǎn)都是我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)必須掌握和學(xué)會(huì)運(yùn)用的。</p><p

34、>　　三．完成程序功能的設(shè)置后，應(yīng)對程序進(jìn)行調(diào)試，以便在調(diào)試中能及時(shí)地找出錯(cuò)誤并加以更正，這樣能使程序功能進(jìn)一步的完善和正確。這就要求我們在編程和調(diào)試過程中養(yǎng)成認(rèn)真分析和善于發(fā)現(xiàn)問題并及時(shí)解決的習(xí)慣，不懂的及時(shí)問老師或者其他同學(xué)。</p><p>　　第二章 系統(tǒng)功能模塊的設(shè)計(jì)</p><p>　　2.1 系統(tǒng)功能分析及設(shè)計(jì)</p><p><b>

35、　　2.1.1系統(tǒng)簡介</b></p><p>　　該課題可以分為如下幾個(gè)模塊：控制選擇功能項(xiàng)的main函數(shù)、定義各類抽象結(jié)構(gòu)體的模塊typedef struct{}、有向圖的建立與初始化函數(shù)MGraph InitGraph(void)、鄰接矩陣的輸出函數(shù)void DispMat(MGraph g)、顯示輸出函數(shù)void out()、求最小路徑的函數(shù)void Floyd(MGraph g)、以及中轉(zhuǎn)站

36、的輸出函數(shù)void ppath(int path[][MAXV],int i,int j)。</p><p>　　2.1.2 系統(tǒng)流程圖</p><p>　　2.2各功能模塊簡介</p><p>　　2.2.1結(jié)構(gòu)體的建立</p><p>　　本次設(shè)計(jì)中需要運(yùn)用有向圖來顯示交通網(wǎng)絡(luò)圖，顧建立抽象數(shù)據(jù)結(jié)構(gòu)體便是很重要的一項(xiàng)工序。首先要先建立頂

37、點(diǎn)的結(jié)構(gòu)體，邊的結(jié)構(gòu)體以及圖的結(jié)構(gòu)體。這些均是為了以后的數(shù)據(jù)存儲和算法的實(shí)現(xiàn)做的基本定義。此模塊如下：</p><p>　　typedef int InfoType; //假設(shè)InfoType為int類型</p><p>　　typedef struct</p><p>　　{ int no;//頂點(diǎn)編號</p>&

38、lt;p>　　InfoType info;//頂點(diǎn)其他信息，這里用于存放邊的權(quán)值</p><p>　　char name[30]; //頂點(diǎn)名稱</p><p>　　} VertexType;//頂點(diǎn)類型</p><p>　　typedef struct</p><p><b&g

39、t;　　{</b></p><p>　　int lengh; //邊的權(quán)值，表示路徑長度</p><p>　　int ivex,jvex; //邊得兩端頂點(diǎn)號</p><p>　　}EdgeType; //邊的類型</p><p

40、>　　typedef struct //圖的定義</p><p>　　{ int edges[MAXV][MAXV]; //鄰接矩陣</p><p>　　int n,e; //頂點(diǎn)數(shù)，弧數(shù)</p><p>　　VertexType vexs[MAXV];//存放頂點(diǎn)信息</p>&

41、lt;p>　　} MGraph;//圖的鄰接矩陣類型</p><p>　　2.2.2圖的建立與初始化</p><p>　　圖是這個(gè)題目課程設(shè)計(jì)的核心。所以對圖的建立是必要的，并且對圖的初始化賦值也同樣重要。在創(chuàng)建圖是，同時(shí)進(jìn)行對頂點(diǎn)的編號，名稱的填寫以及鄰接矩陣的輸入。這樣才能構(gòu)成完整的有向圖，才能建立確切的交通網(wǎng)絡(luò)圖，以便實(shí)現(xiàn)交通的查詢。此函數(shù)為：</p>

42、<p><b>　　MGraph G;</b></p><p>　　MGraph InitGraph(void)</p><p><b>　　{</b></p><p><b>　　MGraph G;</b></p><p><b>　　int i,j;&

43、lt;/b></p><p><b>　　G.n=14;</b></p><p><b>　　G.e=24;</b></p><p>　　Int A[14][14]={{32767,32767,32767,32767,32767,32767,32767,8,32767,32767,32767,32767,32767,

44、32767},{32767,32767,32767,32767,32767,32767,32767,6,32767,8,32767,32767,32767,32767},{32767,32767,32767,32767,32767,32767,32767,32767,32767,7,32767,32767,32767,32767},{32767,32767,32767,32767,32767,32767,32767,32767,5,32

45、767,7,32767,32767,32767},{32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,32767,9},{32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,8},{32767,32</p><p>　　for (i=

46、0;i<14;i++)</p><p>　　for (j=0;j<14;j++)</p><p>　　G.edges[i][j]=A[i][j];</p><p>　　for(i=0;i<G.n;i++)</p><p>　　G.vexs[i].no=i;</p><p>　　strcpy(G.vex

47、s[0].name,"湖南林業(yè)科技大學(xué)");</p><p>　　strcpy(G.vexs[1].name,"瀟湘晨報(bào)");</p><p>　　strcpy(G.vexs[2].name,"市中心醫(yī)院");</p><p>　　strcpy(G.vexs[3].name,"鐵道學(xué)院"

48、);</p><p>　　strcpy(G.vexs[4].name,"新開鋪路口");</p><p>　　strcpy(G.vexs[5].name,"南郊公園");</p><p>　　strcpy(G.vexs[6].name,"后湖路口");</p><p>　　strcp

49、y(G.vexs[7].name,"猴子石大橋");</p><p>　　strcpy(G.vexs[8].name,"桃源村");</p><p>　　strcpy(G.vexs[9].name,"沙泥塘");</p><p>　　strcpy(G.vexs[10].name,"王家灣"

50、;);</p><p>　　strcpy(G.vexs[11].name,"中南大學(xué)校本部");</p><p>　　strcpy(G.vexs[12].name,"八字墻");</p><p>　　strcpy(G.vexs[13].name,"左家垅");</p><p>　　}

51、//站點(diǎn)和路徑數(shù)據(jù)源初始化</p><p>　　2.2.3鄰接矩陣的輸出</p><p>　　鄰接矩陣是用來存儲邊權(quán)信息的。通過鄰接矩陣可直接讀出兩頂點(diǎn)間是否有直通路線，同時(shí)還可以找到是否轉(zhuǎn)戰(zhàn)，但不如圖形直觀。但鄰接矩陣是用來存儲有向圖通路信息的最普遍方法之一，顧我們這次同樣選擇用鄰接矩陣來儲存。</p><p>　　在我們的系統(tǒng)中設(shè)置了專門顯示鄰接矩陣情況的函數(shù)模

52、塊，一邊直觀的觀察到鄰接矩陣輸入狀況以及通路狀況。所以函數(shù)為：</p><p>　　void DispMat(MGraph g) //輸出鄰接矩陣g</p><p><b>　　{int i,j;</b></p><p>　　for (i=0;i<14;i++)</p><p><b>

53、　　{</b></p><p>　　for (j=0;j<14;j++)</p><p>　　if (g.edges[i][j]==INF)</p><p>　　printf("%3s","∞");</p><p><b>　　else</b></p>

54、<p>　　printf("%3d",g.edges[i][j]);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("\n\n");</p><p><b>　

55、　}</b></p><p>　　2.2.4 顯示函數(shù)</p><p>　　顯示函數(shù)是本系統(tǒng)中的第二項(xiàng)重要功能?？梢燥@示出站點(diǎn)名及編號，以便用戶查詢方便。此功能函數(shù)為：</p><p>　　void out()</p><p>　　{ printf("\n站名編號為：\n 0.湖南林業(yè)科技大學(xué)

56、1.瀟湘晨報(bào)\n 2.市中心醫(yī)院 3.鐵道學(xué)院\n 4.新開鋪路口 5.南郊公園\n 6.后湖路口 7.猴子石大橋\n 8.桃源村 9.沙泥塘\n 10.王家灣 11.中南大學(xué)校本部\n 12.八字墻 13.左家垅\

57、n\n\n");</p><p><b>　　}</b></p><p>　　另外，我們?yōu)閷?shí)現(xiàn)可以顯示中轉(zhuǎn)站的功能，又另設(shè)立一函數(shù)為求出起點(diǎn)與終點(diǎn)的路徑中所經(jīng)的站點(diǎn)編號，這樣方便旅者轉(zhuǎn)車。此部分函數(shù)為：</p><p>　　void ppath(int path[][MAXV],int i,int j) //輸出各條最短路經(jīng)<

58、/p><p><b>　　{ int k;</b></p><p>　　k=path[i][j];</p><p>　　if (k==-1) return;</p><p>　　ppath(path,i,k);</p><p>　　printf("%3d,",k);</p

59、><p>　　ppath(path,k,j);</p><p><b>　　}</b></p><p>　　2.2.5 最短路徑算法</p><p>　　本設(shè)計(jì)中用多源有向圖來顯示交通網(wǎng)絡(luò)的交通圖，顧采用弗洛里德算法來求兩頂點(diǎn)之間的最短路徑問題。此功能為人工輸入要查詢的起點(diǎn)及終點(diǎn)，系統(tǒng)將自動(dòng)輸出兩點(diǎn)之間的最短路徑，以及期間所

60、經(jīng)過的站點(diǎn)編號。此功能為交通咨詢系統(tǒng)的最核心函數(shù)。其代碼如下：</p><p>　　void Floyd(MGraph g)//弗洛伊德算法從每對頂點(diǎn)之間的最短路徑</p><p>　　{int A[MAXV][MAXV],path[MAXV][MAXV];</p><p>　　int i,j,k,r,f,n=14;</p><p>　　f

61、or (i=0;i<n;i++)//給A數(shù)組置初值</p><p>　　for (j=0;j<n;j++)</p><p>　　{A[i][j]=g.edges[i][j];</p><p>　　path[i][j]=-1;}</p><p>　　for (k=0;k<n;k++)//計(jì)算Ak<

62、;/p><p>　　{for (i=0;i<n;i++)</p><p>　　for (j=0;j<n;j++)</p><p>　　if (A[i][j]>(A[i][k]+A[k][j]))</p><p>　　{A[i][j]=A[i][k]+A[k][j];</p><p>　　path[i][

63、j]=k;}}</p><p>　　printf("請輸入需要查找的兩個(gè)站點(diǎn)(站點(diǎn)編號為0-13):\n");</p><p><b>　　out();</b></p><p>　　printf("起點(diǎn):");scanf("%3d",&f);</p><

64、p>　　while(f>=n)</p><p>　　{ printf("該站不存在，請重新輸入！\n");</p><p>　　printf("起點(diǎn):");scanf("%3d",&f); };</p><p>　　printf("終點(diǎn):");scanf("

65、%3d",&r);</p><p>　　while(r>=n){</p><p>　　printf("該站不存在，請重新輸入！\n");</p><p>　　printf("終點(diǎn):");scanf("%3d",&r); };</p><p>　　whi

66、le(r==f){</p><p>　　printf("不能等于起點(diǎn)，請重新輸入！\n");</p><p>　　printf("終點(diǎn):");scanf("%3d",&r);};</p><p>　　printf("\n輸出最短路徑:\n");</p><p&

67、gt;　　if (A[f][r]==INF){ if(f!=r)printf("從%3d到%3d沒有路徑\n\n\n",f,r);}</p><p><b>　　else</b></p><p>　　{ printf("從%3d到%3d路徑為:",f,r);</p><p>　　printf("

68、;%3d,",f);</p><p>　　ppath(path,f,r);</p><p>　　printf("%3d",r);</p><p>　　printf("\n路徑長度為:%3d km \n\n\n",A[f][r]);</p><p><b>　　}</b>&

69、lt;/p><p><b>　　}</b></p><p><b>　　2.2.6主函數(shù)</b></p><p>　　主函數(shù)在此系統(tǒng)中主要實(shí)現(xiàn)主界面的設(shè)置，菜單功能的實(shí)現(xiàn)。同時(shí)使其他模塊函數(shù)的功能連接起來，共同組成一個(gè)完整的咨詢系統(tǒng)。顧主函數(shù)如下：</p><p>　　void main()</p

70、><p>　　{ int i,j,n,k=1;</p><p>　　MGraph InitGraph(void);</p><p>　　while(k==1)</p><p><b>　　{</b></p><p>　　printf(" **********

71、***歡迎進(jìn)入公交查詢系統(tǒng)************* \n");</p><p>　　printf(" 制作人：韋千慧 周韻\n");</p><p>　　printf(" 請輸入選擇：\n");</p>

72、;<p>　　printf(" 1.查詢站點(diǎn)\n");</p><p>　　printf(" 2.查看鄰接矩陣\n");</p><p>　　printf("

73、3.查找路徑\n");</p><p>　　printf(" 4.退出\n");</p><p>　　printf(" ********************************************** \n");</

74、p><p>　　scanf("%d",&n);</p><p><b>　　switch(n)</b></p><p>　　{case 1:system("cls");out();break;</p><p>　　case 2: system("cls");

75、</p><p>　　printf("交通網(wǎng)路的鄰接矩陣為\n");</p><p>　　DispMat(G);</p><p><b>　　break;</b></p><p>　　case 3: system("cls");</p><p>　　Floy

76、d(G);break;</p><p>　　case 4:k=2;break;</p><p>　　default:printf("輸入錯(cuò)誤！請重新輸入！");</p><p><b>　　}</b></p><p><b>　　}</b></p><p>

77、;<b>　　}</b></p><p>　　第三章 實(shí)踐結(jié)果與調(diào)試</p><p>　　3.1運(yùn)行結(jié)果 </p><p><b>　　3.1.1主界面</b></p><p>　　主界面運(yùn)行結(jié)果如下圖：</p><p>　　輸入選項(xiàng)編號后即可進(jìn)入功能輸出！&l

78、t;/p><p>　　3.1.2查詢站點(diǎn)編號模塊</p><p>　　查詢站點(diǎn)編號模塊運(yùn)行如下圖：</p><p>　　此模塊為輸出頂點(diǎn)即站點(diǎn)的編號與名稱所對應(yīng)的列表。</p><p>　　3.1.3鄰接矩陣查詢模塊</p><p>　　鄰接矩陣查詢模塊運(yùn)行如下圖：</p><p>　　此為鄰接矩陣

79、的數(shù)值輸入狀況。</p><p>　　3.1.4最短路徑查詢模塊</p><p>　　最短路徑查詢模塊運(yùn)行如下圖：</p><p>　　（1）兩點(diǎn)之間沒有路徑：</p><p>　　此圖為輸入的起點(diǎn)與終點(diǎn)之間沒有路徑可以到達(dá)。</p><p>　?。?）兩點(diǎn)之間有直接通路：</p><p>　　

80、此圖為兩點(diǎn)之間的通路是直接通路，并輸出了路徑長度。</p><p>　?。?）兩點(diǎn)之間間接通路：</p><p>　　此圖為兩點(diǎn)之間的通路是間接的，不僅輸出了路徑長度，并且將中轉(zhuǎn)站點(diǎn)的編號也一同輸出，方便旅客轉(zhuǎn)車。</p><p>　　3.2運(yùn)行調(diào)試及發(fā)現(xiàn)問題</p><p><b>　　3.2.1調(diào)試過程</b><

81、;/p><p>　　一開始運(yùn)行此系統(tǒng)，會(huì)發(fā)現(xiàn)很多錯(cuò)誤而無法運(yùn)行。在不斷的查找資料與復(fù)習(xí)書本上所學(xué)習(xí)過的內(nèi)容不斷改正后正式運(yùn)行成功。然而，每個(gè)模塊都有小小的不足之處，運(yùn)行出的結(jié)果也并不與我們所想象的一樣。</p><p>　　首先，主界面的運(yùn)行就需要許多的調(diào)試，比如并未對齊，或詞語串行等等，都需要我們不斷調(diào)整空格格數(shù)以及語句的篩選才能實(shí)現(xiàn)理想的結(jié)果。</p><p>　　

82、其次，對于顯示的函數(shù)同樣存在著與主界面同樣的問題，我們需要一點(diǎn)一點(diǎn)的調(diào)整才可以完全輸出想要的結(jié)果。</p><p>　　另外，最短路徑的輸出函數(shù)，一開始并未正確的輸出，這需要我們不斷的查找問題并解決，最后再進(jìn)行一步步的調(diào)整，才可以正確的輸出。并且在沒有直通路徑的時(shí)候還需要輸出所經(jīng)站點(diǎn)的編號，這也需要我們調(diào)整。一切完成后才可正常工作。</p><p>　　最后，退出系統(tǒng)的功能也需要自己編譯以

83、及調(diào)試。有時(shí)候無法跳出主函數(shù)的循環(huán)，或者無法跳出系統(tǒng)的循環(huán)，這都是編譯出了問題，均需要一點(diǎn)點(diǎn)調(diào)試才可。</p><p><b>　　3.2.2發(fā)現(xiàn)問題</b></p><p>　　這次課程設(shè)計(jì)的系統(tǒng)并不完善，只實(shí)現(xiàn)了最基本的功能。其實(shí)還可以更加完善，多添加幾個(gè)模塊功能，使其更加完整，比如：管理員身份登錄后可以修改線路的權(quán)值，站點(diǎn)的名稱，可以添加、刪除、修改這些信息。這

84、樣就使得這個(gè)系統(tǒng)更加的人性化，并且更加先進(jìn)，可以及時(shí)更新最新信息。另外在用戶查詢中，也可多添加幾項(xiàng)為旅游服務(wù)的項(xiàng)目，比如：為站點(diǎn)做簡介，介紹當(dāng)?shù)氐奶厣约熬包c(diǎn)，還可以提供查詢路徑時(shí)不僅可查出距離的長短，還有時(shí)間花費(fèi)等均可以查詢。</p><p>　　以上僅僅只是發(fā)現(xiàn)這次所做系統(tǒng)的不足，功能的缺少，但并未能真正的實(shí)現(xiàn)。然而在已有的功能中，查詢最短路徑函數(shù)中，也有小小的不足：在查詢后顯示出的并非站點(diǎn)名稱而是編號，這還

85、需用戶自己對照列表進(jìn)行查找，這便不是很直觀方便了。我們想了很多種方法想要更正這一點(diǎn)，但怎么都無法實(shí)現(xiàn)。我想我們學(xué)習(xí)的還是不夠，動(dòng)手能力還是沒有真正的達(dá)到隨心所欲的境界，這還需要我們不斷的積累經(jīng)驗(yàn)，不斷的動(dòng)手實(shí)踐才能完成心中所想得效果吧。</p><p>　　第四章 設(shè)計(jì)總結(jié)與心得</p><p>　　做了一個(gè)星期的程序設(shè)計(jì)終于做完了，在這次程序設(shè)計(jì)課中，真是讓我獲益匪淺，我突然發(fā)現(xiàn)寫程序還

86、挺有意思的。</p><p>　　由于上學(xué)期的C語言跟數(shù)據(jù)結(jié)構(gòu)都算不上真正的懂，對于書上的稍微難點(diǎn)的知識就是是而非的，所以我只是對老師的程序理解，我也試著去改變了一些變量，自己也盡量多的去理解老師做程序的思路。當(dāng)我第一天坐在那里的時(shí)候，我就不知道該做些什么，后來我只有下來自己看了一遍書來熟悉下以前學(xué)過的知識。</p><p>　　通過這次的程序設(shè)計(jì)，發(fā)現(xiàn)一個(gè)程序設(shè)計(jì)就是算法與數(shù)據(jù)結(jié)構(gòu)的結(jié)合

87、體，自己也開始對程序產(chǎn)生了前所未有的興趣，以前偷工減料的學(xué)習(xí)也不可能一下子寫出一個(gè)程序出來，于是我就認(rèn)真看老師寫的程序，發(fā)現(xiàn)我們看懂了一個(gè)程序其實(shí)不難，難的是對于一個(gè)程序的思想的理解，我們要掌握一個(gè)算法，不僅僅限于讀懂，主要的是要理解老師的思路，學(xué)習(xí)老師的解決問題的方法。</p><p>　　這次試驗(yàn)中，我發(fā)現(xiàn)書本上的知識是一個(gè)基礎(chǔ)，但是我基礎(chǔ)都沒掌握，更別說寫出一個(gè)整整的程序了。自己在寫程序的時(shí)候，也發(fā)現(xiàn)自己的

88、知識太少了，特別是基礎(chǔ)知識很多都是模模糊糊的一個(gè)概念，沒有落實(shí)到真正的程序，所以自己寫的時(shí)候也感到萬分痛苦，基本上涉及一個(gè)知識我就會(huì)去看看書，對于書本上的知識沒掌握好。在飯后閑暇時(shí)間我也總結(jié)了一下，自己以前上課也認(rèn)真的聽了，但是還是寫不出來，這主要?dú)w結(jié)于自己的練習(xí)太少了，而且也總是半懂就不管了。在改寫老師的程序中也出現(xiàn)了很多的問題，不斷的修改就是不斷的學(xué)習(xí)過程，當(dāng)我們?nèi)硇牡耐度肫渲袝r(shí)，實(shí)際上是一件很有樂趣的事情。</p>

89、<p>　　通過此次課程設(shè)計(jì)，使我更加扎實(shí)的掌握了有關(guān)數(shù)據(jù)結(jié)構(gòu)方面的知識，在設(shè)計(jì)過程中雖然遇到了一些問題，但經(jīng)過一次又一次的思考，一遍又一遍的檢查終于找出了原因所在，也暴露出了前期我在這方面的知識欠缺和經(jīng)驗(yàn)不足。實(shí)踐出真知，通過親自動(dòng)手制作，使我們掌握的知識不再是紙上談兵。</p><p>　　過而能改，善莫大焉。在課程設(shè)計(jì)過程中，我們不斷發(fā)現(xiàn)錯(cuò)誤，不斷改正，不斷領(lǐng)悟，不斷獲取。最終的檢測調(diào)試環(huán)節(jié)，本

90、身就是在踐行“過而能改，善莫大焉”的知行觀。這次課程設(shè)計(jì)終于順利完成了，在設(shè)計(jì)中遇到了很多問題，最后在老師的指導(dǎo)下，終于游逆而解。在今后社會(huì)的發(fā)展和學(xué)習(xí)實(shí)踐過程中，一定要不懈努力，不能遇到問題就想到要退縮，一定要不厭其煩的發(fā)現(xiàn)問題所在，然后一一進(jìn)行解決，只有這樣，才能成功的做成想做的事，才能在今后的道路上劈荊斬棘，而不是知難而退，那樣永遠(yuǎn)不可能收獲成功，收獲喜悅，也永遠(yuǎn)不可能得到社會(huì)及他人對你的認(rèn)可！</p><p&

91、gt;　　課程設(shè)計(jì)誠然是一門專業(yè)課，給我很多專業(yè)知識以及專業(yè)技能上的提升，同時(shí)又是一門講道課，一門辯思課，給了我許多道，給了我很多思，給了我莫大的空間。同時(shí)，設(shè)計(jì)讓我感觸很深。使我對抽象的理論有了具體的認(rèn)識。我認(rèn)為，在這學(xué)期的實(shí)驗(yàn)中，不僅培養(yǎng)了獨(dú)立思考、動(dòng)手操作的能力，在各種其它能力上也都有了提高。更重要的是，在實(shí)驗(yàn)課上，我們學(xué)會(huì)了很多學(xué)習(xí)的方法。而這是日后最實(shí)用的，真的是受益匪淺。要面對社會(huì)的挑戰(zhàn)，只有不斷的學(xué)習(xí)、實(shí)踐，再學(xué)習(xí)、再實(shí)踐

92、。這對于我們的將來也有很大的幫助。以后，不管有多苦，我想我們都能變苦為樂，找尋有趣的事情，發(fā)現(xiàn)其中珍貴的事情。就像中國提倡的艱苦奮斗一樣，我們都可以在實(shí)驗(yàn)結(jié)束之后變的更加成熟，會(huì)面對需要面對的事情。</p><p>　　實(shí)驗(yàn)過程中，也對團(tuán)隊(duì)精神的進(jìn)行了考察，讓我們在合作起來更加默契，在成功后一起體會(huì)喜悅的心情。果然是團(tuán)結(jié)就是力量，只有互相之間默契融洽的配合才能換來最終完美的結(jié)果。</p><p

93、>　　此次設(shè)計(jì)也讓我明白了思路即出路，有什么不懂不明白的地方要及時(shí)請教或上網(wǎng)查詢，只要認(rèn)真鉆研，動(dòng)腦思考，動(dòng)手實(shí)踐，就沒有弄不懂的知識，收獲頗豐。</p><p><b>　　附錄：程序源代碼</b></p><p>　　#include <stdio.h></p><p>　　#include<stdlib.h>

94、</p><p>　　#include<conio.h></p><p>　　#include<string.h></p><p>　　#defineMAXV 20//最大頂點(diǎn)個(gè)數(shù)</p><p>　　#define INF 32767 //用32767表示∞</p>

95、<p>　　typedef int InfoType; //假設(shè)InfoType為int類型</p><p>　　//以下定義鄰接矩陣類型</p><p>　　typedef struct</p><p>　　{ int no;//頂點(diǎn)編號</p><p>　　InfoType info;

96、//頂點(diǎn)其他信息，這里用于存放邊的權(quán)值</p><p>　　char name[30]; //頂點(diǎn)名稱</p><p>　　} VertexType;//頂點(diǎn)類型</p><p>　　typedef struct</p><p><b>　　{</b></p>

97、<p>　　int lengh; //邊的權(quán)值，表示路徑長度</p><p>　　int ivex,jvex; //邊得兩端頂點(diǎn)號</p><p>　　}EdgeType; //邊的類型</p><p>　　typedef struct

98、 //圖的定義</p><p>　　{ int edges[MAXV][MAXV]; //鄰接矩陣</p><p>　　int n,e; //頂點(diǎn)數(shù)，弧數(shù)</p><p>　　VertexType vexs[MAXV];//存放頂點(diǎn)信息</p><p>　　} MGraph;/

99、/圖的鄰接矩陣類型</p><p><b>　　MGraph G;</b></p><p>　　MGraph InitGraph(void)</p><p><b>　　{</b></p><p><b>　　MGraph G;</b></p><p>

100、<b>　　int i,j;</b></p><p><b>　　G.n=14;</b></p><p><b>　　G.e=24;</b></p><p>　　for(i=0;i<G.n;i++)</p><p>　　G.vexs[i].no=i;</p>

101、<p>　　strcpy(G.vexs[0].name,"湖南林業(yè)科技大學(xué)");</p><p>　　strcpy(G.vexs[1].name,"瀟湘晨報(bào)");</p><p>　　strcpy(G.vexs[2].name,"市中心醫(yī)院");</p><p>　　strcpy(G.vexs[

102、3].name,"鐵道學(xué)院");</p><p>　　strcpy(G.vexs[4].name,"新開鋪路口");</p><p>　　strcpy(G.vexs[5].name,"南郊公園");</p><p>　　strcpy(G.vexs[6].name,"后湖路口");<

103、/p><p>　　strcpy(G.vexs[7].name,"猴子石大橋");</p><p>　　strcpy(G.vexs[8].name,"桃源村");</p><p>　　strcpy(G.vexs[9].name,"沙泥塘");</p><p>　　strcpy(G.vexs

104、[10].name,"王家灣");</p><p>　　strcpy(G.vexs[11].name,"中南大學(xué)校本部");</p><p>　　strcpy(G.vexs[12].name,"八字墻");</p><p>　　strcpy(G.vexs[13].name,"左家垅");

105、</p><p>　　}//頂點(diǎn)和路徑數(shù)據(jù)源初始化</p><p>　　void DispMat(MGraph g) //輸出鄰接矩陣g</p><p><b>　　{int i,j;</b></p><p>　　for (i=0;i<14;i++)</p><p><

106、;b>　　{</b></p><p>　　for (j=0;j<14;j++)</p><p>　　if (g.edges[i][j]==INF)</p><p>　　printf("%3s","∞");</p><p><b>　　else</b><

107、/p><p>　　printf("%3d",g.edges[i][j]);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("\n\n");</p><p><

108、b>　　}</b></p><p>　　void ppath(int path[][MAXV],int i,int j) //輸入各條最短路經(jīng)</p><p><b>　　{ int k;</b></p><p>　　k=path[i][j];</p><p>　　if (k==-1) retur

109、n;</p><p>　　ppath(path,i,k);</p><p>　　printf("%3d,",k);</p><p>　　ppath(path,k,j);</p><p><b>　　}</b></p><p>　　void out()</p>&l

110、t;p>　　{ printf("\n站名編號為：\n 0.湖南林業(yè)科技大學(xué) 1.瀟湘晨報(bào)\n 2.市中心醫(yī)院 3.鐵道學(xué)院\n 4.新開鋪路口 5.南郊公園\n 6.后湖路口 7.猴子石大橋\n 8.桃源村 9.沙泥塘\n 10.王家灣

111、 11.中南大學(xué)校本部\n 12.八字墻 13.左家垅\n\n\n");</p><p><b>　　}</b></p><p><b>　　//輸出站點(diǎn)列表</b></p><p>　　void Floyd(MGraph g)//弗洛伊德算法從每對

112、頂點(diǎn)之間的最短路徑</p><p>　　{int A[MAXV][MAXV],path[MAXV][MAXV];</p><p>　　int i,j,k,r,f,n=14;</p><p>　　for (i=0;i<n;i++)//給A數(shù)組置初值</p><p>　　for (j=0;j<n;j++)</p>

113、;<p>　　{A[i][j]=g.edges[i][j];</p><p>　　path[i][j]=-1;}</p><p>　　for (k=0;k<n;k++)//計(jì)算Ak</p><p>　　{for (i=0;i<n;i++)</p><p>　　for (j=0;j<n;j++)&l

114、t;/p><p>　　if (A[i][j]>(A[i][k]+A[k][j]))</p><p>　　{A[i][j]=A[i][k]+A[k][j];</p><p>　　path[i][j]=k;}}</p><p>　　printf("請輸入需要查找的兩個(gè)站點(diǎn)(站點(diǎn)編號為0-13):\n");</p&

115、gt;<p><b>　　out();</b></p><p>　　printf("起點(diǎn):");scanf("%3d",&f);</p><p>　　while(f>=n)</p><p>　　{ printf("該站不存在，請重新輸入！\n");</

116、p><p>　　printf("起點(diǎn):");scanf("%3d",&f); };</p><p>　　printf("終點(diǎn):");scanf("%3d",&r);</p><p>　　while(r>=n){</p><p>　　printf(

117、"該站不存在，請重新輸入！\n");</p><p>　　printf("終點(diǎn):");scanf("%3d",&r); };</p><p>　　while(r==f){</p><p>　　printf("不能等于起點(diǎn)，請重新輸入！\n");</p><p&

118、gt;　　printf("終點(diǎn):");scanf("%3d",&r);};</p><p>　　printf("\n輸出最短路徑:\n");</p><p>　　if (A[f][r]==INF){ if(f!=r)printf("從%3d到%3d沒有路徑\n\n\n",f,r);}</p>

119、<p><b>　　else</b></p><p>　　{ printf("從%3d到%3d路徑為:",f,r);</p><p>　　printf("%3d,",f);</p><p>　　ppath(path,f,r);</p><p>　　printf(&q

120、uot;%3d",r);</p><p>　　printf("\n路徑長度為:%3d km \n\n\n",A[f][r]);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void main()</p>

121、<p>　　{ int i,j,n,k=1;</p><p>　　MGraph InitGraph(void);</p><p>　　int A[14][14]={{32767,32767,32767,32767,32767,32767,32767,8,32767,32767,32767,32767,32767,32767},{32767,32767,32767,327

122、67,32767,32767,32767,6,32767,8,32767,32767,32767,32767},{32767,32767,32767,32767,32767,32767,32767,32767,32767,7,32767,32767,32767,32767},{32767,32767,32767,32767,32767,32767,32767,32767,5,32767,7,32767,32767,32767},{327

123、67,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,32767,9},{32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,8},{32767,32</p><p>　　for (i=0;i<14;i++)</p><

124、;p>　　for (j=0;j<14;j++)</p><p>　　G.edges[i][j]=A[i][j];</p><p>　　while(k==1)</p><p><b>　　{</b></p><p>　　printf(" *************歡迎進(jìn)入公交查詢系統(tǒng)******