用数据结构求图的关键路径问题.doc

1、 数据结构程序设计 数据结构课程设计报告 学 院 计算机与通信工程 专 业 网络工程 班 级 学 号 学生姓名 指导教师 课程成绩 完成日期 2011年2月27日课程设计成绩评定学 院 计算机与通信工程学院 专 业 网络工程 班 级 学 号 学生姓名 指导教师 完成日期 2011年2月27日 指导教师对学生在课程设计中的评价评分项目优良中及格不及格课程设计中的创造性成果学生掌握课程内容的程度课程设计完成情况课程设计动手能力文字表达学习态度规范要求课程设计论文的质量指导教师对课程设计的评定意见综合成绩 指导教师签字 2011年2月27日课程设计任务书计算机与通信工程学院 网络工程专业 课程名称数

2、据结构课程设计时间20102011学年第2学期12周学生姓名指导老师题 目用数据结构求图的关键路径问题主要内容： 用C+语言和数据结构思想构建图，并求出关键路径。要求：（1）通过实际课题的分析、设计、编码、测试等工作，掌握用C+语言和数据结构思想结合来开发和维护软件。（2）按要求编写课程设计报告书，能正确编写分析、设计、编码、测试等技术文档和用户使用手册。应当提交的文件：（1）课程设计论文。（2）课程设计附件（主要是源程序）。数据结构课程设计报告摘 要关键路径是我们估算某些工程非常有用，是一种非常重要的估算一项工程所需的最短时间的依据。本文对如何求一个工程的关键路径做了详细的说明，包括需求分析

3、、概要设计、详细设计、测试与分析、总结、源程序清单。首先，做了需求分析，解释了什么是关键路径，并指出它在估算工程中的重要作用。然后给出求关键路径的概要设计，包括程序中用到的所有抽象数据类型的定义，主程序的流程以及各程序模块之间的层次(调用)关系。在概要设计的基础上，又给出了详细的算法设计，实现概要设计中定义的所有函数,对每个函数写出核心算法，并画出了流程图。然后对编码进行了测试与分析（并在最后附上C语言编写的程序代码）。最后对整个设计过程进行了总结关键词：关键路径；抽象数据类型；程序模块；核心算法；流程图目录1绪论- 1 -11前言- 1 -12研究意义- 1 -2 需求分析- 2 -21问题

4、描述- 2 -22基本要求- 2 -23目的- 2 -3 概要设计- 3 -31算法分析- 3 -32算法步骤- 3 -33数据结构- 4 -4 详细设计- 5 -41主要函数的核心代码- 5 -42程序流程图- 5 -5 测试- 6 -51开始界面- 6 -52进入求关键路径的系统- 6 -53输入节点数和活动个数- 7 -54输入某项目的信息（弧头，弧尾，权值）- 7 -55打印出关键路径- 8 -56错误测试- 9 -57回路测试- 10 -6 总结- 11 -参考文献- 12 -附录：源程序清单- 13 -1绪论11前言 我们通常把计划、施工过程、生产流程、程序流程等都当成一个工程。工

5、程通常分为若干个称为“活动”的子工程。完成了这些“活动”，这个工程就可以完成了。 我们通常用AOE-网来表示工程。AOE-网是一个带权的有向无环图，其中，顶点表示事件（EVENT），弧表示活动，权表示活动持续的时间。AOE-网可以用来估算工程的完成时间。他可以使人们了解：1. 研究某个工程至少需要多少时间?2. 哪些活动是影响工程进度的关键？由于AOE-网中的有些活动可以并行进行，从开始点到各个顶点，以致从开始点到完成点的有向路径可能不止一条，这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成工程所需的最短时间是从开始

6、点到完成点的最长路径的长度，即在这条路径上的所有活动的持续时间之和.这条路径长度就叫做关键路径(Critical Path)。12研究意义 关键路径可以很方便的让我们估算出某个工程最短的时间开销，以及这个工程中哪些活动，即哪些项目是主要的，是影响工程进度的关键，从而让我们对工程的实施作出更好的时间安排，并且可以分清主次，抓住核心工程，做到有的放矢。总的来说，正因为关键路径可以帮助我们对工程进行非常有必要的估算，让我们得以看清全局，作出更为优化的安排，所以可见关键路径的求出对一项工程而言是非常必要的。这亦是本次对关键路径求法的研究意义所在。-1-2 需求分析21问题描述 （1）选取建图的一种算法

