关键路径-数据结构课程设计任务书

课程设计(论文)任务书软件学院软件工程专业2011-2班一、课程设计(论文)题目数据结构课程设计二、课程设计(论文)工作自2012年12月17日起至2012年12月18日止。三、课程设计(论文)地点:软件工程实训中心四、课程设计(论文)内容要求：1．本课程设计的目的（1）使学生熟练掌握抽象数据类型的组织和定义；（2）使学生熟练掌握数据类型的定义和实现；（3）培养学生组织和分析数据的能力；（4）培养学生分析和应用基于不同数据结构的算法的能力；（5）提高学生的科技论文写作能力。2．基本要求：每位同学在以下题目中任选一题（在方框中打勾），独立完成课程设计：□稀疏矩阵运算：实现稀疏矩阵的输入、输出、加减乘的运算。□关键路径：求出完成整项工程至少需要多少时间以及整项工程中的关键活动。（1）能够输入并存储一个描述工程的AOE网；（1）对输入的AOE网，应判断其是否能够顺利进行；（2）若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。□银行业务模拟：参见《数据结构》教材P68。3．课程设计论文编写要求（1）要按照书稿的规格打印誊写课设报告；（2）报告分为封面、任务书（本文档）、正文、课程设计体会和参考文献四部分；学生签名：年月日课程设计(论文)评审意见（1）题目分析（20分）：优（）、良（）、中（）、一般（）、差（）；（2）流程分析（30分）：优（）、良（）、中（）、一般（）、差（）；（3）数据定义（30分）：优（）、良（）、中（）、一般（）、差（）；（4）代码编写（10分）：优（）、良（）、中（）、一般（）、差（）；（5）创新能力（10分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性、设计态度及考勤是否降等级：是（）、否（）评阅人：职称：讲师年月日3正文一、数据结构定义1.抽象数据类型本设计中用到的数据结构ADT定义如下：ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={v,w|v,w(-V且P(v,w),v,w表示从v到w的弧，谓词P(v,w)定义了弧v,w的意义或信息}基本操作P：CreateGraph(*G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。Thelongestkey_Way(*G,V,VR,T)初始条件：图G存在，T表示完成此项工程至少需要的时间。操作结果：利用V和VR计算出结果T。ThekeyWay()//关键活动函数初始条件：图G存在，函数调用的程序函数。操作结果：输入V和VR计算结果T。}ADTGraph42.存储结构定义数据存储结构的C语言定义如下：//邻接表类型typedefstructANode//弧的节点结构类型{intadjvex;//弧的终点位置（弧头）intdut;//弧的权值structANode*nextarc;//指向下一条弧的指针}ArcNode;typedefstruct//头结点的类型{intprojectname;//顶点域intid;//顶点的入度信息ArcNode*firstarc;//指向第一条弧}Vexnode;53.基本操作数据结构的基本操作实现如下：voidCreateGraph(Vexnode*G,intprojectnum,intactivenum)初始条件：projectnum是图的顶点集，activenum是图中弧的集合即活动时间。操作结果：输入顶点数和弧的值，构造图G。intThelongestkey_Way(Vexnode*G,intprojectnum,intactivenum,int&totaltime)初始条件：图G存在，totaltime是计算图中工程的时间。操作结果：由存在的图G，利用顶点和弧的关系信息，计算出工程至少需要的时间。voidThekeyWay()初始条件：由上面两个函数存在。操作结果：显示进入求关键活动的结果。Intmain()初始条件：由上面函数存在。操作结果：显示最终结果。6二、解题过程1.问题分解该问题主要应实现以下功能：（1）计算完成整个工程的至少需要的时间。（2）确定关键路径，以找出哪些活动时影响工程进度的关键。因此须计算以下几点：a.事件的最早发生时间ve[k]；b.事件最迟发生时间vl[k]；c.活动最早开始时间ee[i]；d.活动的最迟开始时间el[i]；计算其过程必须分别在拓扑有序和逆拓扑有序的前提下进行。也就说，ve[k]必须在事件vk所有前驱的最早发生的时间求得之后才能确定。因此，可以在拓扑排序的基础上计算ve[k]和vl[k]。由此得到求解关键路径的方法：首先输入e条有向边i,j，建立AOE-网的邻接表存储结构；然后从始点出发，令事件的最早发生时间为0，按拓扑有序求其余各顶点时间的最早发生时间ve[k]；(代码如下)while(p){k=p-adjvex;Graph[k].id--;if(ve[j]+p-wve[k])ve[k]=ve[j]+p-w;}7接着从终点出发，令事件最迟发生时间等于其最早发生时间，按逆拓扑排序求其余各顶点事件最迟发生时间vl[k]；最后根据各顶点事件的ve和vl值，求所有活动最早开始时间ee和最迟开始时间el。如果某活动满足条件ee＝el，则为关键活动。(代码如下)if(ee==el)//关键活动printf(是）；同时，为计算各顶点事件的ve值是在拓扑排序的过程中进行的，因此需一个队列来记录拓扑排序，如果顶点的入度为0，则该顶点从队尾进入队列，拓扑排序时，从队头出队列。(代码如下)if(G[k].id==0)//如果入度为0，则入队TopoQueue[++rear]=k;p=p-nextarc;//指向下一个结点82.模块结构系统主要由4个模块组成，分别是：（1）创建图（2）求完成此项工程至少要多少时间（3）求关键活动函数（4）主函数模块之间的结构如下：93.解题思路各模块的实现步骤为（1）首先主函数main();（2）调用实现求关键活动的函数ThekeyWay();（3）再调用CreateGraph(Vexnode*G,intprojectnum,intactivenum);创建图；（4）再调用Thelongestkey_Way(Vexnode*G,intprojectnum,intactivenum,int&totaltime)；求完成此项工程至少要多少时间10三、实现#includestdio.h#includestdlib.h//malloc();free();exit();#includeiomanip.h//I/O控制头文件#includeprocess.h//控制过程函数system(cls);//邻接表类型typedefstructANode//弧的节点结构类型{intadjvex;//弧的终点位置（弧头）intdut;//弧的权值structANode*nextarc;//指向下一条弧的指针}ArcNode;typedefstruct//头结点的类型{intprojectname;//顶点域intid;//顶点的入度信息ArcNode*firstarc;//指向第一条弧}Vexnode;voidCreateGraph(Vexnode*G,intprojectnum,intactivenum)//创建图{intbegin,end,duttem;//弧的前结点，尾结点，活动时间ArcNode*p;//弧指针for(inti=0;iprojectnum;i++)11{G[i].projectname=i;//顶点命名G[i].id=0;//顶点信息的度数均赋值为零G[i].firstarc=NULL;//顶点指针为空}printf(\n);printf(请输入活动工程的信息，温馨提示：（请用int型格式输入：弧尾，弧头，活动时间）\n);printf(例如：输入1,2,3即代表弧1,2的活动时间为3。\n);printf(\n);for(intk=0;kactivenum;k++)//activenum为活动的数目，即弧的条数{scanf(%d,%d,%d,&begin,&end,&duttem);//输入弧的前结点，尾结点，活动时间p=(ArcNode*)malloc(sizeof(ArcNode));//开辟弧的存储空间pp-adjvex=end-1;//数组下标从0开始记录，故减一，将弧头插入邻接表内p-dut=duttem;//此弧的活动时间为duttemG[end-1].id++;//弧头指向，入度+1p-nextarc=G[begin-1].firstarc;//插入弧p，使得下一结点作为下一条弧的弧尾（前结点）G[begin-1].firstarc=p;}}intThelongestkey_Way(Vexnode*G,intprojectnum,intactivenum,int&totaltime)//求完成此项工程至少要多少时间{12inti,j,k,m=0;intfront=-1,rear=-1;int*TopoQueue=(int*)malloc(projectnum*sizeof(int));//用拓扑序列保存数据int*vl=(int*)malloc(projectnum*sizeof(int));//vl表示最迟发生时间int*ve=(int*)malloc(projectnum*sizeof(int));//ve表示最早发生时间int*l=(int*)malloc(activenum*sizeof(int));//l表示活动最迟开始时间int*e=(int*)malloc(activenum*sizeof(int));//e表示活动最早开始时间ArcNode*p;totaltime=0;//完成此工程至少需要的时间for(i=0;iprojectnum;i++)ve[i]=0;//活动的最早发生时间均赋值为0for(i=0;iprojectnum;i++){if(G[i].id==0)//入度为0，即为头结点{TopoQueue[++rear]=i;//所有头结点队尾插入，且队尾指针+1m++;//记录入队列的顶点个数}}while(front!=rear)//队列不为“空”{front++;//出队列，队头指针+1j=TopoQueue[front];//结点依次出队列m++;//记录结点数p=G[j].firstarc;//指向其下一个顶点13while(p){k=p-adjvex;//弧头G[k].id--;//删除一个入度为0的前结点和其弧，入度减一if(ve[j]+p-dutve[k])//将最长路径赋值给ve[k]ve[k]=ve[j]+p-dut;if(G[k].id==0)//如果入度为0，则入队TopoQueue[++rear]=k;p=p-nextarc;//指向下一个结点}}if(mprojectnum)//设有环，则不能遍历{printf(\n工程建立的图有环，不能计算关键路径！\n);printf(即将退出工程！谢谢使用！\n);return0;}totaltime=ve[projectnum-1];//完成的至少时间为所有结点累加的时间和for(i=0;iprojectnum;i++)vl[i]=totaltime;for(i=projectnum-2;i=0;i--)//逆拓扑排序，求vl{j=TopoQueue[i];p=G[j].firstarc;14while(p){k=p-adjvex;//指向弧头if((vl[k]-p-dut)vl[j])vl[j]=vl[k]-p-dut;p=p-nextarc;}}i=0;printf(\n);printf(|起点（弧尾）|终点（弧头）|最早开始时间|最迟完成时间|活动差值|关键活动\