1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 題 目： 管道鋪設(shè)設(shè)計(jì) 專(zhuān) 業(yè)： 軟件072 學(xué) 號(hào)： 04號(hào) 姓 名： 指導(dǎo)老師： 時(shí) 間： 6.297.8 目 錄摘要-3一、問(wèn)題重述、需求分析及研究意義-31.1 問(wèn)題重述-31.2 需求分析-31.3 研究意義-3二、數(shù)據(jù)結(jié)構(gòu)的邏輯設(shè)計(jì)和物理存儲(chǔ)設(shè)計(jì)-42.1 數(shù)據(jù)結(jié)構(gòu)的邏輯設(shè)計(jì)-42.2 數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)設(shè)計(jì) -4三、詳細(xì)設(shè)計(jì)-53.1 普里姆算法分析 -53.1.1 普里姆算法思想-53.1.2 算法過(guò)程描述-53.2 各功能模塊的劃分 -63.3 數(shù)據(jù)結(jié)構(gòu) -73.4 流程描述 -73.4.1 信息輸入模塊-73.4.2 建立最小生成樹(shù)并輸出結(jié)果-83.

2、5 算法時(shí)間復(fù)雜度分析及流程圖-83.5.1 時(shí)間復(fù)雜度 -83.5.2 流程圖-93.6 源程序代碼-93.7 程序最終實(shí)現(xiàn)結(jié)果 -12四、小結(jié)- -14參考文獻(xiàn) -14摘要：N(N10)個(gè)居民區(qū)之間需要鋪設(shè)煤氣管道。假設(shè)任意兩個(gè)居民區(qū)之間都可以 鋪設(shè)煤氣管道，但代價(jià)不同。一、問(wèn)題重述、分析及研究意義1.1 問(wèn)題重述N(N10)個(gè)居民區(qū)之間需要鋪設(shè)煤氣管道。假設(shè)任意兩個(gè)居民區(qū)之間都可以 鋪設(shè)煤氣管道，但代價(jià)不同。問(wèn)題的實(shí)質(zhì)就是編寫(xiě)相應(yīng)程序求解最小生成樹(shù)問(wèn)題。程序要求：事先任意兩居民區(qū)之間鋪設(shè)煤氣管道的代價(jià)存入磁盤(pán)文件中。設(shè)計(jì)一個(gè)最佳方案使得這N個(gè)居民區(qū)之間鋪設(shè)煤氣管道所需代價(jià)最小，并將結(jié)果以

3、圖形方式在屏幕上輸出。1.2 需求分析在N(N10)個(gè)居民區(qū)之間鋪設(shè)煤氣管道所需代價(jià)最小，即求最小生成樹(shù)問(wèn)題。在我們的課程中介紹了兩種求解方法：普里姆（prim）算法和克魯斯卡爾（kruskal）算法。普里姆算法與網(wǎng)的變數(shù)無(wú)關(guān)，時(shí)間復(fù)雜度為O（n2),適宜求解邊稠密的網(wǎng)的最小生成樹(shù)。而克魯斯卡爾算法正好相反，時(shí)間復(fù)雜度為O（eloge）（e為網(wǎng)中邊的數(shù)目），故而該算法適宜求邊稀疏的最小生成樹(shù)。由于在實(shí)際應(yīng)用中，居民區(qū)數(shù)量一般很有限，而任何兩個(gè)居民區(qū)間都可能有連線(xiàn)，即這樣的圖應(yīng)該是邊較為稠密的。因此，我們選擇普里姆算法對(duì)問(wèn)題進(jìn)行求解。1、 建立一個(gè)帶權(quán)無(wú)向圖的鄰接矩陣，然后進(jìn)行深度和廣度優(yōu)先搜索