7、建立图，有邻接矩阵，邻接表，十字链表，邻接多重表等多种方法，要选取一种适当的方法建立图，才能提高算法效率，降低时间复杂度和空间复杂度。（2）两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间。对于给出的事件AOE网络，要求求出从起点到终点的所有路径，经分析、比较后找出长读最大的路径，从而得出求关键路径的算法，并给出计算机上机实现的源程序。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。具体要解决的问题有如下四个：1） 将项目中的各项活动视为有一个时间属性的结点，从项目起点到终点进行排列； 2） 用有方向的线段标出各结点的紧前活动和紧后活动

8、的关系，使之成为一个有方向的网络图； 3） 用正推法和逆推法计算出各个活动的最早开始时间，最晚开始时间，最早完工时间和最迟完工时间，并计算出各个活动的时差； 4） 找出所有时差为零的活动所组成的路线，即为关键路径； 22基本要求 （1）选取建图的一种算法建立图；选取邻接表的算法来建立图，是一种顺序+ 链式存储结构。用顺序表存放顶点，为每个顶点建立一个单链表，单链表中的结点表示依附于该顶点的边或以该顶点为尾的弧。（2）两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间 参照该工程所化的AOE-网，求出从起点到终点的所有路径，然后通过拓扑排序和逆拓扑排序求出最早与最晚发生时间，找出长

9、度最大的路径，从而求得关键路径。 23目的在该部分，即需求分析中，根据设计题目的要求，充分地分析和理解问题，叙述系统的功能要求，明确问题要求做什么，以及限制条件是什么。 程序所能达到的功能：通过输入所要构建的图的顶点数，弧数，创建图，并打印出来，对图进行拓扑排序，求得此图的最早发生时间和最迟发生时间，并求得关键活动和关键路径，打印出来。-2-3 概要设计31算法分析（1）求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；（2）只有缩短关键活动的工期才有可能缩短工期；（3）若一个关键活动不在所有的关键路径上，减少它并不能减少工期； （4）只有在不改变关键路径的前提下，缩短关键活动才能缩

10、短整个工期。（5）关键路径：从源点到汇点的路径长度最长的路径叫关键路径。（6）活动开始的最早时间e(i)；（7）活动开始的最晚时间l(i)；（8）定义e(i)=l(i)的活动叫关键活动；（9）事件开始的最早时间ve(i)；（10）事件开始的最晚时间vl(i)。设活动ai由弧(即从顶点j到k)表示，其持续时间记为dut(),则： e(i)=ve(j) l(i)=vl(k)-dut() 求ve(i)和vl(j)分两步： 1.从ve(1)=0开始向前递推ve(j)=Max ve(i)+dut() T,2=j=n 其中，T是所有以j为弧头的弧的集合。 2.从vl(n)=ve(n)开始向后递推 vl(i

11、)=Min vl(j)-dut() S,1=i=n-1 其中，S是所有以i为弧尾的弧的集合。两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。32算法步骤(1)输入e条弧，建立AOE网的存储结构。(2)从源点v1出发，令ve(1)=0,求 ve(j)，2=j=n。(3)从汇点vn出发，令vl(n)=ve(n),求 vl(i) 1=i=n-1。(4)根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。-3-33数据结构typedef struct node/边表结点 int adjvex; /邻接点编号int dut; /

12、弧的信息 struct node *next; /下一条弧指针edgenode; typedef struct /顶点表结点 int projectname;/顶点域 int id;/顶点的入度信息 edgenode *link; /边表头指针 vexnode; int main() 界面程序的主函数void seekkeyroot()求关键路径的主函数 void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber)函数建立AOE图 int SearchMapPath(vexnode* Graphicmap,

13、int projectnumber,int activenumber,int& totaltime) 求出最大路径，并打印出关键路径 主函数void main()要调用：求关键路径的函数seekkeyroot()；求关键路径的函数seekkeyroot()要调用：创建图的函数CreateGraphic(Graphicmap,projectnumber,activenumber)求最大路径并打印出关键路径的函数int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int& totaltime) -4-4

14、详细设计41主要函数的核心代码1. 首先写出一个构建一个有向图的函数，包括节点，活动个数以及个节点之间的权值输入,为求关键路径作准备。即函数CreateGraphic（）。2. 写求出关键路径的主函数，以及实现显示求关键路径过程的函数，里面用到线性表链表的算法数据结构。即函数seekkeyroot()3. 编写主函数mian（）对函数CreateGraphic（）和函数seekkeyroot()进行调用，实现程序求关键路径的功能。 具体代码请见附录：源程序清单。42程序流程图图4.1 程序流程图-5-5 测试51开始界面开始界面如图5.1所示图5.1 开始界面图52进入求关键路径的系统输入s之

