管道鋪設(shè)課程設(shè)計報告

1、編號： 江西理工大學(xué) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 班 級： 學(xué) 號： 姓 名： 時 間： 2015年6月22日2015年7月3日 指導(dǎo)教師： 2015年06月目 錄一、 摘要 .3二、 引言.3三、 需求分析.3四、 概要設(shè)計.41. 普利姆算法分析.62. 模塊分析.63. 抽象數(shù)據(jù)類型分析.64. 全部流程.6五、 詳細設(shè)計.71. 算法分析.7（一） 信息輸入模塊.7（二） 建立最小生成樹并輸出結(jié)果.82. 源程序代碼.9六、 測試結(jié)果.14程序開始.14信息輸入.14輸出結(jié)果.14七、 設(shè)計體會.15八、 結(jié)束語.16參考文獻.16 一、 摘要 N(N>10)個居民區(qū)之間需要鋪設(shè)煤氣管

2、道。假設(shè)任意兩個居民區(qū)之間都可以鋪設(shè)煤氣管道，但代價不同。問題的實質(zhì)就是編寫相應(yīng)程序求解最小生成樹問題。程序要求：事先任意兩個居民區(qū)之間鋪設(shè)煤氣管道的代價存入磁盤文件中。設(shè)計一個最佳方案使得這N個居民區(qū)之間鋪設(shè)煤氣管道所需代價最小，并將結(jié)果以圖形方式在屏幕上輸出。二、 引言C語言作為一門最通用的語言，從語言產(chǎn)生到現(xiàn)在，它已經(jīng)成為最重要和最流行的編程語言之一。在各種流行編程語言中，都能看到C語言的影子。學(xué)習(xí)掌握C語言是每一個計算機技術(shù)人員的基本功之一。實際生活中最小生成樹的問題具有很大的意義。例如，本文所討論的構(gòu)架居民區(qū)之間鋪設(shè)煤氣管道代價最小，還有在若干地區(qū)鋪設(shè)光纜等等。最小生成樹讓許多諸如求

3、造價最小、最短路徑等最優(yōu)化的現(xiàn)實問題找到了理論依據(jù)，并提供了有效的解決方法。三 需求分析 在N（N>10）個居民區(qū)之間鋪設(shè)煤氣管道所需代價最小，即求最小生成樹問題。在我們的課本中介紹了兩種求解方法：普利姆算法和克魯斯卡爾算法。普利姆算法與網(wǎng)的變數(shù)無關(guān)， 適宜求解邊稠密的網(wǎng)的最小生成樹。而克魯斯卡爾算法正好相反， 適宜求解邊稀疏的最小生成樹。 由于在實際問題中，居民數(shù)量一般很有限，而任何兩個居民區(qū)都可能有連線，即這樣的圖應(yīng)該是邊較為稠密的。因此，我們選擇了普利姆算法對問題進行求解。四 概要設(shè)計1. 普利姆算法分析1普利姆算法思想 普利姆算法的思想是：在圖中人去一個定點k0作為開始點，令U=

4、k0，W=V-U，其中V為圖中所有頂點集，然后找一個頂點在U中，另一個頂點在w中的邊中最短的一條，找到后，將該邊作為最小生成樹的樹邊保存起來，并將該邊頂點全部加入U集合中，并從W中刪除這些頂點，然后重新調(diào)整U中頂點到W中頂點的距離，使之保持最小，再重復(fù)此過程，直到W為空集。2 算法過程描述1） 在圖G=（V，E）（V是頂點，E是邊）中，從集合V中任取一個頂點，如k0放入集合U中，這時，U=k0，集合T（E）為空。2） 從k0出發(fā)尋找與U中頂點相鄰權(quán)值最小的邊的另一頂點k1 ，并使k1加入U。即U=k0，k1，同時將該邊加入集合T（E）中。3） 重復(fù)（2），直到U=V為止。4） 這時T（E）中有

