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

关键路径代码课程设计一、教学目标本课程的教学目标是使学生掌握关键路径法的基本概念、计算方法和应用技巧。

通过本课程的学习，学生将能够：1.理解关键路径法的定义、原理和作用。

2.掌握关键路径法的计算步骤和技巧。

3.应用关键路径法分析项目的进度和风险。

4.能够运用关键路径法解决实际项目管理和工程问题。

二、教学内容本课程的教学内容主要包括以下几个部分：1.关键路径法的定义和原理：介绍关键路径法的概念、特点和应用范围。

2.关键路径法的计算：讲解关键路径法的计算步骤、技巧和注意事项。

3.关键路径法的应用：通过案例分析，使学生掌握关键路径法在项目管理和工程中的应用。

4.关键路径法的扩展：介绍关键路径法的改进和扩展方法，如PERT图、CPM分析等。

三、教学方法为了实现上述教学目标，我们将采用以下教学方法：1.讲授法：通过讲解、演示和案例分析，使学生掌握关键路径法的基本概念和计算方法。

2.讨论法：学生进行小组讨论，分享学习心得和实际应用经验。

3.实验法：安排实践环节，让学生动手操作，提高实际应用能力。

四、教学资源为了支持本课程的教学内容和教学方法，我们将准备以下教学资源：1.教材：选用权威、实用的教材，为学生提供系统的学习材料。

2.参考书：推荐相关参考书籍，丰富学生的知识体系。

3.多媒体资料：制作PPT、视频等多媒体资料，增强课堂趣味性和实用性。

4.实验设备：准备项目管理软件、计算器等实验设备，方便学生进行实践操作。

五、教学评估本课程的教学评估将采用多元化方式，全面、客观地评价学生的学习成果。

评估方式包括：1.平时表现：通过课堂参与、提问、讨论等环节，评估学生的学习态度和积极性。

2.作业：布置适量的作业，检查学生对知识的掌握和应用能力。

3.考试：设置期中考试和期末考试，全面测试学生的知识水平和运用能力。

4.项目实践：学生进行小组项目实践，评估学生在实际操作中的能力和团队协作精神。

六、教学安排本课程的教学安排将根据课程内容和学生的实际情况进行设计，确保教学进度合理、紧凑。

用C语言实现图的关键路径学生姓名：指导老师：肖增良摘要本课程设计主要解决图的关键路径的实现。

在项目管理中，编制网络计划的基本思想就是在一个庞大的网络图中找出关键路径，并对各关键活动，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。

而对非关键路径的各个活动，只要在不影响工程完工时间的条件下，抽出适当的人力、物力和财力等资源，用在关键路径上，以达到缩短工程工期，合理利用资源等目的。

在执行计划过程中，可以明确工作重点，对各个关键活动加以有效控制和调度。

关键路径法将项目分解成为多个独立的活动并确定每个活动的工期，然后用逻辑关系（结束-开始、结束-结束、开始-开始和开始结束）将活动连接，从而能够计算项目的工期、各个活动时间特点（最早最晚时间、时差）等。

在关键路径法的活动上加载资源后，还能够对项目的资源需求和分配进行分析。

在本程序设计中，要求实现图的关键路径，最小生成树，判断两点之间是否有路径，程序由2个模块组成，分别为主函数的创建及其他相关函数的设计。

程序通过调试运行，初步实现了设计目标。

在课程设计中，系统开发平台为Windows 2000，程序设计设计语言采用Visual C++，数据库采用MS SQL 2000，程序运行平台为Windows 98/2000/XP。

关键词程序设计；数据库；SQL；C++；图；关键路径1 引言1.1 课题背景数据结构课程是计算机专业最重要的基础课之一，主要研究分析计算机存储、组织数据的方式，使学生能够根据数据对象的特征，选择适当的数据结构、存储结构及相应算法，初步掌握各种算法在时间和空间上的分析技巧，并能够进行算法和程序设计，使所涉及的程序结构清楚，正确易读[3]。

数据的组织方法和现实世界问题在计算机内部的表示方法，并能针对应用问题，选择合适的数据逻辑结构、存储结构及其算法，掌握解决复杂问题的程序设计方法和技术。

选择合适的数据结构更容易设计出更高效运行或存储效率的算法；图是一种较线性表和树更为复杂的数据结构。

