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

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

ID:36042582

大小:286.00 KB

页数:17页

时间:2019-05-02

c++实现关键路径算法课程设计报告_第1页
c++实现关键路径算法课程设计报告_第2页
c++实现关键路径算法课程设计报告_第3页
c++实现关键路径算法课程设计报告_第4页
c++实现关键路径算法课程设计报告_第5页
资源描述:

《c++实现关键路径算法课程设计报告》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

1、word完美格式计算机与软件工程学院课程设计说明书课程名称:数据结构与算法课程设计课程代码:题目:年级/专业/班:学生姓名:学  号:开始时间:2013年12月18日完成时间:2013年12月28日课程设计成绩:学习态度及平时成绩(20)技术水平与实际能力(20)完成情况(20)创新(5)说明书(计算书、图纸、分析报告)撰写质量(35)总分(100)指导教师签名:年月日精心整理学习帮手word完美格式目录引言11需求分析11.1任务与分析11.2测试数据12概要设计32.1设计思路32.2层次图33详细设计43.1主函数的实现43.2数据录入实现53.3输出图的各顶点和弧的

2、实现63.4计算各顶点的入度73.5输出关键路径74调试分析85用户使用说明96测试结果96.1录入数据96.2功能实现96.3测试结论11致谢13参考文献14精心整理学习帮手word完美格式摘要具有最大路径长度的路径称关键路径,关键路径上的活动称关键活动。课程设计主要要求求有向图的关键路径。用领接表存储结构储存有向图。用深度遍历的方式输出有向图的顶点和弧。程序实现了存储有向图,输出有向图的各顶点和弧,计算顶点的入度和求有向图的关键路径这四个功能。用领接表存储结构储存有向图,用深度遍历的方式输出有向图的顶点和弧,用遍历查找的方式计算顶点的入度。求关键路径时先用拓扑排序函数判

3、断有向图是否有回路,调用求关键活动的函数找到关键路径,最后输出。关键词:领接表;入度;AOE网;关键路径;精心整理学习帮手word完美格式引言工程有很多的阶段,这些阶段之间有一定的先后关系和自己的时间。我们可以用图来表示工程,将其输入程序中,可以用程序计算出工程的相关信息,如,工程完成的最短时间,哪些活动会影响工程的进度等。要解决这些问题就可以用领接表储存图,并计算各个事件和各个阶段的最早发生时间和最晚发生时间,得到关键活动,从而的到关键路径。1需求分析从键盘上输入图的各顶点和弧上的权值,用领接表储存。在屏幕上输出图的顶点和弧。计算输出顶点的入度。如果图是AOE网,输出关键

4、路径。1.1任务与分析1、首先定义边节点和顶点的结构体,将输入的数据用链接表储存起来,领接表即是顺序+链式的存储方式。将顶点顺序储存,将该顶点为起点的弧指向的另一顶点及其相关信息存储在链表中。2、采用深度遍历的方式,输出顶点和弧。3、判断顶点是否在弧尾,在弧尾就在入度的计数变量上加一。4、首先要将图进行拓扑排序,看是否有回路,没有回路才能求关键路径。求AOE网的关键路径要先求到各个事件的最早发生时间和最迟发生时间,再求有向边的最早和最迟发生时间,活动的最晚发生时间和最早发生时间相减等于0时,该活动即为关键活动,再将关键活动按顺序连起来极为关键路径。1.2测试数据带权有向图测

5、试数据如下:测试数据1如图1-1:精心整理学习帮手word完美格式图1-1测试图1测试数据2如图1-2:图1-2测试图2测试数据3如图1-3:图1-2测试图3精心整理学习帮手word完美格式2概要设计2.1设计思路程序分总的来说分为四大功能模块:输入储存;输出顶点和弧;输出各顶点的入度;输出关键路径。在输出关键路径的模块中包括:拓扑排序判断是否有回路;计算各事件的最早发生时间和最晚发生时间;求活动的最晚发生时间,判断该活动是否是关键活动;输出关键路径。首先调用输入存储模块创建图,用菜单工作的方式来实现对各个输出功能模块的调用。输入储存:ALGraph::ALGraph

6、(Ta[],intn,inte)输出顶点和弧:voidPrint();输出各顶点的入度:voidindegree();输出关键路径:voidcritical_path(ALGraphG);输出关键路径模块中的子模块:拓扑排序:voidTopSort(ALGraphG);事件的时间:voidvv(ALGrapphG);判断是否是关键活动:voidkeyEvent(ALGraphG);2.2层次图各模块间的层次如图2-1:精心整理学习帮手word完美格式图2-1各模块间的层次图3详细设计3.1主函数的实现首先输入图的顶点的个数和边的个数,程序通过输入的数来判断要创建的图的大小,

7、调用图的构造函数,输入图的相关信息。之后,为了方便用户操作,用工作菜单的方式来实现对各个功能的调用。voidmain(){intn,e;intchoose=1;//控制intwhich;//功能选择变量string*vname;//[MaxSize];cout<<"请输入图的顶点数:";cin>>n;while(n<0

8、

9、n>20){cout<<"顶点个数应在-20之间!请重新输入!"<>n;}cout<<"请输入图的边数:";cin>>e;while(e<0){cout<<"您输入的顶点个数小

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。