4、遍歷，并輸出遍歷的結(jié)果序列。最后若此圖是連通圖，輸出該網(wǎng)的一顆最小生成樹(shù)。2、 網(wǎng)中頂點(diǎn)的編號(hào)從0開(kāi)始頂點(diǎn)的信息為字符。3、 按照網(wǎng)的鄰接矩陣定義輸出該矩陣。4、 在非連通圖的情況下要能夠按深度和廣度優(yōu)先搜索遍歷整個(gè)網(wǎng)。5、 用普里姆法構(gòu)造最小生成樹(shù)。在最小生成樹(shù)算法中，應(yīng)判斷該網(wǎng)是否連通，如果非連通，則需輸出提示信息并退出程序。1.3 研究意義實(shí)際生活中最小生成樹(shù)的問(wèn)題具有很大的意義。例如，本文所討論的構(gòu)架居民區(qū)之間鋪設(shè)煤氣管道代價(jià)最小，還有在若干的地區(qū)見(jiàn)鋪設(shè)光纜，等等。最小生成樹(shù)讓許多諸如求造價(jià)最小、最短路徑等最優(yōu)化的現(xiàn)實(shí)問(wèn)題找到了理論依據(jù)，并提供了有效的解決方法。二、數(shù)據(jù)結(jié)構(gòu)的邏輯設(shè)計(jì)和

5、物理存儲(chǔ)設(shè)計(jì)2.1 數(shù)據(jù)結(jié)構(gòu)的邏輯設(shè)計(jì)每個(gè)居民區(qū)可能與其他任何一個(gè)居民區(qū)相連，也即居民區(qū)與居民區(qū)之間是一種多對(duì)多的關(guān)系。把一個(gè)城市抽象成為一個(gè)頂點(diǎn)，居民區(qū)之間的連線(xiàn)抽象為圖中頂點(diǎn)之間的邊，路程作為邊的權(quán)值。那么，結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素（頂點(diǎn)）都可能有任意多個(gè)直接前驅(qū)和直接后繼，即是一種圖結(jié)構(gòu)。當(dāng)然，從居民區(qū)0到居民區(qū)1應(yīng)和從居民區(qū)1到居民區(qū)0是等價(jià)的。因此，我們把該數(shù)據(jù)的邏輯結(jié)構(gòu)定義為無(wú)向圖結(jié)構(gòu)。圖示如下：2.2 數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)設(shè)計(jì) 為了方便圖的各種操作，如該算法當(dāng)中需要判斷某頂點(diǎn)間是否有邊、比較邊的權(quán)值、求頂點(diǎn)的位置等問(wèn)題，而且這是個(gè)邊較為稠密的圖。鑒于此，我們采取鄰接矩陣表示法來(lái)存儲(chǔ)圖結(jié)

6、構(gòu)。如對(duì)上圖采用鄰接矩陣存儲(chǔ)可表示為： B=用鄰接矩陣創(chuàng)建無(wú)向圖的算法：/鄰接矩陣數(shù)據(jù)類(lèi)型描述#define MAX 30 /*最大定點(diǎn)數(shù)*/typedef structelemtype vertexvnum;/* 存放頂點(diǎn)信息,若頂點(diǎn)除編號(hào)外無(wú)其它信息，則無(wú)需數(shù)組*/int matrixvnumvnum;adjmatrix; /求頂點(diǎn)位置函數(shù) int LocateVertex (AdjMatrix *G,VertexData v)int j=ERROR，k; for(k=0;kvexnum;k+)if(G-vexsk=v) j=k;break;return(j);/創(chuàng)建一個(gè)無(wú)向圖#defin

7、e INFINITY 9999 /INFINITY代表一個(gè)無(wú)窮大的數(shù)int CreatUDN(AdjMtrix *G) int i,j,k,weight;VertexData v1,v2; scanf(%d,%d,&G-arcnum,&G-vexnum);/輸入圖的頂點(diǎn)個(gè)數(shù)和邊的條數(shù) for(i=0;ivexnum;i+) /初始化鄰接矩陣 for（j=0;jvexnum;j+) G-arcsij.Adj=INFINITY; for(i=0;ivexnum;i+) scanf(%d,&G-vexsi); /輸入圖的頂點(diǎn) for(k=0;kvexnum;k+) scanf(%d,%d,%d,&i

8、,&j,&weight);G-arcsij.Adj=G-arcsji=weight;/建立邊 reurn （OK）；三、詳細(xì)設(shè)計(jì)3.1 普里姆算法分析3.1.1普里姆算法思想 普里姆方法的思想是：在圖中任取一個(gè)頂點(diǎn)k0作為開(kāi)始點(diǎn)，令U=k0，W=V-U，其中V為圖中所有頂點(diǎn)集，然后找一個(gè)頂點(diǎn)在U中，另一個(gè)頂點(diǎn)在W中的邊中最短的一條，找到后，將該邊作為最小生成樹(shù)的樹(shù)邊保存起來(lái)，并將該邊頂點(diǎn)全部加入U(xiǎn)集合中，并從W中刪去這些頂點(diǎn)，然后重新調(diào)整U中頂點(diǎn)到W中頂點(diǎn)的距離, 使之保持最小，再重復(fù)此過(guò)程，直到W為空集止。3.1.2該算法過(guò)程描述(1)在圖G=(V, E) （V表示頂點(diǎn) ，E表示邊）中，從集

