數據構造課程設計說明書學院：信息科學與工程學院班級：計算機11-2完成人：姓名：學號：01050220姓名：學號：01050221指導教師：山東科技大學12課程設計任務書一、課程設計題目：構造能夠使n個都市連接的最小生成樹二、課程設計應解決的重要問題：（1）鄰接矩陣的構造及其存儲（2）判斷與否能夠生成最小生成樹（3）克魯斯算法的設計（4）運用克魯斯算法構造最小生成樹時與否產生回路的判斷（5）界面的設計三、任務發出日期：-11-28課程設計完畢日期：-12

小組分工闡明小組編號35題目：構造可使n個都市連接的最小生成樹小組分工狀況：王露：算法設計，voidKruskal()函數，voidset()函數，voidfind()函數，voidUnion()函數王煒程：voidcreat()函數，voidjudge()函數，intmain()函數；intmenu()函數，voiddisplay()函數 組長簽字：年月日指導教師對課程設計的評價成績：指導教師簽字：年月日

目錄重要問題------------------------------------------------------------------5基本規定------------------------------------------------------------------5算法基本思想描述------------------------------------------------------5具體設計------------------------------------------------------------------51、數據構造的設計-----------------------------------------5<1>存儲構造-------------------------------------------------------5<2>圖的表達--------------------------------------------------------62、算法的設計---------------------------------------------6<1>克魯斯卡爾算法設計----------------------------------------------6<2>避免不能構成最小生成樹的圖--------------------------------------6<3>模塊構造及功效--------------------------------------------------7<4>重要模塊算法描述------------------------------------------------7五、源程序清單-----------------------------------------------------------------9六、測試數據及測試成果-----------------------------------------------------91、開始畫面---------------------------------------------------------92、輸入信息---------------------------------------------------------103、數據解決---------------------------------------------------------10（1）判斷能否構成最小生成樹---------------------------------------10（2）遍歷全部的最小生成樹-----------------------------------------10（3）退出---------------------------------------------------------11七、課程設計總結--------------------------------------------------------------11八、附錄--------------------------------------------------------------------------------11參考書目--------------------------------------------------------------------------15構造能夠使n個都市連接的最小生成樹一、重要問題給定一種地區的n個都市間的距離網，用Prim算法或Kruskal算法建立最小生成樹，并計算得到的最小生成樹的代價。二、基本規定（1）都市間的距離網采用鄰接矩陣表達，鄰接矩陣的存儲構造定義采用課本中給出的定義，若兩個都市之間不存在道路，則將對應邊的權值設為自己定義的無窮大值。規定在屏幕上顯示得到的最小生成樹中涉及了哪些都市間的道路，并顯示得到的最小生成樹的代價。（2）表達都市間距離網的鄰接矩陣（規定最少6個都市，10條邊）（3）最小生成樹中涉及的邊及其權值，并顯示得到的最小生成樹的代價。三、算法基本思想描述Kruskal算法思想基本描述：假設連通圖N=（V，{E}），則令最小生成樹的初始狀態為只有n個頂點而無邊的非連通圖T=(V,{})，圖中每個頂點自成一種連通分量。在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價最小的邊。以這類推，直至T中全部頂點都在同一種連通分量上為止。四、具體設計1、數據構造的設計<1>存儲構造鄰接矩陣存儲辦法（數組存儲辦法），運用兩個數組來存儲一種圖，其構造原理比較簡樸。對于含有n個頂點的圖G=(V,E),定義一種含有n個元素的一維數組VERTEX[0..n-1]，將圖中頂點的數據信息分別存入該數組的一種數組元素中。另外，定義一種二維數組A[0..n-1][0..n-1],該二維數組普通被稱為鄰接矩陣。若以頂點在VERTEX數組中的下標來代表一種頂點，則鄰接矩陣中元素A[i][j]寄存頂點i到頂點j之間的關系信息，有1 當頂點i與頂點j之間有邊時A[i][j]=0 當頂點i與頂點j之間無邊時對于網絡，有當頂點i與頂點j之間有邊時，且邊上的權值為時A[i][j]= 當頂點i與頂點j之間無邊時<2>圖的表達用n表達都市的個數，st表達起始都市，ed表達終點都市，dis表達兩都市間的距離。下面是構成該構造體的源代碼：typedefstructnode { intst;/*起點*/ inted;/*終點*/ intdis;/*距離*/ }node;nodep[]；/*p[]數組用來儲存都市和都市間的信息*/2、算法的設計<1>克魯斯卡爾算法設計a.設立計數器E，初值為0，統計已選中的邊數。將全部邊從小到大排序，存于p[]中。b.從p[]中選擇一條權值最小的邊，檢查其加入到最小生成樹中與否會構成回路，若是，則此邊不加入生成樹；否則，加入到生成樹中，計數器E累加1。c.從E中刪除此最小邊，轉b繼續執行，直到k=n-1,算法結束d.判斷與否構成回路的辦法：

