一、摘要N(N>10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以 铺设煤气管道，但代价不同。程序要求:事先任意两居民区之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民区之间铺设煤气管道所需代价最小，并将结果以图形方式在屏幕上输出。

数据结构课程设计报告

管道设计问题

——二维数组的运用

班 级： 姓 名： 指导教师： 成 绩：__________________________

2010年 1 月 20日

一、摘要N(N>10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以 铺设煤气管道，但代价不同。程序要求:事先任意两居民区之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民区之间铺设煤气管道所需代价最小，并将结果以图形方式在屏幕上输出。

目 录

一、摘要........................................................................................... 3 二、引言........................................................................................... 3 三、需求分析 .................................................................................. 3 四、概要设计 .................................................................................. 4 1.普里姆算法分析 ..................................................................... 4 2.模块分析 .................................................................................. 5 3.抽象数据类型分析................................................................. 5 5.全部流程 .................................................................................. 6 五、详细设计 .................................................................................. 7 1.算法分析 .................................................................................. 7 ①信息输入模块................................................................... 7 ②建立最小生成树并输出结果 ......................................... 8 2.源程序代码 ............................................................................. 9 六、测试结果 ................................................................................ 14 程序开始 ................................................................................... 14 信息输入 ................................................................................... 14 输出结果 ................................................................................... 15 七、设计体会 ................................................................................ 15 八、 结束语 .................................................................................. 16 参考文献......................................................................................... 16

一、摘要N(N>10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以 铺设煤气管道，但代价不同。程序要求:事先任意两居民区之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民区之间铺设煤气管道所需代价最小，并将结果以图形方式在屏幕上输出。

一、摘要

N(N>10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以 铺设煤气管道，但代价不同。问题的实质就是编写相应程序求解最小生成树问题。程序要求：

事先任意两居民区之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民区之间铺设煤气管道所需代价最小，并将结果以图形方式在屏幕上输出。

二、引言

C语言作为一门最通用的语言，在过去很流行，将来依然会如此。几乎每一个理工科或者其他专业的学生毫不例外地要学习它。

从C语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子。学习、掌握C语言是每一个计算机技术人员的基本功之一。

C语言具有高级语言的强大功能，却又有很多直接操作计算机硬件的功能，因此，C语言通常又被称为中级语言。

实际生活中最小生成树的问题具有很大的意义。例如，本文所讨论的构架居民区之间铺设煤气管道代价最小，还有在若干的地区见铺设光缆，等等。最小生成树让许多诸如求造价最小、最短路径等最优化的现实问题找到了理论依据，并提供了有效的解决方法。

三、需求分析

在N(N>10)个居民区之间铺设煤气管道所需代价最小，即求最小生成树问题。在我们的课程中介绍了两种求解方法：普里姆（prim）算法和克鲁斯卡尔（kruskal）算法。普里姆算法与网的变数无关，时间复杂度为O（n2),适宜求解边稠密的网的最小生成树。而克鲁斯卡尔算法正好相反，时间复杂度为O（eloge）（e为网中边的数目），故而该算法适宜求边稀疏的最小生成树。

一、摘要N(N>10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以 铺设煤气管道，但代价不同。程序要求:事先任意两居民区之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民区之间铺设煤气管道所需代价最小，并将结果以图形方式在屏幕上输出。

由于在实际应用中，居民区数量一般很有限，而任何两个居民区间都可能有连线，即这样的图应该是边较为稠密 …… 此处隐藏：7705字，全部文档内容请下载后查看。喜欢就下载吧 ……