課程設計報告--管道鋪設施工的最佳方案選擇

1、<p>　　數(shù)據(jù)結構課程設計報告</p><p><b>　　原題重現(xiàn)： </b></p><p>　　課題5：管道鋪設施工的最佳方案選擇</p><p>　　N(N>10)個居民之間需要鋪設煤氣管道。假設任意兩個居民之間都可以鋪設煤氣管道，但代價不同。事先將任意兩個居民之間鋪設煤氣管道的代價存入磁盤文件中。設計一個最佳方案使得

2、這N個居民之間鋪設煤氣管道所需代價最少，并希望以圖形方式在屏幕上輸出結果。</p><p><b>　　一、算法思想</b></p><p><b>　　1,數(shù)據(jù)結構設計</b></p><p><b>　　代價文件的結構</b></p><p>　　代價文件主要存儲 表示N(

3、N>10) 個居民的符號,以及兩個居民之間鋪設煤氣管道的代價。除此之外代價文件是用來得到圖的存儲結構的，考慮到圖的存儲結構定義中有vexs[N]數(shù)組存儲頂點，以及arcs[N][N]數(shù)組存儲邊，vexnum,arcnum這兩個變量分別表示頂點數(shù)和邊數(shù)；最后考慮格式。</p><p>　　所以綜合以上考慮代價文件的結構如下： 第一行存頂點個數(shù)，邊的個數(shù)；接下來存頂點，也就是表示居民的符號，第二行A，第三行 B

4、，第四行 Ｃ……；然后存邊和邊的權值（例如A B 32）以這種形式存放到磁盤文件中。 </p><p>　　圖的存儲結構：鄰接矩陣。</p><p>　　鄰接矩陣是表示圖形中頂點之間相鄰關系的矩陣。一個圖的鄰接矩陣是唯一的。圖的鄰接矩陣表示，除了需要用一個二維數(shù)組存儲頂點之間的相鄰關系的鄰接矩陣外，通常還需要使用一個具有n個元素的一維數(shù)組來存儲頂點信息，其中下標為i的元素存儲頂點

5、vi的信息。因此，圖的鄰接矩陣的存儲結構定義如下：</p><p>　　#define N 20</p><p>　　#define INFINITY 9999</p><p>　　typedef struct</p><p>　　{　char vexs[N];</p><p>　　int arcs[N][N];<

6、;/p><p>　　int vexnum,arcnum;</p><p><b>　　}MGraph;</b></p><p>　　最小生成樹的存儲結構</p><p>　　因為準備采用prime算法，所以存儲結構定義如下：</p><p>　　typedef struct{</p>&

7、lt;p>　　char adjvex;</p><p>　　int lowcost;</p><p><b>　　}close;</b></p><p>　　close closedge[N];</p><p>　　圖形中的結點、邊的數(shù)據(jù)結構。</p><p>　　用兩個數(shù)組,分別存儲邊的兩

8、個頂點。確定坐標、顏色、文字標識。</p><p><b>　　2,功能設計</b></p><p>　　(1) 準備代價文件</p><p>　　也就是要準備圖的節(jié)點，和邊的權值，在這方面要注意文件的格式，以便在今后讀取得到圖的存儲結構的時候比較方便。至于，權值也就是居民之間的距離，是按照一個現(xiàn)實的小區(qū)設計的。</p><

9、;p>　　其中的頂點是設的A B C D……之類的英文字母，代表居民的名字。字母對于構造最小生成樹不是很方便。所以程序當中有一步很重要，就是把字母轉變成數(shù)字。這樣就可以比較方便了。</p><p>　　代價文件中共有11個頂點分別是A B C……一直到K，20條邊,及權值。具體數(shù)據(jù)，在最后的執(zhí)行結果中可以看到。</p><p>　　讀代價文件,得到圖的存儲結構　</p>

10、<p>　　讀代價文件這個過程我做了很久，需要注意的地方有很多。特別是格式，一個空格或回車就能影響讀文件的結果。還有文件的路徑也不能搞錯。</p><p><b>　　計算最小生成樹</b></p><p>　　普里姆算法  假設  WN=(V,{E})  是一個含有  n  個頂點的連通網(wǎng)，TV

11、60;是  WN  上最小生成樹中頂點的集合，TE  是最小生成樹中邊的集合。顯然，在算法執(zhí)行結束時，TV=V，而  TE  是  E  的一個子集。在算法開始執(zhí)行時，TE  為空集，TV  中只有一個頂點，因此，按普里姆算法構造最小生成樹的過程為：在所有“其一個頂點已經(jīng)落在生成樹上，而另一個頂點尚未落在生成樹上”的邊中取一條權值為最小的邊，逐條加

