搜索
首页 电脑/网络 程序设计 C/C++

请高手帮我做程序,用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两种方案,供用户二选一。【测试数据样例】46望京太阳华城武夷 望京 太阳 51望京 武夷 62望京 华城 97太阳 武夷 75太阳 华城 36华城 武夷 29【实现提示】1.首先将输入文件给出的地图信息转换成一张带权的无向图。
  居民小区作为无向图的顶点,小区间的铺设线路作为无向图的边,铺设费用作为边上的权值。需要为无向图选用易于操作的存储方式。对于上面给定的输入信息,可以构造如图所示的无向图。 为了便于操作,可以为每个居民小区分配一个编号,并利用一维数组实现小区编号与名称的映射。
  即数组下标表示服务器的编号,数组元素的内容记录居民小区名称。 uskal算法属于“贪心”算法,每次都从边集的剩余边中挑选权值最小者。Kruskal算法按权值非降序选边,生成最小生成树,即若某条边是最小生成树中第i小的边,则它必须在比它权值小的第1至第(i-1)条边全部判断后,才进行判断;若符合要求,则该边加入到生成树中。
  3. 由于对输入的权值没有要求,因此需要按权值对边非降序排序,需要选用一种排序方法。4. Kruskal算法主要操作有:“合并子树”和“检查是否构成回路”。其中,检查“某条边(u,w)的加入是否构成回路”,可以通过“检查u和w是否在同一个结点集合中”实现。对集合操作有:求集合并集、查找等(需要自己实现)。
  5. 为了便于控制显示过程,约定:需要按“回车”键才开始动态显示本次选中的一条边和一个结点;再次按“回车”才开始动态显示下一步过程。【扩展要求】在完成基本要求之后,本题可以从下面几个方面扩展其功能:1.若施工单位有总投资上限额度限制,需要在工程未完成但已超出额度时,适时提示用户(开发商)追加投资,得到认可后才能继续,否则退出;2.在课程设计实验报告中对Kruskal算法中权值排序算法的选择做分析,说明选择的理由;3.对Kruskal算法“合并子树”和“判断是否构成回路”的操作做进一步分析,探索其它优化解决方案(多多益善),实现之,并在报告中比较不同方案的优劣。
  【测试内容】第1周:明确Prim数据结构和算法框架、明确Kruskal的数据结构第2周:实现Prim算法、确定Kruskal算法解决方案第3周:实现Kruskal算法。

全部回答

2005-06-28

0 0
先做好核心算法再做界面. 核心算法是有无问题,你的问题是数据结构中的基础问题,随便找一个数据结构的书上都有大大把的现成算法,网上大把源码, 仔细研究后可以少作修改,不建议自己想算法,时间和效果都比较差; 界面问题是一个好与坏的问题,实现功能的难度很低,但是做好需要仔细下一些功夫

2005-06-28

24 0
看谁有时间吧,真够麻烦的,用C++倒简单的多

2005-06-28

58 0
    做成代码也太长了啊…… 晕乐,没太长时间给你写代码,给你个思路吧。 问题1:简单说来就是构造最小生成树的问题,数据结构因为是无向图,使用数组感觉比较舒服。使用指针的话,感觉麻烦一些。
  
  把图中每个节点作为一个树的顶点,然后生成出n个哈夫曼树(就是出哈夫曼编码的那个树),最后比较这n个树的总长度(还是深度什么的,就是把树的权值相加),既可得出图的最小生成树。   不要被他那些输入控制和显示之类的乱七八糟的东西束缚思路,先做出核心算法,然后再扩充数据输入,其实那些东西很简单,就是调用几个基类库就可以实现。

类似问题换一批

热点推荐

热度TOP

相关推荐
加载中...

热点搜索 换一换

电脑/网络
C/C++
程序设计
电脑装机
操作系统/系统故障
硬件
笔记本电脑
百度
互联网
反病毒
软件
程序设计
C/C++
数据库
VB
JAVA相关
C#/.NET
VC++
汇编语言
其他编程语言
C/C++
C/C++
举报
举报原因(必选):
取消确定举报