15、后则出现如图5.2，开始进入程序图5.2 进入程序界面图-6-53输入节点数和活动个数输入节点数和活动点数为3，如图5.3所示图5.3 建立节点图54输入某项目的信息输入各节点之间的联系，弧头，弧尾以及之间的权值如图5.4所示图5.4 输入节点信息图-7-55打印出关键路径按回车之后，程序则会自动计算关键路径，过程如图5.5所示图5.5 打印关键路径图-8-56错误测试应输入的数为整形，若输入非整形的数据，则程序遇到问题如图5.6关闭。图5.1图5.6 错误侧测试图-9-57回路测试如果输入的节点构成的图有回路则会出现如图5.7的提示无法计算出关键路径图5.7 回路测试错误图-10- 数据结构

16、程序设计 6 总结 历时两周的课程设计终于结束了，现在来做一下总结。首先，关于程序方面，我发现即使对设计思路有了眉目，知道了所要用到的数据结构、用邻接表来存储AOE-网、建立栈来求拓扑序列、输出的拓扑序列的个数少于节点数则有回路等等，要把这些方法写成函数代码，其实还是一件非常不容易的事情。再加上要完善设计思路，构造整个程序框架在内，都是一件工作量非常大的工作。 幸好，有很多资料可以在网路上搜到。所以课程设计的第一天，我们搜集了很多关于关键路径的资料，包括几种不同思路的程序代码，以及程序流程。然后我们的工作就变成：看懂并整理这些代码，然后再其基础上增加自己需要的功能，按照自己的意愿来修改与完善。

17、 不过在操作界面的人性化上，我倒尽可能的做得很完善，无论从美观角度还是方便清楚操作，都实行了非常人性化的方式。因为通常清楚程序的人，知道怎么操作以及该输入什么，而不清楚的人却有很大可能在细节方面输入错误导致程序运行失败，或是根本不知道应该怎么输入。所以，尽可能的人性化的设计是非常有必要的，让不懂程序的人也可以正确的操作运行。 其次，关于课程设计报告方面，老师对我们的要求非常严格，对课程设计报告的要求与毕业设计的格式相当，以便为大四时做毕业设计打下良好的基础。 初期，因为之前为了搜集资料模板，有参考一下已经做完数据结构课设的对日班即十二班的报告，发现她们的报告相当简单，所以确实觉得老师对我们要求

18、太严了，虽然看似简单，但一大堆的要求、规定、格式等，完成起来却真的很麻烦也很辛苦。 然而，经过了几天的“努力报告ing”的状态，常常一弄就弄很长时间，时常做到很晚还在做报告内容、目录、页眉页脚、程序截图再加上关键路径的课程内容，是在十几辛苦又充实。虽然辛苦程度相差很远，但也有些明白大四的学生为什么几乎没课却也整天在那里做毕业设计了。我认为这样的课程设计比较有意义，独立完成资料的搜集以及课设的内容，然后独立的做出报告，让这个过程很完整，无论是知识方面、还是报告的书写方面，都学到了更多的东西，为毕业设计打下了良好的基础。 最后，做再次一下总结。程序方面仍有为解决的问题，希望即便课设之后也可以努力将

19、问题解决掉。然后关键路径的算法中，有些知道怎么做却很难清楚回答出来的问题，希望可以再好好的查找一下相关资料，将知识系统化、理论化、规范化。-11-参考文献1 杨路明.C语言程序设计教程.北京：北京邮电大学出版社，2000.12 严蔚敏，吴伟民.数据结构. 北京：清华大学出版社，20063 谭浩强.C程序设计.北京：北京清华大学出版社，1999.14 北京金洪恩电脑有限公司.C/C+程序设计入门.天津：天津电子出版社，2003.4-12- 数据结构程序设计 附录：源程序清单#include#include#include#include typedef struct node/边表结点 int

