1、目 錄1 問題描述12 需求分析13 概要設(shè)計131抽象數(shù)據(jù)類型定義132模塊劃分24 詳細設(shè)計341數(shù)據(jù)類型的定義342主要模塊的算法描述35 測試分析56 課程設(shè)計總結(jié)6參考文獻7附錄（源程序清單）81 問題描述在n個城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟的架設(shè)方法。存儲結(jié)構(gòu)采用多種。求解算法多種。2 需求分析1. 要在n個城市間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條線路即可，建立的最小生成樹即能實現(xiàn)付出最低的經(jīng)濟代價。2. 程序利用的是克魯斯卡爾算法或prim算法求網(wǎng)的最小生成樹。3. 輸出結(jié)果為文本形式的生成樹和他們之間的權(quán)值。4. 演示程序以用戶和計算機對話的形式進行，即在計算機終端

2、中顯示提示信息之后，有用戶自行選擇下一步命令，相應(yīng)輸入數(shù)據(jù)和運算結(jié)果在其后顯示。3 概要設(shè)計31抽象數(shù)據(jù)類型定義ADT Graph數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。數(shù)據(jù)關(guān)系R：R=VR VR=<v,w>|v,wV且P(v,w)，<v,w>表示從v到w的弧，謂詞P(v,w)定義了弧<v,w>的意義或信息基本操作： CreateGraph( &G, V, VR ) 初始條件：V是圖的頂點集，VR是圖中弧的集合。操作結(jié)果：按V和VR的定義構(gòu)造圖G。DestroyGraph( &G ) 初始條件：圖G存在。 操作結(jié)果：銷毀圖G

3、。LocateVex( G, u ) 初始條件：圖G存在，u和G中頂點有相同特征。 操作結(jié)果：若G中存在頂點u，則返回該頂點在圖中位置；否則返回其它信息。GetVex( G, v ) 初始條件：圖G存在，v是G中某個頂點。 操作結(jié)果：返回v的值。PutVex( &G, v, value ) 初始條件：圖G存在，v是G中某個頂點。 操作結(jié)果：對v賦值value。FirstAdjVex( G, v ) 初始條件：圖G存在，v是G中某個頂點。 操作結(jié)果：返回v的第一個鄰接頂點。若頂點在G中沒有鄰接頂點，則返回“空”。NextAdjVex( G, v, w ) 初始條件：圖G存在，v是G中某個

4、頂點，w是v的鄰接頂點。 操作結(jié)果：返回v的（相對于w的）下一個鄰接頂點。若w是v的最后一個鄰接點，則返回“空”。InsertVex( &G, v ) 初始條件：圖G存在，v和圖中頂點有相同特征。 操作結(jié)果：在圖G中增添新頂點v。DeleteVex( &G, v ) 初始條件：圖G存在，v是G中某個頂點。 操作結(jié)果：刪除G中頂點v及其相關(guān)的弧。InsertArc( &G, v, w ) 初始條件：圖G存在，v和w是G中兩個頂點。 操作結(jié)果：在G中增添弧<v,w>，若G是無向的，則還增添對稱弧<v,w>。DeleteArc( &G, v,

5、w ) 初始條件：圖G存在，v和w是G中兩個頂點。 操作結(jié)果：在G中刪除弧<v,w>，若G是無向的，則還刪除對稱弧<v,w>。DFSTraverse( G, Visit() ) 初始條件：圖G存在，Visit是頂點的應(yīng)用函數(shù)。 操作結(jié)果：對圖進行深度優(yōu)先遍歷。在遍歷過程中對每個頂點調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。BFSTraverse( G, Visit() ) 初始條件：圖G存在，Visit是頂點的應(yīng)用函數(shù)。 操作結(jié)果：對圖進行廣度優(yōu)先遍歷。在遍歷過程中對每個頂點調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。A

