管道铺设施工的最佳方案 课程设计题目 N ( N >10 )个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以铺设煤气管道,但代价不同。事先将任意两个居民区之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这 N 个居民区之间铺设煤气管道所需代价最少 , 并希望以图形方式在屏幕上输出结果。 1 课程设计目的及要求: 目的:1.能根据实际问题的具体情况,结合数据结构课程中的基本理论和基本算法,正确分析出数据的逻辑结构,合理地选择相应的存储结构,并能设计出解决问题的有效算法 2.提高程序设计和调试能力.学生通过上机实习,验证自己设计的算法的正确性,学会有效利用基本调试方法,迅速找出程序代码中的错误并且修改. 3.培养算法分析能力.分析所设计算法的时间复杂度和空间复杂度,进一步提高程序设计水平. 要求: 求解的算法为:在可能架设的m 条管道中选取n-1 条,即能连通n-1 个居民区,又使总投资达到“最小”。网采用邻接矩阵为存储结构,以顶点对(i,j)的形式输出最小生成树的边。 二、数据结构设计 ①图文件的结构? ②图在内存中的存储结构 邻接矩阵、邻接表、三元组 ③最小生成树的存储结构 ④图形的显示结构 三、功 能设计 ①准 备 代价 文件 自动 随 机生成、用户 可以自定 义 ②读 图文件,得 到图的存储结构 ③计算最小生成树 何 种 算法效率 更 好 ?Prim、Kruskal ④显示最小生成树 文本方式:各 边、总权 值 图形函 数:屏 幕 初 始 化 、端 点位 置 的初 始 化 、绘 边函 数、代价 显示函 数、绘 无 边图函 数...... 2 课程设计详细内容: //main.ccp #include
#include #include #include "Pipe.h" using namespace std; int main() { int n; for(int i = 1; i <= 10; i++) cout<>n; switch (n) { case 1: m.create(); break; case 2: m.prim (); break; case 3: m.print (); break; case 4: m.print2...