5、n-1條邊，T=（U，T（E）就是一一顆最小生成樹。 2、模塊分析 根據(jù)對模型的功能分析，該管道鋪設(shè)設(shè)計可以具有以下功能： 1管道鋪設(shè)信息的輸入； 2最小生成樹信息的輸出； 功能模塊圖： 3.抽象數(shù)據(jù)類型分析areanum 居民區(qū)總數(shù)（頂點總數(shù)）；edgenum 邊的總數(shù)；date 20 鄰接矩陣存儲圖結(jié)構(gòu)；s 邊的權(quán)值；short-wayi 居民區(qū)i到目前生成樹中所有點集U中某個居民區(qū)的路程最小值near-areai U中能使其最小的居民區(qū)5. 全部流程 五、詳細設(shè)計1.算法分析1信息輸入模塊/讀入圖的信息，并將鄰接矩陣輸出Void read（）/輸入頂點個數(shù)和邊的條數(shù)Printf（“請輸入

6、：定點數(shù)，變數(shù)：n”）;Scanf(“%d,%d”,&areanum,&dedgenm);/初始化鄰接矩陣各元素值Int i, j,k;for(i=0;i<areanum;i+)for(j=0;j<areanum;j+)date i j=INFINITY;/讀入邊Int from,to ,s;Printf(“輸入邊，格式為i，j，k，表示i到j(luò)的權(quán)值是k：n”);For(i=0;i<degenum;i+)Scanf(“%d,%d,%d”,&from,&to,&s);date fromto=s;date tofromst;/輸出鄰接矩陣f

