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

《C实现关键路径算法课程设计报告》由会员分享，可在线阅读，更多相关《C实现关键路径算法课程设计报告（18页珍藏版）》请在装配图网上搜索。

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

2、用户使用说明96测试结果96.1录入数据96.2功能实现106.3测试结论11致谢13参考文献14摘要具有最大路径长度的路径称关键路径，关键路径上的活动称关键活动。 课程设计主要要求求有向图的关键路径。用领接表存储结构储存有向图。 用深度遍历的方式输出有向图的顶点和弧。程序实现了存储有向图，输出 有向图的各顶点和弧，计算顶点的入度和求有向图的关键路径这四个功能。 用领接表存储结构储存有向图，用深度遍历的方式输出有向图的顶点和弧， 用遍历查找的方式计算顶点的入度。求关键路径时先用拓扑排序函数判断 有向图是否有回路，调用求关键活动的函数找到关键路径，最后输出。关键词：领接表；入度；AOE网；关键路

3、径;引言工程有很多的阶段，这些阶段之间有一定的先后关系和自己的时间。我们可 以用图来表示工程，将其输入程序中，可以用程序计算出工程的相关信息，如， 工程完成的最短时间，哪些活动会影响工程的进度等。要解决这些问题就可以用 领接表储存图，并计算各个事件和各个阶段的最早发生时间和最晚发生时间，得 到关键活动，从而的到关键路径。1需求分析从键盘上输入图的各顶点和弧上的权值，用领接表储存。在屏幕上输出图的 顶点和弧。计算输出顶点的入度。如果图是AOE网，输出关键路径。1.1任务与分析1、首先定义边节点和顶点的结构体，将输入的数据用链接表储存起来，领 接表即是顺序+链式的存储方式。将顶点顺序储存，将该顶点

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

5、分总的来说分为四大功能模块：输入储存；输出顶点和弓瓜；输出各顶点 的入度；输出关键路径。在输出关键路径的模块中包括：拓扑排序判断是否有回 路；计算各事件的最早发生时间和最晚发生时间；求活动的最晚发生时间，判断 该活动是否是关键活动；输出关键路径。首先调用输入存储模块创建图，用菜单工作的方式来实现对各个输出功能模 块的调用。输入储存：ALGraph:ALGraph(T a , int n, int e)输出顶点和弓瓜：void Print();输出各顶点的入度：void indegree()；输出关键路径：void critical_path(ALGraph G)；输出关键路径模块中的子模块：拓

