数据结构课程设计报告-煤气管道铺设程序设计报告.doc

数据结构课程设计报告
班级:
姓名:
指导教师:
成绩:

2011年6月24日
以下文档为第15题煤气管道铺设程序设计报告!
摘要
N(N>10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以铺设煤气管道,但代价不同。问题的实质就是编写相应程序求解最小生成树问题。
程序要求:
事先任意两个居民区之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民区之间铺设煤气管道所需代价最小,并将结果以图形方式在屏幕上输出。
目录
一、引言 3
二、需求分析 3
三、概要设计 3
1普利姆算法思想 3
2、模块分析 4
系统功能模块图: 4
6
四、详细设计 6
6
2建立最小生成树并输出结果 7
8
8
9
9
六、调试分析 9
9
八、结束语 10
九、参考文献 10
附录: 10

一、引言
C语言作为一门最通用的语言,从语言产生到现在,它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中,都能看到C语言的影子。学习掌握C语言是每一个计算机技术人员的基本功之一。
实际生活中最小生成树的问题具有很大的意义。例如,本文所讨论的构架居民区之间铺设煤气管道代价最小,还有在若干地区铺设光缆等等。最小生成树让许多诸如求造价最小、最短路径等最优化的现实问题找到了理论依据,并提供了有效的解决方法。
二、需求分析
在多个居民区之间铺设煤气管道所需代价最小,即求最小生成树问题。在我们的课本中介绍了两种求解方法:普利姆算法和克鲁斯卡尔算法。普利姆算法与网的边数无关, 适宜求解边稠密的网的最小生成树。而克鲁斯卡尔算法正好相反,适宜求解边稀疏的最小生成树。
由于在实际问题中,居民数量一般很有限,而任何两个居民区都可能有连线,即这样的图应该是边较为稠密的。因此,我们选择了普利姆算法对问题进行求解最小生成树。
三、概要设计
1普利姆算法思想
普利姆算法的思想是:在图中人去一个定点k0作为开始点,令U={k0},W=V-U,其中V为图中所有顶点集,然后找一个顶点在U中,另一个顶点在w中的边中最短的一条,找到后,将该边作为最小生成树的树边保存起来,并将该边顶点全部加入U集合中,并从W中删除这些顶点,然后重新调整U中顶点到W中顶点的距离,使之保持最小,再重复此过程,直到W为空集。
○2 算法过程描述
在图G=(V,E)(V是顶点,E是边)中,从集合V中任取一个顶点,如k0放入集合U中,这时,U={k0},集合T(E)为空。
从k0出发寻找与U中顶点相邻权值最小的边的另一顶点k1 ,并使k1加入U。即U={k0,k1},同时将该边加入集合T(E)中。重复(2),直到U=V为止。这时T(E)中有n-1条边,T=(U,T(E))就是一颗最小生成树。

2、模块分析
系统功能模块图:
输入存储
构造无向网
输出结果
输出最小生成树
系统
普利姆算法流程图
开始
j=0
j<
strcpy(closedge[j].adjvex,[k])
++j
Y
N
i<
Y
k=minimum(closedge,G)
closedge[j].lowest=[k][j].adj
k=locatevex(G,u)
closedge[k].lowest=0
j=1
closedge[k].lowest=0
c
printf(closedge[k].[k])
j=0
j<
++j
Y
[k][j].adj<closedge[j].lowest
Closedge[j]={[k]},[k][j]}
Y
j=0
结束
N
N

areanum 居民区总数(顶点总数);
edgenum 边的总数;
date[20][20] 邻接矩阵存储图结构;
s 边的权值;
short-way[i] 居民区i到目前生成树中所有点集U中某个居民区的路程最小值
near-area[i] U中能使其最小的居民区
四、详细设计

○1信息输入模块
//读入图的信息,并将邻接矩阵输出
void read()
{
int areanum, edgenum,data[20][20];
printf("请依次输入顶点数和边数:\n");
scanf("%d,%d",&areanum,&edgenu