《数据结构》课程设计报告课程题目：关键路径学院：班级：学号：XX： 指导教师 完成日期目录一、需求分析3、概要设计4 三、详细设计5四、调试分析11五、用户使用说明12六、测试结果13 七、附录13一、需求分析1、问题描述AOE 网(即边表示活动的网络)，在某些工程估算方面非常有用它可以使人 们了解：(1)研究某个工程至少需要多少时间？(2)哪些活动是影响工程进度 的关键？在AOE网络中，从源点到汇点的有向路径可能不止一条，但只有各条 路径上所有活动都完成了，这个工程才算完成因此，完成整个工程所需的时间 取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之 和，这条路径就叫做关键路径(critical path )2、设计步骤(1) 、 以某一工程为蓝本，采用图的结构表示实际的工程计划时间2) 、 调查并分析和预测这个工程计划每个阶段的时间3) 、用调查的结果建立AOE网，并用图的形式表示4 )、用CreateGraphic ()函数建立图的邻接表存储结构，能够输入图的顶 点和边的信息，并存储到相应存储结构中5) 、用SearchMaxPath()函数求出最大路径，并打印出关键路径。
6) 、 编写代码并调试、测试通过3、测试数据6v1 v2 v3 v4 v5 v68v1 v2 a1 3v1 v3 a2 2v2 v4 a3 2v2 v5 a43v3 v4 a5 4v3 v6 a6 3v4 v6 a7 2v5 v6 a8 1—. rzw f i为了实现上述函数功能：1、抽象数据类型图的定义如下：ADT Graph {数据对象V：v是具有相同特性的数据元素的集合，称为顶点集数据关系R：R={VR}；VR={|v, WeV,且P(v, w), 表示从v到w的弧，谓词P(v, w)定义了弧的意义和信息}基本操作：InitGraph(G);初始条件：图G存在操作结果：构造一个图的顶点数为M AX，弧的个数也为M AX，其他信息都相应初 始化了的图CreatGraph(& G);初始条件：已经初始化了的图G操作结果：通过输入函数输入图的顶点个数，各顶点信息，弧的条数，以及弧的 其他信息，构造图G}2、抽象数据类型栈的定义如下：ADT Stack {数据对象：D={ai | ai wElemSet,i=1,2,…，n, n三0}数据关系：Rl={ | ai-1, a#D,i=2,…，n }约定如端为栈顶，ai端为栈底。
基本操作：InitStack（&S）操作结果：构造一个空栈sStackEmpty（S）初始条件：栈S已经存在操作结果：若栈S为空栈，则返回TRUE,否则FALSEPush（&S，e）初始条件：栈S已经存在操作结果：插入元素e为新的栈顶元素Pop（&S，&e）初始条件：栈S已存在且不为空操作结果：删除S的栈顶元素，并用e返回其值}三、详细设计1、图的邻接表存储结构如下#define MAX 20typedefstruct Arode//表节点int adjvex;struct Arodechar * info1;int info2;//该弧所指向的顶点的位置//指向下一条弧的指针〃表示活动，如a1、a2、a3等等//表示权值next;}Arode;typedefstruct VNode//头结点〃顶点信息，如v1、v2、v3等等Vertextype data[3];Arode * first;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX];typedefstruct{AdjList vertices;int vexnum;//图的顶点数int arum;//图的弧数}ALGraph;2、 栈的顺序存储结构如下：#define SIZEMAX 20 #defineADD 10typedefint Elemtype;typedefstruct{Elemtype * base;Elemtype * top;int maxsize;}Stack;3、 图的构建函数设计如下：int ID[MAX]={0}; 〃存放每个顶点的入度的数组IDint ve[MAX]={0}; 〃用来存放每个顶点的最早发生时间的数组vechar str3[MAX][10]; //存放活动的字符串数组void InitGraph(ALGraph &G)〃初始化图时将图的顶点数、弧数都赋为MAX {G.vexnum=MAX;G.arum=MAX;for(int i=0;iadjvex=s; 〃将弧头所指向的顶点的位置下标存放在pp的adjvex域中 pp->info1=str3[i];〃将该弧的活动信息存放在pp的info1域中 pp->info2=n;〃将该弧的权值大小存放在pp 的info2域中 pp->next=NULL; //pp 的 next指向 空ID[s]++; 〃s的入度加1if(G.vertices[j].first!=NULL) //如 果序号为 j的头结点的first所指向 的不为{ 空，则表示该顶点已经连好了一条弧，需要找下一个可存放的位置 p=G.vertices[j].first; 〃用一个临时指针保存该头结点的first指针 if(p->next!=NULL) 〃如果first所指向 的表结点的 next指向 不为空，{ //则需要找下一个可存放位置while(p->next->next!=NULL) 〃如果 p所指向的表结点的 next{ 所指向另一表结点的next不为空，就把p指针往后移一位p=p->next;}p=p->next;}p->next=pp; 〃直到p的next指向为空，再把p的next指向pp}elseG.vertices[j].first=pp; 〃如果序号为j的头结点的first所指向的为空，直接把它 的 first指向pp}}4、 堆栈的功能函数设计如下：Status InitStack(Stack &S) //栈的初始化操作{5. base=(Elemtype *)malloc(SIZEMAX*sizeof(Elemtype)); //给栈分配存空间if(!S.base)exit (OVERFLOW); 〃若分配不成功，则返回OVERFLOW；S.top=S.base; //让栈的栈顶指针和栈底指针相等S.maxsize=SIZEMAX; 〃栈的当前容量为 SIZEMAXreturn OK;}Status Pop(Stack &S,int &e){if(S.top==S.base) //如果栈的栈顶指针等于栈底指针，则表示当前栈为空 return ERROR; 〃栈顶元素不存在，所以返回ERRORe=*(--S.top);〃如果栈不为空，就取出S的栈顶指针所指向的数据， return OK; 〃并把top指针往下移一个位置}Status Push(Stack &S,int e){if(S.top-S.base>=S.maxsize) //如果当前栈存的元素超过了它的最大存放量{ //则必须追加空间S.base=(Elemtype *)realloc(S.base,(S.maxsize+ADD)*sizeof(Elemtype));if(!S.base)exit (OVERFLOW);S.top=S.base+S.maxsize;S.maxsize=S.maxsize+ADD;}*(S.top++)=e; //top指针往上移一位后，让top指针指向元素ereturn OK;}Status Empty(Stack S){ if(S.top==S.base)return OK;〃如果栈的栈顶指针等于栈底指针，则表示当前栈为空,返回OK elsereturn ERROR; 〃否则返回 ERROR}5、求关键路径的函数设计如下：Status Topo(ALGraph G,Stack &T) //拓扑排序函数{int i,j,k;Arode *p; 〃定义一个指向Arode表结点的指针pStack S; //定义一个存放入度为0的顶点所在的下标值的栈InitStack(S); 〃初始化栈Sfor(j=0;jnext){ 〃找以第j个顶点为弧尾的弧的弧头k=p->adjvex; //保存弧头所示的顶点的位置下标ID[k]--; //删除该弧后，弧头所示的顶点入度减1if(ID[k]==O)Push(S,k); 〃如果该顶点入度为0,就入栈Sif( ( ve[j] + (p->info2) ) > ve[k] )ve[k]=ve[j]+(p->info2);〃如果j号顶点的最早发生时间与该弧的权值之和大于k号定点的 }〃最早发生时间，就改变k号顶点的最早发生时间}if(countnext){ 〃取出栈顶元素，并查找以j号顶点为弧尾的弧的弧头k=p->adjvex; 〃把弧头所示的顶点位置下标值存放在k中if(vl[k]-(p->info2)info2); 〃如果k号顶点的最迟发生时间与该弧的权值之差小于j号定点的最迟发生时间，就改变vl[j] }printf("关键顶点为a：");for(j=0;jnext){k=p->adjvex;ee=ve[j]; el=vl[k]-(p->info2);if(el==ee)printf("%s ",p->info1);}}printf("\n");return OK;}四、 调试分析1、本次课程设计题目思路特别清晰，算法特别简单，但是在编程过程中遇到了 一系列的问题都值得思考与分析。
2、首先是在图的创建过程中，用邻接表创建图的时候，指针使用没有正确到 位而引发了一系列问题，后来通过与老师同学一起分析才找到了问题的症结所 在之前用临时指针P保存头结点的first指针，然后让p指向已经存好信息的表 结点PP，这样操作并没有真正把它连起来，下次循环时，又覆盖了原来的信息3、在成功创建了图后，把主函数中生成的图作为参数传给CritialO时，又发 现原来图中的活动这一信息又改变了，全变成乱码了，原来是由于存放活动的字 符串str3，由于不断的输入，导致最后字符串什么也没有了，而图中每个弧的活 动指针都指向它，所以就全乱了，后来就把它改为字符串数组，并且把它设为全 局变量4、在调试CritialO这一函数中，也遇到了一些问题，在观察零入度栈S的栈顶 元素和拓扑序列栈T的时候，在watch窗口中输入*(S.top--),发现一直乱变，根本 不知道它的栈元素，甚至怀疑栈的初始化函数有没有写对，后来通过查找以前堆 栈类型问题以及与同学题目作对比才发现就是由于窗口输入容写错了，应该改为 *(S.top-1)五、 用户使用说明第一行输入顶点个数 vexnum 第二行输入各个顶点的名称。
第三行输入弧的边数 arum接下来的arum行输入每一条弧的弧尾顶点、弧头顶点、活动以及权值大小六、 测试结果皿 v2 A± 3v3 2v2 v4 a3 2vZ a4 3“5 4s3 u& a6 3虫 u& a? 2s5 u& aS 1关犍顶点为’咀v3 v4 u6 关犍路桎为’ a2 aS a?Pp&es： smy ke9 to continue七、附录以下是该程序设计的完整代码：#include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MAX 20#define SIZEMAX 20#defineADD 10 typedefint Status; typedefint Infotype; typedefchar Vertextype; typedefint Elemtype; int ID[MAX]={0}; int ve[MAX]={0}; char str3[MAX][10]; typedefstruct Arode { int adjvex; struct Arode * next; char * info1;int info2;}Arode; typedefstruct VNode {Vertextype data[3];Arode * first; }VNode,AdjList[MAX]; typedefstruct {AdjList vertices;int vexnum;int arum;}ALGraph;typedefstruct{Elemtype * base;Elemtype * top;int maxsize;}Stack;void Init(ALGraph &G){G.vexnum=MAX;G.arum=MAX;for(int i=0;iadjvex=s;pp->info1=str3[i];pp->info2=n;pp->next=NULL;ID[s]++;if(G.vertices[j].first!=NULL){p=G.vertices[j].first;if(p->next!=NULL){ while(p->next->next!=NULL){p=p->next;}p=p->next;}p->next=pp;}elseG.vertices[j].first=pp;}}Status InitStack(Stack &S){S.base=(Elemtype *)malloc(SIZEMAX*sizeof(Elemtype));if(!S.base)exit (OVERFLOW);S.top=S.base;S.maxsize=SIZEMAX;return OK;}Status Pop(Stack &S,int &e){if(S.top==S.base)return ERROR;e=*(--S.top);return OK;}Status Push(Stack &S,int e){if(S.top-S.base>=S.maxsize){S.base=(Elemtype *)realloc(S.base,(S.maxsize+add)*sizeof(Elemtype)); if(!S.base)exit (OVERFLOW);S.top=S.base+S.maxsize;S.maxsize=S.maxsize+add;}*(S.top++)=e; //*(S.top)=e,S.top++;return OK;}Status Empty(Stack S){if(S.top==S.base)return OK;elsereturn ERROR;}Status Topo(ALGraph G,Stack &T){int i,j,k;Arode *p;Stack S;InitStack(S);for(j=0;jnext){k=p->adjvex;ID[k]--;if(ID[k]==0) Push(S,k);if( ( ve[j] + (p->info2) ) > ve[k] )ve[k]=ve[j]+(p->info2);}}if(countnext){k=p->adjvex;if(vl[k]-(p->info2)info2);}printf("关键顶点为a：");for(j=0;jnext){k=p->adjvex;ee=ve[j];el=vl[k]-(p->info2);if(el==ee)printf("%s ",p->info1);}}printf("\n");return OK;}int main(){ALGraph G;Init(G);CreateGraphic(G);Critial(G); return 0;}。