6、DT Graph32模塊劃分本程序包括四個模塊：（1）主程序模塊int main(void)初始化；選擇菜單；構(gòu)造無向圖；構(gòu)造最小生成樹；輸出最小生成樹（2）圖模塊實現(xiàn)圖的抽象數(shù)據(jù)類型（3）prim算法模塊（4）kruskal算法模塊4 詳細設(shè)計41數(shù)據(jù)類型的定義（1）圖類型#define M 20#define MAX 20#define null 0#define MAX_VERTEX_NUM 20/ 最大頂點個數(shù)#define MAX_NAME 3 / 頂點字符串的最大長度+1 #define MAX_INFO 20 / 相關(guān)信息字符串的最大長度+1 #define INFINITY I

7、NT_MAX/ 用整型最大值代替typedef int VRType;typedef char InfoType;typedef char VertexTypeMAX_NAME;/ 鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)typedef structVRType adj; / 頂點關(guān)系類型。對無權(quán)圖，用1(是)或0(否)表示相鄰否； / 對帶權(quán)圖，則為權(quán)值類型 InfoType *info; / 該弧相關(guān)信息的指針(可無) ArcCell, adjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 圖的數(shù)據(jù)結(jié)構(gòu)typedef structVertexType vexsMAX_VERTEX_NU

8、M;/ 頂點向量adjMatrix arcs;/ 鄰接矩陣int vexnum,/ 圖的當(dāng)前頂點數(shù)arcnum;/ 圖的當(dāng)前弧數(shù) mGraph;/ 記錄從頂點集U到V-U的代價最小的邊的輔助數(shù)組定義typedef structVertexType adjvex;VRType lowcost;minsideMAX_VERTEX_NUM;42主要模塊的算法描述(1) 主函數(shù)int main(void) /主函數(shù) int i;scanf("%d",&i);switch(i) /*選擇菜單*/case 1: 用prim算法求最小生成樹 break;case 2: 用krus

9、kal算法求最小生成樹break;default:printf("tt輸入錯誤！請重新輸入！n");(2)用prim算法求最小生成樹模塊偽代碼如下定義圖的數(shù)據(jù)結(jié)構(gòu)；圖的構(gòu)建； /*prim算法求最小生成樹*/ 對I,j,k定義；記錄從頂點集U到V-U的代價最小的邊的輔助數(shù)組定義；把頂點信息的賦給k；輔助數(shù)組初始化；令最小代價初始化為0，closedgek.lowcost=0; / 初始,U=u；滿足當(dāng)循環(huán)變量i小于圖的當(dāng)前節(jié)點數(shù)時循環(huán)；按照選取最小代價法則（即求closedge.lowcost的最小正值）選取當(dāng)前節(jié)點的下一結(jié)點（第k頂點）；輸出生成樹的邊；將第k頂點并入U集

10、合； 滿足循環(huán)變量j小于圖的當(dāng)前點數(shù)時循環(huán)；新頂點并入U集后重新選擇最小邊； (3)用kruskal算法求最小生成樹模塊偽代碼如下圖的構(gòu)建并初始化 定義圖的數(shù)據(jù)結(jié)構(gòu)；申請節(jié)點空間(如果失敗則返回信息)；創(chuàng)建圖； /*kruskal算法求最小生成樹*/對i,j,n,m, parentM,edge edgesM定義或初始化；滿足當(dāng)循環(huán)變量i小于圖的當(dāng)前節(jié)點數(shù)時循環(huán)；滿足循環(huán)變量j=i+1小于圖的當(dāng)前點數(shù)時循環(huán)；if(第i個頂點于第j個頂點相連) 把i賦給edgesk.begin； 把j賦給edgesk.end； 把i，j之間的權(quán)值賦給edgesk.weight； K+；/*對結(jié)構(gòu)體edge進行初始

11、化*/ 對圖G邊的權(quán)值進行排序sort(edges, G)； 當(dāng)循環(huán)變量i小于當(dāng)前弧度數(shù)時將0賦給parenti，初始化數(shù)組；當(dāng)循環(huán)變量i小于當(dāng)前弧度數(shù)時(此時第i條弧為最小的) 找第i條弧的起點和終點；并分別賦給你n，m； 當(dāng)n，m不相等時把m賦給parentn；輸出此時第i條弧的起點、終點、權(quán)值； 5 測試分析測試數(shù)據(jù)及結(jié)果如下：圖一：prim算法求最小生成樹結(jié)果圖圖二：kruskal算法求最小生成樹結(jié)果圖 從結(jié)果顯示來看，結(jié)果也與編程的理論一樣，所以，此程序正確。6 課程設(shè)計總結(jié)數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的一門專業(yè)基礎(chǔ)課，設(shè)計到計算機軟、硬件等各方面的知識，如計算機硬件范圍的存儲裝置和存取方法

