公園導(dǎo)游圖課程設(shè)計

1、<p><b>　　課 程 設(shè) 計</b></p><p><b>　　課程設(shè)計任務(wù)書</b></p><p>　　2009～2010學(xué)年第 1學(xué)期</p><p>　　一、課程設(shè)計題目: 公園導(dǎo)游圖</p><p><b>　　二、課程設(shè)計內(nèi)容</b></p&

2、gt;<p>　　給出一張某公園的導(dǎo)游圖，游客通過終端詢問可知：從某一景點到另一景點的最短路徑。游客從公園大門進入，選一條最佳路線，使游客可以不重復(fù)地游覽各景點，最后回到出口（出口就在入口旁邊）。</p><p><b>　　三、進度安排</b></p><p>　　1． 初步完成總體設(shè)計，搭好框架，確定人機對話的界面，確定函數(shù)個數(shù)；</p>

3、<p>　　2． 完成最低要求：建立一個文件，包括5個景點情況，能完成遍歷功能；</p><p>　　3． 進一步要求：進一步擴充景點數(shù)目，畫出景點圖，有興趣的同學(xué)可以自己擴充系統(tǒng)功能。四、基本要求</p><p>　　1. 界面友好，函數(shù)功能要劃分好</p><p>　　2. 總體設(shè)計應(yīng)畫一流程圖</p><p>　　3.

4、 程序要加必要的注釋</p><p>　　4. 要提供程序測試方案</p><p>　　5. 程序一定要經(jīng)得起測試，寧可功能少一些，也要能運行起來，不能運行的程序是沒有價值的。</p><p>　　教研室主任簽名： </p><p>　　年 月 日</p><p><b>

5、;　　目 錄</b></p><p><b>　　摘要 </b></p><p><b>　　1 問題描述3</b></p><p>　　1.1圖、無向圖3</p><p>　　1.1.1圖的存儲結(jié)構(gòu)3</p><p>　　1.1.2 圖的鄰接矩陣表示法

6、3</p><p>　　1.2算最短路徑4</p><p>　　1.3無向圖遍歷4</p><p>　　1.4廣度優(yōu)先搜索4</p><p><b>　　2.系統(tǒng)分析5</b></p><p>　　2.1系統(tǒng)流程圖5</p><p><b>　　3 系

7、統(tǒng)設(shè)計5</b></p><p>　　3.1主要數(shù)據(jù)結(jié)構(gòu)6</p><p>　　3.2 主要函數(shù)說明6</p><p>　　3.3主要算法說明6</p><p>　　3.3.1數(shù)組表示法6</p><p>　　3.3.2Floyd算法6</p><p><b>

8、　　4 心得體會7</b></p><p><b>　　附錄一：源程序8</b></p><p>　　附錄三：參考文獻14</p><p>　　摘 要 </p><p>　　計算機解決一個

9、具體問題時，大致需要經(jīng)過下列幾個步驟：首先要從具體問題中抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計一個解此數(shù)學(xué)模型的算法（Algorithm），最后編出程序、進行測試、調(diào)整直至得到最終解答。尋求數(shù)學(xué)模型的實質(zhì)是分析問題，從中提取操作的對象，并找出這些操作對象之間含有的關(guān)系，然后用數(shù)學(xué)的語言加以描述。計算機算法與數(shù)據(jù)的結(jié)構(gòu)密切相關(guān)，算法無不依附于具體的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)直接關(guān)系到算法的選擇和效率。運算是由計算機來完成，這就要設(shè)計相應(yīng)的插入、刪除和

10、修改的算法 。也就是說，數(shù)據(jù)結(jié)構(gòu)還需要給出每種結(jié)構(gòu)類型所定義的各種 運算的算法。</p><p><b>　　1.問題描述</b></p><p><b>　　１.１圖的存儲結(jié)構(gòu)</b></p><p>　　圖的存儲方式很多，這里用的是鄰接矩陣的方式。為了適合用C語言描述，以下假定頂點序號從0開始，即圖G的頂點集的一般形式

11、是V(G)={v 0 ，v i ，…，V n-1 }。</p><p>　　1.1.1 圖的鄰接矩陣表示法</p><p>　　（１）用鄰接矩陣表示頂點之間的相鄰關(guān)系；</p><p>　　（２）用一個順序表來儲存頂點信息</p><p>　　1.1.2　圖的鄰接矩陣(Adacency Matrix)</p><p>

