管道铺设课程设计报告.doc

《管道铺设课程设计报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编号：江西理工大学数据结构课程设计报告班级：学号：姓名：时间：2015年6月22日～2015年7月3日指导教师：2015年06月目录一、摘要.....................................................................3二、引言.......................................................................3三、需求分析..............................................

2、.................3四、概要设计...............................................................41.普利姆算法分析...............................................62.模块分析...........................................................63.抽象数据类型分析...........................................64.全

3、部流程...........................................................6五、详细设计...............................................................71.算法分析...........................................................7（一）信息输入模块.........................................7（二）建立最小生成树并输出结果...

4、..............82.源程序代码.......................................................9六、测试结果...............................................................14程序开始...............................................................14信息输入..............................................

5、.................14输出结果...............................................................14七、设计体会...............................................................15一、结束语...................................................................16参考文献...............................

6、................................16一、摘要N(N>10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以铺设煤气管道，但代价不同。问题的实质就是编写相应程序求解最小生成树问题。程序要求：事先任意两个居民区之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民区之间铺设煤气管道所需代价最小，并将结果以图形方式在屏幕上输出。二、引言C语言作为一门最通用的语言，从语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子。学习掌握C语言是每

7、一个计算机技术人员的基本功之一。实际生活中最小生成树的问题具有很大的意义。例如，本文所讨论的构架居民区之间铺设煤气管道代价最小，还有在若干地区铺设光缆等等。最小生成树让许多诸如求造价最小、最短路径等最优化的现实问题找到了理论依据，并提供了有效的解决方法。三需求分析在N（N>10）个居民区之间铺设煤气管道所需代价最小，即求最小生成树问题。在我们的课本中介绍了两种求解方法：普利姆算法和克鲁斯卡尔算法。普利姆算法与网的变数无关，适宜求解边稠密的网的最小生成树。而克鲁斯卡尔算法正好相反，适宜求解边稀疏的最小生成树。由于在实际问题中，居民数

8、量一般很有限，而任何两个居民区都可能有连线，即这样的图应该是边较为稠密的。因此，我们选择了普利姆算法对问题进行求解。四概要设计1.普利姆算法分析1普利姆算法思想普利姆算法的思想是：在图中人去一个定点k0作为开始点，令U={k0}，W=V-U，其中V