設立集合S，其中寄存已加入到生成樹中的邊所連接的頂點集合，當一條新的邊要加入到生成樹中時，檢查此邊所連接的兩個頂點與否都已經在S中，若是，則表達構成回路，否則，若有一種頂點不在S中或者兩個頂點都不在S中，則不夠成回路。<2>避免不能構成最小生成樹的圖為避免輸入的圖構成的不是連通圖，設計了judge()函數來判斷輸入數據構成的與否為連通圖，此函數的重要算法是源于普里姆算法，通過改編，形成了新的函數。<3>模塊構造及功效主程序主程序輸入都市信息退出初始化判斷與否為連通圖求最小生成樹判斷與否構成回路將能夠最小生成樹的邊集合打印輸出最小生成樹及代價打印輸出最小生成樹及代價intmain() //主程序intmenu() //菜單函數voidcreate() //輸入都市信息函數voidjudge() //判斷與否能夠生成最小生成樹函數voiddisplay()//打印輸出voidset()//初始化pre[],rank[]函數voidfind（）//判斷與否構成回路函數voidUnion()//將能構成最小生成樹的邊添加到一種集合voidKrushal()//克魯斯算法求最小生成樹<4>重要模塊算法描述Krushal算法描述：/*下面三個函數作用是檢查當一條邊添加進去，與否會產生回路*/voidset(intx)/*初始化*/{ pre[x]=x; rank[x]=0;}intfind(intx)/*找到這個點的祖先*/{ if(x!=pre[x])pre[x]=find(pre[x]); returnpre[x];}voidUnion(intx,inty)/*將這兩個添加到一種集合里去*/{ x=find(x); y=find(y); if(rank[x]>=rank[y]) { pre[y]=x; rank[x]++;} elsepre[y]=x; }voidKruskal() { intans=0,i,j,k=0; /*ans用來統計生成最小樹的權總值*/ intindex; intcount=0; /*統計打印邊的條數*/ for(i=1;i<=n;i++)/*初始化數組pre[x],rank[x]*/ set(i); for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { p[++k].st=i; p[k].ed=j; p[k].dis=a[i][j];/*先把全部都市之間的路段當作一種邊*/ } } for(i=1;i<=k;i++) /*把全部的邊按從小到大進行排序*/ { index=i; for(j=i+1;j<=k;j++)if(p[j].dis<p[index].dis)index=j; temp=p[index]; p[index]=p[i]; p[i]=temp; } for(i=1;i<=k;i++) { if(find(p[i].st)!=find(p[i].ed))/*如果這兩點連接在一起不構成一種回路，則執行下面操作*/ { printf("\t第%d條路段為：%d--%d,權值為%d\n",++count,p[i].st,p[i].ed,p[i].dis);/*將這條邊的起點、終點打印出來*/ ans+=p[i].dis; /*闡明這條路段要用*/ Union(p[i].st,p[i].ed); } } printf("\t遍歷全部都市得到最小生成樹的代價為:%d\n\n",ans); }五、源程序清單（詳見附錄）六、測試數據及測試成果11以一種6個都市、10條邊的網絡圖為例進行測試11 161120 11 51119 611221491118網絡圖GE=鄰接矩陣1、開始畫面2、輸入信息設立兩頂點之間無邊時∞權值為10000003、數據解決(1)、判斷能否構成最小生成樹（2）、遍歷全部都市生成最小生成數21 16 2163 11 563 654 1854生成的最小生成樹（3）、退出七、課程設計總結通過最小生成樹的學習，我學會了樹的多個存儲構造和遍歷辦法，最小生成樹的設計能夠應用于我們生活中。我們能夠把生活中碰到的實際問題轉化為一種算法問題來進行解決。八、附錄源程序：#include<stdio.h>#include<string.h>#include<stdlib.h>typedefstructnode/*構造一種構造體，兩個都市能夠當作起點和終點，之間的道路能夠當作一種邊*/{ intst;/*起點*/ inted;/*終點*/ intdis;/*距離*/}node;nodep[1000],temp; /*p統計都市信息*/intpre[1000],rank[1000];/*用于判斷與否構成回路*/intn=0,a[100][100];/*n表達都市個數，a[][]統計都市間權值*/intmenu()/*菜單函數*/{ intm; printf("求最小生成樹\n"); printf("________________________________\n\n"); printf("1輸入都市之間的信息\n"); printf("2判斷與否能構成一種最小生成樹\n"); printf("3遍歷全部都市生成最小生成樹\n"); printf("4退出\n"); printf("________________________________\n\n"); printf("請輸入所選功效--4\n"); scanf("%d",&m); returnm;}/*下面三個函數作用是檢查當一條邊添加進去，與否會產生回路*/voidset(intx)/*初始化*/{ pre[x]=x;}intfind(intx)/*找到這個點的祖先*/{ if(x!=pre[x])pre[x]=find(pre[x]); returnpre[x];}voidUnion(intx,inty)/*將這兩個添加到一種集合里去*/{ x=find(x); y=find(y);pre[y]=x;}voidKruskal() { intans=0,i,j,k=0; /*ans用來統計生成最小樹的權總值*/ intindex; intcount=0; /*統計打印邊的條數*/ for(i=1;i<=n;i++)/*初始化數組pre[x],rank[x]*/ set(i); for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { p[++k].st=i; p[k].ed=j; p[k].dis=a[i][j];/*先把全部都市之間的路段當作一種邊*/ } } for(i=1;i<=k;i++) /*把全部的邊按從小到大進行排序*/ { index=i; for(j=i+1;j<=k;j++)if(p[j].dis<p[index].dis)index=j; temp=p[index]; p[index]=p[i]; p[i]=temp; } for(i=1;i<=k;i++) { if(find(p[i].st)!=find(p[i].ed))/*如果這兩點連接在一起不構成一種回路，則執行下面操作*/ { printf("\t第%d條路段為：%d--%d,權值為%d\n",++count,p[i].st,p[i].ed,p[i].dis);/*將這條邊的起點、終點打印出來*/ ans+=p[i].dis; /*闡明這條路段要用*/ Union(p[i].st,p[i].ed); } } printf("\t遍歷全部都市得到最小生成樹的代價為:%d\n\n",ans); }voidcreate() /*輸入都市信息*/ { inti,j; if(n!=0) { charstr[100]; printf("與否要擬定輸入新的都市之間的信息?(y/n)?\n"); scanf("%s",str); if(strcmp(str,"n")==0) return; } printf("請輸入都市的個數:\n"); scanf("%d",&n); printf("輸入%d個都市的鄰接矩陣:\n",n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) scanf("%d",&a[i][j]); } }voiddisplay() /*顯示生成的最小生成樹*/ { if(n==0) { printf("這里沒有都市之間的信息\n"); return; } printf("遍歷全部都市得到最小生成樹為：\n\n\n"); Kruskal(); }voidjudge()/*判斷與否能夠生成最小生成樹*/ { intclose[100],low[100],i,j,ans=0;/*close[j]表達離j近來的頂點，low[j]表達離j最短的距離*/ intuse[100]; use[1]=1; for(i=2;i<=n;i++) {low[i]=a[1][i];/*初始化*/close[i]=1;use[i]=0;