1、課 程 設 計 報 告構造可以使n個城市連接的最小生成樹課程名稱：數據結構與算法課程設計院 （系）：信息科學與技術學院 專業班級： 學 號： 姓 名： 指導老師： 目 錄一需求分析31.1問題描述：31.2功能要求：3二概要設計3三詳細設計33.1數據類型定義33.2程序的主要函數43.3克魯斯卡爾算法思想描述43.4克魯斯卡爾算法設計5四測試分析5五心得體會8附錄：程序源代碼8 一、 需求分析1.1問題描述給定一個地區的n個城市間的距離網，用Prim算法或Kruskal算法建立最小生成樹，并計算得到的最小生成樹的代價。1.2功能要求城市間的距離網采用鄰接矩陣表示，鄰接矩陣的存儲結構定義采用課

2、本中給出的定義，若兩個城市之間不存在道路，則將相應邊的權值設為自己定義的無窮大值。 要求在屏幕上顯示得到的最小生成樹中包括了哪些城市間的道路，并顯示得到的最小生成樹的代價。城市間的距離以鄰接矩陣的方式輸入（要求至少6個城市，10條邊）。二、概要設計2.1該程序的主要功能：能實現根據輸入城市的信息可以判斷該城市間的距離網 是否構成最小生成樹，遍歷城市生成最小生成樹，通過計算得到最小生成樹的代價。2.2該城市間的距離網用鄰接矩陣表示。并且把2個城市的看成起點和終點，城市之間的距離看成邊，并以此設計結構體。定義結構體數組，將輸入的矩陣轉化為相對應的結構體來存儲城市與城市直接的關系2.3先用judge

3、()判斷能否生成是否為聯通圖，再用克魯斯卡爾（Kruskal）算法將輸入的矩陣生立最小生成樹，打印出來。創建用鄰接矩陣表示的城市道路網輸入城市數道路權值判斷是否可以連通Krushal算法，并將所到的結果輸出退出三、詳細設計3.1數據類型定義typedef struct node /*構造一個結構體*/int str; /*起點*/int end; /*終點*/int dis;/*距離*/node; 為了用鄰接矩陣表示圖 G ，先是定義二維數組的每一個元素含道路值然后在圖的定義中定義一個此二維數組的結構成員。并且在圖中還定義一個用來存放城市的一維數組及int 型的城市數級道路數。用二維數組的兩個

4、下標表示道路，這兩個下標又在一位數組中對應兩個城市，這樣就建立起了一個城市到城市之間的鄰接矩陣。將該鄰接矩陣轉化為圖示的結構體，用于計算。 3.2程序的主要函數能實現根據輸入城市的信息可以判斷出該城市間的距離網是否構成最小生成樹，遍歷城市生成最小生成樹，通過計算得到最小生成樹的代價主要函數：a) int menu ( ) 菜單函數，給用戶提示信息，讓用戶選擇相應功能。 b) void create ( ) 輸入城市信息函數，將用戶輸入的鄰接矩陣以二維數組的形式存放到內存中，為Krushal( )服務c) void judge ( ) 判斷用戶輸入的鄰接矩陣所轉化的圖是否可以生成最小生成樹d)

5、void find ( ) 判斷當前是否構成回路的函數 e) void Union ( ) 將能構成最小生成樹的邊添加到一個集合 ，f） void Krushal( ) 克魯斯算法求最小生成樹3.3克魯斯卡爾算法思想基本描述： 假設連通圖N=（V，E），則令最小生成樹的初始狀態為只有n 頂點而無邊的非連通圖T=(V, )，圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價最小的邊。以此類推，直至T中所有頂點都在同一個連通分量上為止3.4克魯斯卡爾算法設計a. 設置計數器E，初值為0，記錄已選中的邊數。

6、將所有邊從小到大排序，存于p 中。b. 從p 中選擇一條權值最小的邊，檢查其加入到最小生成樹中是否會構成回路，若是，則此邊不加入生成樹；否則，加入到生成樹中，計數器E累加1。c. 從E中刪除此最小邊，轉b繼續執行，直到k=n-1, 算法結束 d. 判斷是否構成回路的方法： 設置集合S，其中存放已加入到生成樹中的邊所連接的頂點集合，當一條新的邊要加入到生成樹中時，檢查此邊所連接的兩個頂點是否都已經在S中，若是，則表示構成回路，否則，若有一個頂點不在S中 或者兩個頂點都不在S中，則不夠成回路。四、測試分析以一個6個城市、10條邊的網絡圖為例進行測試1系統界面：2輸入信息 設置兩頂點之間無邊時權值為