12、；計算機軟件范圍的數(shù)據(jù)的動態(tài)存儲與管理，信息檢索等。更重要的是，它能實現(xiàn)程序算法和實際高效的結(jié)合。圖是上學(xué)期學(xué)習(xí)的一個比較復(fù)雜的知識點，它包含了豐富的內(nèi)容。通過課程設(shè)計加深了我對圖知識的認識，鞏固了關(guān)于圖的一些算法：建立鄰接矩陣，Prim、Kruskal生成最小生成樹算法。通過課程設(shè)計，有如下幾點收獲和體會：1.其實我在編程方面并不擅長，水平有限，在程序設(shè)計上存在不少缺陷，并且程序如何與實際項目相結(jié)合，還需進一步探索。盡管如此，經(jīng)過了這次圖的最小生成樹的實現(xiàn)的課程設(shè)計我從中學(xué)到了很多,不僅是對于一個成熟的程序的構(gòu)思，還有算法的規(guī)范化、高效化，以及如何將算法合理的應(yīng)用于工程項目中，這是一個關(guān)鍵的

13、環(huán)節(jié).還有就是程序設(shè)計和運行測試中遇到的問題該如何解決,從解決問題中我也學(xué)到了許多平時課本上所沒有的知識.當(dāng)然,能夠?qū)崿F(xiàn)圖的關(guān)鍵路徑我自己也感覺有一定的成就感。2.通過課程設(shè)計還提高了一點改錯能力，對于一些常見問題加深了印象。每次課程設(shè)計都會有多多少少的收獲，這些收獲將成為以后學(xué)習(xí)中一筆不可或缺的財富?？偨Y(jié)不足：在編寫源程序代碼的過程中對語言的運用還需要提高,應(yīng)使寫出來的程序更加簡潔,易讀懂,更加滿足實際工作的需要.要想使做出來的程序更好的利用還需根據(jù)實際需要在今后的運用中不斷的改進和完善。在此我非常要感謝的是我的指導(dǎo)老師黃磊老師，感謝老師的細心認真的輔導(dǎo)，讓我對數(shù)據(jù)結(jié)構(gòu)這門課程有了更加深刻的

14、認識和了解；我還要感謝父母，因為有了父母對我的熱切關(guān)注，讓我有了直面困難的勇氣；我還要感謝我的同學(xué)們，每當(dāng)我碰到一個難題的時候，他們也會熱心的幫我想辦法，也讓我感受到團隊合作的力量。參考文獻1 黃同成，黃俊民，董建寅數(shù)據(jù)結(jié)構(gòu)M北京：中國電力出版社，20082 董建寅，黃俊民，黃同成數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)與題解M北京：中國電力出版社，20083 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）M. 北京：清華大學(xué)出版社，20024 劉振鵬，張曉莉，郝杰數(shù)據(jù)結(jié)構(gòu)M北京：中國鐵道出版社，20035 譚浩強. C語言程序設(shè)計（第二版）M.北京：清華大學(xué)出版社，2003附錄（源程序清單）#include<stdi