12、在生成樹上，直至生成樹中含有  n-1條邊為止。  </p><p>　　(4) 顯示小生成樹</p><p>　　文本方式：最初用的最小生成樹的顯示方法，只要按次序讀出邊和權值就行了。</p><p>　　圖形方式：這種顯示方法比較復雜，需要用到許多畫圖的函數(shù)——屏幕初始化、頂點位置的初始化、繪頂點函數(shù)、繪邊函數(shù)、代價顯示函數(shù)……</p

13、><p>　　(5) 確定頂點位置的方法</p><p>　　我是利用圓周分布法確定頂點的位置的，我認為用這種方法畫圖比較穩(wěn)定，然后圖也不是很難看。先把一個圓周按照頂點個數(shù)分成幾份，計算出弧度，然后確定坐標。除了用圓周分布法還可以用其他的方法確定頂點的位置，比如說人工指定法（這種方法比較局限，覺得不太好）、多次隨機生成加人工選擇（這也是一種比較好的方法）。</p><p&

14、gt;<b>　　二、程序結構</b></p><p>　?。?）全局變量、符號、函數(shù)的說明</p><p>　　MGraph G；G表示圖。</p><p>　　char xian1[N],xian2[N],str1[N],str2[N] ；</p><p>　　xian1[N],xian2[N]這兩個數(shù)組是存儲原圖邊

15、的兩個頂點的；而str1[N],str2[N]這兩個數(shù)組是存儲最小生成樹的邊的兩個頂點的。</p><p>　　Creat() 這是讀代價文件,得到圖的存儲結構的函數(shù)。</p><p>　　initgraph(&gd,&gm,"D:\\TC\\BGI") 這是畫圖的時候圖形初始化的函數(shù)。</p><p>　　MiniSpanTr

16、ee_PRIM() 這是求最小生成樹的函數(shù)。</p><p>　　output() 這是畫邊的函數(shù)</p><p>　　locatevex() 這是將頂點由字母轉變?yōu)閿?shù)字的函數(shù)。</p><p>　　minimun(close closedge[N],int n) 找權值最小的邊的下標。</p><p><b>　?。?）函數(shù)關系

17、圖</b></p><p><b>　　三、運行結果</b></p><p>　　四、技術討論[運行結果分析、有那些可改進之處]</p><p>　　繪制最小生成樹的辦法?</p><p>　　我是一次性繪制全部最小生成樹的。這種方法比較簡單，因為最小生成樹的邊都存儲在一個數(shù)組中了。</p>&

18、lt;p>　　如果是按次序逐一繪制最小生成樹，這種方法比較復雜，對于我來說太難搞了。</p><p>　　如何計算鋪設煤氣管道的費用?</p><p>　　設其中一個頂點為煤氣供應站。</p><p>　　管道口徑和被供氣的居民區(qū)數(shù)量成正比；單位長度管</p><p>　　道費用和管道口徑成正比。</p><p>

19、;　　例如：為一棟居民樓供應煤氣的管道的單位長度費用是</p><p>　　給k棟居民樓供應煤氣的管道的單位長度費用是</p><p>　　ka。討論最小代價的管道鋪設計劃。</p><p>　　所求出的最小生成樹是否是最費用最小的鋪設方案？</p><p><b>　　四、收獲與體會</b></p>&l

20、t;p>　　編程序，一向都不是我的專長，可以說是我的弱項。這次課程設計是最讓我頭痛的一次事件。</p><p>　　雖然這樣，事情總是要干的。剛拿到這個題目的時候，我覺得這是一個棘手的問題，因為我以前編的程序全都是手工輸入的，從來沒有通過讀文件得到存儲結構，這是一道我要越過的坎，當然，這花了我相當多的時間。在中期檢查的時候，我還沒搞好這一步，文件怎么也讀不正確。終于，成功總是要付出代價的，在我的辛勤勞動下,

21、我成功啦!雖然這只是向前跨了一小步,可是我的這一小步跨得好艱辛啊。經(jīng)過這次歷練，在接下來畫圖著一個難點的時候，我就顯得比較得心應手了。雖然我以前也從來沒畫過圖，可是這次好象不是覺得是天大的難事了。因為再難的事都會有解決的辦法，而且是跟自己付出的努力相關的。</p><p>　　任何工作，毋須預設立場予以排斥，只要以平常心面對它，充分了解它的特性，那么困難自會迎刃而解。沒想到這次課程設計，居然也讓我悟出一些人生的道