数据结构——求关键路径(共14页).doc
精选优质文档-倾情为你奉上数据结构课程设计说明书基于AOE网络的关键路径问题学院（部）： 计算机科学与工程学院 专业班级： 学 号： 学生姓名： 指导教师： 年 月 日安徽理工大学课程设计（论文）任务书 计算机科学与工程 学院 学 号学生姓名专业（班级）设计题目 设计技术参数（1）用C+或C语言实现设计任务；（2）所设计的程序可读性好，执行效率高；（3）有良好的操作界面；（4）设计说明书能很好地反映设计内容设计要求(1) 要求输入使用教材图7.29，将数据存放在origin.txt，直接读出；(2) 将项目中的各项活动视为有一个时间属性的结点，用有方向的线段标出各结点的紧前活动和紧后活动的关系，使之成为一个有方向的网络图，在界面中输出；(3) 用正推法和逆推法计算出各个活动的最早开始时间，最晚开始时间，最早完工时间和最迟完工时间，并计算出各个活动的时差，分别输出顶点表和活动表，参图7.31。 (4) 找出所有时差为零的活动所组成的路线，即为关键路径，并在图中描红；(5) 使用MFC编制图形界面，界面友好，易与操作。采用菜单方式进行选择。工作量课程设计报告要求不少于3000字。源程序要求不少于300行工作计划2014.12.06-12.12 根据课程设计大纲的要求，查找相关资料，完成需求分析；2014.12.13-12.15 进行系统的概要设计；2014.12.16-12.31 进行系统的详细设计和源代码的书写；2015.01.01-01.11 对系统进行调试分析，写出课程设计报告。参考资料1谭浩强编著.C程序设计（第二版）.北京：清华大学出版社,1999.2严蔚敏,吴伟民编著.数据结构（C语言版）北京：清华大学出版社,2002.指导教师签字教研室主任签字 2014年 11 月 20 日 学生姓名： 杜争争 学号： 专业班级： 物联网13-1 课程设计题目： 基于AOE网络的关键路径问题 指导教师评语： 成绩： 指导教师： 年 月 日安徽理工大学课程设计（论文）成绩评定表专心-专注-专业目录1、需求分析1 1.1 引言.1 1.2 算法分析.12、 总体设计3 2.存储结构设计.33、详细设计53.1 结构53.2测试54、 总结8 4.1收获.8 4.2不足.8参考文献9 1 需求分析1.1 引言 两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间。对于给出的事件AOE网络，要求求出从起点到终点的所有路径，经分析、比较后找出长度最大的路径，从而得出求关键路径的算法，并给出计算机上机实现的源程序。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。1.2算法分析： （1） 求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径； （2） 只有缩短关键活动的工期才有可能缩短工期； （3） 若一个关键活动不在所有的关键路径上，减少它并不能减少工期； （4） 只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。 （5） 关键路径 ：从源点到汇点的路径长度最长的路径叫关键路径。 （6） 活动开始的最早时间e(i)； （7） 活动开始的最晚时间l(i)； （8） 定义e(i)=l(i)的活动叫关键活动； （9） 事件开始的最早时间ve(i)； （10）事件开始的最晚时间vl(i)。2 总体设计程序流程图2.1存储结构设计对于带权有向图构造的AOE网，采用链式存储结构，定义的结构体如下：typedef struct node /定义表结点 int adjvex; /该弧所指向的顶点的位置 int dut; /弧的权值 struct node *next; /指向下一条弧的指针 edgenode; typedef struct /定义头结点 int projectname; /顶点信息 int id; /结点入度 edgenode *link; /指向第一条依附该顶点的弧的指针vexnode; 3 详细设计3.1 结构 （1） 创建图的函数 （2） 求出最大路径，并打印出关键路径的函数 （3） 球关键路径的函数 （4） 主函数3.2测试（1） 开始界面（2）回路测试（3） 课本上图7.29的程序测试求的关键路径为：4、总结.（1）收获通过这次实训，使我学到了很多。由于对标准C语言缺乏深入的学习，致使我在编程中遇到了很多困难，但在攻克困难的过程中提高了自己的自学能力，分析问题及解决问题的能力、熟练运用理论知识的能力。同时，让我更深入的掌握了有关AOE网表示工程计划及关键路径问题等方面的知识，巩固了所学内容。（2）不足这次实训也让我认识到了自己在很多方面的不足之处。首先，我的基础知识掌握的不很牢固，以至于在编程的时候，遇到了一些不必要的问题。其次，我认识到了自己对算法的应用上还有欠缺，虽然我们学习了很多算法，而且我也了解掌握了一些经典的算法的思想，但在具体编程时，却明显感觉到自己在编程方面的不足，知识运用不够灵活。因此，在以后的学习中我会加强自己的实战能力，克服眼高手低的习惯。参考文献1 严蔚敏，吴伟民.数据结构. 北京：清华大学出版社，2006.2 谭浩强. C程序设计（第二版）作者：清华大学出版社，20063 夏克俭编著.数据结构.北京: 国防工业出版社，2000.7 4 彭勃.数据结构.北京: 电子工业出版社，2007.6 5 宜晨编著.Visual C+5.0实用培训教程.北京：电子工业出版社，1998.56 崔武子.C语言程序设计实践教程.北京:清华大出版社, 2006.1 7 庞振平.计算机程序设计基础.广州: 华南理工出版社，2002.9
