logo资料库

拓扑排序和关键路径课设.docx

发布时间：2022-06-12 发布人：admin 分类：说明书 资料大小：0.71M 资料格式：docx 举报 版权申诉
第1页 / 共26页
第2页 / 共26页
第3页 / 共26页
第4页 / 共26页
第5页 / 共26页
第6页 / 共26页
第7页 / 共26页
第8页 / 共26页
资料共26页，剩余部分请下载后查看
    1.设计任务书
    1.1设计任务
    1.2程序功能
    1.3运行环境
    2.本组课题
    2.1课题
    2.2本人任务
    3.程序功能简介
    3.1拓扑排序算法分析
    3.2关键路径算法分析
    4.功能实现分析
    4.1拓扑排序功能
    4.1.1具体实例
    4.1.2程序流程图
    4.1.3关键代码
    4.2关键路径功能
    4.2.1具体实例
    4.2.2程序流程图
    4.2.3关键代码
    4.3设计过程浅谈
    4.4源代码
    4.4.1拓扑排序
    4.4.2拓扑排序程序运行截图
    4.4.3关键路径
    4.4.4关键路径程序运行截图
    附件 1 XI`AN TECHNOLOGICAL UNIVERSITY 实验报告 实验课程名称 算法与数据结构课程设计 专 班 姓 学 业： 软件工程 级： 17060209 名： 杨路恒 号： 17060209117 指导教师： 潘煜 成 绩： 2019 年 1 月 1 日
    西安工业大学实验报告 专业 软件工程 班级 17060209 117 姓名 杨路恒 学号 170602091 17 算法与数据结构 课程设计 指导教师 潘煜 实验日期 2019.1. 1 同实验者 杨路恒 用代码实现拓扑排序和关键路径 计算机、课本 实验课程 实验项目 实验设备 及器材 目录 1. 设计任务书.......................................................................................................................................................3 1.1 设计任务 ..............................................................................................................................................................................3 1.2 程序功能 ..............................................................................................................................................................................3 1.3 运行环境 ..............................................................................................................................................................................3 2. 本组课题........................................................................................................................................................... 3 2.1 课题 ...................................................................................................................................................................................... 3 2.2 本人任务 ..............................................................................................................................................................................3 3.程序功能简介.......................................................................................................................................................4 3.1 拓扑排序算法分析 ............................................................................................................................................................. 4 3.2 关键路径算法分析 ............................................................................................................................................................. 4 4.功能实现分析.......................................................................................................................................................5 4.1 拓扑排序功能 ......................................................................................................................................................................5 4.1.1 具体实例.......................................................................................................................................................................................... 5 4.1.2 程序流程图......................................................................................................................................................................................6 4.1.3 关键代码.......................................................................................................................................................................................... 6 4.2 关键路径功能 ......................................................................................................................................................................7 1
    4.2.1 具体实例.......................................................................................................................................................................................... 7 4.2.2 程序流程图......................................................................................................................................................................................7 4.2.3 关键代码.......................................................................................................................................................................................... 8 4.3 设计过程浅谈 ................................................................................................................................................................... 10 4.4 源代码 ................................................................................................................................................................................11 4.4.1 拓扑排序 ........................................................................................................................................................................ 11 4.4.2 拓扑排序程序运行截图 ............................................................................................................................................... 18 4.4.3 关键路径 ........................................................................................................................................................................ 18 4.4.4 关键路径程序运行截图 ............................................................................................................................................... 25 2
    1.设计任务书 1.1 设计任务 阅读了《数据结构(C 语言)》的经典著作后，学习了有关简单算法的实现，认识到数学可 以应用到各个领域。本次算法课程设计运用所学的图论的拓扑排序和关键路径，去实现工程 中的花费时间和顺利进行问题。拓扑排序主要用于检验工程能否施工，关键路径主要用于看 出工程施工时间消耗。 1.2 程序功能 本程序可以对给定输入的图进行拓扑排序以及利用拓扑排序的到的序列进行关键路径的 求解，程序采用 C 语言代码实现，用到链表、图论等相关知识构成。 1.3 运行环境 运行系统：Windows 10、Centos 7; 运行环境：C; 编译环境：CodeBlocks、Sublime Text 3； 2.本组课题 2.1 课题 编写数据结构广泛使用拓扑排序和关键路径算法。 2.2 本人任务 使用代码实现拓扑排序，进而利用拓扑排序得到的序列球的关键路径。 3
    3.程序功能简介 3.1 拓扑排序算法分析 用顶点表示活动，用弧表示活动间的优先关系的有向图为 AOV 网。 AOV 网中没有环，检测的办法是进行拓扑排序。 步骤： (1)在有向图中选一个没有前驱的顶点且输出之。 (2)从图中删除该顶点和所有以它为尾的弧。 重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。另一种情 况则说明有向图中存在环。 3.2 关键路径算法分析 与 AOV 网对应的是 AOE 网，即用边表示活动的网，AOE 网是一个带权的有向无环图，顶点 表示事件，弧表示活动，权表示活动持续的时间。通常用 AOE 网估计工程的完成时间。 由于在 AOE 网中有些活动可以并行的进行，所以完成工程的最短时间是从开始点到完成点 的最长路径的长度。路径最长的叫关键路径，我们用 e(i)表示活动最早开始时间，l(i)表示最 迟开始时间。两者之差 l(i)一 e(i)意味着完成活动 a 的时间余量。我们把 l(i)=e(i)的活动叫做 关键活动。显然;关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加 快工程的进度。 4
    4.功能实现分析 4.1 拓扑排序功能 4.1.1 具体实例 1 4 6 1 4 6 1 4 2 3 5 4 2 3 5 2 3 5 2 5 5 实例所示为拓扑排序过程。 最终得到的拓扑序列：V1-V6-V4-V3-V2-V5 5
    图 的 基 本 操作 4.1.2 程序流程图 图的邻接存 储 TopologicalSo rt(ALGraph G) 得 到 拓 扑 序列 4.1.3 关键代码 Status TopologicalSort(ALGraph G) { /* 有向图 G 采用邻接表存储结构。若 G 无回路,则输出 G 的顶点的一个拓扑序列并返回 OK, */ /* 否则返回 ERROR。算法 7.12 */ int i,k,count,indegree[MAX_VERTEX_NUM]; SqStack S; ArcNode *p; FindInDegree(G,indegree); /* 对各顶点求入度 indegree[0..vernum-1] */ InitStack(&S); /* 初始化栈 */ for(i=0;inextarc) { /* 对 i 号顶点的每个邻接点的入度减 1 */ k=p->adjvex; if(!(--indegree[k])) /* 若入度减为 0,则入栈 */ Push(&S,k); } } if(count
    printf("此有向图有回路\n"); return ERROR; } else { printf("为一个拓扑序列。\n"); return OK; } } 4.2 关键路径功能 4.2.1 具体实例 4.2.2 程序流程图 图的邻接表 栈操作 7
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料