《数据结构》
课 程 设 计 报 告
课题名称 自来水管架设问题
姓 名 × × ×
学 院 广陵学院
系科班级 软件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 Graph
2、程序包含模块
1） 主程序模块，其中主函数为
main()
{初始化图形界面；
读入用户选择信息；
根据用户选择执行相应模块；
关闭文件及图形界面；
}；
2） 创建模块——实现将八个居民区设计成无向图G和有向图H的创建；
3） 普里姆模块——实现图G的经济代价最低的自来水管道的架设方案；
4） 克鲁斯卡尔模块——实现图G的经济代价最低的自来水管道的架设方案；
5） 拓扑排序模块——实现图H的拓扑排序；
6） 最短距离模块——实现有向网H从A区（v0）到其它各区的最短距离。
3、模块功能框图
四、详细设计
1、顶点、边、图和最小生成树的边类型
#define MaxVertexNum 20 //最大顶点数设为20
#define INF 32767 //无穷设为32767
typedef 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 32767
typedef 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);}
else
printf("从%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。
2. 进入系统后显示选择菜单：
****自来水管道的架设方案****
1. prim算法的实现
2. 克鲁斯卡尔（Kruskual）算法的实现
3. 输出拓扑排序序列
4. A区到各个区的最短距离
5. 退出
请选择<1~5>：
八、课程设计的小结
九、参考文献
1、《数据结构》（C语言版） 严蔚敏，吴伟民编著。--北京：清华大学出版社，2007
2、《数据结构实验编导》