数据结构实验报告-----用C#实现关键路径using System;using System.Collections.Generic;using System.Text;namespace LJH.AOE{//项目过程public class ProjectItem{//起始项目private int begin;//终止项目private int end;//所用的时间private int buttom;//构造函数public ProjectItem(int b,int e,int but){begin= b;end= e;buttom= but;}//属性public int Begin{get{return begin;}set{begin= value;}}public int End{get{return end;}set{end= value;}}public int Buttom{get{return buttom;}set{buttom= value;}}}//结点类public class EdgeNode{private int adjvex;/* 邻接点域*/private int period;/* 时间域*/private EdgeNode next;public int Adjvex{get{return adjvex;}set{adjvex= value;}}public int Period{get{return period;}set{period= value;}}public EdgeNode Nextget{return next;}set{next= value;}}}//定义链接图的类型public class Vexnode{private string vertex;private int id;private EdgeNode link;//属性public string Vertex{get{return vertex;}set{vertex= value;}}public int ID{get{return id;}set{id= value;}}public EdgeNode Link{getreturn link;}set{link= value;}}}//AOE网public class AlGraph{private Vexnode[] graphic;private int projectnum;private int activenum;private int totaltime;int[] vl ;int[] ve ;int[] l ;int[] e ;//属性public Vexnode[] Graphic{get{return graphic;}set{graphic= value;}}public int TotalTime{get{return totaltime;}}public int[] Vl{getreturn vl;}}public int[] Ve{get{return ve;}}public int[] L{get{return l;}}public int[] E{get{return e;}}//构造函数public AlGraph(int pnum,int anum){totaltime= 0;projectnum= pnum;activenum= anum;graphic= new Vexnode[pnum];for (int i= 0; i< projectnum; i++){graphic[i]= new Vexnode();}}//建立AOE网private void CreateGraph(ProjectItem[] item){for (int i= 0; i< projectnum; i++){graphic[i].Vertex= i.ToString();graphic[i].ID= 0;graphic[i].Link= null;}for (int k= 0; k< activenum; k++){EdgeNode p= new EdgeNode();p.Adjvex= item[k].End- 1;p.Period= item[k].Buttom;graphic[item[k].End- 1].ID++;p.Next= graphic[item[k].Begin- 1].Link;graphic[item[k].Begin- 1].Link= p;}}//搜索关键路径public bool SearchMap(ProjectItem[] item){int rear= -1, m= 0, front= -1, j, k;EdgeNode p;CreateGraph(item);int[] topstack= new int[projectnum];l= new int[activenum*2];e= new int[activenum*2];vl= new int[projectnum];ve= new int[projectnum];for (int i= 0; i< projectnum; i++){ve[i]= 0;}for (int i= 0; i< projectnum; i++){if (graphic[i].ID== 0){topstack[++rear]= i;m++;}}while (front!= rear){front++;j= topstack[front];m++;p= graphic[j].Link;while (p!= null){k= p.Adjvex;graphic[k].ID--;if (ve[j]+ p.Period> ve[k]){ve[k]= ve[j]+ p.Period;}if (graphic[k].ID== 0){topstack[++rear]= k;}p= p.Next;}}if (m< projectnum){return false;}totaltime= ve[projectnum- 1];for (int i= 0; i< projectnum; i++){vl[i]= totaltime;}for (int i= projectnum- 2; i>= 0; i--){j= topstack[i];p= graphic[j].Link;while (p!= null){k= p.Adjvex;if ((vl[k]- p.Period)< vl[j])vl[j]= vl[k]- p.Period;p= p.Next;}}return true;}}}。

关键路径法c语言详解关键路径法是一种用于项目管理的技术，用于确定项目中最长的路径，即关键路径，以便有效地进行资源分配和时间管理。

在本文中，我们将详细介绍关键路径法的原理和应用，并使用C语言进行示例演示。

一、原理介绍关键路径法是一种基于网络图的分析方法，它将项目分解成一系列活动，并通过活动之间的依赖关系构建网络图。

在这个网络图中，每个活动表示一个任务，箭头表示任务之间的依赖关系。

根据活动的持续时间和依赖关系，我们可以计算出每个活动的最早开始时间（EST）和最晚开始时间（LST），从而确定关键路径。

关键路径是指项目中最长的路径，即这条路径上的活动不能延迟，否则会导致整个项目延迟。

