c实现关键路径算法课程设计报告.docVIP

有向图的关键路径 有向图的关键路径 计算机与软件工程学院 课程设计说明书 课 程 名 称: 数据结构与算法课程设计 课 程 代 码: 题 目: 年级/专业/班: 学 生 姓 名: 学　　 号: 开 始 时 间: 2013 年 12 月 18 日 完 成 时 间: 2013 年 12 月 28 日 课程设计成绩： 学习态度及平时成绩（20） 技术水平与实际能力（20） 完成情况(20) 创新（5） 说明书（计算书、图纸、分析报告）撰写质量（35） 总 分（100） 指导教师签名： 年 月 日 目 录 TOC \o 1-2 \h \u HYPERLINK \l _Toc20097 引 言 PAGEREF _Toc20097 1 HYPERLINK \l _Toc24802 1需求分析 PAGEREF _Toc24802 1 HYPERLINK \l _Toc13286 1.1任务与分析 PAGEREF _Toc13286 1 HYPERLINK \l _Toc21459 1.2测试数据 PAGEREF _Toc21459 1 HYPERLINK \l _Toc17102 2 概要设计 PAGEREF _Toc17102 3 HYPERLINK \l _Toc31885 2.1设计思路 PAGEREF _Toc31885 3 HYPERLINK \l _Toc8815 2.2层次图 PAGEREF _Toc8815 3 HYPERLINK \l _Toc16857 3 详细设计 PAGEREF _Toc16857 4 HYPERLINK \l _Toc20763 3.1主函数的实现 PAGEREF _Toc20763 4 HYPERLINK \l _Toc14536 3.2数据录入实现 PAGEREF _Toc14536 5 HYPERLINK \l _Toc26518 3.3输出图的各顶点和弧的实现 PAGEREF _Toc26518 6 HYPERLINK \l _Toc30494 3.4计算各顶点的入度 PAGEREF _Toc30494 7 HYPERLINK \l _Toc19552 3.5输出关键路径 PAGEREF _Toc19552 7 HYPERLINK \l _Toc31229 4调试分析 PAGEREF _Toc31229 8 HYPERLINK \l _Toc32298 5用户使用说明 PAGEREF _Toc32298 9 HYPERLINK \l _Toc19203 6测试结果 PAGEREF _Toc19203 9 HYPERLINK \l _Toc5897 6.1录入数据 PAGEREF _Toc5897 9 HYPERLINK \l _Toc7989 6.2功能实现 PAGEREF _Toc7989 9 HYPERLINK \l _Toc30244 6.3测试结论 PAGEREF _Toc30244 11 HYPERLINK \l _Toc18032 致 谢 PAGEREF _Toc18032 13 HYPERLINK \l _Toc11247 参考文献 PAGEREF _Toc11247 14 摘 要 具有最大路径长度的路径称关键路径，关键路径上的活动称关键活动。课程设计主要要求求有向图的关键路径。用领接表存储结构储存有向图。用深度遍历的方式输出有向图的顶点和弧。程序实现了存储有向图，输出有向图的各顶点和弧，计算顶点的入度和求有向图的关键路径这四个功能。用领接表存储结构储存有向图，用深度遍历的方式输出有向图的顶点和弧，用遍历查找的方式计算顶点的入度。求关键路径时先用拓扑排序函数判断有向图是否有回路，调用求关键活动的函数找到关键路径，最后输出。 关键词：领接表；入度；AOE网；关键路径； PAGE PAGE 33 引 言 工程有很多的阶段，这些阶段之间有一定的先后关系和自己的时间。我们可以用图来表示工程，将其输入程序中，可以用程序计算出工程的相关信息，如，工程完成的最短时间，哪些活动会影响工程的进度等。要解决这些问题就可以用领接表储存图，并计算各个事件和各个阶段的最早发生时间和最晚发生时间，得到关键活动，从而的到关键路径。 1需