6、扑排序：void TopSort(ALGraph G);事件的时间：void vv(ALGrapph G);判断是否是关键活动：void keyEvent(ALGraph G);2.2层次图各模块间的层次如图2-1：图2-1各模块间的层次图3详细设计3.1主函数的实现首先输入图的顶点的个数和边的个数，程序通过输入的数来判断要创建的图 的大小，调用图的构造函数，输入图的相关信息。之后，为了方便用户操作，用 工作菜单的方式来实现对各个功能的调用。void main()(int n,e;int choose=1;/控制int which;/功能选择变量string *vname;/MaxSize;c

7、outn;while(n20)(cout顶点个数应在-20之间！请重新输入！ n;coute;while(e0)(cout您输入的顶点个数小于零！请重新输入！ e;vname二new stringn;cout请输入顶点：； for(int j=0;jvnamej;ALGraph g(vname, n, e);while(choose=1) (coutendl; coutn1*输出该有有向图的个顶点和孤一*；coutn2*计算各顶点的入度*;coutn3*计算AOE网的关键路径*;coutn4* 退出-*endl;coutwhich; switch(which) ( case 1:g.Print

8、(); break; case 2:g.indegree(); break; case 3:g.critical_path(); break; case 4: choose=0; break; 3.2数据录入实现定义边表节点和顶点表节点。 struct ArcNode (int adjvex,weight;ArcNode *next;template struct VertexNode (T vertex; int in;ArcNode *firstedge;用构造函数实现数据的录入，录入时根据程序的提示录入数据。ALGraph:ALGraph(T a , int n, int e)(vert

9、exNum=n;arcNum=e;int i,j,k,w;for (i=0; ivertexNum; i+)(adjlisti.vertex=ai;adjlisti.firstedge二NULL;for (k=0; karcNum; k+)(cout请输入图中孤的起始点及权值：其格式为；cinijw;ArcNode *s;s=new ArcNode;s-adjvex=j;s-weight=w;s-next=adjlisti.firstedge;adjlisti.firstedge=s; 3.3输出图的各顶点和弧的实现对图进行深度遍历，输出顶点和弓瓜。void ALGraph:Print()/输

10、出有向图的个顶点和弓瓜(for(int i=0;ivertexNum;i+)(ArcNode *p;p=adjlisti.firstedge;while(p) (coutadjlisti.vertex;int j;j=p-adjvex;coutadjlistj.vertext权值：weightnext;3.4计算各顶点的入度用双重循环，外层循环找到各个顶点，内层循环计算有几条孤指向外层循环 中的顶点，用累加器累加，最后累加器得到的数就是该顶点的入度。void ALGraph:indegree() /输出每个顶点的入度(ArcNode *p;int count;for(int i=0;ivert

11、exNum;i+)(count=0;for(int j=0;jadjvex=i) count+;p=p-next;else continue;adjlisti.in=count;coutadjlisti.vertex的入度为：adjlisti.inendl;3.5输出关键路径首先，调用拓扑排序判断有向图中是否回路，有回路不能求关键路径，没有 回路则求关键路径。先调用vv函数求顶点的最早发生时间和最迟发生时间，在 调用keyEvent函数找到关键活动，再将关键路径串起来输出。void ALGraph:critical_path()(int tsMaxSize,veMaxSize,vlMaxSiz

12、e;if (TopSort(ts)=0)(cout有关键路径！ endl;int k,v;k=ts0;vv(ve,vl,ts);keyEvent(ve,vl,ts);cout关键路径：endl;coutadjlistk.vertex;for (int i=0;i10;i+)(if (evi.v1=k)(v=evi.v2;coutadjlistv.vertex;k=evi.v2;coutendl;else(cout，没有关键路径！ next语句导致出现了死循环。在while 循环中加上P=P-next语句。5用户使用说明按照提示输入数据后，在菜单出现后，从键盘输入功能的编号就可以实现不 同的功能

13、。简单，方便，易操作。6测试结果用测试数据1进行测试。6.1录入数据从键盘上输入顶点的个数，边的条数，再根据提示输入顶点、边、权值，用 领接表来进行储存。如图6-1所示：645112974241234456778800012344567占罟罟罟罟罟罟罟罟罟罟g终终终终终终终终终终终占罟罟罟罟罟罟罟罟罟罟g 己-己-己-己-己-己-己-己-己-己-己- 8 一 T-JT-JT-JT-JT-JI1-JI1-JI1-JI1-JI1-JI1S=. 占 U0 而抒L.T1h1.T1h1.T1h1.T1h1.T1h1.T1h1.T1h1.T1h1.T1h1.T1h1.T1h1. TJ .1/: P-T?

14、P-T? P-T? P-T? P-T? P-T? P-T? P-T? P-T? P-T? P-T? 的占 g 口 口口口口口口口口口口 图图顶图图图图图图图图图图图 R入入入入入入入入入入入入入 -._ 刖 刖 刖 刖 刖 刖 刖 刖 刖 刖 刖 刖 刖 刖5 苴aaaaCH苴a苴aCH uu2占罟罟罟罟罟罟罟罟罟罟5 1A口A口A口A口A口A口A口A口A口A口A口 II:日-日-日-日-日-日 _图6-1录入存储6.2功能实现根据菜单选择功能。测试输出各顶点和孤的功能，结果如图6-2所示。新世咨有有厦图里个顶点和弧一 g景A0备耘二二二 j 艮出XXXXX X0 12 3 4 4 53214

15、45767uuuuuuuuuRRRR根成RRRRR54611279424图6-2输出顶点和孤测试计算各顶点的入度功能，结果如图6-3所示。2叩的入度为：0 ”的入度为：1 叫的入度为：1 忡的入度为：1 U4的入度为：2 帕的入度为:1 g的入度为：1 四的入度为：2 M的入度为：2JCNNXNJCNNXNNXXXXXXXXXXXXXX输出该有有向图的个顶点和弧一* 5荏2 MMMMMM图6-3计算各顶点的入度测试计算AOE网的关键路径的功能，结果如图6-4所示。La b*t待出童有有厦图里个顶点和弧 寸昼岛总二二二 j艮出xxxxx xXXXXXX:MNJCJCXN3U3 U5 U7 U8

16、有关键路径!的扑排序：U0 U1 U2 U4 U6国键路径：W0-U1-U4-U7-U8图6-4计算AOE网的关键路径6.3测试结论通过测试得知该程序实现了需求中的所有功能。测试的结果完全符合预期结 果。结论通过这次实训，使我学到了很多。由于求关键路径的算法在上课时没有深入 学习，课后没有重视关键路径这块基本上没有理解，我在编程中遇到了很多困难， 但在攻克困难的过程中提高了自己的自学能力，分析问题及解决问题的能力、熟 练运用理论知识的能力。同时，让我更深入的掌握了有关求AOE网关键路径等方 面的知识，巩固了所学内容。我从这次课程设计中所得的另外一个很大的收获是： 不能因为问题难就逃避它，只有勇

17、于尝试才可能解决根本问题。数据结构这门课 程对我们学习好这个专业很重要，在以后，我会尽量利用我的空闲时间把以前不 熟的和掌握不牢固的知识点再学习一遍。尽管这次的实习是独立的个人工作，但在完成课程设计遇到困难时，也得到 了很多老师的指导和同学的帮助。然我明白了合作的重要性。在实训过程中收获 了很多的丰富的经验知识，更加深了我对一些算法和新知识的理解与应用，让我 受益匪浅。在实训中认识自己不足的地方。自己了解一些算法，但是在具体编程的时候 不会应用。写的程序复杂度高，效率低下。因此，在以后的学习中我会更加注重 学以致用。致谢感谢有这次实训的机会。通过这次实训，我学到了很多，认识到了自己的不 足。感谢老师的耐心的指导。感谢同学的热心帮助。参考文献1 严蔚敏，吴伟民.数据结构.清华大学出版社出版。2 严蔚敏，吴伟民.数据结构题集（C语言版）.清华大学出版社.2003年5 月。3 唐策善，李龙澎.数据结构（作C语言描述）.高等教育出版社.2001年9 月4 朱战立.数据结构（C+语言描述）（第二版本）.高等出版社出版.2004年 4月。5 胡学钢.数据结构（C语言版）.高等教育出版社.2004年8月。6 陈明编著.数据结构.北京：清华大学出版社，2005年。7 王红梅，胡明，王涛编著（C+版）（第2版）.清华大学出版社.2011年6 月