关键路径上的活动被称为关键活动。

通过确定关键路径，项目管理者可以有效地分配资源和控制进度，以确保项目按时完成。

二、关键路径法的步骤1. 确定项目的活动和依赖关系：将项目分解成一系列活动，并确定它们之间的依赖关系。

活动可以使用字母或数字进行标识，依赖关系可以用箭头表示。

2. 构建网络图：根据活动和依赖关系，构建项目的网络图。

网络图可以使用邻接矩阵或邻接表表示。

3. 计算活动的最早开始时间（EST）：从起始节点开始，根据依赖关系和活动持续时间，计算每个活动的最早开始时间。

最早开始时间可以通过递归或拓扑排序算法计算得出。

4. 计算活动的最晚开始时间（LST）：从终止节点开始，根据依赖关系和活动持续时间，计算每个活动的最晚开始时间。

最晚开始时间可以通过逆序递归或拓扑排序算法计算得出。

5. 计算活动的总时差（TF）：根据最早开始时间和最晚开始时间，计算每个活动的总时差。

总时差可以通过最晚开始时间减去最早开始时间得出。

6. 确定关键路径：找出总时差为0的活动，这些活动构成了关键路径。

关键路径上的活动不能延迟，否则会延误整个项目。

三、C语言示例演示以下是一个使用C语言实现关键路径法的简单示例：```c#include <stdio.h>void calculate_early_start(int activity[], int duration[], int dependency[], int n, int est[]) {for (int i = 0; i < n; i++) {if (dependency[i] == -1) {est[i] = 0;} else {if (est[dependency[i]] + duration[dependency[i]] > est[i]) {est[i] = est[dependency[i]] + duration[dependency[i]];}}}}void calculate_late_start(int activity[], int duration[], int dependency[], int n, int est[], int lst[]) {lst[n - 1] = est[n - 1];for (int i = n - 2; i >= 0; i--) {if (dependency[i] == -1) {lst[i] = lst[i + 1] - duration[i];} else {if (est[i] > lst[i + 1] - duration[i]) {lst[i] = est[i];} else {lst[i] = lst[i + 1] - duration[i];}}}}void find_critical_activities(int est[], int lst[], int n) {printf("Critical activities: ");for (int i = 0; i < n; i++) {if (est[i] == lst[i]) {printf("%d ", i + 1);}}printf("\n");}int main() {int n = 6; // Number of activitiesint activity[] = {1, 2, 3, 4, 5, 6}; // Activity IDsint duration[] = {5, 3, 2, 4, 2, 6}; // Durationsint dependency[] = {-1, 1, 2, 1, 4, 3}; // Dependency (indexstarts from 0)int est[n]; // Early start timesint lst[n]; // Late start timescalculate_early_start(activity, duration, dependency, n, est); calculate_late_start(activity, duration, dependency, n, est, lst);printf("Activity\tDuration\tEST\t\tLST\n");for (int i = 0; i < n; i++) {printf("%d\t\t%d\t\t%d\t\t%d\n", activity[i], duration[i], est[i], lst[i]);}find_critical_activities(est, lst, n);return 0;}```在上述示例中，我们使用了一个包含6个活动的项目进行演示。

数据结构课程设计报告小组成员：王瑞琦 13052007 姜薇 13052011 刘倩 13052027小组课题：1-1有向图十字链表的操作2-5 关键路径有向图十字链表的操作功能概述将有向图以是十字链表的形式存储，并借助十字链表对有向图进行查找有向图中指定结点的度（出度和入度）、插入有向边和删除有向边等操作。