12、　　設(shè)G=(V，E)是具有n個頂點的圖，則G的鄰接矩陣是具有如下性質(zhì)的n階方陣：</p><p>　　若Ｇ是網(wǎng)絡(luò)，則鄰接矩陣可定義為：</p><p><b>　?。?２求最短路徑</b></p><p>　　給定一個帶權(quán)有向圖 G=(V,E) ，其中每條邊的權(quán)是一個非負實數(shù)。另外，還給定 V 中的一個頂點，稱為源?，F(xiàn)在我們要計算從源到所有其他

13、各頂點的最短路徑長度。這里的長度是指路上各邊權(quán)之和。這個問題通常稱為單源最短路徑問題。</p><p>　　1.2.1單源最短路徑問題　　Dijkstra提出按各頂點與源點v間的路徑長度的遞增次序，生成到各頂點的最短路徑的算法。既先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從源點v 到其它各頂點的最短路徑全部求出為止。</p><p><b>

14、;　?。城笞钚∩蓸?lt;/b></p><p>　　對于連通的帶權(quán)圖(連通網(wǎng))G，其生成樹也是帶權(quán)的。生成樹T各邊的權(quán)值總和稱為該樹的權(quán)，記作：</p><p>　　Te,W(u , v)　　TE表示T的邊集　　w(u，v)表示邊(u，v)的權(quán)。</p><p>　　權(quán)最小的生成樹稱為G的最小生成樹(Minimum Spanning Tree)。最小生

15、成樹可簡記為MST。</p><p><b>　　最小生成樹性質(zhì)：</b></p><p>　　設(shè)G=(V，E)是一個連通網(wǎng)絡(luò)，U是頂點集V的一個真子集。若(u，v)是G中一條“一個端點在U中(例如：u∈U)，另一個端點不在U中的邊(例如：v∈V-U)，且(u，v)具有最小權(quán)值，則一定存在G的一棵最小生成樹包括此邊(u，v)。</p><p>

16、<b>　?。?系統(tǒng)分析</b></p><p><b>　　１系統(tǒng)流程</b></p><p>　　本系統(tǒng)主要是實現(xiàn)圖的最短路徑問題</p><p>　　2.2系統(tǒng)相關(guān)抽象數(shù)據(jù)類型</p><p>　　2.2.1圖的鄰接矩陣存儲結(jié)構(gòu)形式說明</p><p>　　#defin

17、e MaxVertexNum l00 //最大頂點數(shù)，應(yīng)由用戶定義</p><p>　　typedef char VertexType; //頂點類型應(yīng)由用戶定義</p><p>　　typedef int EdgeType; //邊上的權(quán)值類型應(yīng)由用戶定義</p><p>　　typedef struct{</p><p>　　Vextex

18、Type vexs[MaxVertexNum] //頂點表</p><p>　　EdeType edges[MaxVertexNum][MaxVertexNum];</p><p>　　//鄰接矩陣，可看作邊表</p><p>　　int n，e; //圖中當(dāng)前的頂點數(shù)和邊數(shù)</p><p><b>　　}MGragh;</b

19、></p><p>　　2.2.2建立無向網(wǎng)絡(luò)的算法</p><p>　　void CreateMGraph(MGraph *G)</p><p>　　{//建立無向網(wǎng)的鄰接矩陣表示</p><p>　　int i，j，k，w;</p><p>　　scanf("%d%d"，&G-&g

20、t;n，&G->e); //輸入頂點數(shù)和邊數(shù)</p><p>　　for(i=0;in;i++) //讀人頂點信息，建立頂點表</p><p>　　G->vexs[i]=getchar();</p><p>　　for(i=0;in;i++)</p><p>　　for(j=0;jn;j++)</p><

21、;p>　　G->edges[i][j]=0; //鄰接矩陣初始化</p><p>　　for(k=0;ke;k++){//讀入e條邊，建立鄰接矩陣</p><p>　　scanf("%d%d%d"，&i，&j，&w);//輸入邊(v i ,v j )上的權(quán)w</p><p>　　G->edges[i][j

22、]=w;</p><p>　　G->edges[j][i]=w;</p><p><b>　　}</b></p><p>　　}//CreateMGraph</p><p><b>　　3.系統(tǒng)設(shè)計</b></p><p><b>　　3.1系統(tǒng)功能</

