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

《数据结构课程设计报告-煤气管道铺设程序设计报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构程序设计报告.数据结构课程设计报告班级:姓名：指导教师：成绩：2011年6月24日32数据结构程序设计报告以下文档为第15题煤气管道铺设程序设计报告！摘要N(N>10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以铺设煤气管道，但代价不同。问题的实质就是编写相应程序求解最小生成树问题。程序要求：事先任意两个居民区之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民区之间铺设煤气管道所需代价最小，并将结果以图形方式在屏幕上输出。32数据结构程序设计报告目录一、引言3二、需求分析3三、概要设计31普利姆算法思想32、模块分

2、析4系统功能模块图：43.抽象数据类型分析6四、详细设计61.算法分析62建立最小生成树并输出结果7五.测试结果81.程序开始82.信息输入93.输出结果9六、调试分析9七.设计体会9八、结束语10九、参考文献10附录：1032数据结构程序设计报告一、引言C语言作为一门最通用的语言，从语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子。学习掌握C语言是每一个计算机技术人员的基本功之一。实际生活中最小生成树的问题具有很大的意义。例如，本文所讨论的构架居民区之间铺设煤气管道代价最小，还有在若干地区铺设光缆等等。

3、最小生成树让许多诸如求造价最小、最短路径等最优化的现实问题找到了理论依据，并提供了有效的解决方法。二、需求分析在多个居民区之间铺设煤气管道所需代价最小，即求最小生成树问题。在我们的课本中介绍了两种求解方法：普利姆算法和克鲁斯卡尔算法。普利姆算法与网的边数无关，适宜求解边稠密的网的最小生成树。而克鲁斯卡尔算法正好相反，适宜求解边稀疏的最小生成树。由于在实际问题中，居民数量一般很有限，而任何两个居民区都可能有连线，即这样的图应该是边较为稠密的。因此，我们选择了普利姆算法对问题进行求解最小生成树。三、概要设计1普利姆算法思想普利姆算法的思想是：在图中人去一个定

4、点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中顶点相邻权值最小的边的另一顶点k132数据结构程序设计报告，并使k1加入U。即U={k0，k1}，

5、同时将该边加入集合T（E）中。重复（2），直到U=V为止。这时T（E）中有n-1条边，T=（U，T（E））就是一颗最小生成树。2、模块分析系统功能模块图：输入存储构造无向网输出结果输出最小生成树系统普利姆算法流程图32数据结构程序设计报告开始j=0j

6、closedge[k].lowest=0cprintf(closedge[k].adjvex.G.vexs[k])j=0j

7、area[i]U中能使其最小的居民区四、详细设计1.算法分析○1信息输入模块//读入图的信息，并将邻接矩阵输出voidread(){intareanum,edgenum,data[20][20];printf("请依次输入顶点数和边数:");scanf("%d,%d",&areanum,&edgenum);//初始化邻接矩阵各元素值inti,j;for(i=0;i

8、k,表示i到j的权值是k.");for(i=0;i