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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告題 目： 光纖通信網(wǎng)鋪設(shè)方案設(shè)計(jì) 班 級(jí)： 姓 名： 學(xué) 號(hào)： 完成日期： 2012/5/28 1問(wèn)題描述在n個(gè)城市間建設(shè)光纖通信網(wǎng)絡(luò)，要求僅選擇n-1條線路鋪設(shè)光纜，且達(dá)到每個(gè)城市都有光纜連通。請(qǐng)用C語(yǔ)言編寫程序，求出以最低經(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ù)字 范圍：無(wú)限（2）輸出的形式；最小生成樹 （3）程序所能達(dá)到的功能。在n個(gè)城市間建設(shè)光纖通信網(wǎng)絡(luò)，要求僅選擇n-1條線路鋪設(shè)光纜，且達(dá)到每個(gè)城市都有光

2、纜連通。3概要設(shè)計(jì)（1）說(shuō)明本程序中用到的所有抽象數(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&GT,int n,adjmatrix GA)for(int i=1;i<n;i+)GTi.frontvex=1;G

3、Ti.rearvex=i+1;GTi.weight=GA1i+1; 子程序：初始化的無(wú)向圖，將每條邊的權(quán)值賦值為無(wú)窮void insitadj(adjmatrix &GA) for(int i=1;i<maxvertexnum;i+)for(int j=1;j<maxvertexnum;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;j<n+1;j+)printf("請(qǐng)輸入第%d個(gè)城

4、市到第%d個(gè)城市的距離：",i,j);scanf("%d",&GAij);for(i=1;i<=n+1;i+)for(int j=i+1;j<n+1;j+)GAji=GAij;子程序：輸出我們所找到的最小生成樹void fun(adjmatrix GA,adgeset&GT,int n) int i;for(i=1;i<n;i+)int min=10000,m=i;for(int j=i;j<n;j+)if(GTj.weight<min)min=GTj.weight;m=j;edgenode temp=GTi;GTi=

5、GTm;GTm=temp;int k=GTm.rearvex;for(j=i;j<n;j+)int t=GTj.rearvex;int w=GAkt;if(w<GTj.weight)GTj.weight=w;GTj.frontvex=k;void display(adgeset GT,int n)for(int i=1;i<n;i+)printf("第%d個(gè)城市到第%d城市修建一條電纜!n",GTi.frontvex,GTi.rearvex); printf("這樣修建可以使距離最短！n");（3）主程序及各程序模塊（函數(shù)）之間的層次（

6、調(diào)用）關(guān)系。int main() printf("請(qǐng)問(wèn)您要在幾個(gè)城市間建立網(wǎng)絡(luò)？n請(qǐng)?jiān)诖溯斎耄?quot;);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;4詳細(xì)設(shè)計(jì)普利姆算法求最小生成樹的主要思想假設(shè)N=（V，E）是連通網(wǎng)，TE是N上最小生成樹中邊的集合。算法從U=u0( u0V),TE=開始，重復(fù)執(zhí)行下述操作：在所有uU,vV-U的邊（u,v）E中找一條

7、代價(jià)最小的邊（u0,v0）并入集合TE，同時(shí)v0并入U(xiǎn)，直至U=V為止。此時(shí)TE中必有n-1條邊，則T=（V，E）為N的最小生成樹。對(duì)于最小生成樹問(wèn)題：最小生成樹是指在所有生成樹中，邊上權(quán)值之和最小的生成樹，另外最小生成樹也可能是多個(gè)但是他們權(quán)值之和是相等的。5總結(jié)這次試驗(yàn)是關(guān)于最小生成樹的一次試驗(yàn)，這次試驗(yàn)利用光纖這個(gè)實(shí)際問(wèn)題，將如何設(shè)計(jì)最小生成樹的理論知識(shí)應(yīng)用在實(shí)踐層面，巧妙地叫理論知識(shí)和實(shí)際情況結(jié)合起來(lái)，對(duì)我們有一個(gè)很好地鍛煉方法。這次試驗(yàn)我收獲很多，將老師在上課講解的有關(guān)于最小生成樹的相關(guān)知識(shí)很有效的結(jié)合起來(lái)了，充分的鍛煉了自己的動(dòng)手能力。 在本次試驗(yàn)的學(xué)習(xí)中讓我很清楚的認(rèn)識(shí)了利用普利

8、姆和克魯斯卡爾算法求解最小生成樹的算法思想，明白了最小生成樹是怎么樣形成的。我們將我們的城市的空間分布抽象為一個(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í)踐才能出真知，在我們?cè)O(shè)計(jì)程序的時(shí)候遇到困難不要急躁，要耐心，細(xì)心認(rèn)真的完成，只有這樣才能得到事半功倍的效果。遇到挫折不要放棄，一步一個(gè)腳印，最終會(huì)得到自己想要的成果。6附錄源程序代碼：#include<stdio.h>#define maxvertexnum 20 #defin

9、e maxedgenum 40 typedef int adjmatrixmaxvertexnummaxvertexnum;struct edgenodeint frontvex;int rearvex;int weight;typedef edgenode adgesetmaxedgenum;void insitadj(adjmatrix &GA);void setadj(adjmatrix &GA,int n);void fun(adjmatrix GA,adgeset &GT,int n);void display(adgeset GT,int n);void i

10、nsit(adgeset &GT,int n,adjmatrix GA);void insit(adgeset&GT,int n,adjmatrix GA)for(int i=1;i<n;i+)GTi.frontvex=1;GTi.rearvex=i+1;GTi.weight=GA1i+1; void insitadj(adjmatrix &GA)for(int i=1;i<maxvertexnum;i+)for(int j=1;j<maxvertexnum;j+)GAij=20000;void setadj(adjmatrix &GA,int

11、 n) /建立網(wǎng)絡(luò)for(int i=1;i<=n+1;i+)for(int j=i+1;j<n+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;j<n+1;j+)GAji=GAij;void fun(adjmatrix GA,adgeset&GT,int n) int i;for(i=1;i<n;i+)int min=10000,m=i;for(int j=i;j<n;j

12、+)if(GTj.weight<min)min=GTj.weight;m=j;edgenode temp=GTi;GTi=GTm;GTm=temp;int k=GTm.rearvex;for(j=i;j<n;j+)int t=GTj.rearvex;int w=GAkt;if(w<GTj.weight)GTj.weight=w;GTj.frontvex=k;void display(adgeset GT,int n)for(int i=1;i<n;i+)printf("第%d個(gè)城市到第%d城市修建一條電纜!n",GTi.frontvex,GTi.rearvex); printf("這樣修建可以使距離最短！n");int main() printf("請(qǐng)問(wèn)您要在幾個(gè)城市間建立網(wǎng)絡(luò)？n請(qǐng)?jiān)诖溯斎耄?quot;);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)問(wèn)您要在幾個(gè)城市間建立網(wǎng)絡(luò)？請(qǐng)?jiān)诖溯斎耄?請(qǐng)輸入第1個(gè)城市到第2個(gè)城