課程設(shè)計(jì)報(bào)告---管道鋪設(shè)施工

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告</p><p><b>　　管道鋪設(shè)施工</b></p><p>　　——采用最小生成樹(shù)算法</p><p><b>　　目錄</b></p><p>　　課程設(shè)計(jì)課題………………………………………………………3設(shè)計(jì)要求及分析………………………………………

2、……………3</p><p>　　開(kāi)發(fā)環(huán)境……………………………………………………………3</p><p>　　類(lèi)的結(jié)構(gòu)圖…………………………………………………………4</p><p>　　程序結(jié)構(gòu)……………………………………………………………4</p><p>　　測(cè)試結(jié)果……………………………………………………………5</p>

3、<p>　　收獲與體會(huì)…………………………………………………………6</p><p>　　【一】課程設(shè)計(jì)課題：</p><p>　　管道鋪設(shè)施工的最佳方案選擇</p><p>　　【二】設(shè)計(jì)要求及分析：</p><p>　　要求： N(N>10)個(gè)居民區(qū)之間需要鋪設(shè)煤氣管道。假設(shè)任意兩個(gè)居民區(qū)之間都可以 鋪設(shè)煤氣管道，但代

4、價(jià)不同。要求事先任意兩居民區(qū)之間鋪設(shè)煤氣管道的代價(jià)存入磁盤(pán)文件中。設(shè)計(jì)一個(gè)最佳方案使得這N個(gè)居民區(qū)之間鋪設(shè)煤氣管道所需代價(jià)最小，并將結(jié)果以圖形方式在屏幕上輸出。</p><p>　　MST性質(zhì)：最小生成樹(shù)具有MST性質(zhì)，即，假設(shè)G=（V，E）是一個(gè)無(wú)向連通圖，U是頂點(diǎn)集V的一個(gè)非空子集。若（u,v）是一條具有最小權(quán)值的邊，其中u∈U,v∈V-U,則必存在一顆包含邊(u,v)的最小生成樹(shù)。</p>&

5、lt;p>　　Prim算法：Prim算法的基本思想是：設(shè)G=(V,E)是一個(gè)無(wú)向連通圖，令T=(U,TE)是G的最小生成樹(shù)。T的初始狀態(tài)為U={v0}(v0∈V),TE={}.然后重復(fù)執(zhí)行下述操作：在所有u∈U，v∈V-U的邊中找一條代價(jià)最小的邊(u,v)并入集合TE，同時(shí)v并入U(xiǎn)，直至U=V為止。此時(shí)TE中必有n-1條邊，T就是最小生成樹(shù)。</p><p>　　顯然 ，prim算法的關(guān)鍵是圖和找到鏈接U和

6、V-U的最短邊來(lái)擴(kuò)充生成樹(shù)T。設(shè)當(dāng)前T中有k個(gè)頂點(diǎn)，則所有滿足u∈U,v∈V-U的邊最多有k*(n-k)條，從如此大的邊集中選取最短邊是不太經(jīng)濟(jì)的。利用MST性質(zhì)，可以用下述方法構(gòu)造候選最短邊集：對(duì)應(yīng)v-u中的每個(gè)頂點(diǎn)，保留從該頂點(diǎn)到U中各頂點(diǎn)的最短邊，取候選最短邊集為V-U中n-k個(gè)頂點(diǎn)所關(guān)聯(lián)的n-k條最短邊的集合。</p><p>　　需求分析:設(shè)計(jì)要求是選擇管道鋪設(shè)施工的最佳方案，則必須采用prim算法來(lái)選

7、擇出最佳方案。且由于原始數(shù)據(jù)量較大，則需要使用讀取磁盤(pán)文件的方法來(lái)讀入數(shù)據(jù)。由于在算法執(zhí)行過(guò)程中，需要不斷讀取任意兩個(gè)頂點(diǎn)之間邊的權(quán)值，所以，圖采用鄰接矩陣存儲(chǔ)；為了能訪問(wèn)鄰接矩陣類(lèi)中的私有成員變量，將Prim算法設(shè)為鄰接矩陣的成員函數(shù)。而由于設(shè)計(jì)要求以圖形方式在屏幕上輸出，則使用MFC將結(jié)果一圖形方式輸出。</p><p><b>　　【三】開(kāi)發(fā)環(huán)境：</b></p><

