数据结构课程设计

1、1 ABSTRACT1.1图和栈的结构定义struct SqStack/ 栈部分SEIemType *base; 栈底指针 SEIemType *top; 栈顶指针 int stacksize;/ 栈的大小int eleme nt_coun t;/栈中元素个素;/AOE 网的存储结构 struct ArcNode / 表结点in t lastcompletetime;/活动最晚开始时间int adjvex; /点结点位置int info; / 所对应的弧的权值struct ArcNode *n ext;/指向下一个表结点指针;struct VNode / 点结点VertexType data;

2、 / 结点标志int in degree; / 该结点入度数in t ve; /记录结点的最早开始时间in t vl; /记录结点的最晚开始时间struct ArcNode *first_out_arc; /存储下一个出度的表结点struct ArcNode *first_i n_arc;存储下一个入度的表结点;struct ALGraph VNode *vertices; /结点数组int vex num; /结点数int arcnum; /弧数int kin d; / 该图的类型;2系统总分析2.1关键路径概念分析什么是关键路径关键路径法(CriticalPath Method, CPM最

3、早出现于20世纪50年代，它是通过分析项目过程中哪个活动序列进度安排的总时差最少来预测项目工期的网 络分析。这种方法产生的背景是，在当时出现了许多庞大而复杂的科研和工程项 目，这些项目常常需要运用大量的人力、物力和财力，因此如何合理而有效地对这些项目进行组织，在有限资源下以最短的时间和最低的成本费用下完成整个项 目就成为一个突出的问题，这样 CPM就应运而生了。 对于一个项目而言，只有 项目网络中最长的或耗时最多的活动完成之后，项目才能结束，这条最长的活动路线就叫关键路径(Critical Path )，组成关键路径的活动称为关键活动。关键路径特点关键路径上的活动持续时间决定了项目的工期，关键

4、路径上所有活动的持续 时间总和就是项目的工期。关键路径上的任何一个活动都是关键活动，其中任何一个活动的延迟都会导致整个项目完工时间的延迟。关键路径上的耗时是可以完工的最短时间量，若缩短关键路径的总耗时，会 缩短项目工期；反之，则会延长整个项目的总工期。 但是如果缩短非关键路径上 的各个活动所需要的时间，也不至于影响工程的完工时间。关键路径上活动是总时差最小的活动，改变其中某个活动的耗时，可能使 关键路径发生变化。可以存在多条关键路径， 它们各自的时间总量肯定相等，即 可完工的总工期。关键路径是相对的，也可以是变化的。在米取一定的技术组织措施之后，关 键路径有可能变为非关键路径，而非关键路径也有

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

6、点到终点 进行排列；(2) 用有方向的线段标出各结点的紧前活动和紧后活动的关系，使之成为 一个有方向的网络图；(3) 用正推法和逆推法计算出各个活动的最早开始时间，最晚开始时间， 最早完工时间和最迟完工时间，并计算出各个活动的时差；(4) 找出所有时差为零的活动所组成的路线，即为关键路径；(5) 识别出准关键路径，为网络优化提供约束条件；算法分析(1) 求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；(2) 只有缩短关键活动的工期才有可能缩短工期；(3) 若一个关键活动不在所有的关键路径上，减少它并不能减少工期；(4) 只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。(

7、5) 关键路径：从源点到汇点的路径长度最长的路径叫关键路径。(6) 活动的最早开始时间e(i)；(7) 活动的最晚开始时间l(i)；(8) 定义e(i)=l(i)的活动叫关键活动；(9) 事件的最早开始时间ve(i)；(10) 事件的最晚开始时间vl(i)。设活动ai由弧<j,k>(即从顶点j到k)表示，其持续时间记为dut(vj,k>), 则：e(i)=ve(j)l(i)=vl(k)-dut(vj,k>)求ve(i)和vl(j) 分两步：1. 从ve(1)=0开始向前递推ve(j)=Max ve(i)+dut(<i,j>) <i,j>T,2&l

8、t;=j <=n其中，T是所有以j为弧头的弧的集合。2. 从vl(n)=ve(n)开始向后递推vl(i)=Mi n vl(j)-dut(<i,j>) <i,j>S,1<=i<=n-1其中，S是所有以i为弧尾的弧的集合。 两个公式是在拓扑有序和逆拓扑有序的前提下进行算法步骤(1) 输入e条弧<j,k>，建立AOE网的存储结构。(2) 从源点v1出发，令ve(1)=0,求个点的最早开始时间ve(j)。(3) 从汇点vn出发，令vl(n)=最大值，求个点的最晚开始时间vl(j)。(4) 由于各结点的最早开始时间已求出来，所以各活动的最早开始时间即

9、(每条弧s (活动)的最早开始时间)就等于该结点的最早开始时间，并由上可同时求出该活动的最晚开始时间l(j)。(5) 具体表达式为：e(i)=ve(j)l(i)=vl(k)-dut(vj,k>)(6) 当结点的最早开始时间ve(j)=最晚开始时间时vl(j)，则该结点为关 键结点。(7) 当活动的最早开始时间e(j)=最晚开始时间时l(j)，则该结点为关键 活动。3主要功能模块设计3.1程序模块栈部分模块Status In itStack(SqStack & S) / 初始化栈Status DestroyStack(SqStack & S)销毁栈Status ClearS

10、tack(SqStack & S)/ 清空栈Status StackEmpty(SqStack S)/判断是否为空Status StackEmpty(SqStack S)/判断是否为空Status Pop(SqStack & S,SEIemType & e) /弹出元素Status GetEleme nt(SqStack & S,i nt positio n,SEIemType & e) /取元素，非弹出,i为要去元素位置无向图(AOE网)部分模块void CreateALGraph(ALGraph &graph)/初始化 AOE网Status

11、TopologicalSort(ALGraph & graph,SqStack & ToPoReverseSort) /求拓扑排序Status Put In foToPoSort(SqStack temp,ALGraph graph) /输出拓扑顺序排序(当拓扑序列存在时)Status GetVeA ndVI(ALGraph & graph,SqStack OrderSort,SqStack RevSort) /求出结点和活动的最晚开始时间和最早开始时间Status CriticalPath(ALGraph & graph,SqStack RevSort) /求

12、出关键活动和关键事件并输出4系统详细设计4.1主函数模块main 函数首先调用 SqStack ToPoSort;SqStack ToPoReverseSort;函数来定 义栈，调用InitStack(ToPoSort);来初始化存拓扑排序的栈和In itStack(ToPoReverseSort); 来初始化逆拓扑排序的栈。其次调用CreateALGraph(ALGraph &graph)函数定义和初始化 AOE网，调用 TopologicalSor t(ALGraph &graph,SqStack &ToPoReverseSort)函数求拓扑序 列和调用PutInf

13、oToPoSort(ToPoSort,graph); 函数来输出输出拓扑顺序排序。然后调用 GetVeAndVl(graph,ToPoSort,ToPoReverseSort)函数求结点和活 动的最晚开始时间、最早开始时间并输出。最后调用 Status CriticalPath(ALGraph &graph,SqStack RevSort) 函数来 求关键活动、关键事件并输出。4.2初始化模块初始化模块用来初始化图，要求用户自己输入数据，并程序构造AOE网。本程序是用自己改进的邻接表来构造 AOE网。见图2-4-2图 2-4-3图 2-4-24.3求拓扑序列模块利用栈来存储入度为零的结

14、点，然后逐个弹出，来进行与该结点的出度结点 来比较，是否符合拓扑排序的规则，最后用ToPoReverseSort存放拓扑逆序序列 来完成整个拓扑排序。见图2-4-34.4求最晚开始时间和最早开始时间模块（包括结点和活动的最早和最晚开始时间）见图 2-4-4图 2-4-44.5关键活动和关键事件见图2-4-5图 2-4-54.6输出模块输出相应结点的信息，拓扑序列，以及事件的最早开始时间和最晚开始时间, 输出相应的活动的最早开始时间和最晚开始时间，关键活动以及关键事件。5测试分析5.1测试内容求的关键路径为:程序输入部分:求拓扑序列部分求结点和活动的最早开始时间和最晚开始时间输出图中的关键事件和

15、关键活动（关键路径）测试关键路径结果:5.2回路测试结果分析：结果完全符合所求，但是输出的方面不够完美，并且自我感觉程序所使用的空间比较大，算法复杂度较高，所以效率比较低下，当程序输入存在有环的时候，程序没有发生任何错误，直接输出“图存在有环”然后退出程序。由此可见本程序计划实施到完工比较顺利的完成了，并且在程序测试中能够 得到预期的结果出来，不过唯一不满意的是程序过于复杂化，使用的太多的空间， 致使程序成为一个缺陷。参考文献1 严蔚敏，吴伟民.数据结构.北京：清华大学出版社，2006.2 谭浩强.C程序设计（第二版）作者：清华大学出版社，2006心得体会经历几天的编程之后，课程设计终于结束了

16、。一开始整个程序不知道怎么开始，而且算法是怎么样的都不知道，不过经过 一番的查书、翻阅资料、上网查找之后终于了解到整个算法流程以及实现，首先，关键路径的实现是用邻接表来存储的，对于这个来说，本人觉得单纯按照书本的邻接表来做不太合适，于是就自己改进了一个邻接表，加上在结点里加上存储入 度的变量，和加上指向所以入度的表的指针。并且在表结构上加上入度表结构。由于搜集了很多关于关键路径的资料，包括几种不同思路的程序代码，以及 程序流程。然后看懂并整理这些代码，然后再其基础上增加自己需要的功能，按照自己的意愿来修改与完善。在程序输入部分采用结点，结点，弧(即结点和结点之间的权值)，由于输入贯穿整个程序部

17、分，所以输入部分十分重要。 之后创建整个程序的结构，其中 包括入度和出度的表结点，这两个都依附在结点结构之上。在程序求关键路径的时候，首先必须要求出整个图的拓扑排序，并用栈来保 存起来，然后并在主函数里定义了两个栈，分别来存储顺序拓扑排序和逆序拓扑排序，其中在求拓扑排序的时候就遇到了一个问题就是结点存储的度数发生变化 了，这个问题在后来的时候才发现的，因为之后还需要用到入度数，由此，在求 拓扑序列的时候必须把入度数先用一个数组来存起来，然后求完拓扑序列之后必须把整个结点的入度数还原。/保留入度度数 /in t *in degree_copy=(i nt *)malloc(sizeof(i nt

18、)*graph.vex nu m);for(i=0;i<graph.vex nu m;i+)*(i ndegree_copy+i)=(graph.vertices +i+1)->in degree ; _/还原入度度数 /for(i=0;i<graph.vex nu m;i+)(graph.vertices +i+1)->in degree=*(i ndegree_copy+i);/最后按照拓扑的顺序序列求出结点的最早开始时间，但是源结点的最早开始 时间必须赋予一定的值，所以按照顺序的拓扑序列并且还可以求出活动的最早开 始时间。再次，按照逆序拓扑序列来求出结点和活动的最

19、晚开始时间。然后根据 算法就可以轻易的求出关键路径和关键事件。其中在编译过程中出现了一个编译的异常，上网找了一下，说是指针越界了，于是，再设断点等手段经过长时间的摸索之后就发现了原来是程序中的栈的部分 出问题了，由于之前都没有过栈出问题的情况，于是就改变了一下这个问题就没出现过了。教师评语附录程序源代码：/关键路径.cpp :定义控制台应用程序的入口点。#i nclude "stdafx.h"#i nclude<stdio.h>#in clude<stdlib.h>#defi ne VertexType int/ 栈部分#defi ne STACK_

20、ADDITION sizeof(SEIemType)#defi ne SElemType int#defi ne OK true#defi ne ERROR false#defi ne Status boolstruct SqStackSElemType *base;SElemType *top;int stacksize;int eleme nt_coun t;/元素个素; 一Status In itStack(SqStack & S) /初始化栈S.base =(SElemType *)malloc(STACK_ADDITION);S.stacksize =STACK_ADDITI

21、ON;S.eleme nt_co unt =0;if(S.base =NULL)prin tf("malloc error n");exit(0);elseS.top=S.base ;return OK;Status DestroyStack(SqStack & S)/ 销毁栈if(S.base=NULL)prin tf("Stack is not existe ntn");else delete(S.base);return OK;Status ClearStack(SqStack & S)/清空栈if(S.base=NULL)prin

22、 tf("Stack is not existe ntn");else if(S.base =S.top )prin tf("Sack is NULLn");elseS.top=S.base ;S.eleme nt_co unt =0; _return OK;Status StackEmpty(SqStack S)/判断是否为空if(S.base=NULL)prin tf("Stack is not existe ntn"); return false;if(S.top =S.base )return true;elsereturn

23、false;Status Push(SqStack & S,SEIemType e) /增加元素SEIemType *temp仁S.base;SEIemType *temp2=S.top;if(S.stacksize-(S.eleme nt_cou nt *STACK_ADDITION)=STACK_ADDITION) S.base=(SElemType*)realloc(S.base ,(S.stacksize+STACK_ADDITION);S.stacksize+=STACK_ADDITION;S.top =S.base + (temp2-temp1);*S.top =e;S.t

24、op =S.top +1;S.eleme nt_co un t+; _else*S.top =e;S.top =S.top+1;S.eleme nt_co un t+; _return OK;Status Pop(SqStack & S,SElemType & e) /弹出元素if(S.top=S.base )prin tf("Stack is null! Pop error!n");return false;elsee=*-S.top ;S.eleme nt_cou nt -;return OK;int StackLe ngth(SqStack S)ret

25、urn S.eleme nt_cou nt ; 一Status GetEleme nt(SqStack & S,i nt positio n,SEIemType & e) /取元素，非弹出,i为要去元素位置SElemType *temp;temp=S.top;if(S.top=S.base)printf("Stack is null! GetElement error!n");return false;else if(positi on<=S.eleme nt_co unt)e=*(temp-positio n);return OK;elseprint

26、f("error!由于输入位置比栈元素数目大");return false;/= struct ArcNode / 表结点int lastcompletetime;/活动最晚完成时间int adjvex; /点结点位置int info; /所对应的弧的权值struct ArcNode *n ext;/下一个表结点;struct VNode / 点结点VertexType data; / 标志int in degree; / 该结点入度数in t ve; /记录最早开始时间in t vl; /记录最晚开始时间struct ArcNode *first_out_arc; /存储

27、下一个出度的表结点struct ArcNode *first_i n_arc;存储下一个入度的表结点; _ _struct ALGraphVNode *vertices; /结点数组int vex num; /结点数int arcnum; /弧数int kind; / 该图的类型;void CreateALGraph(ALGraph & graph)int temp1=1;int temp2=0;int temp3=0;权int i=0;struct ArcNode *arc仁NULL;struct ArcNode *arc2=NULL;printf("请输入结点数(结点由1

28、开始)和图的类型：n");sca nf("%d %d",&graph.vex num,&graph.k ind );graph.vertices =(VNode *)malloc(graph.vex nu m+1)*sizeof(VNode); for(i=0;i<=graph.vex nu m;i+)(graph.vertices+i)->data=i;(graph.vertices+i)->first_in_arc =NULL;(graph.vertices+i)->first_out_arc=NULL;(graph.v

29、ertices+i)->ve =0;(graph.vertices+i)->vl=0;(graph.vertices+i)->i ndegree =0;printf("请输入(格式：点，点，两点之间的权值n");graph.arc num =-1;while(!(temp1=0&&temp2=0&&temp3=0)graph.arc nu m+; / 图的弧数scan f("%d %d %d", &temp1, &temp2, &temp3);(graph.vertices +te

30、mp2)->in degree) +;if(graph.vertices+temp2)->first_in_arc=NULL) 一一(graph.vertices+temp2)->first_in_arc=(ArcNode*)malloc(sizeof(ArcNode);(graph.vertices+temp2)->first_in_arc->adjvex =temp1; (graph.vertices+temp2)->first_in_arc->i nfo =temp3; (graph.vertices+temp2)->first_in_ar

31、c->lastcompletetime=0;/活动最晚完成时间初始化(graph.vertices+temp2)->first_in_arc ->next =NULL;else arc2=(graph.vertices+temp2)->first_in_arc; while(arc2-> next!=NULL) /如果下一个不为空的话就存储下一个地址arc2=arc2->n ext ;arc2->next =(ArcNode *)malloc(sizeof(ArcNode);arc2->n ext->adjvex =temp1;arc2-&

32、gt;lastcompletetime =0;/活动最晚完成时间初始化arc2->n ext- >info =temp3; arc2-> next-> next =NULL;/=if(graph.vertices+temp1)->first_out_arc=NULL)(graph.vertices+temp1)->first_out_arc=(ArcNode*)malloc(sizeof(ArcNode);(graph.vertices+temp1)->first_out_arc->adjvex =temp2; (graph.vertices+t

33、emp1)->first_out_arc->i nfo =temp3; (graph.vertices+temp1)->first_out_arc->lastcompletetime=0;/活动最晚完成时间初始化(graph.vertices+temp1)->first_out_arc- >next =NULL; 一 一else arc1=(graph.vertices+temp1)->first_out_arc; while(arc1-> next!=NULL) /如果下一个不为空的话就存储下一个地址arc1=arc1- >n ext ;

34、arc1- >next =(ArcNode *)malloc(sizeof(ArcNode);arc1- >n ext->adjvex =temp2;arc1- >n ext-> info =temp3;arc1- >n ext->lastcompletetime =0;/活动最晚完成时间初始化arc1- >n ext- >n ext =NULL;/求拓扑排序Status TopologicalSort(ALGraph & graph,SqStack & ToPoReverseSort)SqStack S;struct Ar

35、cNode *p=NULL;int k=0;int i=0;in t cou nter;/计算拓扑序列的个数/保留入度度数 / in t *in degree_copy=(i nt *)malloc(sizeof(i nt)*graph.vex nu m); for(i=0;i<graph.vex nu m;i+)*(i ndegree_copy+i)=(graph.vertices +i+1)->in degree ; _/if(!I nitStack(S)printf("初始化栈失败");for(i=1;i<=graph.vex nu m;i+)if(

36、!(graph.vertices +i)->in degree )Push(S,i);coun ter=0;i=0;while(!StackEmpty(S)Pop(S,i);Push(ToPoReverseSort,i);用栈 ToPoReverseSort 存放拓扑逆序序列coun ter+;for(p=(graph.vertices +i)->first_out_arc);p;p=p->next ) 一 一 k=p->adjvex ;if(!(-(graph.vertices +k)->in degree )Push(S,k);DestroyStack(S);

37、/ 还原入度度数 /for(i=0;i<graph.vex nu m;i+)(graph.vertices +i+1)->in degree=*(i ndegree_copy+i); _/if(co un tervgraph.vex num ) return ERROR;elsereturn OK;/输出拓扑顺序排序(当拓扑序列存在时)Status Putl nfoToPoSort(SqStack temp,ALGraph graph)SElemType e=0;int j=temp.eleme nt_count;for(int i=1;i<=j ;i+)Pop(temp,e

38、);printf(" 该结点为 V%d: 数组下标为：dn",(graph.vertices +e)->data ,e);return OK;/求出结点和活动的最晚开始时间和最早开始时间Status GetVeA ndVI(ALGraph & graph,SqStack OrderSort,SqStack RevSort) int i=0,j=0;int kk=0;struct ArcNode *p=NULL;SElemType e1;SElemType e2;/求出所有结点的最早开始时间/Pop(OrderSort,e1);(graph.vertices+e

39、1)->ve =1;kk=OrderSort.eleme nt_count;for(i=1;i<=kk ;i+)Pop(OrderSort,e2);for(j=1,p=(graph.vertices+e2)->first_i n_arc);jv=(graph.vertices+e2)->in degree ;j+,p=p->n ext ) if(graph.vertices+e2)->ve<(graph.vertices+p->adjvex )->ve + p->i nfo ) (graph.vertices+e2)->ve=(

40、graph.vertices+p->adjvex )->ve + p->i nfo ; /求出所有结点的最晚开始时间/Pop(RevSort,e1); /弹出拓扑序列最后一个元素for(i=1;i<=graph.vexnum ;i+) (graph.vertices+i)->vl =2147483647;最晚开始时间=(graph.vertices+e1)->vl = (graph.vertices+e1)->ve ;/ 最早开始时间kk=RevSort.eleme nt_count; for(i=1;i<=kk ;i+)Pop(RevSort,

41、e2);for(p=(graph.vertices +e2)->first_out_arc);p;p=p->n ext ) 一 一p->adjvex )->vl)>(graph.vertices+=(graph.vertices+p->lastcompletetime =(graph.vertices+ (p->i nfo);if( (graph.vertices+e2)->vlp->adjvex )->vl) - (p->i nfo)(graph.vertices+e2)->vlp->adjvex )->vl

42、) - (p->i nfo);/prin tf("nn结点信息n");printf("结点t最早开始时间t最晚开始时间t入度数n");for(i=1;i<=graph.vex nu m;i+)prin tf("V%dt%2dtt%2dtt%2dn",(graph.vertices+i)->data,(graph .vertices+i)->ve,(graph.vertices+i)->vl,(graph.vertices+i)->i ndegree)prin tf("n活动信息n");printf(" 活动最早开始时间最晚开始时间为n");for(i=1;i<=graph.vexnum ;i+)for(p=(graph.vertices +i)->first_out_arc);p;p=p->next ) 一 一prin tf("<V%d,V%d>tt%dtt%dn",i,p->adjvex(graph.vertices+