課程設計報告---管道鋪設施工

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

2、……………3</p><p>　　開發(fā)環(huán)境……………………………………………………………3</p><p>　　類的結構圖…………………………………………………………4</p><p>　　程序結構……………………………………………………………4</p><p>　　測試結果……………………………………………………………5</p>

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

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

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

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

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

8、;p>　　軟件：Microsoft Visual Studio 2005 </p><p>　　OS 名稱：Microsoft Windows XP Professional</p><p><b>　　硬盤：160G</b></p><p><b>　　內存：1G</b></p><p&

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

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

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

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

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

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

15、線及特殊顏色的線條。</p><p>　　生成點的函數(shù)語句如下：</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ù)語句如下：</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>　　添加顏色的畫筆函數(shù)語句如下：</p><p>　　HPEN hPen=CreatePen(PS_SOLID,3,RG

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

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

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

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