最小生成树问题

《最小生成树问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、河南城建学院课程设计报告书专业：计算机科学与技术课程设计名称：《数据结构课程设计》题目：最小生成树问题班级：学　　　　号：姓　　　　名：同组人员:指导老师：完成时间：2012年2月17日摘要本课程设计主要解决图的关键路径的实现。在项目管理中，编制网络计划的基本思想就是在一个庞大的网络图中找出关键路径，并对各关键活动，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。而对非关键路径的各个活动，只要在不影响工程完工时间的条件下，抽出适当的人力、物力和财力等资源，用在关键路径上，以达到缩短工程工期，合理利用资源等目的。在执行计划过程中，可以明确工作重点，对各个关键活动加以有效控制和调度。关键

2、路径法将项目分解成为多个独立的活动并确定每个活动的工期，然后用逻辑关系（结束-开始、结束-结束、开始-开始和开始结束）将活动连接，从而能够计算项目的工期、各个活动时间特点（最早最晚时间、时差）等。在关键路径法的活动上加载资源后，还能够对项目的资源需求和分配进行分析。在本程序设计中，要求实现图的关键路径，最小生成树，判断两点之间是否有路径，程序由2个模块组成，分别为主函数的创建及其他相关函数的设计。程序通过调试运行，初步实现了设计目标。在课程设计中，系统开发平台为Windows2000，程序设计设计语言采用VisualC++，程序运行平台为Windows98/2000/XP。关键词程序设计；C+

3、+；图；关键路径目录目录-3-第一章开发环境和开发工具41.1C/C++语言简介41.1开发背景41.3开发环境5第二章算法思想62.1系统需求分析62.2系统总体设计72.2.1系统设计目标72.2.2开发设计思想72.2.3系统功能模块设计92.3算法思想描述9第三章算法实现113.1数据结构113.2程序模块121.insertsort函数123.3各模块之间的调用关系173.4源程序代码17第四章测试与分析274.1测试数据选择27总结30心得体会31参考文献32第一章开发环境和开发工具1.1C/C++语言简介C语言是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点

4、。它由美国贝尔研究所的D.M.Ritchie于1972年推出。1978后，C语言已先后被移植到大、中、小及微型机上。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C语言，适于编写系统软件，三维，二维图形和动画。具体应用比如单片机以及嵌入式系统开发C++语言是一种优秀的面向对象程序设计语言，它在C语言的基础上发展而来，但它比C语言更容易为人们学习和掌握。C++以其独特的语言机制在计算机科学的各个领域中得到了广泛的应用。面向对象的设计思想是在原来结构化程

5、序设计方法基础上的一个质的飞跃，C++完美地体现了面向对象的各种特性。1.1开发背景数据结构课程是计算机专业最重要的基础课之一，主要研究分析计算机存储、组织数据的方式，使学生能够根据数据对象的特征，选择适当的数据结构、存储结构及相应算法，初步掌握各种算法在时间和空间上的分析技巧，并能够进行算法和程序设计，使所涉及的程序结构清楚，正确易读[3]。数据的组织方法和现实世界问题在计算机内部的表示方法，并能针对应用问题，选择合适的数据逻辑结构、存储结构及其算法，掌握解决复杂问题的程序设计方法和技术。选择合适的数据结构更容易设计出更高效运行或存储效率的算法；图是一种较线性表和树更为复杂的数据结构。在图形

6、结构中，结点之间的关系可以是任意的，图中的任意两个元素之间都可能相关。在社会主义建设时期，各个城市建设问题尤其是网络建设尤为重要。在保证各个城市能互相连通的情况下，怎么保证建设网络，怎么建设最省钱是建设工程公司所需考虑的重大情况。从而能节省更多的钱来投资其他地方建设，如农村交通建设。各个各个城市建设好之后，则可再根据将城市作为一个结点和其它城市再次运用最小生成树。最小生成树则能有效的解决此问题。例如，以尽可能低的总价建设若干网络管道，把n个城市联系在一起。1.3开发环境本文所采用的开发环境主要是基于WindowsXP系统，编程环境主要是在VC6.0++中。第二章算法思想2.1系统需求分析根据课

7、设题目要求，拟将整体程序分为三大模块。以下是三个模块的大体分析：1.要确定图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。2.Kruskal算法。该算法设置了集合A，该集合一直是某最小生成树的子集。在每步决定是否把边（u,v）添加到集合A中，其添加条件是A∪{（u,v）}仍然是最小生