光纖通信網(wǎng)鋪設(shè)方案設(shè)計

1、數(shù)據(jù)結(jié)構(gòu)實驗報告題 目： 光纖通信網(wǎng)鋪設(shè)方案設(shè)計 班 級： 姓 名： 學(xué) 號： 完成日期： 2012/5/28 1問題描述在n個城市間建設(shè)光纖通信網(wǎng)絡(luò)，要求僅選擇n-1條線路鋪設(shè)光纜，且達(dá)到每個城市都有光纜連通。請用C語言編寫程序，求出以最低經(jīng)濟(jì)代價（光纜總量最短）建設(shè)這個通信網(wǎng)的方案。城市個數(shù)、兩個城市間的距離由學(xué)生自己設(shè)計，存儲結(jié)構(gòu)和實現(xiàn)算法由學(xué)生自己選定并實現(xiàn)。2需求分析（1）輸入的形式和輸入值的范圍； 形式：數(shù)字 范圍：無限（2）輸出的形式；最小生成樹 （3）程序所能達(dá)到的功能。在n個城市間建設(shè)光纖通信網(wǎng)絡(luò)，要求僅選擇n-1條線路鋪設(shè)光纜，且達(dá)到每個城市都有光纜連通。3概要設(shè)計（1）說

2、明本程序中用到的所有抽象數(shù)據(jù)類型的定義（含數(shù)據(jù)對象、數(shù)據(jù)關(guān)系、基本操作）；typedef int adjmatrixmaxvertexnummaxvertexnum;struct edgenodeint frontvex;int rearvex;int weight;typedef edgenode adgesetmaxedgenum（2）系統(tǒng)中子程序及功能要求；子程序：將建立的網(wǎng)絡(luò)各個連接的節(jié)點賦上權(quán)值void insit(adgeset>,int n,adjmatrix GA)for(int i=1;in;i+)GTi.frontvex=1;GTi.rearvex=i+1;GTi.we

3、ight=GA1i+1; 子程序：初始化的無向圖，將每條邊的權(quán)值賦值為無窮void insitadj(adjmatrix &GA) for(int i=1;imaxvertexnum;i+)for(int j=1;jmaxvertexnum;j+)GAij=20000;子程序：以各個城市為基礎(chǔ)建立一個網(wǎng)絡(luò)void setadj(adjmatrix &GA,int n) /建立網(wǎng)絡(luò)for(int i=1;i=n+1;i+)for(int j=i+1;jn+1;j+)printf(請輸入第%d個城市到第%d個城市的距離：,i,j);scanf(%d,&GAij);for(i=1;i=n+1;i+)

4、for(int j=i+1;jn+1;j+)GAji=GAij;子程序：輸出我們所找到的最小生成樹void fun(adjmatrix GA,adgeset>,int n) int i;for(i=1;in;i+)int min=10000,m=i;for(int j=i;jn;j+)if(GTj.weightmin)min=GTj.weight;m=j;edgenode temp=GTi;GTi=GTm;GTm=temp;int k=GTm.rearvex;for(j=i;jn;j+)int t=GTj.rearvex;int w=GAkt;if(wGTj.weight)GTj.weig

5、ht=w;GTj.frontvex=k;void display(adgeset GT,int n)for(int i=1;in;i+)printf(第%d個城市到第%d城市修建一條電纜!n,GTi.frontvex,GTi.rearvex); printf(這樣修建可以使距離最短！n);（3）主程序及各程序模塊（函數(shù)）之間的層次（調(diào)用）關(guān)系。int main() printf(請問您要在幾個城市間建立網(wǎng)絡(luò)？n請在此輸入：);int n; scanf(%d,&n) ;adgeset GT;adjmatrix GA;insitadj(GA);setadj(GA,n);insit(GT,n,GA)