8、;p>　　軟件：Microsoft Visual Studio 2005 </p><p>　　OS 名稱(chēng)：Microsoft Windows XP Professional</p><p><b>　　硬盤(pán)：160G</b></p><p><b>　　內(nèi)存：1G</b></p><p&

9、gt;<b>　　【四】類(lèi)的結(jié)構(gòu)圖：</b></p><p>　　本程序只有一個(gè)大類(lèi)，即鄰接矩陣。該鄰接矩陣用于存儲(chǔ)各個(gè)居民區(qū)之間數(shù)據(jù)的無(wú)向圖。</p><p><b>　　具體成員有：</b></p><p>　　char vertex[Max] ,用于存儲(chǔ)各個(gè)居民區(qū)的名稱(chēng)，該數(shù)據(jù)為char型，則名稱(chēng)一般為單個(gè)字符。&l

10、t;/p><p>　　Int arc[Max][Max] 則用于存儲(chǔ)相對(duì)應(yīng)兩個(gè)居民區(qū)之間鋪設(shè)管道所需要的代價(jià)，故該數(shù)組為二維整型數(shù)組。</p><p>　　Int PrimArc[Max][Max]也是一個(gè)二維整型數(shù)組，用于記錄最小代價(jià)的路線。</p><p>　　Int lowcost[Max],int adjvex[Max]兩個(gè)數(shù)組則是用于輔助Prim算法。為表示候

11、選最短邊集，需設(shè)置兩個(gè)一維數(shù)組，其中l(wèi)owcost用來(lái)保存集合V-U中各頂點(diǎn)與集合U中頂點(diǎn)最短邊的權(quán)值，lowcoat[v]=0表示頂點(diǎn)v已加入最小生成樹(shù)中；adjvex用來(lái)保存依附于該邊在集合U中的頂點(diǎn)。</p><p><b>　　成員函數(shù)有：</b></p><p>　　MGraph（）為構(gòu)造函數(shù)。由于數(shù)據(jù)的讀入在構(gòu)造函數(shù)中進(jìn)行，則不需要參數(shù)傳遞。但在函數(shù)中則需

12、要文件流來(lái)讀入磁盤(pán)文件，并將數(shù)據(jù)保存在各個(gè)數(shù)組中。</p><p>　　~MGraph（）則為析構(gòu)函數(shù)。</p><p>　　Get（int i）則是取圖中第i個(gè)頂點(diǎn)的數(shù)據(jù)信息。</p><p>　　Search（char value）則是取圖中數(shù)據(jù)為value的頂點(diǎn)的位置。</p><p>　　Minedge（）則是在lowcost中尋找最

13、短邊的頂點(diǎn)k</p><p>　　Prim（）則是最小生成樹(shù)函數(shù)，該算法運(yùn)行結(jié)束后，將最小生成樹(shù)輸入PrimArc數(shù)組中。</p><p><b>　　【五】程序結(jié)構(gòu)</b></p><p>　　由于任意兩居民區(qū)之間鋪設(shè)煤氣管道的代價(jià)存在磁盤(pán)文件中，則使用文件讀入流將數(shù)據(jù)分別按需要讀入不同數(shù)組，建立居民區(qū)與居民區(qū)之間所需代價(jià)的對(duì)應(yīng)圖中，使用最小

14、生成樹(shù)Prim算法來(lái)確定N個(gè)居民區(qū)之間鋪設(shè)煤氣管道的最小代價(jià)，最后使用繪圖語(yǔ)句將原始圖輸入，并使用特殊顏色來(lái)標(biāo)出煤氣管道最小代價(jià)的路線圖。</p><p>　　由于該程序是在MFC環(huán)境下 運(yùn)行，通過(guò)電腦自動(dòng)生成MainFrm，pine，pineDoc，pineView，stdafx等源文件與頭文件，一個(gè)自動(dòng)窗口已生成。設(shè)計(jì)要求將運(yùn)行結(jié)果以圖形方式輸出。則需要在pineView中繪圖，根據(jù)資源文件，生成相對(duì)應(yīng)的點(diǎn)，