模块简介创建有向图十字链表：void creat_crosslink(ALGraph *&G,char vex[],int n,etype edge[],int e)查找结点在十字链表中的位置：int LocateVex(ALGraph *G,Vertex u)插入指定边：bool InsertArc(ALGraph *G,etype a)删除指定边：bool DeletetArc(ALGraph *G,etype a)查找有向图中指定结点的度（出度和入度）：int Count(ALGraph *G,Vertex u)数据类型/*边的数据类型*/typedef struct{ char vi,vj;int info;}etype;/*弧结点数据类型*/typedef struct ArcNode{ int tailvex,headvex;/* 该弧的尾和头顶点的位置*/struct ArcNode *hlink,*tlink;/* 分别为弧头相同和弧尾相同的弧的链域*/InfoType info;/*若为网络则为权值*/}ArcNode;/*表头结点数据类型*/typedef struct VexNode{ Vertex data;ArcNode *firstin,*firstout; /* 指向该顶点的第一条入弧和出弧*/}VexNode;typedef VexNode AdjList[MAXV];/*十字链表数据类型*/typedef struct{ AdjList adjlist;int n,e;/*图中顶点数n和边数e*/}ALGraph;概要设计CreateDG(建表)（1）获取有向图的顶点数、弧数并存入；（2）依次获取各顶点的值，存入数组，构建十字链表头结点向量组；（3）依次获取弧信息，存入，确认弧结点在十字链表中的位置并对弧赋值；（4）十字链表创建成功；LocateVex(查找)传参：有向图，顶点利用指针依次扫描表头数组，当找到该顶点时，返回该顶点在十字链表表头数组的位置（序号），未找到该顶点时，返回-1。

关键路径输出是项目管理中的重要概念，它指的是项目中最长的任务路径。

在项目管理中，对于关键路径的确定可以帮助项目团队合理安排资源，确保项目按时完成。

在这篇文章中，我们将讨论关键路径输出的含义和计算方法，并使用C语言实现关键路径输出的算法。

一、关键路径输出的含义关键路径输出是指在项目管理中，确定项目中最长的任务路径，该路径上的任务对于项目的完成时间具有关键作用。

在关键路径上的任务如果出现延误，将会直接影响整个项目的进度。

二、关键路径输出的计算方法1.确定活动的最早开始时间（ES）最早开始时间是指最早可以开始执行活动的时间。

对于一个活动来说，它的最早开始时间等于其前置活动的最早完成时间。

最早开始时间的计算方法可以使用如下公式进行计算：ES = Max{前置活动的最早完成时间} + 12.确定活动的最晚开始时间（LS）最晚开始时间是指在不影响项目进度的前提下，活动最晚可以开始的时间。

对于最后一个活动来说，其最晚开始时间等于其最早开始时间。

对于其他活动来说，其最晚开始时间等于其最晚完成时间减去活动持续时间。

最晚开始时间的计算方法可以使用如下公式进行计算：LS = Min{后继活动的最晚开始时间} - 活动持续时间3.确定活动的最早完成时间（EF）最早完成时间是指最早可以完成活动的时间。

对于一个活动来说，它的最早完成时间等于其最早开始时间加上活动持续时间。

最早完成时间的计算方法可以使用如下公式进行计算：EF = ES + 活动持续时间4.确定活动的最晚完成时间（LF）最晚完成时间是指在不影响项目进度的前提下，活动最晚可以完成的时间。

对于最后一个活动来说，其最晚完成时间等于其最晚开始时间。

对于其他活动来说，其最晚完成时间等于其后继活动的最晚开始时间减去活动持续时间。

最晚完成时间的计算方法可以使用如下公式进行计算：LF = Min{后继活动的最晚开始时间} - 15.确定活动的总时差（TS）总时差是指在不影响项目进度的前提下，活动可以推迟的时间。

中北大学数据结构课程设计说明书2011年12月20日设计内容：设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。

1、对一个描述工程的AOE网，应判断其是否能够顺利进行。

2、若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。

设计要求：(1) 符合课题要求，实现相应功能；(2) 要求界面友好美观，操作方便易行；(3) 注意程序的实用性、安全性；1.本设计所采用的数据结构（图）程序流程图2.功能模块详细设计2.1 详细设计思想主函数switch()对条件进行选择判断，进入关键路径的程序，然后对结点数的接收，分配相应的存储空间，构建AOE-网，逐个对图结点信息（包括俩邻接点，权值）输入接收，并与分配存储空间。

寻找关键路径：构建栈用与存储拓扑排序序列，求得每个接点的相应最早发生时间，最迟完成时间，关键事件的求取，并输出关键路径。