23、b></p><p>　　提供無向圖的生成，并保證了該無向圖為一個無向網(wǎng)，同時也提供了計算最短距離的迪杰斯特拉算法，以及圖的遍歷。</p><p><b>　　3.2主要函數(shù)說明</b></p><p>　　本系統(tǒng)用了一個類來實現(xiàn)程序，里面包含了4個對象，即void graph::picture()；void graph::creatp(

24、graph &t)；void graph::floyd(graph &t,const int n)；void graph::bfs(graph t)</p><p><b>　　3.3主要算法說明</b></p><p>　　3.3.1無向網(wǎng)的建立</p><p>　　由于圖的結(jié)構(gòu)比較復(fù)雜，任意兩個頂點之間都可能存在聯(lián)系，因此無

25、法以數(shù)據(jù)元素在存儲 區(qū)中的物理位置來表示元素之間的關(guān)系，即圖沒有順序映像的存儲結(jié)構(gòu)，但可以借助數(shù)組的數(shù)據(jù)類型表示元素之間的關(guān)系。另一方面，用多重鏈表表示 圖是自然的事，它是一種最簡單的這式映像結(jié)構(gòu)，聚聚以一個由一個數(shù)據(jù)域和多個指針域存儲該頂點，其中數(shù)據(jù)域存儲該頂點的信息，指針域存儲指向其鄰接點的指針.</p><p>　　3.3.2數(shù)組表示法</p><p>　　用兩個數(shù)組分別存儲數(shù)據(jù)元素

26、的信息和數(shù)據(jù)元素這間的關(guān)系的信息。以二維數(shù)組表示有N個頂點的圖時，需存放N個頂點信息和N2個弧信息的存儲量。</p><p>　　3.3.3Floyd算法</p><p>　　Floyd算法又稱為弗洛伊德算法，插點法，是一種用于尋找給定的加權(quán)圖中頂點間最短路徑的算法。</p><p>　　Floyd算法適用于APSP(All Pairs Shortest Paths

27、)，是一種動態(tài)規(guī)劃算法，稠密圖效果最佳，邊權(quán)可正可負。此算法簡單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法。</p><p>　　優(yōu)點：容易理解，可以算出任意兩個節(jié)點之間的最短距離，代碼編寫簡單；</p><p>　　缺點：時間復(fù)雜度比較高，不適合計算大量數(shù)據(jù)。</p><p><b>　　4.心得體會</b&

28、gt;</p><p>　　當(dāng)今世界，C語言作為國際上廣泛流行的通用程序設(shè)計語言，在計算機的研究和應(yīng)用中已展現(xiàn)出強大的生命力。C語言兼顧了諸多高級語言的特點，是一種典型的結(jié)構(gòu)化程序設(shè)計語言，它處理能力強，使用靈活方便，應(yīng)用面廣，具有良好的可移植性。</p><p>　　而數(shù)據(jù)結(jié)構(gòu)-作為C語言使用的途徑學(xué)科,也是計算機學(xué)科的一門核心課程.雖然我們學(xué)C語言和數(shù)據(jù)結(jié)構(gòu)已快一年了，但一直都注重理論

29、概念，而實際上機操作卻不多.很感謝這次的課程設(shè)計，它使我更加深刻地體會到多看專業(yè)書、多學(xué)習(xí)專業(yè)知識的重要性，只有掌握了一定量的專業(yè)知識才能得心應(yīng)手地解決諸多問題；另外，在課程設(shè)計過程中，我遇到了很多棘手的問題，好幾次都差點放棄了，但最終還是堅持下來了，所以我懂得了，做任何事都要有耐心，不要一遇到困難就退縮；當(dāng)遇到那么多的問題時，我自己能解決的并不多，大部分都是通過和小組同學(xué)討論而解決的。所以，在學(xué)習(xí)和工作中要時刻謹記“團結(jié)”二字，它好比

30、通向成功的鋪路石，不可或缺。在編程過程中，有編得很順利的，也有很多不順利的，正如人生的道路是曲折的，但正是因為曲折人生才光彩奪目，在人生的路上，總遇到重重困難，但正是因為這些困難我們才變的更加堅強，才能夠不斷地提高自己，充實自己，最后達到我們理想的彼岸。</p><p>　　感謝zz老師在授課期間對我們嚴(yán)厲的態(tài)度和嚴(yán)格的管理，才造就了今天的我們。在課程設(shè)計過程中，我們幾乎每個小組都遇到了不同程度的問題，但老師都細