15、線及特殊顏色的線條。</p><p>　　生成點(diǎn)的函數(shù)語(yǔ)句如下：</p><p>　　pDC->TextOut(a[j],b[j],s);</p><p>　　pDC->Ellipse(a[j]-5,b[j]-5,a[j]+5,b[j]+5);</p><p>　　生成線條的函數(shù)語(yǔ)句如下：</p><p>

16、　　pDC->TextOut(m, n, str);</p><p>　　pDC->MoveTo(a[i],b[i]);</p><p>　　pDC->LineTo(a[j],b[j]);</p><p>　　添加顏色的畫(huà)筆函數(shù)語(yǔ)句如下：</p><p>　　HPEN hPen=CreatePen(PS_SOLID,3,RG

17、B(0,225,255));</p><p>　　pDC->SelectObject(hPen);</p><p>　　該程序主要框架由系統(tǒng)自動(dòng)生成，通過(guò)添加鄰接矩陣的頭文件，以及繪圖函數(shù)后，將結(jié)果按要求輸出。</p><p><b>　　【六】測(cè)試結(jié)果</b></p><p>　　原始數(shù)據(jù)為：文本文檔</p

18、><p>　　輸出數(shù)據(jù)為窗口，圖形</p><p><b>　　【七】收獲與體會(huì)</b></p><p>　　通過(guò)這次的課程設(shè)計(jì)，使我收獲頗豐。最小生成樹(shù)Prim算法在一開(kāi)始學(xué)習(xí)的時(shí)候，就是作為一個(gè)重點(diǎn)，并且在之后的練習(xí)中也多次運(yùn)用到。使我對(duì)Prim算法有了一定的理解，而這次的課程設(shè)計(jì)則大大地加深了我對(duì)于算法的理解。通過(guò)對(duì)實(shí)際應(yīng)用的探討，讓我了解了

19、算法在日常生活中的廣泛應(yīng)用。比如各個(gè)城市間路線的造價(jià)，以及這次的管道鋪設(shè)等，而且不止一個(gè)算法，在數(shù)據(jù)結(jié)構(gòu)課程中學(xué)習(xí)的算法可以說(shuō)是算法思想對(duì)生活應(yīng)用的一個(gè)提煉。</p><p>　　文件的讀入輸出雖然并沒(méi)有太大的難度，但同樣是一個(gè)日常應(yīng)用的重點(diǎn)，畢竟大部分的程序都不可能局限于幾個(gè)簡(jiǎn)單數(shù)據(jù)的轉(zhuǎn)換，程序是用來(lái)解決問(wèn)題的，而這些問(wèn)題的數(shù)據(jù)絕對(duì)不會(huì)是少量的，甚至是巨大的。如此簡(jiǎn)單的應(yīng)用手動(dòng)輸入，那么一個(gè)程序的強(qiáng)壯性，可讀性

20、將會(huì)大大減小，讀取文件，是解決這樣一個(gè)問(wèn)題的最好的方法，必須掌握。</p><p>　　將結(jié)果以圖形方式輸出，可以說(shuō)是這個(gè)程序的一大亮點(diǎn)，現(xiàn)在大部分程序都是在dos界面上運(yùn)行，而MFC對(duì)于大部分同學(xué)都是較為陌生的。通過(guò)這樣的一個(gè)鍛煉，我更加認(rèn)識(shí)到對(duì)于面向用戶而言，窗口界面比dos更有實(shí)用性，也是我們必須掌握的。熟練的掌握MFC，使用MFC本身提供的函數(shù)，以及一些普通且必要的函數(shù)來(lái)顯示各種數(shù)據(jù)，將會(huì)比dos界面更加