課程設(shè)計(jì)報(bào)告--管道鋪設(shè)施工的最佳方案選擇

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

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

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

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

5、vi的信息。因此，圖的鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義如下：</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>　　最小生成樹(shù)的存儲(chǔ)結(jié)構(gòu)</p><p>　　因?yàn)闇?zhǔn)備采用prime算法，所以存儲(chǔ)結(jié)構(gòu)定義如下：</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>　　圖形中的結(jié)點(diǎn)、邊的數(shù)據(jù)結(jié)構(gòu)。</p><p>　　用兩個(gè)數(shù)組,分別存儲(chǔ)邊的兩

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

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

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

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

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

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

14、gt;<b>　　二、程序結(jié)構(gòu)</b></p><p>　　（1）全局變量、符號(hào)、函數(shù)的說(shuō)明</p><p>　　MGraph G；G表示圖。</p><p>　　char xian1[N],xian2[N],str1[N],str2[N] ；</p><p>　　xian1[N],xian2[N]這兩個(gè)數(shù)組是存儲(chǔ)原圖邊

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

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

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

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

19、;　　例如：為一棟居民樓供應(yīng)煤氣的管道的單位長(zhǎng)度費(fèi)用是</p><p>　　給k棟居民樓供應(yīng)煤氣的管道的單位長(zhǎng)度費(fèi)用是</p><p>　　ka。討論最小代價(jià)的管道鋪設(shè)計(jì)劃。</p><p>　　所求出的最小生成樹(shù)是否是最費(fèi)用最小的鋪設(shè)方案？</p><p><b>　　四、收獲與體會(huì)</b></p>&l

20、t;p>　　編程序，一向都不是我的專長(zhǎng)，可以說(shuō)是我的弱項(xiàng)。這次課程設(shè)計(jì)是最讓我頭痛的一次事件。</p><p>　　雖然這樣，事情總是要干的。剛拿到這個(gè)題目的時(shí)候，我覺(jué)得這是一個(gè)棘手的問(wèn)題，因?yàn)槲乙郧熬幍某绦蛉际鞘止ぽ斎氲?，從?lái)沒(méi)有通過(guò)讀文件得到存儲(chǔ)結(jié)構(gòu)，這是一道我要越過(guò)的坎，當(dāng)然，這花了我相當(dāng)多的時(shí)間。在中期檢查的時(shí)候，我還沒(méi)搞好這一步，文件怎么也讀不正確。終于，成功總是要付出代價(jià)的，在我的辛勤勞動(dòng)下,

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