数据结构——求关键路径

数据结构课程设计说明书基于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日安徽理工大学课程设计（论文）成绩评定表学生姓名：杜争争学号：2013303012专业班级：物联网13-1课程设计题目：基于AOE网络的关键路径问题指导教师评语：成绩：指导教师：年月日I目录1、需求分析..................................................................................................................11.1引言...................................................................................................................11.2算法分析...........................................................................................................12、总体设计..................................................................................................................32.存储结构设计.....................................................................................................................33、详细设计..................................................................................................................53.1结构.................................................................................................................53.2测试..................................................................................................................54、总结..........................................................................................................................84.1收获.....................................................................................................................................84.2不足.....................................................................................................................................8参考文献........................................................................................................................911需求分析1.1引言两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间。对于给出的事件AOE网络，要求求出从起点到终点的所有路径，经分析、比较后找出长度最大的路径，从而得出求关键路径的算法，并给出计算机上机实现的源程序。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。1.2算法分析：（1）求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；（2）只有缩短关键活动的工期才有可能缩短工期；（3）若一个关键活动不在所有的关键路径上，减少它并不能减少工期；（4）只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。（5）关键路径：从源点到汇点的路径长度最长的路径叫关键路径。（6）活动开始的最早时间e(i)；2（7）活动开始的最晚时间l(i)；（8）定义e(i)=l(i)的活动叫关键活动；（9）事件开始的最早时间ve(i)；（10）事件开始的最晚时间vl(i)。32总体设计程序流程图2..1存储结构设计对于带权有向图构造的AOE网，采用链式存储结构，定义的结构体如下：typedefstructnode//定义表结点{intadjvex;//该弧所指向的顶点的位置intdut;//弧的权值structnode*next;//指向下一条弧的指针4}edgenode;typedefstruct//定义头结点{intprojectname;//顶点信息intid;//结点入度edgenode*link;//指向第一条依附该顶点的弧的指针}vexnode;53详细设计3.1结构（1）创建图的函数（2）求出最大路径，并打印出关键路径的函数（3）球关键路径的函数（4）主函数3.2测试（1）开始界面6（2）回路测试（3）课本上图7.29的程序测试7求的关键路径为：84、总结.（1）收获通过这次实训，使我学到了很多。由于对标准C语言缺乏深入的学习，致使我在编程中遇到了很多困难，但在攻克困难的过程中提高了自己的自学能力，分析问题及解决问题的能力、熟练运用理论知识的能力。同时，让我更深入的掌握了有关AOE网表示工程计划及关键路径问题等方面的知识，巩固了所学内容。（2）不足这次实训也让我认识到了自己在很多方面的不足之处。首先，我的基础知识掌握的不很牢固，以至于在编程的时候，遇到了一些不必要的问题。其次，我认识到了自己对算法的应用上还有欠缺，虽然我们学习了很多算法，而且我也了解掌握了一些经典的算法的思想，但在具体编程时，却明显感觉到自己在编程方面的不足，知识运用不够灵活。因此，在以后的学习中我会加强自己的实战能力，克服眼高手低的习惯。9参考文献[1]严蔚敏，吴伟民.数据结构.北京：清华大学出版社，2006.[2]谭浩强.C程序设计（第二版）作者：清华大学出版社，2006[3]夏克俭编著.数据结构.北京:国防工业出版社，2000.7[4]彭勃.数据结构.北京:电子工业出版社，2007.6[5]宜晨编著.VisualC++5.0实用培训教程.北京：电子工业出版社，1998.5[6]崔武子.C语言程序设计实践教程.北京:清华大出版社,2006.1[7]庞振平.计算机程序设计基础.广州:华南理工出版社，2002.9