數(shù)據(jù)結構課程設計---交通旅游圖的最短路徑問題

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

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

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

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

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

6、t;</p><p>　　第二章系統(tǒng)功能模塊的設計5</p><p>　　2.1 系統(tǒng)功能分析與設計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結構體的建立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>　　第三章 實踐結果與調(diào)試..........................................................................................................12<

11、;/p><p>　　3.1運行結果.........................................................................................................................12</p><p>　　3.1.1主界面.......................................

12、............................................................................12</p><p>　　3.1.2查詢站點編號模塊...............................................................................................12</p>

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

14、...................................13</p><p>　　3.2運行調(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>　　第四章設計總結與心得............................................................................................................16</p><p>　　附錄：程序源代碼........................

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

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

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

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

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

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

23、個方向又可能對應多個路線號。 </p><p>　?。?）算法：按選定的數(shù)據(jù)結構設計相應的算法。注意，當從乘車站到目的站存在多種乘車路線時，必須確定路線選取標準。例如，要求換車次數(shù)最少等。 </p><p>　　數(shù)據(jù)結構可以采用鏈接結構：</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ù)結構也可以采用順序結構：</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>　?。?）另外，還需建立兩個數(shù)組；一個是線路序號和線路號“值”的對照表；另一個是站號和站名對照表。</p><p>　?。?）對所采用的算法進行算法分析 </p><p><b>　　三. 實現(xiàn)提示</b

27、></p><p>　　假定頂點編號為1..n，數(shù)據(jù)結構采用連接結構。設置表頭數(shù)組為head[1..n]，head[i]包含站i的名字和一指針，該指針指向i的所有鄰接頂點組成的單鏈表。單鏈表中的每個結點包含3個域：一個站號域，兩個指針域。一個指針指向i的下一個鄰接頂點，另一個指針指向從i到該結點的所有線路號組成的鏈表。 </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ù)最少的原則來確定乘車路線，實際上是最短路徑問題

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

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

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

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

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

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

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結構體的建立</p><p>　　本次設計中需要運用有向圖來顯示交通網(wǎng)絡圖，顧建立抽象數(shù)據(jù)結構體便是很重要的一項工序。首先要先建立頂

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

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

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

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

41、lt;p>　　} MGraph;//圖的鄰接矩陣類型</p><p>　　2.2.2圖的建立與初始化</p><p>　　圖是這個題目課程設計的核心。所以對圖的建立是必要的，并且對圖的初始化賦值也同樣重要。在創(chuàng)建圖是，同時進行對頂點的編號，名稱的填寫以及鄰接矩陣的輸入。這樣才能構成完整的有向圖，才能建立確切的交通網(wǎng)絡圖，以便實現(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è)科技大學");</p><p>　　strcpy(G.vexs[1].name,"瀟湘晨報");</p><p>　　strcpy(G.vexs[2].name,"市中心醫(yī)院");</p><p>　　strcpy(G.vexs[3].name,"鐵道學院"

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,"中南大學校本部");</p><p>　　strcpy(G.vexs[12].name,"八字墻");</p><p>　　strcpy(G.vexs[13].name,"左家垅");</p><p>　　}

51、//站點和路徑數(shù)據(jù)源初始化</p><p>　　2.2.3鄰接矩陣的輸出</p><p>　　鄰接矩陣是用來存儲邊權信息的。通過鄰接矩陣可直接讀出兩頂點間是否有直通路線，同時還可以找到是否轉戰(zhàn)，但不如圖形直觀。但鄰接矩陣是用來存儲有向圖通路信息的最普遍方法之一，顧我們這次同樣選擇用鄰接矩陣來儲存。</p><p>　　在我們的系統(tǒng)中設置了專門顯示鄰接矩陣情況的函數(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)中的第二項重要功能?？梢燥@示出站點名及編號，以便用戶查詢方便。此功能函數(shù)為：</p><p>　　void out()</p><p>　　{ printf("\n站名編號為：\n 0.湖南林業(yè)科技大學

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

57、n\n\n");</p><p><b>　　}</b></p><p>　　另外，我們?yōu)閷崿F(xiàn)可以顯示中轉站的功能，又另設立一函數(shù)為求出起點與終點的路徑中所經(jīng)的站點編號，這樣方便旅者轉車。此部分函數(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>　　本設計中用多源有向圖來顯示交通網(wǎng)絡的交通圖，顧采用弗洛里德算法來求兩頂點之間的最短路徑問題。此功能為人工輸入要查詢的起點及終點，系統(tǒng)將自動輸出兩點之間的最短路徑，以及期間所

60、經(jīng)過的站點編號。此功能為交通咨詢系統(tǒng)的最核心函數(shù)。其代碼如下：</p><p>　　void Floyd(MGraph g)//弗洛伊德算法從每對頂點之間的最短路徑</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++)//計算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("請輸入需要查找的兩個站點(站點編號為0-13):\n");</p><p><b>　　out();</b></p><p>　　printf("起點:");scanf("%3d",&f);</p><

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

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

66、le(r==f){</p><p>　　printf("不能等于起點，請重新輸入！\n");</p><p>　　printf("終點:");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)中主要實現(xiàn)主界面的設置，菜單功能的實現(xiàn)。同時使其他模塊函數(shù)的功能連接起來，共同組成一個完整的咨詢系統(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、***歡迎進入公交查詢系統(tǒng)************* \n");</p><p>　　printf(" 制作人：韋千慧 周韻\n");</p><p>　　printf(" 請輸入選擇：\n");</p>

72、;<p>　　printf(" 1.查詢站點\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("輸入錯誤！請重新輸入！");</p><p><b>　　}</b></p><p><b>　　}</b></p><p>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

93、>　　此次設計也讓我明白了思路即出路，有什么不懂不明白的地方要及時請教或上網(wǎng)查詢，只要認真鉆研，動腦思考，動手實踐，就沒有弄不懂的知識，收獲頗豐。</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//最大頂點個數(shù)</p><p>　　#define INF 32767 //用32767表示∞</p>

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

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

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

98、 //圖的定義</p><p>　　{ int edges[MAXV][MAXV]; //鄰接矩陣</p><p>　　int n,e; //頂點數(shù)，弧數(shù)</p><p>　　VertexType vexs[MAXV];//存放頂點信息</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è)科技大學");</p><p>　　strcpy(G.vexs[1].name,"瀟湘晨報");</p><p>　　strcpy(G.vexs[2].name,"市中心醫(yī)院");</p><p>　　strcpy(G.vexs[

102、3].name,"鐵道學院");</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,"中南大學校本部");</p><p>　　strcpy(G.vexs[12].name,"八字墻");</p><p>　　strcpy(G.vexs[13].name,"左家垅");

105、</p><p>　　}//頂點和路徑數(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è)科技大學 1.瀟湘晨報\n 2.市中心醫(yī)院 3.鐵道學院\n 4.新開鋪路口 5.南郊公園\n 6.后湖路口 7.猴子石大橋\n 8.桃源村 9.沙泥塘\n 10.王家灣

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

112、頂點之間的最短路徑</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++)//計算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("請輸入需要查找的兩個站點(站點編號為0-13):\n");</p&

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

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

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

118、gt;　　printf("終點:");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(" *************歡迎進入公交查詢系統(tǒng)******