7、or(i=0;i<areanum;i+)for(j=0;j<areanum;j+)Printf(“%dt”,datei j);Printf(“n”); 2建立最小生成樹并輸出結(jié)果 / 用普里姆算法從第u個頂點出發(fā)構(gòu)造網(wǎng)G的最小生成樹T,輸出T的各條邊void MiniSpanTree_PRIM(MGraph G,VertexType u) /system("cls");int i,j,k;minside closedge;k=LocateVex(G,u);for(j=0;j<G.vexnum;+j) / 輔助數(shù)組初始化 if(j!=k)strcpy(clo

8、sedgej.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=minimum(closedge,G); / 求出T的下一個結(jié)點：第K頂點 printf("(%s-%s)n",closedgek.adjvex,G.vexsk); / 輸出生成樹的邊 closedgek.lowcost=0; / 第K頂點并入U集 for(

9、j=0;j<G.vexnum;+j)if(G.arcskj.adj<closedgej.lowcost)/ 新頂點并入U集后重新選擇最小邊 strcpy(closedgej.adjvex,G.vexsk);closedgej.lowcost=G.arcskj.adj;system("pause");2. 源程序代碼#include <stdio.h>#include <limits.h>#include<string.h>#include <malloc.h>#include<stdlib.h>#def

10、ine MAX_VERTEX_NUM 20/ 最大頂點個數(shù)#define MAX_NAME 3 / 頂點字符串的最大長度+1 /#define MAX_INFO 20 / 相關(guān)信息字符串的最大長度+1 #define INFINITY INT_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 *

11、info; / 該弧相關(guān)信息的指針(可無) ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; / 圖的數(shù)據(jù)結(jié)構(gòu)typedef structVertexType vexsMAX_VERTEX_NUM;/ 頂點向量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

12、,則返回該頂點在圖中位置;否則返回-1。int LocateVex(MGraph G,VertexType u)int i;for(i = 0; i < G.vexnum; +i)if( strcmp(u, G.vexsi) = 0)return i;return -1;/代價保存為文件/代價存入文件void wenjian()/system("cls");FILE *fp;char s50,ch;strcpy(s,"D:record.txt");if(fp=fopen(s,"ab+")=NULL) printf("無

13、法打開此文件n");exit(0);else/printf("請向磁盤中輸入原點總數(shù)和邊的總數(shù)：n"); /printf("請輸入頂點數(shù)邊數(shù)n");/scanf("%d %d",&G.vexnum,&G.arcnum);/printf("請輸入各居民點:");/for(int i=1;i<=N;i+)/scanf("%c",&G.vexsi);/in/fput(G.vexsi,fp);/ /printf("請向磁盤中輸入各原點和邊的總數(shù)同時記錄原

14、點，目的點，及相應(yīng)的權(quán)值:(輸入#鍵表示結(jié)束)n");printf("請向磁盤中輸入各原點和邊的總數(shù):(輸入$鍵表示結(jié)束)n"); ch=getchar();while(ch!='$')fputc(ch,fp);ch=getchar();printf("請向磁盤中輸入原點，目的點，及相應(yīng)的權(quán)值:(輸入#鍵表示結(jié)束)n"); ch=getchar();while(ch!='#')fputc(ch,fp);ch=getchar();fclose(fp);system("pause");/從文件中得

15、到信息構(gòu)成圖void xianshi () /system("cls"); FILE *fp;char s50,ch;strcpy(s,"D:record.txt");if(fp=fopen(s,"r")=NULL) printf("無法打開此文件n");exit(0);elsewhile(!feof(fp)ch=fgetc(fp);putchar(ch);putchar(10);fclose(fp);system("pause"); / 算法7.2 P162/ 采用數(shù)組(鄰接矩陣)表示法,構(gòu)造

16、無向網(wǎng)G。int CreateAN(MGraph *G)/system("cls");int i,j,k,w;/char sMAX_INFO,*info;/char *info;VertexType va,vb;printf("請輸入無向網(wǎng)G的頂點數(shù),邊數(shù),(空格區(qū)分) ");scanf("%d%d",&(*G).vexnum,&(*G).arcnum); printf("請輸入%d個頂點的值:n",(*G).vexnum);for(i=0;i<(*G).vexnum;+i) / 構(gòu)造頂點向量

17、 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).arcnum;+k)scanf("%s%s%d%*c",va,vb,&w); / %*c

18、吃掉回車符 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).=info; / 無向 /printf("輸出臨接矩陣：n

19、");for(i=0;i<(*G).vexnum;+i)for(j=0;j<(*G).vexnum;+j) if( j%3=0)printf("n");printf("%d ", (*G).arcsij.adj);return 1;system("pause"); / 求closedge.lowcost的最小正值int minimum(minside SZ,MGraph G)int i=0,j,k,min;while(!SZi.lowcost)i+;min=SZi.lowcost; / 第一個不為0的值 k=i;

20、for(j=i+1;j<G.vexnum;j+)if(SZj.lowcost>0)if(min>SZj.lowcost)min=SZj.lowcost;k=j;return k; / 算法7.9 P175 / 用普里姆算法從第u個頂點出發(fā)構(gòu)造網(wǎng)G的最小生成樹T,輸出T的各條邊void MiniSpanTree_PRIM(MGraph G,VertexType u) /system("cls");int i,j,k;minside closedge;k=LocateVex(G,u);for(j=0;j<G.vexnum;+j) / 輔助數(shù)組初始化 if

21、(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=minimum(closedge,G); / 求出T的下一個結(jié)點：第K頂點 printf("(%s-%s)n",closedgek.adjvex,G.vexsk); / 輸出生成樹的邊 closedgek.lowcost=0;

22、 / 第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;system("pause"); void main() /system("cls"); MGraph G; int xz; while(1) /system("cls"); printf("n");prin

23、tf("*管道鋪設(shè)最佳方案選擇*n"); printf(" 0 記錄保存為文件n"); printf(" 1 從文件中讀記錄n");printf(" 2 構(gòu)造無向網(wǎng)n "); printf(" 3 求出最小生成樹n"); printf(" 4 退出n");printf("*n"); printf(" 請輸入操作序號(0-4):n"); scanf("%d",&xz); switch(xz) case 0: wenjian();break; case 1: xianshi ();break; case 2: CreateAN(&G);break; case 3: MiniSpanTree_PRIM(G,G.vexs0);break; case 4: exit(0); default:printf("輸入無效指令!按任意鍵繼續(xù)!");system("paus