2.2 核心代码#include "stdafx.h"#include <cstdio>#include <cstdlib>#include <iostream>#include <iomanip>#include <process.h>using namespace std;//#define PROJECTUNMBER 9//10//#define PLANNUMBER 11//13typedef struct node{int adjvex;int dut;struct node *next;}edgenode;typedef struct{int projectname;int id;edgenode *link;}vexnode;//vexnode Graphicmap[PROJECTNUMBER];void GreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber){int begin,end,duttem;edgenode *p;for(int i=0;i<projectnumber;i++){Graphicmap[i].projectname=i;Graphicmap[i].id=0;Graphicmap[i].link=NULL;}printf("某项目的开始到结束在图中的节点输入<vi,vj,dut>\n");printf("如：3，4，9回车表示第三节点到第四节点之间的活动用了9个单位时间\n");printf("*********************************************\n");for(int k=0;k<activenumber;k++){scanf("%d,%d,%d",&begin,&end,&duttem);p=(edgenode*)malloc(sizeof(edgenode));p->adjvex=end-1;p->dut=duttem;Graphicmap[end-1].id++;p->next=Graphicmap[begin-1].link;Graphicmap[begin-1].link=p;}}int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int& totaltime){int i,j,k,m=0;int front=-1,rear=-1;int* topologystack=(int*)malloc(projectnumber*sizeof(int));//用来保存拓扑排列int* vl=(int*)malloc(projectnumber*sizeof(int));//用来表示在不推迟整个工程的前提下，vl允许最迟发生时间int* ve=(int*)malloc(projectnumber*sizeof(int));//用来表示vj最早发生时间int* l=(int*)malloc(activenumber*sizeof(int));//用来表示活动Ai最迟完成开始时间int* e=(int*)malloc(activenumber*sizeof(int));//表示活动最早开始时间edgenode *p;totaltime=0;for(i=0;i<projectnumber;i++) ve[i]=0;for(i=0;i<projectnumber;i++){if(Graphicmap[i].id==0){topologystack[++rear]=i;m++;}}while(front!=rear){front++;j=topologystack[front];m++;p=Graphicmap[j].link;while(p){k=p->adjvex;Graphicmap[k].id--;if(ve[j]+p->dut>ve[k])ve[k]=ve[j]+p->dut;if(Graphicmap[k].id==0)topologystack[++rear]=k;p=p->next;}}if(m<projectnumber){printf("\n本程序说建立的图有回路不可计算出关键路径\n");printf("将退出本程序\n");return 0;}totaltime=ve[projectnumber-1];for(i=0;i<projectnumber;i++)vl[i]=totaltime;for(i=projectnumber-2;i>=0;i--){j=topologystack[i];p=Graphicmap[j].link;while(p){k=p->adjvex;if((vl[k]-p->dut)<vl[j])vl[j]=vl[k]-p->dut;p=p->next;}}i=0;printf("|起点|终点|最早开始时间|最迟完成时间|差值| 备注|\n");for(j=0;j<projectnumber;j++){p=Graphicmap[j].link;while(p){k=p->adjvex;e[++i]=ve[j];l[i]=vl[k]-p->dut;printf("| %4d | %4d | %4d | %4d | %4d |",Graphicmap[j].projectname+1,Graphicmap[k].projectname+1,e[i],l[i],l[i]-e[i]);if(l[i]==e[i])printf("关键活动 |");printf("\n");p=p->next;}}return 1;}void seekkeyroot(){int projectnumber,activenumber,totaltime=0;system("cls");printf("请输出这个工程的化成图形的节点数：");scanf("%d",&projectnumber);printf("\n");printf("请输入这个工程的活动个数:");scanf("%d",&activenumber);printf("\n");vexnode*Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode));GreateGraphic(Graphicmap,projectnumber,activenumber);SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime);printf("整个工程所用的最短时间为：%d个单位时间\n",totaltime);system("pause");}int main(){char ch;for(;;){do{system("cls");printf("| 欢迎进入求关键路径算法程序 |");for(int i=0;i<80;i++)printf("*");printf("\n");printf("%s","(S)tart 开始输入工程的节点数据并求出关键路径\n");printf("\n");printf("%s","(E)xit 退出\n");printf("\n");printf("%s","请输入选择:");scanf("%c",&ch);ch=toupper(ch);if(ch!='S'&&ch!='E')printf("请输入正确的字符！\n");system("pause");}while(ch!='S'&&ch!='E');switch(ch){case'S':seekkeyroot();break;case'E':return 1;}}}2.3程序运行结果输入S开始程序（如图）输入节点数和活动个数（如图）输入E，退出程序3.课程设计心得这次的课程设计主要是对基础知识的灵活使用，这就让我进一步提高了对数据结构知识的巩固。