6、;fun(GA,GT,n);display(GT,n);return 0;4詳細(xì)設(shè)計普利姆算法求最小生成樹的主要思想假設(shè)N=（V，E）是連通網(wǎng)，TE是N上最小生成樹中邊的集合。算法從U=u0( u0V),TE=開始，重復(fù)執(zhí)行下述操作：在所有uU,vV-U的邊（u,v）E中找一條代價最小的邊（u0,v0）并入集合TE，同時v0并入U，直至U=V為止。此時TE中必有n-1條邊，則T=（V，E）為N的最小生成樹。對于最小生成樹問題：最小生成樹是指在所有生成樹中，邊上權(quán)值之和最小的生成樹，另外最小生成樹也可能是多個但是他們權(quán)值之和是相等的。5總結(jié)這次試驗是關(guān)于最小生成樹的一次試驗，這次試驗利用光纖這個

7、實際問題，將如何設(shè)計最小生成樹的理論知識應(yīng)用在實踐層面，巧妙地叫理論知識和實際情況結(jié)合起來，對我們有一個很好地鍛煉方法。這次試驗我收獲很多，將老師在上課講解的有關(guān)于最小生成樹的相關(guān)知識很有效的結(jié)合起來了，充分的鍛煉了自己的動手能力。 在本次試驗的學(xué)習(xí)中讓我很清楚的認(rèn)識了利用普利姆和克魯斯卡爾算法求解最小生成樹的算法思想，明白了最小生成樹是怎么樣形成的。我們將我們的城市的空間分布抽象為一個帶有權(quán)值的網(wǎng)絡(luò)為我們利用普利姆算法和克魯斯卡爾算法提供了基礎(chǔ)。在完成此次試驗之后我感觸很深。認(rèn)識到數(shù)據(jù)結(jié)構(gòu)這門課的重要性，在以后的學(xué)習(xí)計算機(jī)方面的課程時我們要注意理論與實踐并行。多多上機(jī)實踐。只有實踐才能出真知

8、，在我們設(shè)計程序的時候遇到困難不要急躁，要耐心，細(xì)心認(rèn)真的完成，只有這樣才能得到事半功倍的效果。遇到挫折不要放棄，一步一個腳印，最終會得到自己想要的成果。6附錄源程序代碼：#include#define maxvertexnum 20 #define maxedgenum 40 typedef int adjmatrixmaxvertexnummaxvertexnum;struct edgenodeint frontvex;int rearvex;int weight;typedef edgenode adgesetmaxedgenum;void insitadj(adjmatrix &GA)

9、;void setadj(adjmatrix &GA,int n);void fun(adjmatrix GA,adgeset >,int n);void display(adgeset GT,int n);void insit(adgeset >,int n,adjmatrix GA);void insit(adgeset>,int n,adjmatrix GA)for(int i=1;in;i+)GTi.frontvex=1;GTi.rearvex=i+1;GTi.weight=GA1i+1; void insitadj(adjmatrix &GA)for(int i=1;im

10、axvertexnum;i+)for(int j=1;jmaxvertexnum;j+)GAij=20000;void setadj(adjmatrix &GA,int n) /建立網(wǎng)絡(luò)for(int i=1;i=n+1;i+)for(int j=i+1;jn+1;j+)printf(請輸入第%d個城市到第%d個城市的距離：,i,j);scanf(%d,&GAij);for(i=1;i=n+1;i+)for(int j=i+1;jn+1;j+)GAji=GAij;void fun(adjmatrix GA,adgeset>,int n) int i;for(i=1;in;i+)int mi

11、n=10000,m=i;for(int j=i;jn;j+)if(GTj.weightmin)min=GTj.weight;m=j;edgenode temp=GTi;GTi=GTm;GTm=temp;int k=GTm.rearvex;for(j=i;jn;j+)int t=GTj.rearvex;int w=GAkt;if(wGTj.weight)GTj.weight=w;GTj.frontvex=k;void display(adgeset GT,int n)for(int i=1;in;i+)printf(第%d個城市到第%d城市修建一條電纜!n,GTi.frontvex,GTi.rearvex); printf(這樣修建可以使距離最短！n);int main() printf(請問您要在幾個城市間建立網(wǎng)絡(luò)？n請在此輸入：);int n; scanf(%d,&n) ;adgeset GT;adjmatrix GA;insitadj(GA);setadj(GA,n);insit(GT,n,GA);fun(GA,GT,n);display(GT,n);return 0;程序運行結(jié)果：請問您要在幾個城市間建立網(wǎng)絡(luò)？請在此輸入：4請輸入第1個城市到第2個城市的距離：10請輸