扬州大学《数据结构》课程设计报告课题名称自来水管架设问题姓名×××学院广陵学院系科班级软件812 指导老师陈宏建日期一、课程设计的题目自来水管理架设问题【问题描述】若要在扬州大学的八个居民区（A区、B区、C区、D区、E区、F区、G区、H区）之间架设自来水管道，如何以最低的经济代价架设这个自来水管道。
【基本要求】（1）利用二种方法（Prim算法和克鲁斯卡尔（Kruskual）算法生成自来水管道的架设方案（2）将八个居民区设计成一个有向图,输出一个拓扑排序序列.（3）求出A区到其它各区的最短距离。
（4）写出课程设计报告。
【测试数据】分别对每种方法选定三组测试数据进行测试，验证程序的正确性。
二、课程设计的目的课程设计的目的是培养学生综合程序设计的能力，训练学生灵活应用所学数据结构知识，独立完成问题分析、总体设计、详细设计和编程实现等软件开发全过程的综合实践能力。
巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的学习作风。
为今后学习其他计算机课程打下基础。
课程设计为学生提供了一个既动手又动脑，独立实践的机会，将书本上的理论知识和工作、生产实际有机地结合起来，从而锻炼学生分析问题、解决实际问题的能力，提高学生的编程序能力和创新意识。
三、概要设计1、抽象数据类型定义ADT Graph{数据对象V：V是具有相同特性的数据元素的集合，成为顶点集。
数据关系R：R={VR}VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在路径}基本操作P：CreateMGraph1(MGragh &G)操作结果：建立自来水管道图G的邻接矩阵存储。
CreateALGraph2(ALGraph *&H)操作结果：建立自来水管道有向图H的邻接表存储。
prim(MGragh &G)初始条件：图G存在。
操作结果：用Prim算法建立经济代价最低的自来水管道架设方案。
Sort(MGragh G,TreeEdge edge[])初始条件：图G存在。
操作结果：在G中选择经济代价最低的自来水管道。
Kruskal(TreeEdge edge[],TreeEdge tree[],int n)初始条件：图G存在。
操作结果：用克鲁斯卡尔（Kruskual）算法求经济代价最低的自来水管道架设方案。
TopoSort(ALGraph *H)初始条件：有向图H存在。
操作结果：求拓扑排序序列。
ShortPath（int path[],int I,int v0）初始条件：有向图H存在。
操作结果：将源点设为v0。
Distance(MGragh G,int v0)初始条件：有向图H存在。
操作结果：求出A区（v0）到其它各区的最短距离。
}ADT Graph2、程序包含模块1）主程序模块，其中主函数为main(){初始化图形界面；读入用户选择信息；根据用户选择执行相应模块；关闭文件及图形界面；}；2）创建模块——实现将八个居民区设计成无向图G和有向图H的创建；3）普里姆模块——实现图G的经济代价最低的自来水管道的架设方案；4）克鲁斯卡尔模块——实现图G的经济代价最低的自来水管道的架设方案；5）拓扑排序模块——实现图H的拓扑排序；6）最短距离模块——实现有向网H从A区（v0）到其它各区的最短距离。
3、模块功能框图四、详细设计1、顶点、边、图和最小生成树的边类型#define MaxVertexNum 20 //最大顶点数设为20#define INF 32767 //无穷设为32767typedef struct node{int adjvex; //邻接点域struct node * next; //指向下一个邻接点的指针域}EdgeNode;typedef struct vnode{int vertex; //顶点域int indegree; //入度域EdgeNode * firstedge; //边表头指针}VertexNode;typedef VertexNode AdjList[MaxVertexNum];typedef struct{AdjList adjlist; //邻接表int vexnum,arcnum; //顶点数和边数}ALGraph;typedef struct{int vexs[MaxVertexNum]; //定点表int AdjMatrix[MaxVertexNum][MaxVertexNum]; //邻接矩阵int vexnum,arcnum; //顶点数和边数}MGragh;typedef struct{ int begin,end; //边顶点序号int cost; //边上的权值}TreeEdge;2、图的基本操作void CreateMGraph1(MGragh &G)//将八个居民区设计成一个无向图G，创建无向图G的邻接矩阵存储void CreateALGraph2(ALGraph *&H)//将八个居民区设计成一个有向图H，创建有向图H的邻接表存储void prim(MGragh &G)//用Prim算法建立经济代价最低的自来水管道架设方案void Sort(MGragh G,TreeEdge edge[])//：在G中选择经济代价最低的自来水管道void Kruskal(TreeEdge edge[],TreeEdge tree[],int n)//用克鲁斯卡尔算法求图G的经济代价最低的自来水管道架设方案void TopoSort(ALGraph *H)//实现有向图H的拓扑排序序列void ShortPath(int path[],int i,int v0)//将源点设为v0（A区）void Distance(MGragh G,int v0)//求有向网H的从A区（v0）到其它各区的最短距离3、函数调用关系五、源程序#include<stdio.h>#include<malloc.h>#define MaxVertexNum 20#define INF 32767typedef struct node{int adjvex;struct node * next;}EdgeNode;typedef struct vnode{int vertex;int indegree;EdgeNode * firstedge;}VertexNode;typedef VertexNode AdjList[MaxVertexNum];typedef struct{AdjList adjlist;int vexnum,arcnum;}ALGraph;typedef struct{int vexs[MaxVertexNum];int AdjMatrix[MaxVertexNum][MaxVertexNum];int vexnum,arcnum;}MGragh;typedef struct{ int begin,end;int cost;}TreeEdge;void CreateMGraph1(MGragh &G){int i,j,k,x;printf("请输入居民区区总数和自来水管道数(输入格式为:区数管道数):\n");scanf("%d %d",&(G.vexnum),&(G.arcnum));for (i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)G.AdjMatrix[i][j]=INF;printf("输入%d条边，格式：行下标列下表管道长度<CR>\n",G.arcnum);for(k=0;k<G.arcnum;k++){scanf("%d %d %d",&i,&j,&x);G.AdjMatrix[i][j]=x;G.AdjMatrix[j][i]=G.AdjMatrix[i][j];}}void CreateALGraph2(ALGraph *&H){int i,j,k; EdgeNode * s;H=(ALGraph *)malloc(sizeof(ALGraph));printf("请输入居民区区数和自来水管道数(顶点数边数):\n");scanf("%d %d",&(H->vexnum),&(H->arcnum));printf("请输入居民区区号:\n");for(i=0;i<H->vexnum;i++){scanf("%d",&(H->adjlist[i].vertex));H->adjlist[i].firstedge=NULL;H->adjlist[i].indegree=0;}printf("请输入自来水管道的信息(输入格式为:i j):\n");for(k=0;k<H->arcnum;k++){scanf("\n%d %d",&i,&j);s=(EdgeNode*)malloc(sizeof(EdgeNode));s->adjvex=j;s->next=H->adjlist[i].firstedge;H->adjlist[i].firstedge=s;H->adjlist[j].indegree++;}}void prim(MGragh &G){int n=G.vexnum;int lowerCost[MaxVertexNum],mincost=0,closeVertex[MaxVertexNum];TreeEdge close[MaxVertexNum];int i,j,k,sum=0;for(i=1;i<n;i++){lowerCost[i]=G.AdjMatrix[0][i];closeVertex[i]=0;}lowerCost[0]=0;closeVertex[0]=0;for(i=1;i<n;i++){mincost=INF;j=1;k=1;while(j<n){if(lowerCost[j]!=0 && lowerCost[j]<mincost){mincost=lowerCost[j];k=j;}j++;}close[i-1].begin=closeVertex[k];close[i-1].end=k;close[i-1].cost=mincost;sum=sum+mincost;lowerCost[k]=0;for(j=1;j<n;j++)if(G.AdjMatrix[k][j]<lowerCost[j]){lowerCost[j]=G.AdjMatrix[k][j];closeVertex[j]=k;}}printf("自来水管道架设如下所示：\n始点终点管道长度\n");for(i=0;i<n-1;i++){printf("%3d %3d %3d\n",close[i].begin,close[i].end,close[i].cost); }printf("自来水管道总长为:%d\n",sum);}void Sort(MGragh G,TreeEdge edge[]){int i,j,k=0,p;TreeEdge temp;for(i=0;i<G.vexnum;i++)for(j=0;j<=i;j++)if(G.AdjMatrix[i][j]<INF){edge[k].begin=i;edge[k].end=j;edge[k].cost=G.AdjMatrix[i][j];k++;}for(i=0;i<k-1;i++){p=i;for(j=i;j<k;j++)if(edge[j].cost<edge[p].cost)p=j;if(p!=i){temp=edge[i];edge[i]=edge[p];edge[p]=temp;}}}void Kruskal(TreeEdge edge[],TreeEdge tree[],int n){int v=0,j,k,sum=0;int cnvx[MaxVertexNum];for(j=0;j<n;j++)cnvx[j]=j;for(k=0;k<n-1;k++){while(cnvx[edge[v].begin]==cnvx[edge[v].end])v++;tree[k]=edge[v];sum=sum+edge[v].cost;for(j=0;j<n;j++)if(cnvx[j]==cnvx[edge[v].begin])cnvx[j]=cnvx[edge[v].end];v++;}printf("自来水管道架设如图所示：\n始点终点管道长度\n");for(j=0;j<n-1;j++){printf("%3d %3d %3d\n",tree[j].end,tree[j].begin,tree[j].cost);}printf("自来水管道总长为:%d\n",sum);}void TopoSort(ALGraph *H){int i,m=0,stack[MaxVertexNum],num=0;EdgeNode *p;for(i=0;i<H->vexnum;i++)if(H->adjlist[i].indegree== 0){stack[num]=i;num++;}printf("拓扑序列:");while(num!=0){i=stack[num-1];num--;printf(" %d ",H->adjlist[i].vertex);m++;p=H->adjlist[i].firstedge;while (p!=NULL){i=p->adjvex;H->adjlist[i].indegree--;if(H->adjlist[i].indegree==0){stack[num]=i;num++;}p=p->next;}}if(m!=H->vexnum)printf("不存在,网中存在环!!!");printf("\n");}void ShortPath(int path[],int i,int v0){int k;k=path[i];if(k!=v0) ShortPath(path,k,v0);printf("%d ",k);}void Distance(MGragh G,int v0){int v,w,i,min,path[MaxVertexNum],final[MaxVertexNum],dis[MaxVertexNum]; int p[MaxVertexNum][MaxVertexNum];for(v=0;v<G.vexnum;++v){path[v]=0; for(w=0;w<G.vexnum;++w) p[v][w]=0; }for(v=0;v<G.vexnum;++v){final[v]=0;dis[v]=G.AdjMatrix[v0][v];}dis[v0]=0; final[v0]=1; path[v0]=-1;for(i=1;i<G.vexnum;++i){min=INF;for(w=0;w<G.vexnum;++w)if(!final[w])if(dis[w]<min) {v=w; min=dis[w];}final[v]=1;for(w=0;w<G.vexnum;++w)if(!final[w]&&(min+G.AdjMatrix[v][w]<dis[w])){dis[w]=min+G.AdjMatrix[v][w];path[w]=v; }}printf("输出管道最短:\n");for(i=0;i<G.vexnum;++i){if(final[i]==1 && i!=v0){printf("从%d到%d的自来水管道最短路径长度为:%d\t路径为:",v0,i,dis[i]);ShortPath(path,i,v0);printf("%d\n",i);}elseprintf("从%d到%d不存在路径\n",v0,i);}}main(){int flag=1;action:printf("****自来水管道的架设方案****\n");printf(" 1.prim算法的实现\n");printf(" 2.克鲁斯卡尔（Kruskual）算法的实现\n");printf(" 3.输出拓扑排序序列\n");printf(" 4.A区到各个区的最短距离\n");printf(" 5.退出\n");printf(" 请选择<1~5>：");scanf("%d",&flag);switch(flag){case 1:MGragh G;CreateMGraph1(G);prim(G);break;case 2:TreeEdge edge[MaxVertexNum*MaxVertexNum],tree[MaxVertexNum];Sort(G,edge);Kruskal(edge,tree,G.vexnum);break;case 3:ALGraph *H;CreateALGraph2(H);TopoSort(H);break;case 4:Distance(G,0);printf(" 0代表A,1代表B,2代表C,3代表D\n");printf(" 4代表E,5代表F,6代表G,7代表H\n");break;}goto action;return 0;}六、使用方法与说明1、选择1实现用Prim算法实现自来水管道架设方案2、选择2实现用克鲁斯卡尔（Kruskual）算法实现自来水管道架设方案3、选择3实现拓扑排序序列4、 选择4实现A 区（v0）到各个区的最短距离5、选择5退出系统七、用户手册1.本程序运行环境为windows xp操作系统在vc++6.0中运行，执行文件为:自来水管道.cpp。