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

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

2、明本程序中用到的所有抽象數(shù)據(jù)類型的定義（含數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系、基本操作）；typedef int adjmatrixmaxvertexnummaxvertexnum;struct edgenodeint frontvex;int rearvex;int weight;typedef edgenode adgesetmaxedgenum（2）系統(tǒng)中子程序及功能要求；子程序：將建立的網(wǎng)絡(luò)各個(gè)連接的節(jié)點(diǎn)賦上權(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;子程序：以各個(gè)城市為基礎(chǔ)建立一個(gè)網(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(請(qǐng)輸入第%d個(gè)城市到第%d個(gè)城市的距離：,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個(gè)城市到第%d城市修建一條電纜!n,GTi.frontvex,GTi.rearvex); printf(這樣修建可以使距離最短！n);（3）主程序及各程序模塊（函數(shù)）之間的層次（調(diào)用）關(guān)系。int main() printf(請(qǐng)問您要在幾個(gè)城市間建立網(wǎng)絡(luò)？n請(qǐng)?jiā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è)計(jì)普利姆算法求最小生成樹的主要思想假設(shè)N=（V，E）是連通網(wǎng)，TE是N上最小生成樹中邊的集合。算法從U=u0( u0V),TE=開始，重復(fù)執(zhí)行下述操作：在所有uU,vV-U的邊（u,v）E中找一條代價(jià)最小的邊（u0,v0）并入集合TE，同時(shí)v0并入U(xiǎn)，直至U=V為止。此時(shí)TE中必有n-1條邊，則T=（V，E）為N的最小生成樹。對(duì)于最小生成樹問題：最小生成樹是指在所有生成樹中，邊上權(quán)值之和最小的生成樹，另外最小生成樹也可能是多個(gè)但是他們權(quán)值之和是相等的。5總結(jié)這次試驗(yàn)是關(guān)于最小生成樹的一次試驗(yàn)，這次試驗(yàn)利用光纖這個(gè)

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

8、，在我們?cè)O(shè)計(jì)程序的時(shí)候遇到困難不要急躁，要耐心，細(xì)心認(rèn)真的完成，只有這樣才能得到事半功倍的效果。遇到挫折不要放棄，一步一個(gè)腳印，最終會(huì)得到自己想要的成果。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(請(qǐng)輸入第%d個(gè)城市到第%d個(gè)城市的距離：,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個(gè)城市到第%d城市修建一條電纜!n,GTi.frontvex,GTi.rearvex); printf(這樣修建可以使距離最短！n);int main() printf(請(qǐng)問您要在幾個(gè)城市間建立網(wǎng)絡(luò)？n請(qǐng)?jiā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;程序運(yùn)行結(jié)果：請(qǐng)問您要在幾個(gè)城市間建立網(wǎng)絡(luò)？請(qǐng)?jiān)诖溯斎耄?請(qǐng)輸入第1個(gè)城市到第2個(gè)城市的距離：10請(qǐng)輸