31、心指導(dǎo)，耐心地為我們講解。老師認真負責(zé)的工作態(tài)度，對我們這次的課程設(shè)計得以順利完成發(fā)揮了不可估量的作用。最后，再一次感謝在這次課程設(shè)計中對我給予幫助的老師和同學(xué)。通過這次課程設(shè)計，我們不光收獲了知識，還收獲了友誼和歡樂。</p><p><b>　　附錄1 源程序</b></p><p>　　#include <iostream.h></p>

32、<p>　　const int n=5; //n表示公園圖中頂點個數(shù)</p><p>　　const int e=7; //e表示公園圖中路徑</p><p>　　bool visited[n+1]; </p><p>　　#define max 32767</p><p>　　class graph</p><

33、;p><b>　　{</b></p><p><b>　　public:</b></p><p>　　int arcs[n+1][n+1]; //領(lǐng)接矩陣</p><p>　　int a[n+1][n+1]; //距離</p><p>　　int path[n+1][n+1]; //景點

34、</p><p>　　void floyd(graph &t,const int n);</p><p>　　void picture();</p><p>　　void creatp(graph &t);</p><p>　　void bfs(graph t);</p><p><b>　　

35、};</b></p><p>　　void graph::picture() //公園圖</p><p><b>　　{</b></p><p>　　cout<<" ******公園導(dǎo)游圖******"<<endl;</p><p>　　cout<<

36、;"以下是公校的景點"<<endl;</p><p>　　cout<<" ***************************"<<endl;</p><p>　　cout<<" * 1.公園入口 2.水族館 *"<<endl;</p><p&g

37、t;　　cout<<" * 3.摩天輪 4.動物園 * *"<<endl;</p><p>　　cout<<" * 5.公園出口 *"<<endl;</p><p>　　cout<<" *******************

38、********"<<endl;</p><p>　　cout<<"以下是公園的路徑圖 "<<endl;</p><p>　　cout<<" 9 "<<endl;</p><p>　　cout<<&quo

39、t; 2 *---------*4 "<<endl;</p><p>　　cout<<" | \\ /| "<<endl;</p><p>　　cout<<" | 4\\ 5/ | "<<endl;</p>

40、<p>　　cout<<" | \\ / | "<<endl;</p><p>　　cout<<" 3 | \\/ | 2 "<<endl;</p><p>　　cout<<" | * 3 |

41、"<<endl;</p><p>　　cout<<" | / \\ | "<<endl;</p><p>　　cout<<" | /10 \\3| "<<endl;</p><p>　　cout<<

42、" 1 * / \\ * 5 "<<endl;</p><p>　　cout<<" 入口 出口 "<<endl;</p><p>　　cout<<"下面是景點與景點之間的距離和介紹："<<endl;</p><

43、;p>　　cout<<"1.公園入口 ->2.水族館 距離為：3"<<endl;</p><p>　　cout<<"1.公園入口 ->3.摩天輪 距離為：10"<<endl;</p><p>　　cout<<"2.水族館 ->4.動物園

44、 距離為：9"<<endl;</p><p>　　cout<<"2.水族館 ->3.摩天輪 距離為：4"<<endl;</p><p>　　cout<<"3.摩天輪 ->4.動物園 距離為：5"<<endl;</p><

45、p>　　cout<<"4.動物園 ->5.公園出口 距離為：2"<<endl;</p><p>　　cout<<"3.摩天輪 ->5.公園出口 距離為：3"<<endl;</p><p><b>　　}</b></p><p&g

46、t;　　void graph::creatp(graph &t)</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　for(i=1;i<=n;i++)</p><p>　　for(j=1;j<=n;j++)</

47、p><p>　　if(i==j)t.arcs[i][j]=0; //景點一樣則距離為0</p><p>　　else t.arcs[i][j]=max; //i不等于j時</p><p>　　t.arcs[1][2]=3;</p><p>　　t.arcs[2][1]=3;</p><p>　　t.arcs[2][4]=9

48、;</p><p>　　t.arcs[4][2]=9;</p><p>　　t.arcs[3][1]=8;</p><p>　　t.arcs[1][3]=8;</p><p>　　t.arcs[3][2]=4;</p><p>　　t.arcs[2][3]=4;</p><p>　　t.arcs