15、o.h>#include<stdlib.h>#include"malloc.h" #include <io.h>#include <windows.h>#include <limits.h>#define M 20#define MAX 20#define null 0#define MAX_VERTEX_NUM 20/ 最大頂點個數(shù)#define MAX_NAME 3 / 頂點字符串的最大長度+1 #define MAX_INFO 20 / 相關(guān)信息字符串的最大長度+1 #define INFINITY INT_MAX

16、/ 用整型最大值代替typedef int VRType;typedef char InfoType;typedef char VertexTypeMAX_NAME;/ 鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)typedef structVRType adj; / 頂點關(guān)系類型。對無權(quán)圖，用1(是)或0(否)表示相鄰否； / 對帶權(quán)圖，則為權(quán)值類型 InfoType *info; / 該弧相關(guān)信息的指針(可無) ArcCell, adjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 圖的數(shù)據(jù)結(jié)構(gòu)typedef structVertexType vexsMAX_VERTEX_NUM;/ 頂點

17、向量adjMatrix arcs;/ 鄰接矩陣int vexnum,/ 圖的當(dāng)前頂點數(shù)arcnum;/ 圖的當(dāng)前弧數(shù) mGraph;/ 記錄從頂點集U到V-U的代價最小的邊的輔助數(shù)組定義typedef structVertexType adjvex;VRType lowcost;minsideMAX_VERTEX_NUM;/ 若G中存在頂點u,則返回該頂點在圖中位置;否則返回-1。int LocateVex(mGraph G,VertexType u)int i;for(i = 0; i < G.vexnum; +i)if( strcmp(u, G.vexsi) = 0)return i

18、;return -1;/ 采用數(shù)組(鄰接矩陣)表示法,構(gòu)造無向網(wǎng)G。int CreateAN(mGraph *G)int i,j,k,w,IncInfo;char sMAX_INFO,*info;VertexType va,vb;printf("請輸入無向網(wǎng)G的頂點數(shù),邊數(shù),邊是否含其它信息(是:1,否:0):(空格區(qū)分) ");scanf("%d%d%d%*c",&(*G).vexnum,&(*G).arcnum,&IncInfo); printf("請輸入%d個頂點的值(<%d個字符):n",(*G)

19、.vexnum,MAX_NAME);for(i=0;i<(*G).vexnum;+i) / 構(gòu)造頂點向量 scanf("%s",(*G).vexsi);for(i=0;i<(*G).vexnum;+i) / 初始化鄰接矩陣 for(j=0;j<(*G).vexnum;+j)(*G).arcsij.adj=INFINITY; / 網(wǎng)初始化為無窮大 (*G).=NULL;printf("請輸入%d條邊的頂點1 頂點2 權(quán)值(以空格作為間隔): n",(*G).arcnum);for(k=0;k<(*G).arcn

20、um;+k)scanf("%s%s%d%*c",va,vb,&w); / %*c吃掉回車符 i=LocateVex(*G,va);j=LocateVex(*G,vb);(*G).arcsij.adj=(*G).arcsji.adj=w; / 無向 if(IncInfo)printf("請輸入該邊的相關(guān)信息(<%d個字符): ",MAX_INFO);gets(s);w=strlen(s);if(w)info=(char*)malloc(w+1)*sizeof(char);strcpy(info,s);(*G).=(*G)

21、.=info; / 無向 return 1;/ 求closedge.lowcost的最小正值int minimum(minside SZ,mGraph G)int i=0,j,k,min;while(!SZi.lowcost)i+;min=SZi.lowcost; / 第一個不為0的值 k=i;for(j=i+1;j<G.vexnum;j+)if(SZj.lowcost>0)if(min>SZj.lowcost)min=SZj.lowcost;k=j;return k;/ 用普里姆算法從第u個頂點出發(fā)構(gòu)造網(wǎng)G的最小生成樹T,輸出T的各條邊void Min

