光纖通信網(wǎng)鋪設方案設計(共10頁)

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

2、纜連通。3概要設計（1）說明本程序中用到的所有抽象數(shù)據(jù)類型的定義（含數(shù)據(jù)對象、數(shù)據(jù)關系、基本操作）；typedef int adjmatrixmaxvertexnummaxvertexnum;struct edgenodeint frontvex;int rearvex;int weight;typedef edgenode adgesetmaxedgenum（2）系統(tǒng)中子程序及功能要求；子程序：將建立的網(wǎng)絡各個連接的節(jié)點賦上權值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; 子程序：初始化的無向圖，將每條邊的權值賦值為無窮void insitadj(adjmatrix &GA) for(int i=1;i<maxvertexnum;i+)for(int j=1;j<maxvertexnum;j+)GAij=20000;子程序：以各個城市為基礎建立一個網(wǎng)絡void setadj(adjmatrix &GA,int n) /建立網(wǎng)絡for(int i=1;i<=n+1;i+)for(int j=i+1;j<n+1;j+)printf("請輸入第%d個城

4、市到第%d個城市的距離：",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個城市到第%d城市修建一條電纜!n",GTi.frontvex,GTi.rearvex); printf("這樣修建可以使距離最短！n");（3）主程序及各程序模塊（函數(shù)）之間的層次（

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

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

8、姆和克魯斯卡爾算法求解最小生成樹的算法思想，明白了最小生成樹是怎么樣形成的。我們將我們的城市的空間分布抽象為一個帶有權值的網(wǎng)絡為我們利用普利姆算法和克魯斯卡爾算法提供了基礎。在完成此次試驗之后我感觸很深。認識到數(shù)據(jù)結構這門課的重要性，在以后的學習計算機方面的課程時我們要注意理論與實踐并行。多多上機實踐。只有實踐才能出真知，在我們設計程序的時候遇到困難不要急躁，要耐心，細心認真的完成，只有這樣才能得到事半功倍的效果。遇到挫折不要放棄，一步一個腳印，最終會得到自己想要的成果。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)絡for(int i=1;i<=n+1;i+)for(int j=i+1;j<n+1;j+)printf("請輸入第%d個城市到第%d個城市的距離：",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個城市到第%d城市修建一條電纜!n",GTi.frontvex,GTi.rearvex); printf("這樣修建可以使距離最短！n");int main() printf("請問您要在幾個城市間建立網(wǎng)絡？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;程序運行結果：請問您要在幾個城市間建立網(wǎng)絡？請在此輸入：4請輸入第1個城市到第2個城