9、合V中任取一個(gè)頂點(diǎn)（例如取頂點(diǎn)k0）放入集合 U中，這時(shí) U=k0，集合T(E)為空。 (2) 從k0出發(fā)尋找與U中頂點(diǎn)相鄰（另一頂點(diǎn)在V中）權(quán)值最小的邊的另一頂點(diǎn)k1，并使k1加入U(xiǎn)。即U=k0,k1 ，同時(shí)將該邊加入集合T(E)中。 (3) 重復(fù)(2)，直到U = V為止。 (4)這時(shí)T(E)中有n-1條邊，T = (U, T(E)就是一棵最小生成樹(shù)。 Prim算法示意圖3.2 各功能模塊的劃分根據(jù)對(duì)模型的功能分析，該管道鋪設(shè)設(shè)計(jì)可以具有以下功能：1 管道鋪設(shè)信息的輸入；2 最小生成樹(shù)信息的輸出；下面我們給出相應(yīng)的功能模塊圖：管道鋪設(shè)設(shè)計(jì)問(wèn)題最小生成樹(shù)問(wèn)題建立最小生成樹(shù)并輸出信息的輸入模塊

10、3.3 數(shù)據(jù)結(jié)構(gòu)areanum 居民區(qū)總數(shù)（頂點(diǎn)總數(shù)）；edgenum 邊的總數(shù)；date20 鄰接矩陣存儲(chǔ)圖結(jié)構(gòu)；s 邊的權(quán)值；short_wayi 居民區(qū)i到到目前生成樹(shù)中所有點(diǎn)集U中某個(gè)居民區(qū)的路程最小值 near_areai U中能使其最小的居民區(qū) 3.4 流程描述3.4.1信息輸入模塊/讀入圖的信息，并將鄰接矩陣輸出void read（）/輸入頂點(diǎn)個(gè)數(shù)和邊的條數(shù)printf（請(qǐng)輸入：頂點(diǎn)數(shù)，邊數(shù)：n);scanf(%d,%d,&areanum,&edgenum);/初始化矩陣各元素值int i,j,k;for(i=0；iareanum;i+)for(j=0;jareanum;j+)d

11、ateij=INFINITY;/讀入邊int from,to,s; printf(輸入邊,格式為i, j, k,表示i到j(luò)的權(quán)值是k :n); for(i = 0; i edgenum; i+) scanf(%d,%d,%d,&from,&to,&ws); datefromto = s; datetofrom = st; /輸出鄰接矩陣 for(i = 0; i areanum; i+) for(j = 0; j areanum; j+) printf(%dt,dateij); printf(n); 3.4.2建立最小生成樹(shù)并輸出結(jié)果void prim(int dateMAXNODE,int

12、areanum,int near_area)/輔助數(shù)組short_way,near_area /short_wayi表示居民區(qū)i到到目前生成樹(shù)中所有點(diǎn)集U中某個(gè)居民區(qū)（點(diǎn)）的路程最小值 /near_cityi表示U中能使其最小的居民區(qū)(點(diǎn)) int short_way areanum; int min; int i,j,k; /0已經(jīng)放入U(xiǎn)中 /初始化short_way 和 near_area for(i = 1; i areanum; i+) short_wayi = date0i; near_areai = 0; short_wayi=0; near_area0 = 0; for(i =

13、1; i areanum; i+)/有n-1條邊要加入生成樹(shù),所以只要循環(huán)n-1次即可 min =INFINITY;/ 求生成樹(shù)外頂點(diǎn)到生成樹(shù)內(nèi)頂點(diǎn)具有最小權(quán)值的邊 j=1;k=1;while(jareanum)/確定當(dāng)前具有最小權(quán)值的邊及位置 if(short_wayj!=0 & short_wayj min) min = short_wayj; k=j; j+; printf(居民區(qū)序號(hào)為%d，居民區(qū)路程（邊的權(quán)值）為%d,k,min);short_wayk=0;for(j=0;jn;j+) if(datekjshort_wayj) short_wayj = datekj; near_ar