7、100003數據處理(1)、判斷能否構成最小生成樹（2）、遍歷所有城市生成最小生成數 （3）、退出五、體會心得通過本周的課程設計，終于圓滿完成了課程設計的任務，我也有不少收獲。既鞏固和加深了對數據結構的理解，認識到數據結構是計算機專業一門重要的專業技術基礎課程，還提高了我綜合運用本課程所學知識的能力。而且，并不是單純的看看教材就能解決我們的實際問題，所以還要去查找各種我們所需要的資料，所以這次課程設計也培養了我選用參考書，查閱手冊及文獻資料的能力。要完成一個課程設計的課題并不是一次就能編譯成功的，中間會出現很多的大問題小問題，改錯是個很繁瑣的問題。通過這次課程設計培養了我獨立思考，深入研究，分

8、析問題，解決問題的能力。參 考 文 獻1.嚴蔚敏，吳偉民. 數據結構（C語言版）. 清華大學出版社，2007 2.譚浩強，張基溫. C語言程序設計教程（第三版）北京：高等教育出版社，2006 3.陳維新，林小茶. C+面向對象程序設計教程. 北京：清華大學出版社，2004 4.蘇仕華等.數據結構課程設計. 北京： 機械工業出版社，2005附錄：程序源碼#include <stdio.h>#include <string.h>#include <stdlib.h>#define max 20#define MAX_LNT 10typedef struct no

9、de /*構造一個結構體，兩個城市可以看成起點和終點，之間的道路可以看成一個邊*/int str; /*起點*/int end; /*終點*/int dis;/*距離*/node;node pmax,temp;/*p記錄城市信息*/int pre100,rank100;/*用于判斷是否構成回路*/int n=0,arcsMAX_LNTMAX_LNT;/*n表示城市個數，arcs記錄城市間權值*/int menu( ) /*菜單函數*/ int m;printf(" 求最小生成樹n");printf(" _nn");printf(" 1 輸入城市

10、之間的信息n");printf(" 2 判斷是否能構成一個最小生成樹n");printf(" 3 遍歷所有城市生成最小生成樹n");printf(" 4 退出n");printf(" _nn");printf(" 請輸入所選功能1-4n");scanf("%d",&m);return m; /*下面三個函數作用是檢驗當一條邊添加進去，是否會產生回路*/void set(int x)/*初始化*/ prex = x;rankx = 0; int find(in

11、t x)/*找到這個點的祖先*/ if(x != prex) prex = find(prex);return prex; void Union(int x,int y)/*將這兩個添加到一個集合里去*/ x = find(x);y = find(y);if(rankx >= ranky) prey = x; rankx +; else prey = x; void Kruskal( ) int ans = 0,i,j,k = 0;/*ans用來記錄生成最小樹的權總值*/int index;int count = 0;/*記錄打印邊的條數*/for(i = 1;i <= n;i +

12、) /*初始化數組prex,rankx*/set(i);for(i = 1;i <= n;i +)for(j = i + 1;j <= n;j +)p+k.str = i;pk.end = j;pk.dis = arcsij; /*先把所有城市之間的路段看成一個邊*/for(i=1;i<=k;i+)/*把所有的邊按從小到大進行排序*/index=i;for(j=i+1;j<=k;j+) if(pj.dis <pindex.dis) index=j;temp=pindex;pindex=pi;pi=temp;for(i = 1;i <= k;i +)if(fi

13、nd(pi.str) != find(pi.end)/*如果這兩點連接在一起不構成一個回路，則執行下面操作*/ printf("t第%d條路段為：%d-%d,權值為%dn",+ count,pi.str,pi.end,pi.dis);/*將這條邊的起點、終點打印出來*/ans += pi.dis;/*說明這條路段要用*/Union(pi.str,pi.end); printf("t遍歷所有城市得到最小生成樹的代價為: %dnn",ans);void create( )/*輸入城市信息*/int i,j;printf("請輸入城市的個數:n&qu

14、ot;);scanf("%d",&n); printf("輸入%d個城市的鄰接矩陣:n",n);for(i = 1;i <= n;i +)for(j = 1;j <= n;j +)scanf("%d",&arcsij);void display( )/*顯示生成的最小生成樹*/if(n = 0)printf("這里沒有城市之間的信息n");return; printf("遍歷所有城市得到最小生成樹為：nnn"); Kruskal( );void judge( )/*判

15、斷是否能夠生成最小生成樹*/ int close100,low100,i,j,ans = 0;/*closej表示離j最近的頂點，lowj表示離j最短的距離*/ int use100; use1 = 1; for(i = 2;i <= n;i +) lowi = arcs1i; /*初始化*/ closei = 1; usei = 0; for(i = 1;i < n;i +) int min = 100000000,k = 0; for(j = 2;j <= n;j +) if(usej = 0 && min > lowj)/*找到最小的low值，并記錄*/min = lowj;k = j; for(j = 2;j <= n;j +) if(usej = 0 && lowj > arcskj)lowj = arcskj; /*修改low值和close值*/ closej = k; ans += arcsclosekk; if(ans >= 100000000) printf(&quo