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]。

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

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

printf("%c",sv[i]);
if(sv[i]!=Graph[vexnumber-1].data)
printf("--->");
}
printf("\n");
printf("关键路径长度为：%d个单位时间\n",totaltime);
return 1;
}
void main( ) {
}
接着从终点出发，令事件最迟发生时间等于其最早发生时间，按你你逆拓扑排序求其余各顶点事件最迟发生时间vl[k]；最后根据各顶点事件的ve和vl值，求所有活动最早开始时间ee和最迟开始时间el。如果某活动满足条件ee＝el，则为关键活动。(代码如下)
if(el[i]==ee[i]) {
printf("此弧为关键活动");
if(el[i]==ee[i]) {
printf("此弧为关键活动");
sv[t]=Graph[j].data;t++;
}
printf("\n");
p=p->nextedge;
}
}
printf("关键路径节点为：");
sv[t]=Graph[vexnumber-1].data;
for(i=0;i<=t;i++){
}
同时，为计算各顶点事件的ve值是在拓扑排序的过程中进行的，因此需一个队列来记录拓扑排序，如果顶点的入度为0，则该顶点从队尾进入队列，拓扑排序时，从队头出队列。
if(Graph[k].ቤተ መጻሕፍቲ ባይዱd ==0)
topology_queue[++rear]=k;

