请高手帮我做程序，用C语言
数据结构的课设作业，要求如下。做不了整个的帮忙做一部分也成。谢谢了
输管道铺设施工最佳方案选择
【问题描述】
某城市n个居民小区之间需要铺设煤气管道，需将n个小区的管道连通。设任意两个小区间都有条件铺设，但由于地理环境不同，所需经费各不相同。现需要为施工单位设计铺设管道的最优施工方案，使总投资尽可能少。
【基本要求】
请设计一个软件系统，利用图形用户界面模拟该城市居民小区铺设管道的最优施工方案的设计过程。
一 、输入数据要求
测试数据通过一个文本文件读入。该数据文件的第1行为一个正整数n（n<=10），表示居民小区的数目。第2行为一个正整数m（m<=n*(n-1)/2），表示铺设线路的数目。接下来n行字符串表示小区名称，之后的m行中的每行用2个字符串和一个正整数，描述一条铺设线路连接的两个小区的名称以及该线路的铺设费用。铺设费用为不超过100的正整数。
二、输出画面的要求
用图形方式动态模拟一个最优施工方案设计的全过程。为了便于控制画面布局，可以让用户选择几种固定的小区数目，例如：6、8或10，但线路信息必须通过文本文件读入。先显示所有可能的候选铺设线路(边)，生成时需换用不同颜色逐步显示生长的边和顶点。
三、题目约定
l 题目中给出的所有铺设费用的单位均是“千元”；
l 设施工单位用于铺设管道的总投资没有上限额度，但应尽可能节约。
四、题目实现要求
l 应用Prim算法，求最小生成树，动态演示生成过程；
l 应用Kruskal算法，求最小生成树，动态演示生成过程。
l 用户界面提供Prim、Kruskal两种方案，供用户二选一。
【测试数据样例】
4
6
望京
太阳
华城
武夷
望京 太阳 51
望京 武夷 62
望京 华城 97
太阳 武夷 75
太阳 华城 36
华城 武夷 29
【实现提示】
1．首先将输入文件给出的地图信息转换成一张带权的无向图。居民小区作为无向图的顶点，小区间的铺设线路作为无向图的边，铺设费用作为边上的权值。需要为无向图选用易于操作的存储方式。
对于上面给定的输入信息，可以构造如图所示的无向图。
为了便于操作，可以为每个居民小区分配一个编号，并利用一维数组实现小区编号与名称的映射。即数组下标表示服务器的编号，数组元素的内容记录居民小区名称。
uskal算法属于“贪心”算法,每次都从边集的剩余边中挑选权值最小者。Kruskal算法按权值非降序选边,生成最小生成树,即若某条边是最小生成树中第i小的边,则它必须在比它权值小的第1至第(i-1)条边全部判断后,才进行判断;若符合要求,则该边加入到生成树中。3． 由于对输入的权值没有要求，因此需要按权值对边非降序排序，需要选用一种排序方法。
4． Kruskal算法主要操作有：“合并子树”和“检查是否构成回路”。其中，检查“某条边（ｕ，ｗ）的加入是否构成回路”，可以通过“检查ｕ和ｗ是否在同一个结点集合中”实现。对集合操作有：求集合并集、查找等（需要自己实现）。
5． 为了便于控制显示过程，约定：需要按“回车”键才开始动态显示本次选中的一条边和一个结点；再次按“回车”才开始动态显示下一步过程。
【扩展要求】
在完成基本要求之后，本题可以从下面几个方面扩展其功能：
1．若施工单位有总投资上限额度限制，需要在工程未完成但已超出额度时，适时提示用户(开发商)追加投资，得到认可后才能继续，否则退出；
2．在课程设计实验报告中对Kruskal算法中权值排序算法的选择做分析，说明选择的理由；
3．对Kruskal算法“合并子树”和“判断是否构成回路”的操作做进一步分析，探索其它优化解决方案（多多益善），实现之，并在报告中比较不同方案的优劣。
【测试内容】
第1周：明确Prim数据结构和算法框架、明确Kruskal的数据结构
第2周：实现Prim算法、确定Kruskal算法解决方案
第3周：实现Kruskal算法
[展开]
r***
2005-06-27 22:39:34
举报