20、adjvex; /邻接点编号 int dut; /弧的信息 struct node *next; /下一条弧指针edgenode;typedef struct /顶点表结点 int projectname;/顶点域 int id;/顶点的入度信息 edgenode *link; /边表头指针vexnode;void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber)/创建图 int begin,end,duttem; /分别代表弧的前节点，尾节点，活动时间 edgenode *p;/ 边表头指针 for(i

21、nt i=0;iprojectnumber;i+) Graphicmapi.projectname=i;/顶点的命名按0，1，2，3. Graphicmapi.id =0;/顶点的信息的度数均赋为零 Graphicmapi.link =NULL; printf(n); printf(请输入某项目的信息，并请用整形数字表示（格式：弧头，弧尾，权值）：n); printf(例如:输入1,2,4 即代表结点1与4之间的活动需要4个时间单位。n); printf(n); for(int k=0;kadjvex =end-1;/因为是从零开始记的，姑要减一，就是让终点插入到邻接表内 p-dut =dut

22、tem; /该弧的活动时间为duttem Graphicmapend-1.id +; /入度加一 p-next =Graphicmapbegin-1.link ; Graphicmapbegin-1.link =p;/让下一个节点作为下一插入节点的前驱节点 -13-int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int& totaltime) /求出最大路径，并打印出关键路径 int i,j,k,m=0; int front=-1,rear=-1; int* topologystack=(int*

23、)malloc(projectnumber*sizeof(int);/用来保存拓扑排列 int* vl=(int*)malloc(projectnumber*sizeof(int);/用来表示在不推迟整个工程的前提下，VJ允许最迟发生的时间 int* ve=(int*)malloc(projectnumber*sizeof(int);/用来表示Vj最早发生时间 int* l=(int*)malloc(activenumber*sizeof(int);/用来表示活动Ai最迟完成开始时间 int* e=(int*)malloc(activenumber*sizeof(int);/表示活动最早开始时

24、间 edgenode *p; /边表头的指针 totaltime=0; /存放整个工程的最短时间 for(i=0;iprojectnumber;i+) vei=0;/先把每个工程的最早发生时间初始化为零 for(i=0;iadjvex ; / 邻接点编号 Graphicmapk.id -;/让入度减一，相当于删除一个入度为零的前驱节点，和相关的弧 if(vej+p-dut vek)/将最长的路径赋给VEK vek=vej+p-dut ; if(Graphicmapk.id =0)/如果入度为零，则入队列 topologystack+rear=k; p=p-next ; /指向下一个节点 -14

25、- 3 - if(mprojectnumber)/如果有环，则不能遍历每个节点 printf(n本程序所建立的图有回路不可计算出关键路径!n); printf(将退出本程序！n); return 0; totaltime=veprojectnumber-1;/最短完成时间即为最后一个节点所累加的时间之和 for(i=0;i=0;i-)/ 用逆拓扑排序来求活动Ai最迟完成开始时间，即从最后一个节点减去最短的时间 j=topologystacki; p=Graphicmapj.link ; while(p) k=p-adjvex ; if(vlk-p-dut )dut ; p=p-next ; i

26、=0; printf(n); printf(| 起点 | 终点 | 最早开始时间 | 最迟完成时间 | 差值 | 备注 n); for(j=0;jadjvex ; e+i=vej; li=vlk-p-dut; printf(| %4d | %4d | %11d | %11d | %3d |,Graphicmapj.projectname +1,Graphicmapk.projectname +1,ei,li,li-ei); if(li=ei) /当差值为零时，则为关键路径 printf( 关键活动 , Graphicmapj.projectname +1,Graphicmapk.project

27、name +1); printf(n); p=p-next ;-15- return 1;void seekkeyroot()/求关键路径的主函数 int projectnumber,activenumber,totaltime=0; printf(n); printf(输入符合标准，欢迎进入求关键路径的系统!n); printf(n); printf(请输入这个项目的AOE-网的节点数: ); scanf(%d,&projectnumber); printf(请输入这个项目的AOE-网的活动个数: ); scanf(%d,&activenumber); vexnode* Graphicmap

28、=(vexnode*)malloc(projectnumber*sizeof(vexnode); CreateGraphic(Graphicmap,projectnumber,activenumber);/创建邻接图 SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime);/求出最大路径，并打印出关键路径 printf(n); printf(整个工程所用的最短时间为：%d个单位时间n,totaltime); system(pause);int main() char ch; for(;) do system(cls); printf( n); printf( 欢迎进入求关键路径算法程序 n); printf( n); printf(%s,ns(start)开始输入工程的节点数据并求出关键路径n); printf(n); printf(%s,e(exit)退出n); printf(n); printf(%s,请输入选择:); scanf(%c,&ch); ch=toupper(ch);-16- while(ch!=S&ch!=E); switch(ch) caseS: seekkeyroot(); break; caseE: return 1; -17-