数据结构课程设计报告-关键路径

《数据结构课程设计报告-关键路径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构程序设计《数据结构》课程设计报告学院计算机与通信工程专业网络工程班级学号学生姓名指导教师课程成绩完成日期2011年2月27日课程设计成绩评定数据结构程序设计学院计算机与通信工程学院专业网络工程班级学号学生姓名指导教师完成日期2011年2月27日指导教师对学生在课程设计中的评价评分项目优良中及格不及格课程设计中的创造性成果学生掌握课程内容的程度课程设计完成情况课程设计动手能力文字表达学习态度规范要求课程设计论文的质量指导教师对课程设计的评定意见综合成绩指导教师签字2011年2月27日课程设计任务书数据结构程序设计计算机与通信工程学院网络工程专

2、业课程名称数据结构课程设计时间2010～2011学年第2学期1～2周学生姓名指导老师题目用数据结构求图的关键路径问题主要内容：用C++语言和数据结构思想构建图，并求出关键路径。要求：（1）通过实际课题的分析、设计、编码、测试等工作，掌握用C++语言和数据结构思想结合来开发和维护软件。（2）按要求编写课程设计报告书，能正确编写分析、设计、编码、测试等技术文档和用户使用手册。应当提交的文件：（1）课程设计论文。（2）课程设计附件（主要是源程序）。数据结构课程设计报告数据结构程序设计摘要关键路径是我们估算某些工程非常有用，是一种非常重要的估算一项工程所需

3、的最短时间的依据。本文对如何求一个工程的关键路径做了详细的说明，包括需求分析、概要设计、详细设计、测试与分析、总结、源程序清单。 首先，做了需求分析，解释了什么是关键路径，并指出它在估算工程中的重要作用。然后给出求关键路径的概要设计，包括程序中用到的所有抽象数据类型的定义，主程序的流程以及各程序模块之间的层次(调用)关系。在概要设计的基础上，又给出了详细的算法设计，实现概要设计中定义的所有函数,对每个函数写出核心算法，并画出了流程图。然后对编码进行了测试与分析（并在最后附上C语言编写的程序代码）。最后对整个设计过程进行了总结关键词：关键路径；抽象数

4、据类型；程序模块；核心算法；流程图目录1绪论-1-数据结构程序设计1．1前言-1-1．2研究意义-1-2需求分析-2-2．1问题描述-2-2．2基本要求-2-2．3目的-2-3概要设计-3-3．1算法分析-3-3．2算法步骤-3-3．3数据结构-4-4详细设计-5-4．1主要函数的核心代码-5-4．2程序流程图-5-5测试-6-5．1开始界面-6-5．2进入求关键路径的系统-6-5．3输入节点数和活动个数-7-5．4输入某项目的信息（弧头，弧尾，权值）-7-5．5打印出关键路径-8-5．6错误测试-9-5．7回路测试-10-6总结-11-参考文献-

5、12-附录：源程序清单-13-数据结构程序设计1绪论1．1前言我们通常把计划、施工过程、生产流程、程序流程等都当成一个工程。工程通常分为若干个称为“活动”的子工程。完成了这些“活动”，这个工程就可以完成了。我们通常用AOE-网来表示工程。AOE-网是一个带权的有向无环图，其中，顶点表示事件（EVENT），弧表示活动，权表示活动持续的时间。AOE-网可以用来估算工程的完成时间。他可以使人们了解：1.研究某个工程至少需要多少时间?2.哪些活动是影响工程进度的关键？由于AOE-网中的有些活动可以并行进行，从开始点到各个顶点，以致从开始点到完成点的有向路径

6、可能不止一条，这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成工程所需的最短时间是从开始点到完成点的最长路径的长度，即在这条路径上的所有活动的持续时间之和.这条路径长度就叫做关键路径(CriticalPath)。1．2研究意义关键路径可以很方便的让我们估算出某个工程最短的时间开销，以及这个工程中哪些活动，即哪些项目是主要的，是影响工程进度的关键，从而让我们对工程的实施作出更好的时间安排，并且可以分清主次，抓住核心工程，做到有的放矢。总的来说，正因为关键路径可以帮助我们对工

7、程进行非常有必要的估算，让我们得以看清全局，作出更为优化的安排，所以可见关键路径的求出对一项工程而言是非常必要的。这亦是本次对关键路径求法的研究意义所在。-1-数据结构程序设计2需求分析2．1问题描述（1）选取建图的一种算法建立图，有邻接矩阵，邻接表，十字链表，邻接多重表等多种方法，要选取一种适当的方法建立图，才能提高算法效率，降低时间复杂度和空间复杂度。（2）两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间。对于给出的事件AOE网络，要求求出从起点到终点的所有路径，经分析、比较后找出长读最大的路径，从而得出求关键路径的算法，并给出

8、计算机上机实现的源程序。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。具体要解