22、iSpanTree_PRIM(mGraph G,VertexType u)int i,j,k;minside closedge;k=LocateVex(G,u);for(j=0;j<G.vexnum;+j) / 輔助數(shù)組初始化 if(j!=k)strcpy(closedgej.adjvex,u);closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0; / 初始,U=u printf("最小代價生成樹的各條邊為:n");for(i=1;i<G.vexnum;+i) / 選擇其余G.vexnum-1個頂點 k=mini

23、mum(closedge,G); / 求出T的下一個結(jié)點：第K頂點 printf("(%s-%s)n",closedgek.adjvex,G.vexsk); / 輸出生成樹的邊 closedgek.lowcost=0; / 第K頂點并入U集 for(j=0;j<G.vexnum;+j)if(G.arcskj.adj<closedgej.lowcost)/ 新頂點并入U集后重新選擇最小邊 strcpy(closedgej.adjvex,G.vexsk);closedgej.lowcost=G.arcskj.adj;/*下面是kruskal的算法圖的數(shù)據(jù)結(jié)構(gòu)定義*/

24、typedef structint begin;int end;int weight;edge;typedef structint adj;int weight;AdjMatrixMAXMAX;typedef structAdjMatrix arc;int vexnum, arcnum;MGraph;void CreatGraph(MGraph *);/函數(shù)申明void sort(edge* ,MGraph *);void MiniSpanTree(MGraph *);int Find(int *, int );void Swapn(edge *, int, int);void CreatGr

25、aph(MGraph *G)/構(gòu)件圖int i, j,n, m;printf("請輸入邊數(shù)和頂點數(shù):");scanf("%d %d",&G->arcnum,&G->vexnum);for (i = 1; i <= G->vexnum; i+)/初始化圖for ( j = 1; j <= G->vexnum; j+)G->arcij.adj = G->arcji.adj = 0;for ( i = 1; i <= G->arcnum; i+)/輸入邊和權(quán)值printf("

26、n請輸入有邊的2個頂點");scanf("%d %d",&n,&m);while(n < 0 | n > G->vexnum | m < 0 | n > G->vexnum)printf("輸入的數(shù)字不符合要求 請重新輸入:");scanf("%d%d",&n,&m);G->arcnm.adj = G->arcmn.adj = 1;getchar();printf("n請輸入%d與%d之間的權(quán)值:", n, m);scanf(

27、"%d",&G->arcnm.weight);printf("鄰接矩陣為:n");for ( i = 1; i <= G->vexnum; i+)for ( j = 1; j <= G->vexnum; j+)printf("%d ",G->arcij.adj);printf("n");void sort(edge edges,MGraph *G)/對權(quán)值進行排序int i, j;for ( i = 1; i < G->arcnum; i+)for ( j =

28、 i + 1; j <= G->arcnum; j+)if (edgesi.weight > edgesj.weight)Swapn(edges, i, j);printf("權(quán)排序之后的為:n");for (i = 1; i < G->arcnum; i+)printf("<< %d, %d >> %dn", edgesi.begin, edgesi.end, edgesi.weight);void Swapn(edge *edges,int i, int j)/交換權(quán)值 以及頭和尾int temp

29、;temp = edgesi.begin;edgesi.begin = edgesj.begin;edgesj.begin = temp;temp = edgesi.end;edgesi.end = edgesj.end;edgesj.end = temp;temp = edgesi.weight;edgesi.weight = edgesj.weight;edgesj.weight = temp;void MiniSpanTree(MGraph *G)/生成最小生成樹int i, j, n, m;int k = 1;int parentM;edge edgesM;for ( i = 1; i < G->vexnum; i+)for (j = i + 1; j <= G->vexnum; j+)if (G->arcij.adj = 1)edgesk.begin = i;edgesk.end = j;edgesk.weight = G->arcij.weight;k+;sort(edges, G);for (i = 1; i <= G->arcnum; i+)parenti = 0;printf("最小生成樹為:n");for (i = 1; i <= G->arcnum; i+)/核心