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

2、（ 1）說明本程序中用到的所有抽象數據類型的定義（含數據對象、數據關系、 基本操作）；typedef int adjmatrixmaxvertexnummaxvertexnum;struct edgenodeint frontvex;int rearvex;int weight;typedef edgenode adgesetmaxedgenum（ 2）系統中子程序及功能要求；子程序：將建立的網絡各個連接的節點賦上權值void insit（adgeset&GT,int n,adjmatrix GA）for（int i=1;i<n;i+）GTi.frontvex=1;GTi.rea

3、rvex=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 n) / 建立網絡for(int i=1;i<=n+1;i+)for(int j=i+1;j<n+1;j+),i,j);printf(" 請輸入第d個城

4、市到第(個城市的距離: 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=GTm;GTm=t

5、emp;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.fro ntvex,GTi.rearvex);printf(" 這樣修建可以使距離最短！ n");(3)主程序及各程序模

6、塊(函數)之間的層次(調用)關系。int main()printf(" 請問您要在幾個城市間建立網絡？ 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)是連通網，TE是N上最小生成樹中邊的集合。算法從U=uO( u0 V),TE=開始，重復執行下述操作：在所有 u U

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

8、 的動手能力。在本次試驗的學習中讓我很清楚的認識了利用普利姆和克魯斯卡爾算法求解 最小生成樹的算法思想，明白了最小生成樹是怎么樣形成的。我們將我們的城市 的空間分布抽象為一個帶有權值的網絡為我們利用普利姆算法和克魯斯卡爾算法 提供了基礎。在完成此次試驗之后我感觸很深。認識到數據結構這門課的重要性，在以后 的學習計算機方面的課程時我們要注意理論與實踐并行。多多上機實踐。只有實 踐才能出真知，在我們設計程序的時候遇到困難不要急躁，要耐心，細心認真的 完成，只有這樣才能得到事半功倍的效果。遇到挫折不要放棄，一步一個腳印，最終會得到自己想要的成果。6附錄源程序代碼：#include<stdio.

9、h>#define maxvertexnum 20#define maxedgenum 40typedef 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

10、 display(adgeset GT,int n);void insit(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;v

11、oid setadj(adjmatrix &GA,int n) / 建立網絡for(int i=1;i<=n+1;i+)for(int j=i+1;j<n+1;j+),i,j);printf("請輸入第d個城市到第(個城市的距離: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

12、,m=i;for(int j=i;j<n;j+)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("第£個城市到第4城市修建一條電纜

13、!n",GTi.fro ntvex,GTi.rearvex);printf(" 這樣修建可以使距離最短！ n");int main()printf(" 請問您要在幾個城市間建立網絡？ 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 請輸入第 1 個城市到第 2 個城市的距離： 10 請輸入第 1 個城市到第 3 個城市的距離： 19 請