49、[3][4]=5;</p><p>　　t.arcs[4][3]=5;</p><p>　　t.arcs[3][5]=3;</p><p>　　t.arcs[5][3]=3;</p><p>　　t.arcs[5][4]=2;</p><p>　　t.arcs[4][5]=2;</p><p>

50、　　} //把景點跟距離用一個二圍數(shù)組存儲下來</p><p>　　void graph::floyd(graph &t,const int n)</p><p><b>　　{</b></p><p>　　for(int i=1;i<=n;i++)</p><p>　　for(int j=1;j<

51、;=n;j++)</p><p><b>　　{</b></p><p>　　t.a[i][j]=t.arcs[i][j]; //把距離付值給a.[i][j]</p><p>　　if((i!=j)&&(a[i][j]<max))</p><p>　　t.path[i][j]=i;</p>

52、;<p>　　else t.path[i][j]=0;</p><p><b>　　}</b></p><p>　　for(int k=1;k<=n;k++)</p><p><b>　　{</b></p><p>　　for(int i=1;i<=n;i++)</p

53、><p>　　for(int j=1;j<=n;j++)</p><p>　　if(t.a[i][k]+t.a[k][j]<t.a[i][j])</p><p><b>　　{</b></p><p>　　t.a[i][j]=t.a[i][k]+t.a[k][j];</p><p>　　t

54、.path[i][j]=t.path[k][j];</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void graph::bfs(graph t) //從頂點i出發(fā)實現(xiàn)廣度搜索搜索n&

55、lt;/p><p><b>　　{</b></p><p>　　int j,i; //f，r分別為隊列頭，尾指針</p><p><b>　　char ch;</b></p><p>　　cout<<"請輸入一個你想去的地方:";</p>

56、<p><b>　　cin>>i;</b></p><p>　　while(i<=5)</p><p><b>　　{</b></p><p>　　if(i==1)cout<<"這里就是你要去的地方拉!!"<<endl<<endl;&l

57、t;/p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　for(j=1;j<=n;j++)</p><p><b>　　{</b></p><p><b>　　if(i!=j)</b&

58、gt;</p><p><b>　　{</b></p><p>　　cout<<"距離為"<<t.a[i][j]<<": ";</p><p>　　int next=t.path[i][j];</p><p><b>　　cout<

59、;<j;</b></p><p>　　while(next!=i)</p><p><b>　　{</b></p><p>　　cout<<"--"<<next;</p><p>　　next=t.path[i][next];</p><p

60、><b>　　}</b></p><p>　　cout<<"--"<<i<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　cout<<&q

61、uot;等我推薦一條最佳路徑供你返回吧(y/n):";</p><p><b>　　}</b></p><p><b>　　cin>>ch;</b></p><p>　　if(ch=='y')</p><p><b>　　{</b><

62、/p><p>　　if(i==2) cout<<"2--3--5"<<endl;</p><p>　　if(i==3) cout<<"3--5"<<endl;</p><p>　　if(i==4) cout<<"4--5"<<endl;&l

63、t;/p><p>　　cout<<"請問你想去游覽公園全景嗎(y/n)："<<endl;</p><p><b>　　cin>>ch;</b></p><p>　　if(ch=='y')</p><p>　　cout<<"請走1--

64、2--3--4--5路線"<<endl;</p><p>　　cout<<"你還想去別的地方嗎?(y/n)";</p><p><b>　　cin>>ch;</b></p><p>　　if(ch=='y') </p><p>　　{cou

65、t<<"請輸入一個你想去的地方:"; </p><p><b>　　cin>>i;}</b></p><p>　　if(ch!='y') </p><p><b>　　{</b></p><p>　　cout<<"

66、 *****退出程序*****"<<endl;</p><p>　　cout<<" 歡迎下次再來"<<endl;</p><p><b>　　break;</b></p><p><b>　　}</b></p>

67、;<p><b>　　}</b></p><p>　　else break;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int main()</p><p><b>　　{

68、</b></p><p><b>　　graph t;</b></p><p>　　t.picture();</p><p>　　t.creatp(t);</p><p>　　t.floyd(t,n);</p><p><b>　　t.bfs(t);</b>&l

69、t;/p><p><b>　　}</b></p><p><b>　　附錄二：測試數(shù)據(jù)</b></p><p><b>　　圖1—1</b></p><p><b>　　圖1—2</b></p><p><b>　　參考文獻&