数据结构——求关键路径

1、ANHUI UNIVERSITY OF SCIENCE & TECHNOLOGY数据结构课 程设计说明书基于AOE网络的关键路径问题学院（部）： 计算机科学与工程学院专业班级：学 号：学生姓名： 指导教师： 安徽理工大学课程设计（论文）任务书计算机科学与工程学院学号学生姓名专业（班级）设计题目设计技术参数（1 ）用C+或C语言实现设计任务；（2 ）所设计的程序可读性好，执行效率高；（3）有良好的操作界面；（4）设计说明书能很好地反映设计内容设 计 要 求 要求输入使用教材图7.29，将数据存放在origin .txt，直接读出；（2）将项目中的各项活动视为有一个时间属性的结点，用有方向的线段标

2、出各结点的紧前活动和紧后活动的关系，使之成为一个有方向的网络图，在界面中输出；（3）用正推法和逆推法计算出各个活动的最早开始时间，最晚开始 时间，最早完工时间和最迟完工时间，并计算出各个活动的时差，分别 输出顶点表和活动表，参图7.31 o（4）找出所有时差为零的活动所组成的路线，即为关键路径，并在 图中描红；（5）使用MFC编制图形界面，界面友好，易与操作。采用菜单方式 进行选择。工 作 量课程设计报告要求不少于 3000字。源程序要求不少于 300行工 作 计 划2014.12.06-12.12根据课程设计大纲的要求，查找相关资料，完成需求分析；2014.12.13-12.15进行系统的概

3、要设计；2014.12.16-12.31进行系统的详细设计和源代码的书写；2015.01.01-01.11对系统进行调试分析，写出课程设计报告。参 考 资 料1 谭浩强编著.C程序设计（第二版）.北京：清华大学出版社，1999.2 严蔚敏，吴伟民编著.数据结构（C语言版）北京：清华大学出版社,2002.指导教师签字教研室主任签字2014年11月20日安徽理工大学课程设计（论文）成绩评定表学生姓名： 杜争争 学号：2013303012专业班级：物联网13-1课程设计题目：基于AOE网络的关键路径问题指导教师评语:成绩：指导教师：目录1、需求分析 1.1.1 引言 11.2 算法分析 12、总体设

4、计 3.2.存储结构设计 33、详细设计 5.3.1 结构 5.3.2 测试 5.4、总结 8.4.1 收获84.2 不足 8参考文献 9.1 需求分析1.1 引言两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间。对于给出的事件 AOE网络，要求求出从起 点到终点的所有路径， 经分析、 比较后找出长度最大的路径， 从而得出求关键路径的算法，并给出计算机上机实现的源程 序。完成不同路径的活动所需的时间虽然不同，但只有各条 路径上所有活动都完成了，这个工程才算完成。1.2 算法分析：（ 1）求关键路径必须在拓扑排序的前提下进行，有环图不能求 关键路径；（2）只有缩短关键活动的工期才

5、有可能缩短工期；（ 3）若一个关键活动不在所有的关键路径上，减少它并不能减 少工期；（ 4） 只有在不改变关键路径的前提下，缩短关键活动才能缩短 整个工期。（ 5）关键路径 ：从源点到汇点的路径长度最长的路径叫关键路 径。（ 6）活动开始的最早时间 e（i）；7)活动开始的最晚时间 l(i) ；8)定义 e(i)=l(i) 的活动叫关键活动；9)事件开始的最早时间 ve(i) ；10 ) 事 件 开 始 的 最 晚 时 间 vl(i)2总体设计程序流程图定义的2.1存储结构设计对于带权有向图构造的 结构体如下：typedef struct node /int adjvex; /int dut;

6、 / struct node *n ext; /AOE网，采用链式存储结构，定义表结点该弧所指向的顶点的位置弧的权值指向下一条弧的指针定义头结点顶点信息结点入度指向第一条依附该顶点的弧的指edgenode;typedef struct /int projectname; / int id; / edgenode *link; / 针vexnode;3详细设计 3.1结构(1) 创建图的函数(2) 求出最大路径，并打印出关键路径的函数(3) 球关键路径的函数(4) 主函数3.2测试(1 )开始界面(2)回路测试屯応程序设计轴勺送计1卅H-豐节SISStS违麒务用了 *个单位时间不-路息吿“ 丁

7、茁的篁 车 工工始回Trff 9 送的4,. ./冃 5 4-:眾鑒肓- S - 的- 亠肖 建程盘 所本程意 曇王任 蕭个按(3)课本上图7.29的程序测试28整个工程.16148 :7!9 :1S!鸟g短由间为个单血时间幘皱入这T工聲创图羽的龙点数汗怩W回车亲示當三节点到第四节点之间的制用了9个单位时间 肛2花最早开始时间!最迟完成时间丨差値丨备注a!3:3:aI2:2:aI:o:关键E,?,5,8,77,9.2 切上I巔!终点 E: I匚程序设计.De bu g没计1，际求的关键路径为4、总结.（1）收获通过这次实训，使我学到了很多。由于对标准 C 语言缺 乏深入的学习，致使我在编程中遇

8、到了很多困难，但在攻克 困难的过程中提高了自己的自学能力，分析问题及解决问题 的能力、熟练运用理论知识的能力。同时，让我更深入的掌 握了有关 AOE 网表示工程计划及关键路径问题等方面的知 识，巩固了所学内容。（2）不足这次实训也让我认识到了自己在很多方面的不足之处。 首先， 我的基础知识掌握的不很牢固， 以至于在编程的时候， 遇到了一些不必要的问题。其次，我认识到了自己对算法的应用上还有欠缺，虽然 我们学习了很多算法，而且我也了解掌握了一些经典的算法 的思想，但在具体编程时，却明显感觉到自己在编程方面的 不足，知识运用不够灵活。因此，在以后的学习中我会加强 自己的实战能力，克服眼高手低的习惯。参考文献1 严蔚敏，吴伟民 .数据结构 . 北京：清华大学出版社， 2006.2 谭浩强 . C 程序设计（第二版）作者： 清华大学出版社， 20063 夏克俭编著 .数据结构 .北京: 国防工业出版社， 2000.74 彭勃.数据结构. 北京: 电子工业出版社， 20