14、eaj = k; 3.5 算法時(shí)間復(fù)雜度分析及流程圖3.5.1時(shí)間復(fù)雜度: 信息輸入模塊的時(shí)間復(fù)雜度為o（n2);建立最小生成樹(shù)及輸出的時(shí)間復(fù)雜度為o（n2)。整個(gè)程序時(shí)間復(fù)雜度為o（n2）。3.5.2 流程圖：3.6源程序代碼：#include#define INFINITY 9999void main()/輸入頂點(diǎn)個(gè)數(shù)和邊的條數(shù) /system(color 3e);int date2020;int areanum;int edgenum;printf(請(qǐng)輸入：頂點(diǎn)數(shù)，邊數(shù)：n);scanf(%d,%d,&areanum,&edgenum);/初始化矩陣各元素值int i,j;for(i=0

15、;iareanum;i+)for(j=0;jareanum;j+)dateij=INFINITY;/讀入邊int from,to,m; printf(輸入邊,格式為i, j, k,表示i到j(luò)的權(quán)值是m:n); for(i=0;iedgenum;i+) scanf(%d,%d,%d,&from,&to,&m); datefromto = m; datetofrom = m; /輸出鄰接矩陣 printf(輸出鄰接矩陣為：n); for(i=0;iareanum;i+) for(j=0;jareanum;j+) printf(%dt,dateij); printf(n); /prim();/輔助數(shù)

16、組short_way,near_area /short_wayi表示居民區(qū)i到到目前生成樹(shù)中所有點(diǎn)集U中某個(gè)居民區(qū)（點(diǎn)）的路程最小值 /near_areai表示U中能使其最小的居民區(qū)(點(diǎn)) int short_way20; int near_area20; int min; int k,s,price; /0已經(jīng)放入U(xiǎn)中 /初始化short_way 和 near_area for(i = 1; i areanum; i+) short_wayi = date0i; near_areai = 0; short_wayi=0; near_area0 = 0; s=0; printf(從居民區(qū)0出發(fā)

17、,n); for(i = 1; i areanum; i+)/有n-1條邊要加入生成樹(shù),所以只要循環(huán)n-1次即可 min =INFINITY;/ 求生成樹(shù)外頂點(diǎn)到生成樹(shù)內(nèi)頂點(diǎn)具有最小權(quán)值的邊 j=1;k=1;while(jareanum)/確定當(dāng)前具有最小權(quán)值的邊及位置 if(short_wayj!=0 & short_wayj min) min = short_wayj; k=j; j+; printf(從居民區(qū)%d到居民區(qū)%d，居民區(qū)路程（邊的權(quán)值）為%dn,near_areak,k,min);short_wayk=0;s+=min;for(j=0;jareanum;j+) if(date

18、kjshort_wayj) short_wayj = datekj; near_areaj = k; printf(%d個(gè)居民區(qū)之間鋪設(shè)煤氣管道最小生成樹(shù)的總長(zhǎng)度s為:%dn,areanum,s);printf(請(qǐng)輸入單位長(zhǎng)度的價(jià)格：n);scanf(%d,&price);printf(所以%d個(gè)居民區(qū)之間鋪設(shè)煤氣管道所需最小代價(jià)price為:%dn,areanum,s*price);3.7 程序最終實(shí)現(xiàn)結(jié)果建立圖:970 5 12 56 9 7 1 11 9 13 12 15 84 8 9 10 103 3 9 8 4 6 2 12信息輸入：輸出結(jié)果：建立最小生成樹(shù)：970 5 5 12 6 9 7 1 11 9 13 12 15 84 8 9 10 103 3 9 8 4 6 2 12四、小結(jié)通過(guò)數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)使我們對(duì)所學(xué)知識(shí)有了更好的理解，也增強(qiáng)了大家的動(dòng)手能力。同時(shí)也發(fā)現(xiàn)了自己的很多不足之處，對(duì)知識(shí)的應(yīng)用能力