数据结构实验报告-----用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。

}
}
cout<<"关键路径为："<<endl;
for(j = 0;j<algraph.vexnum;j++)
//求ee el和关键活动（同上）
{
for(p = algraph.vertices[j].firstarc;p;p = p->nextarc)
{
k = p->adjvex;
dut = *(p->info);
2、算法设计
源程序：
template <class T>
bool ALGraph<T>::TopologicalOrder(SeqStack<int> &t)
//求各顶点事件的最早发生时间ve
{
int j,k,count,indegree[MAX_VERTEX_NUM];
SeqStack<int> s;
count = 0;
for(j = 0;j<algraph.vexnum;j++)
{
ve[j] = 0;
}
while(!s.IsEmpty())
//S非空
{
s.Pop(j);
t.Push(j); count++; //j号顶点入T栈并计数
for(p = algraph.vertices[j].firstarc;p;p = p->nextarc)
1）画出运行程序中的图。
aቤተ መጻሕፍቲ ባይዱ
b
c
1 1d
e2
2）分析辅助变量的值。
答：j k dut ee e1 tag

在的边。
概
主函数：main()
建图函数：CreateGraph ()
要
求解关键路径函数：CriticalPath ()
设
计
int Criticalpath(ALGraph G){ /* G 为有向网，输出 G 的各项关键活动。*/
InitStack(T); /*建立用于产生拓扑逆序的栈 T*/ if (! TopologicalOrder (G,T) )
中中 T中中中中
j中中中中中中中
从 Vl(n)=Ve(n)开始向后递推
Vl(i) Min{Vl( j) dut( i, j )}, i, j S,1 i n 1 j
中中 S中中中中
i中中中中中中中
程序功能：根据输入的图的信息，能够建立 AOE-网，并能够输出关键路径所
e = ve [j]； l = vl [k] - dut;
tag = (e= =l) ? ‘*’:’’ ;
printf ( j,k,dut,e,l,tag ); /*输出关键活动*/ }
return 1; /*求出关键活动后返回 1*/ } /*Criticalpath*/
测试用例 1：如下图（顶点数和边数：9,11）
需
关键活动——关键路径上的活动，即 l(i)=e(i)的活动
求
设活动 ai 用弧<j,k>表示，其持续时间记为：dut(<j,k>)。则有：
e(i)=Ve(j)
描
l(i)=Vl(k)-dut(<j,k>)
如何求 Ve(j)和 Vl(j)？
述
从 Ve(1)=0 开始向前递推
Ve( j) Max{Ve(i) dut( i, j )}, i, j T ,2 j n i

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

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

在这篇文章中，我们将讨论关键路径输出的含义和计算方法，并使用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.课程设计心得这次的课程设计主要是对基础知识的灵活使用，这就让我进一步提高了对数据结构知识的巩固。

关键路径C语言课程设计一、课程目标知识目标：1. 学生能理解C语言中关键路径算法的基本概念，掌握关键路径的求解方法。

2. 学生能运用C语言实现图的邻接表表示，并能对其进行拓扑排序。

3. 学生能通过C语言编程识别关键路径，并计算出各个顶点的最早开始时间和最迟开始时间。

技能目标：1. 学生能运用C语言编写关键路径求解程序，提高编程能力。

2. 学生通过分析实际问题，培养解决问题的策略和逻辑思维能力。

3. 学生能运用所学知识，对实际项目进行时间管理和优化。

情感态度价值观目标：1. 学生在课程学习中，培养对计算机科学的兴趣和热情，增强学习动力。

2. 学生通过小组合作，培养团队协作精神和沟通能力。

3. 学生在学习过程中，树立正确的价值观，认识到编程在解决实际问题中的重要性。

课程性质：本课程为计算机科学与技术领域的基础课程，旨在帮助学生掌握C 语言在图论中的应用，提高编程能力和解决问题的能力。

学生特点：学生处于高年级阶段，已具备一定的C语言基础，具有较强的逻辑思维能力和独立解决问题的能力。

教学要求：结合学生特点和课程性质，注重理论与实践相结合，强调编程实践，提高学生的动手能力。

通过案例教学，激发学生的兴趣，培养其团队协作和沟通能力。

在教学过程中，关注学生的情感态度，引导其树立正确的价值观。

将课程目标分解为具体的学习成果，便于后续教学设计和评估。

二、教学内容1. 图的基本概念：图的定义、顶点和边、有向图和无向图、路径和连通性。

2. 邻接表表示：图的邻接表存储结构、邻接表的创建和遍历。

3. 拓扑排序：拓扑排序的概念、拓扑排序的算法实现。

4. 关键路径：关键路径的定义、关键路径的求解方法、最早开始时间和最迟开始时间的计算。

5. C语言实现关键路径算法：编写关键路径求解程序、调试和优化程序。

6. 实例分析：结合实际项目，分析关键路径的应用，进行时间管理和优化。

教材章节关联：第1节：图的基本概念（章节1.1）第2节：邻接表表示（章节2.3）第3节：拓扑排序（章节3.2）第4节：关键路径（章节4.3）第5节：C语言实现关键路径算法（章节5.1、5.2）第6节：实例分析（章节6.1）教学内容安排与进度：第1周：图的基本概念、邻接表表示第2周：拓扑排序第3周：关键路径、C语言实现关键路径算法第4周：实例分析、课程总结与拓展确保教学内容科学性和系统性，注重理论与实践相结合，引导学生通过实例掌握关键路径算法，提高编程能力和解决问题的能力。

数据结构课程设计报告题目：关键路径算法院（系）：计算机工程学院专业：计算机科学与技术班级：嵌入式1091学生：吕帅指导教师：寇海洲孙成富邱军林殷路2010年12月目录一、设计目的 (3)二、设计内容 (3)三、程序设计步骤 (4)四、调试分析 (12)五、测试结果 (12)六、课程设计小结 (16)一、设计目的1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。

2、提高程序设计和调试能力。

学生通过上机实习，验证自己设计的算法的正确性。

学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。

3、初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。

4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

5、培养根据选题需要选择学习书籍，查阅文献资料的自学能力。

二、设计内容1、系统名称：关键路径算法AOE网(即边表示活动的网络)，在某些工程估算方面非常有用。

它可以使人们了解：（1）研究某个工程至少需要多少时间？（2）哪些活动是影响工程进度的关键? 在AOE网络中，从源点到汇点的有向路径可能不止一条，但只有各条路径上所有活动都完成了，这个工程才算完成。

因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和，这条路径就叫做关键路径（critical path）。

2、要求：1 以某一工程为蓝本，采用图的结构表示实际的工程计划时间。

2 调查并分析和预测这个工程计划每个阶段的时间。

3 用调查的结果建立AOE网，并用图的形式表示。

4 用CreateGraphic ()函数建立图的邻接表存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中。

5 用SearchMaxPath()函数求出最大路径，并打印出关键路径。

c语言课程设计关键算法一、教学目标本课程的教学目标是使学生掌握C语言的关键算法。

通过本课程的学习，学生将能够：1.理解并掌握C语言的基本数据结构和算法概念。

2.能够运用C语言实现常用的排序、查找等算法。

3.能够分析算法的时间复杂度和空间复杂度。

4.能够运用关键算法解决实际问题，提高编程能力和解决问题的能力。

二、教学内容本课程的教学内容主要包括：1.C语言的基本数据结构：数组、链表、栈、队列等。

2.常见算法：排序算法（冒泡排序、选择排序、插入排序等）、查找算法（顺序查找、二分查找等）。

3.算法分析：时间复杂度和空间复杂度的概念及计算。

4.算法应用：运用关键算法解决实际问题，如数组排序、数据查找等。

三、教学方法本课程采用多种教学方法相结合的方式，包括：1.讲授法：讲解基本概念、算法原理和分析方法。

2.案例分析法：分析实际案例，引导学生运用算法解决问题。

3.实验法：上机实践，让学生动手实现和调试算法。

4.讨论法：学生进行分组讨论，促进学生之间的交流和思考。

四、教学资源本课程所需教学资源包括：1.教材：《C语言程序设计》。

2.参考书：《算法导论》、《数据结构与算法分析》等。

3.多媒体资料：课件、教学视频等。

4.实验设备：计算机、网络等。

以上教学资源将为实现课程目标提供支持，帮助学生更好地学习和掌握C语言的关键算法。

五、教学评估本课程的评估方式包括以下几个方面：1.平时表现：包括课堂参与度、提问回答、小组讨论等，占总评的20%。

2.作业：包括课后练习和编程作业，占总评的30%。

3.考试：包括期中考试和期末考试，占总评的50%。

以上评估方式旨在全面客观地反映学生的学习成果，同时激发学生的学习积极性和主动性。

六、教学安排本课程的教学安排如下：1.教学进度：按照教材的章节顺序进行教学，确保每个章节都有充分的授课和练习时间。

2.教学时间：每周安排2课时，共16周完成本课程的教学内容。

3.教学地点：教室和计算机实验室。

青岛理工大学数据结构课程设计报告题目：关键路径的实现院（系）：计算机工程学院学生姓名:班级：学号:起迄日期: 2014.7.8—2014.7.19指导教师: 张艳一、需求分析1.问题描述找出实际工程中的关键路径，合理安排关键活动的施工顺序。

要求：(1)表示工程的图可以用邻接表或邻接矩阵存储；(2)应能以图形的方式输出图；(3)输出关键路径和关键活动。

2.基本功能(1)用邻接表存储有向图并建立AOE网 CreateGraph（）；(2)用图形的形式输出有向图Display();(3)输出关键路径和关键活动 SearchMapPath（）；3.输入输出输入: (1)有向图的顶点数和弧数，都是int型，中间用空格隔开；(2)图中的各个顶点的值，char型;(3)图中弧的权值、起点、终点,都是int型，中间用空格隔开；输出：起点（char）、终点(char) 、最早开始时间(int)、最迟开始时间(int)、差值(int)、是否为关键活动、关键路径。

二、概要设计1.设计思路：(1) 输入图的顶点数和弧数。

(2) 输入这个图中每段弧的起始点及权值。

(3) 用输入的数据建立AOE网。

(4) 用邻接表来存储图的这些信息。

(5) 用CreateGraph( )函数建立AOE图。

(6)用Display()函数输出AOE图。

(7) 用SearchMapPath ( )函数求出最长路径，并输出关键路径。

(8) 编写程序。

2.数据结构设计：（1）逻辑结构采用图状的结构。

图是一种较线性表和树更为复杂的数据结构。

在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（即其孩子结点）相关，但只能和上一层中一个元素（即其双亲结点）相关；而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

数据结构课程设计报告---关键路径数 据 结 构课 程 设 计报 告院系： 信息管理学院 专业： 软件工程班级： 软件Q1141学号： 11150038姓名： 李艳平 教师： 邓沌华时间： 2013.4.2理论成绩 实践成绩 总成绩目录一、问题的描述二、系统需求及分析1、简要介绍2、需求分析3、概要设计4、详细设计(1)数据结构(2)创建有向图的邻接表(3)计算各事件及活动的相关信息(4)输出有向图的相关信息(5)判断图中是否有回路(6)计算并输出关键活动(7)计算并输出关键路径(8)操作入口三、系统实现四、设计总结五、附件（完整源代码）一、问题的描述：关键路径问题（起评分：85）1、功能：设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。

2、数据：自行设计每个活动的前导活动和后续活动以及活动的进行时间，然后依据这些活动的前后次序，画出其网络图，选择存储结构。

3、操作：（1）求工程最短工期；（2）输出关键路径；（3）输出关键活动。

4、要求：界面友好，提示信息完整。

二、系统需求及分析：1、简要介绍：我们通常把计划、施工过程、生产流程、程序流程等都当成一个工程。

工程通常分为若干个称为“活动”的子工程。

完成了这些“活动”，这个工程就可以完成了。

我们通常用AOE-网来表示工程。

AOE-网是一个带权的有向无环图，其中，顶点表示事件（EVENT），弧表示活动，权表示活动持续的时间。

AOE-网可以用来估算工程的完成时间。

他可以使人们了解：(1). 研究某个工程至少需要多少时间?(2). 哪些活动是影响工程进度的关键？由于AOE-网中的有些活动可以并行进行，从开始点到各个顶点，以致从开始点到完成点的有向路径可能不止一条，这些路径的长度也可能不同。

完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。

因此，完成工程所需的最短时间是从开始点到完成点的最长路径的长度，即在这条路径上的所有活动的持续时间之和.这条路径长度就叫做关键路径(Critical Path)。

数据结构课程设计题目：关键路径的设计报告科系：计算机科学与技术班级：姓名：题目：1、编写拓扑排序和求关键路径的程序2、单源顶点最短路径问题设计报告一．需求分析1.在实际工程中拓扑排序和求关键路径是经常使用来安排任务的先后顺序，以及找出关键的路径，合理的安排非关键任务的施工顺序。

2.对用邻接矩阵表示的有向图，从某一顶点出发（称为源点）到该图其它各顶点（称为终点）有无路径？最短路径是什么？路径长为多少？问题要求写一个程序从有向网中的某一顶点出发找出该顶点到其余各顶点的最短路径。

对邻接矩阵cost[n][n]中的每一个元素只能有三种情况：①当i=j时，cost[i][j]=0；②当顶点i和j无边时，cost[i][j]=∞；③当顶点i和j有边，且其权值为W ij时，cost[i][j]=W ij。

由于题目中没有规定输出格式，此程序以顶点序号的形式将最短路径输出到终端上去，并输出该最短路径的长度。

二．概要设计1.1抽象数据类型图的定义如下：ADT Graph{数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据对象I:I是具有相同特性的数据元素的集合,称为顶点集.数据关系R:R={VR}VR={(v,w)|v,w属于V,(v,w)表示v和w之间存在路径}基本操作P:Creat_ALGraph(&G,V,VR,I)初始条件:V是图的顶点集，VR是图中边的集合,I是边的权值。

操作结果:按V和VR的定义构造图G。

DFS(&G, v)初始条件:v是图的一个顶点，图G存在。

操作结果:从v点深度优先遍历图G。

DFSTraverse(&G)初始条件:图G存在。

操作结果：深度优先遍历图G。

FindIngree( G,b[])初始条件：图G存在，数组b[]已知。

操作结果:图G的每个顶点的度放在数组b中。

TopologicalSort(&G)初始条件:图G存在。

操作结果:对图G进行拓扑排序。

有向图的关键路径计算机与软件工程学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码:题目:年级/专业/班:学生姓名:学号:开始时间:2016 年 5 月8 日完成时间:2016 年5月18 日课程设计成绩：指导教师签名：年月日目录引言 (1)1需求分析 (1)1.1任务与分析 (1)1.2测试数据 (1)2 概要设计 (3)2.1设计思路 (3)2.2层次图 (3)3 详细设计 (4)3.1主函数的实现 (4)3.2数据录入实现 (5)3.3输出图的各顶点和弧的实现 (6)3.4计算各顶点的入度 (7)3.5输出关键路径 (8)4调试分析 (8)5用户使用说明 (9)6测试结果 (9)6.1录入数据 (9)6.2功能实现 (10)6.3测试结论 (11)致谢 (13)参考文献 (14)摘要具有最大路径长度的路径称关键路径，关键路径上的活动称关键活动。

课程设计主要要求求有向图的关键路径。

用领接表存储结构储存有向图。

用深度遍历的方式输出有向图的顶点和弧。

程序实现了存储有向图，输出有向图的各顶点和弧，计算顶点的入度和求有向图的关键路径这四个功能。

用领接表存储结构储存有向图，用深度遍历的方式输出有向图的顶点和弧，用遍历查找的方式计算顶点的入度。

求关键路径时先用拓扑排序函数判断有向图是否有回路，调用求关键活动的函数找到关键路径，最后输出。

关键词：领接表；入度；AOE网；关键路径；有向图的关键路径引言工程有很多的阶段，这些阶段之间有一定的先后关系和自己的时间。

我们可以用图来表示工程，将其输入程序中，可以用程序计算出工程的相关信息，如，工程完成的最短时间，哪些活动会影响工程的进度等。

要解决这些问题就可以用领接表储存图，并计算各个事件和各个阶段的最早发生时间和最晚发生时间，得到关键活动，从而的到关键路径。

1需求分析从键盘上输入图的各顶点和弧上的权值，用领接表储存。

在屏幕上输出图的顶点和弧。

计算输出顶点的入度。