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

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

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

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

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

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

6、3</p><p>　　1.2算最短路徑4</p><p>　　1.3無(wú)向圖遍歷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è)計(jì)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 心得體會(huì)7</b></p><p><b>　　附錄一：源程序8</b></p><p>　　附錄三：參考文獻(xiàn)14</p><p>　　摘 要 </p><p>　　計(jì)算機(jī)解決一個(gè)

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

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

11、是V(G)={v 0 ，v i ，…，V n-1 }。</p><p>　　1.1.1 圖的鄰接矩陣表示法</p><p>　?。ǎ保┯绵徑泳仃嚤硎卷旤c(diǎn)之間的相鄰關(guān)系；</p><p>　?。ǎ玻┯靡粋€(gè)順序表來(lái)儲(chǔ)存頂點(diǎn)信息</p><p>　　1.1.2　圖的鄰接矩陣(Adacency Matrix)</p><p>

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

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

14、;　?。城笞钚∩蓸?lt;/b></p><p>　　對(duì)于連通的帶權(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、成樹可簡(jiǎn)記為MST。</p><p><b>　　最小生成樹性質(zhì)：</b></p><p>　　設(shè)G=(V，E)是一個(gè)連通網(wǎng)絡(luò)，U是頂點(diǎn)集V的一個(gè)真子集。若(u，v)是G中一條“一個(gè)端點(diǎn)在U中(例如：u∈U)，另一個(gè)端點(diǎn)不在U中的邊(例如：v∈V-U)，且(u，v)具有最小權(quán)值，則一定存在G的一棵最小生成樹包括此邊(u，v)。</p><p>

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

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

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

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

20、t;n，&G->e); //輸入頂點(diǎn)數(shù)和邊數(shù)</p><p>　　for(i=0;in;i++) //讀人頂點(diǎn)信息，建立頂點(diǎn)表</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è)計(jì)</b></p><p><b>　　3.1系統(tǒng)功能</

23、b></p><p>　　提供無(wú)向圖的生成，并保證了該無(wú)向圖為一個(gè)無(wú)向網(wǎng)，同時(shí)也提供了計(jì)算最短距離的迪杰斯特拉算法，以及圖的遍歷。</p><p><b>　　3.2主要函數(shù)說明</b></p><p>　　本系統(tǒng)用了一個(gè)類來(lái)實(shí)現(xiàn)程序，里面包含了4個(gè)對(duì)象，即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ú)向網(wǎng)的建立</p><p>　　由于圖的結(jié)構(gòu)比較復(fù)雜，任意兩個(gè)頂點(diǎn)之間都可能存在聯(lián)系，因此無(wú)

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

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

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

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

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

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

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

32、<p>　　const int n=5; //n表示公園圖中頂點(diǎn)個(gè)數(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]; //景點(diǎn)

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、;"以下是公校的景點(diǎn)"<<endl;</p><p>　　cout<<" ***************************"<<endl;</p><p>　　cout<<" * 1.公園入口 2.水族館 *"<<endl;</p><p&g

37、t;　　cout<<" * 3.摩天輪 4.動(dòng)物園 * *"<<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<<"下面是景點(diǎn)與景點(diǎn)之間的距離和介紹："<<endl;</p><

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

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

45、p>　　cout<<"4.動(dòng)物園 ->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; //景點(diǎn)一樣則距離為0</p><p>　　else t.arcs[i][j]=max; //i不等于j時(shí)</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、　　} //把景點(diǎn)跟距離用一個(gè)二圍數(shù)組存儲(chǔ)下來(lái)</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) //從頂點(diǎn)i出發(fā)實(shí)現(xiàn)廣度搜索搜索n&

55、lt;/p><p><b>　　{</b></p><p>　　int j,i; //f，r分別為隊(duì)列頭，尾指針</p><p><b>　　char ch;</b></p><p>　　cout<<"請(qǐng)輸入一個(gè)你想去的地方:";</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<<"請(qǐng)問你想去游覽公園全景嗎(y/n)："<<endl;</p><p><b>　　cin>>ch;</b></p><p>　　if(ch=='y')</p><p>　　cout<<"請(qǐng)走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<<"請(qǐng)輸入一個(gè)你想去的地方:"; </p><p><b>　　cin>>i;}</b></p><p>　　if(ch!='y') </p><p><b>　　{</b></p><p>　　cout<<"

66、 *****退出程序*****"<<endl;</p><p>　　cout<<" 歡迎下次再來(lái)"<<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>　　附錄二：測(cè)試數(shù)據(jù)</b></p><p><b>　　圖1—1</b></p><p><b>　　圖1—2</b></p><p><b>　　參考文獻(xiàn)&