数据结构课程设计汇本:拓扑排序和关键路径
- 格式:doc
- 大小:721.50 KB
- 文档页数:28
数据结构的应用的拓扑排序与关键路径算法拓扑排序与关键路径算法是数据结构中重要的应用之一。
拓扑排序通过对有向图的节点进行排序,使得对于任意一条有向边(u,v),节点 u 在排序中都出现在节点 v 之前。
关键路径算法则是用来确定一个项目的关键活动和最短完成时间。
拓扑排序的实现可以通过深度优先搜索或者广度优先搜索来完成。
深度优先搜索是递归地访问节点的所有未访问过的邻居节点,直到没有未访问过的邻居节点为止,然后将该节点添加到拓扑排序的结果中。
广度优先搜索则是通过使用队列来实现的,将节点的邻居节点逐个入队并进行访问,直到队列为空为止。
无论使用哪种方法,拓扑排序都可以通过判断节点的入度来进行。
拓扑排序在很多实际问题中都有广泛应用。
比如在任务调度中,拓扑排序可以用来确定任务间的依赖关系和执行顺序;在编译原理中,拓扑排序可以用来确定程序中变量的定义和使用顺序。
关键路径算法用于确定项目中的关键活动和最短完成时间。
它通过计算每个活动的最早开始时间和最晚开始时间,以及每个活动的最早完成时间和最晚完成时间来实现。
具体步骤如下:1. 构建有向加权图,其中节点表示项目的活动,有向边表示活动间的先后关系,边的权重表示活动的持续时间。
2. 进行拓扑排序,确定活动的执行顺序。
3. 计算每个活动的最早开始时间,即从起始节点到该节点的最长路径。
4. 计算每个活动的最晚开始时间,即从终止节点到该节点的最长路径。
5. 根据每个活动的最早开始时间和最晚开始时间,可以确定关键活动,即最早开始时间与最晚开始时间相等的活动。
6. 计算整个项目的最短完成时间,即从起始节点到终止节点的最长路径。
拓扑排序与关键路径算法在工程管理、任务调度、生产流程优化等领域都有重要应用。
它们能够帮助我们有效地组织和管理复杂的项目,提高工作效率和资源利用率。
在实际应用中,我们可以借助计算机编程以及各种图算法库来实现这些算法,从而更快速、准确地解决实际问题。
综上所述,拓扑排序与关键路径算法是数据结构的重要应用之一。
数据结构课设——有向图的深度、⼴度优先遍历及拓扑排序任务:给定⼀个有向图,实现图的深度优先, ⼴度优先遍历算法,拓扑有序序列,并输出相关结果。
功能要求:输⼊图的基本信息,并建⽴图存储结构(有相应提⽰),输出遍历序列,然后进⾏拓扑排序,并测试该图是否为有向⽆环图,并输出拓扑序列。
按照惯例,先上代码,注释超详细:#include<stdio.h>#include<stdlib.h>#include<malloc.h>#pragma warning(disable:4996)#define Max 20//定义数组元素最⼤个数(顶点最⼤个数)typedef struct node//边表结点{int adjvex;//该边所指向结点对应的下标struct node* next;//该边所指向下⼀个结点的指针}eNode;typedef struct headnode//顶点表结点{int in;//顶点⼊度char vertex;//顶点数据eNode* firstedge;//指向第⼀条边的指针,边表头指针}hNode;typedef struct//邻接表(图){hNode adjlist[Max];//以数组的形式存储int n, e;//顶点数,边数}linkG;//以邻接表的存储结构创建图linkG* creat(linkG* g){int i, k;eNode* s;//边表结点int n1, e1;char ch;g = (linkG*)malloc(sizeof(linkG));//申请结点空间printf("请输⼊顶点数和边数:");scanf("%d%d", &n1, &e1);g->n = n1;g->e = e1;printf("顶点数:%d 边数:%d\n", g->n, g->e);printf("请输⼊顶点信息(字母):");getchar();//因为接下来要输⼊字符串,所以getchar⽤于承接上⼀条命令的结束符for (i = 0; i < n1; i++){scanf("%c", &ch);g->adjlist[i].vertex = ch;//获得该顶点数据g->adjlist[i].firstedge = NULL;//第⼀条边设为空}printf("\n打印顶点下标及顶点数据:\n");for (i = 0; i < g->n; i++)//循环打印顶点下标及顶点数据{printf("顶点下标:%d 顶点数据:%c\n", i, g->adjlist[i].vertex);}getchar();int i1, j1;//相连接的两个顶点序号for (k = 0; k < e1; k++)//建⽴边表{printf("请输⼊对<i,j>(空格分隔):");scanf("%d%d", &i1, &j1);s = (eNode*)malloc(sizeof(eNode));//申请边结点空间s->adjvex = j1;//边所指向结点的位置,下标为j1s->next = g->adjlist[i1].firstedge;//将当前s的指针指向当前顶点上指向的结点g->adjlist[i1].firstedge = s;//将当前顶点的指针指向s}return g;//返回指针g}int visited[Max];//标记是否访问void DFS(linkG* g, int i)//深度优先遍历{eNode* p;printf("%c ", g->adjlist[i].vertex);visited[i] = 1;//将已访问过的顶点visited值改为1p = g->adjlist[i].firstedge;//p指向顶点i的第⼀条边while (p)//p不为NULL时(边存在){if (visited[p->adjvex] != 1)//如果没有被访问DFS(g, p->adjvex);//递归}p = p->next;//p指向下⼀个结点}}void DFSTravel(linkG* g)//遍历⾮连通图{int i;printf("深度优先遍历;\n");//printf("%d\n",g->n);for (i = 0; i < g->n; i++)//初始化为0{visited[i] = 0;}for (i = 0; i < g->n; i++)//对每个顶点做循环{if (!visited[i])//如果没有被访问{DFS(g, i);//调⽤DFS函数}}}void BFS(linkG* g, int i)//⼴度优先遍历{int j;eNode* p;int q[Max], front = 0, rear = 0;//建⽴顺序队列⽤来存储,并初始化printf("%c ", g->adjlist[i].vertex);visited[i] = 1;//将已经访问过的改成1rear = (rear + 1) % Max;//普通顺序队列的话,这⾥是rear++q[rear] = i;//当前顶点(下标)队尾进队while (front != rear)//队列⾮空{front = (front + 1) % Max;//循环队列,顶点出队j = q[front];p = g->adjlist[j].firstedge;//p指向出队顶点j的第⼀条边while (p != NULL){if (visited[p->adjvex] == 0)//如果未被访问{printf("%c ", g->adjlist[p->adjvex].vertex);visited[p->adjvex] = 1;//将该顶点标记数组值改为1rear = (rear + 1) % Max;//循环队列q[rear] = p->adjvex;//该顶点进队}p = p->next;//指向下⼀个结点}}}void BFSTravel(linkG* g)//遍历⾮连通图{int i;printf("⼴度优先遍历:\n");for (i = 0; i < g->n; i++)//初始化为0{visited[i] = 0;}for (i = 0; i < g->n; i++)//对每个顶点做循环{if (!visited[i])//如果没有被访问过{BFS(g, i);//调⽤BFS函数}}}//因为拓扑排序要求⼊度为0,所以需要先求出每个顶点的⼊度void inDegree(linkG* g)//求图顶点⼊度{eNode* p;int i;for (i = 0; i < g->n; i++)//循环将顶点⼊度初始化为0{g->adjlist[i].in = 0;}for (i = 0; i < g->n; i++)//循环每个顶点{p = g->adjlist[i].firstedge;//获取第i个链表第1个边结点指针while (p != NULL)///当p不为空(边存在){g->adjlist[p->adjvex].in++;//该边终点结点⼊度+1p = p->next;//p指向下⼀个边结点}printf("顶点%c的⼊度为:%d\n", g->adjlist[i].vertex, g->adjlist[i].in);}void topo_sort(linkG *g)//拓扑排序{eNode* p;int i, k, gettop;int top = 0;//⽤于栈指针的下标索引int count = 0;//⽤于统计输出顶点的个数int* stack=(int *)malloc(g->n*sizeof(int));//⽤于存储⼊度为0的顶点for (i=0;i<g->n;i++)//第⼀次搜索⼊度为0的顶点{if (g->adjlist[i].in==0){stack[++top] = i;//将⼊度为0的顶点进栈}}while (top!=0)//当栈不为空时{gettop = stack[top--];//出栈,并保存栈顶元素(下标)printf("%c ",g->adjlist[gettop].vertex);count++;//统计顶点//接下来是将邻接点的⼊度减⼀,并判断该点⼊度是否为0p = g->adjlist[gettop].firstedge;//p指向该顶点的第⼀条边的指针while (p)//当p不为空时{k = p->adjvex;//相连接的顶点(下标)g->adjlist[k].in--;//该顶点⼊度减⼀if (g->adjlist[k].in==0){stack[++top] = k;//如果⼊度为0,则进栈}p = p->next;//指向下⼀条边}}if (count<g->n)//如果输出的顶点数少于总顶点数,则表⽰有环{printf("\n有回路!\n");}free(stack);//释放空间}void menu()//菜单{system("cls");//清屏函数printf("************************************************\n");printf("* 1.建⽴图 *\n");printf("* 2.深度优先遍历 *\n");printf("* 3.⼴度优先遍历 *\n");printf("* 4.求出顶点⼊度 *\n");printf("* 5.拓扑排序 *\n");printf("* 6.退出 *\n");printf("************************************************\n");}int main(){linkG* g = NULL;int c;while (1){menu();printf("请选择:");scanf("%d", &c);switch (c){case1:g = creat(g); system("pause");break;case2:DFSTravel(g); system("pause");break;case3:BFSTravel(g); system("pause");break;case4:inDegree(g); system("pause");break;case5:topo_sort(g); system("pause");break;case6:exit(0);break;}}return0;}实验⽤图:运⾏结果:关于深度优先遍历 a.从图中某个顶点v 出发,访问v 。
数据结构关键路径 如果在有向⽆环图中⽤有向边表⽰⼀个⼯程中的各项活动(Activity),⽤有向边上的权值表⽰活动的持续时间(duration),⽤顶点表⽰事件(Event),则这种有向图叫做⽤边表⽰活动的⽹络(activity on edges),简称AOE⽹络。
例如: 其中,E i表⽰事件,a k表⽰活动。
E0是源点,E8是汇点。
完成整个⼯程所需的时间等于从源点到汇点的最长路径长度,即该路径中所有活动的持续时间之和最⼤。
这条路径称为关键路径(critical path)。
关键路径上所有活动都是关键活动。
所谓关键活动(critical activity),是不按期完成会影响整个⼯程进度的活动。
只要找到关键活动,就可以找到关键路径。
与计算关键活动有关的量: 1 事件E i的最早可能开始时间:Ee[i]—从源点E0到顶点E i的最长路径长度。
在上图中,Ee[4]=7。
2 事件E i的最迟允许开始时间:El(⼩写L)[i]—在保证汇点E n-1最迟允许开始时间El[n-1]等于整个⼯程所需时间的前提下,等于El[n-1]减去从E i到E n-1的最长路径长度。
3 活动a k的最早可能开始时间:e[k]—设该活动在有向边<E i,E j>上,从源点E0到顶点E i的最长路径长度,即等于Ee[i]。
4 活动a k的最迟允许开始时间:l(⼩写L)[k]—设该活动在有向边<E i,E j>上,在不会引起时间延误的前提下,允许的最迟开始时间。
l[k]=El[j]-dur(<E i,E j>),其中dur(<E i,E j>)是完成该活动所需的时间,即有向边<E i,E j>的权值。
l[k]-e[k]表⽰活动a k的最早可能开始时间和最迟允许开始时间的时间余量,也叫做松弛时间(slack time)。
没有时间余量的活动是关键活动。
算法步骤: 1 输⼊顶点数和边数,再输⼊每条边的起点编号、终点编号和权值。
数据结构教案第七章图第7章图【学习目标】1.领会图的类型定义。
2.熟悉图的各种存储结构及其构造算法,了解各种存储结构的特点及其选用原则。
3.熟练掌握图的两种遍历算法。
4.理解各种图的应用问题的算法.【重点和难点】图的应用极为广泛,而且图的各种应用问题的算法都比较经典,因此本章重点在于理解各种图的算法及其应用场合。
【知识点】图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径【学习指南】离散数学中的图论是专门研究图性质的一个数学分支,但图论注重研究图的纯数学性质,而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等.图是较线性表和树更为复杂的数据结构,因此和线性表、树不同,虽然在遍历图的同时可以对顶点或弧进行各种操作,但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法,在本章中主要是介绍它们在计算机中的具体实现。
这些算法乍一看都比较难,应多对照具体图例的存储结构进行学习。
而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似,应将两者的算法对照学习以便提高学习的效益。
【课前思考】1。
你有没有发现现在的十字路口的交通灯已从过去的一对改为三对,即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。
你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的”五叉路口交通管理示意图”相类似的图?2。
如果每次让三条路同时通行,那么从图看出哪些路可以同时通行?同时可通行的路为:(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC)目录第7章图 (1)7.1图的定义和基本术语 (1)7.2图的存储和创建 (2)7.2.1 图的存储表示 (2)7。
2.2 图的创建 (5)7。
3图的遍历 (5)7。
3.1 深度优先搜索 (5)7.3.2 广度优先搜索 (6)7。
4遍历算法的应用 (8)7.4。
《大话数据结构》笔记——第7章图(三)文章目录7.8 拓扑排序7.8.1 拓扑排序介绍7.8.2 拓扑排序算法7.9 关键路径7.9.1 关键路径算法原理7.9.2 关键路径算法7.10 回顾总结7.8 拓扑排序说了两个有环的图应用,现在我们来谈谈无环的图应用。
无环,即是图中没有回路的意思。
7.8.1 拓扑排序介绍在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称为 AOV 网( Activity On Vertex Network )。
AOV 网中的弧表示活动之间存在的某种制约关系。
比如演职人员确定了,场地也联系好了,才可以开始进场拍摄。
另外就是 AOV 网中不能存在回路。
刚才已经举了例子,让某个活动的开始要以自己完成作为先决条件,显然是不可以的。
设 G=(V,E) 是一个具有 n 个顶点的有向图,V 中的顶点序列v1,v2, … ,vn ,满足若从顶点 vi 到 vj 有一条路径,则在顶点序列中顶点 vi 必在顶点 vj 之前。
则我们称这样的顶点序列为一个拓扑序列。
上图这样的 AOV 网的拓扑序列不止一条。
序列 v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 是一条拓扑序列,v0 v1v4 v3 v2 v7 v6 v5 v8 v10 v9 v12 v11 v14 v13 v15 v16 也是一条拓扑序列。
所谓拓扑排序,其实就是对一个有向图构造拓扑序列的过程。
构造时会有两个结果,如果此网的全部顶点都被输出,则说明它是不存在环(回路)的 AOV 网;如果输出顶点数少了,哪怕是少了一个,也说明这个网存在环(回路),不是 AOV 网。
一个不存在回路的 AOV 网,我们可以将它应用在各种各样的工程或项目的流程图中,满足各种应用场景的需要,所以实现拓扑排序的算法就很有价值了。
7.8.2 拓扑排序算法对 AOV 网进行拓扑排序的基本思路是:从 AOV 网中选择一个入度为 0 的顶点输出,然后删去此顶点,并删除以此顶点为尾的弧,继续重复此步骤,直到输出全部顶点或者 AOV 网中不存在入度为 0 的顶点为止。
详解图的应用(最小生成树、拓扑排序、关键路径、最短路径)1.最小生成树:无向连通图的所有生成树中有一棵边的权值总和最小的生成树1.1 问题背景:假设要在n个城市之间建立通信联络网,则连通n个城市只需要n—1条线路。
这时,自然会考虑这样一个问题,如何在最节省经费的前提下建立这个通信网。
在每两个城市之间都可以设置一条线路,相应地都要付出一定的经济代价。
n个城市之间,最多可能设置n(n-1)/2条线路,那么,如何在这些可能的线路中选择n-1条,以使总的耗费最少呢?1.2 分析问题(建立模型):可以用连通网来表示n个城市以及n个城市间可能设置的通信线路,其中网的顶点表示城市,边表示两城市之间的线路,赋于边的权值表示相应的代价。
对于n个顶点的连通网可以建立许多不同的生成树,每一棵生成树都可以是一个通信网。
即无向连通图的生成树不是唯一的。
连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树,对连通图的不同遍历,就可能得到不同的生成树。
图G5无向连通图的生成树为(a)、(b)和(c)图所示:G5G5的三棵生成树:可以证明,对于有n 个顶点的无向连通图,无论其生成树的形态如何,所有生成树中都有且仅有n-1 条边。
1.3最小生成树的定义:如果无向连通图是一个网,那么,它的所有生成树中必有一棵边的权值总和最小的生成树,我们称这棵生成树为最小生成树,简称为最小生成树。
最小生成树的性质:假设N=(V,{ E}) 是个连通网,U是顶点集合V的一个非空子集,若(u,v)是个一条具有最小权值(代价)的边,其中,则必存在一棵包含边(u,v)的最小生成树。
1.4 解决方案:两种常用的构造最小生成树的算法:普里姆(Prim)和克鲁斯卡尔(Kruskal)。
他们都利用了最小生成树的性质1.普里姆(Prim)算法:有线到点,适合边稠密。
时间复杂度O(N^2)假设G=(V,E)为连通图,其中V 为网图中所有顶点的集合,E 为网图中所有带权边的集合。
拓扑排序与关键路径分析拓扑排序和关键路径分析是项目管理和图论中常用的两种技术,用于分析和优化活动的执行顺序。
在本文中,我们将探讨这两种技术的原理、应用和实施方法。
一、拓扑排序拓扑排序是一种用于有向无环图(DAG)的节点排序方法,使得图中的每条边的起始节点都排在终止节点的前面。
在拓扑排序中,节点表示活动,边表示活动间的先后关系。
拓扑排序的实现可以通过深度优先搜索(DFS)或广度优先搜索(BFS)来完成。
DFS方式会将所有可能的路径都遍历一遍,直到没有后续节点为止。
而BFS方式通过从源节点开始,按广度优先的顺序依次处理各个节点,直到所有节点处理完毕。
拓扑排序在项目管理中被广泛应用,用于确定活动执行的先后顺序,确保项目按计划有序地进行。
通过拓扑排序,可以发现项目中的关键路径,进而对项目进行合理的资源分配和时间安排。
二、关键路径分析关键路径分析是项目管理中用于确定项目完成所需的最短时间的方法。
关键路径是指项目中的一条从起始节点到结束节点的路径,其上的活动紧密相连且没有松弛时间,任何活动的延误都会导致整个项目的延误。
关键路径分析需要确定每个活动的最早开始时间、最晚开始时间、最早完成时间和最晚完成时间。
通过计算差异,可以找到关键路径上的活动和总体项目的最短完成时间。
关键路径分析在项目管理中对决策和资源管理具有重要意义。
通过确定关键路径,项目经理可以对重要活动进行优化和调整,以确保项目按时完成。
此外,关键路径还可以用于资源的分配和调度,以提高项目的效率和质量。
三、拓扑排序与关键路径分析的实施方法要实施拓扑排序和关键路径分析,需要按照以下步骤进行:1. 确定项目的活动和其间的依赖关系。
将活动表示为节点,依赖关系表示为边。
2. 使用拓扑排序算法,对活动进行排序,得到一个合理的活动执行顺序。
3. 计算每个活动的最早开始时间、最晚开始时间、最早完成时间和最晚完成时间。
4. 根据计算结果,找到关键路径上的活动,确定项目的最短完成时间。
关键路径(CriticalPath)引⼊拓扑排序主要是为解决⼀个⼯程能否顺序进⾏的问题,但有时还需要解决⼯程完成需要的最短时间问题。
这时仅仅是拓扑排序是不够的。
通过拓扑排序,可以有效地分析出⼀个有向图是否存在环;若不存在,那它的拓扑排序是什么?另⼀⽅⾯,利⽤求关键路径的算法,可以得到完成⼯程的最短⼯期及关键活动有哪些。
(摘⾃《⼤话数据结构》)定义事件:开始XX事情 | 完成XX事情活动:做XX事情源点:某流程的开始汇点:某流程的结束AOE⽹:在⼀个表⽰⼯程的带权有向图中,⽤顶点表⽰事件,⽤有向边表⽰活动,⽤边上的权值表⽰活动的持续时间,这种有向图的边表⽰活动的⽹,我们称之为AOE⽹(Activity On Edge Network)。
把路径上各个活动所持续的时间之和称为路径长度,从源点到汇点具有最⼤长度的路径叫关键路径,在关键路径上的活动叫关键活动。
(摘⾃《⼤话数据结构》)事件是⼀个点,活动是⼀条线。
举例以炒⼀盘⾁作为⽰例:将炒⼀盘⾁⽐作⼀个⼯程。
⼀位⼤⼈负责厨房的事情,⼀位⼩孩负责从院⼦⾥摘菜并送到厨房。
⼩孩从院⼦⾥摘菜并送到厨房需要1.5分钟。
⼤⼈准备⾁需要7分钟;准备菜需要1.5分钟;炒⾁需要2分钟;炒菜需要1分钟。
问题:这项⼯程的最短时间为多少?显然,该⼯程的流程不是这样:摘菜送到厨房(1.5分钟)->准备⾁(7分钟)->准备菜(1.5分钟)->炒⾁(2分钟)->炒菜(1分钟),共13分钟。
因为⼩孩摘菜的同时⼤⼈可以准备⾁;在炒⾁的后⾯阶段可以将菜放⼊锅⾥⼀起炒,这也符合⽇常实践。
⽽准备菜这个活动⼜受到“摘菜并送到厨房”和“准备⾁”这两个活动的制约:先有菜才能对菜进⾏处理!先处理好⾁才能处理菜吧,厨房⾥只有⼀个⼈。
⽤前⾯的“事件”、“活动”、“源点”和“汇点”来表⽰这个⼯程。
源点:开始准备⾁/开始摘菜送到厨房汇点:完成炒菜/完成炒⾁事件:开始摘菜并送到厨房>完成摘菜并送到厨房开始准备⾁>完成准备⾁开始准备菜>完成准备菜开始炒⾁>完成炒⾁开始炒菜>完成炒菜约束条件:“完成准备⾁”和“完成摘菜并送到厨房”才能“开始准备菜”。
目录课题一 joseph环 41.1 问题的提出1.1.问题的提出41.2 概要设计2.1算法思想51.3流程图根据算法思想,画程序流程图如下:661.4 源代码1.3.详细设计 7 输入m 、nm>0且n>0的整数建立含n 个结点的链表且用head 指向第一个元素,结点数据域包含password 、No 、以及指向下一结点的指head=>pn ≥2(m%n)==0?n:m%n=>1=>i i<mp →next=>pi++输出p →Nop →password=>m删除p 所指向结点n--输出p →No结束开始1.5 结果与分析.4 测试及性能分析10课题二拓扑排序 112.1 问题的提出2.1 问题的提出112. 2 概要设计112.3 流程图2.根据算法思想,画流程图如下:1212 开始设辅助数组indegree 记录图的各顶点的入度值,并将indegree 数组各变量赋初值。
输入图的顶点数、边数建立一个栈,存储图的顶点的序号用邻接表法建图,并计算出indegree 数组中各变量值根据indegree 数组将入度为0的顶点入栈count 对输出顶点计数0=>count栈不空删除栈顶元素,赋给i count++将与第i 个顶点链接的各顶点入度减1输出第i 个顶点值 顶点入度为0 顶点序号入栈count<G.vexnum输出“拓扑排序成功” 输出“拓扑排序不成功” 结束2.4 源代码132.5 结果与分析2.4 测试及性能分析17课题三纸牌游戏 193.1 问题的提出.1 问题的提出193. 2 概要设计191.当每个号码每次遇到是某个数的倍数时,都会相应的翻一次,这样,每张牌会翻的次数就各不一样,可能很多次,也可能只有一两次,结果就只是要输出在经过各个不同次数的翻牌后,正面向上的牌都有哪几个。
举例说明一下,比如24,第一次它是2的倍数时要从正面翻到背面,当进行到3时,就又要从背面翻回来,而到4时还要在翻,同理呢,到6.8.12…它都要来回的翻。
1 ABSTRACT1.1图和栈的结构定义struct SqStack////栈部分{SElemType *base;//栈底指针SElemType *top;//栈顶指针int stacksize;//栈的大小int element_count;//栈中元素个素};/////////AOE网的存储结构struct ArcNode //表结点{int lastcompletetime;//活动最晚开始时间int adjvex; //点结点位置int info; //所对应的弧的权值struct ArcNode *next;//指向下一个表结点指针};struct VNode //点结点{VertexType data; //结点标志int indegree; //该结点入度数int ve; //记录结点的最早开始时间int vl; //记录结点的最晚开始时间struct ArcNode *first_out_arc; //存储下一个出度的表结点struct ArcNode *first_in_arc;//存储下一个入度的表结点};struct ALGraph{ VNode *vertices; //结点数组int vexnum; //结点数int arcnum; //弧数int kind; //该图的类型 };2系统总分析2.1关键路径概念分析2.1.1什么是关键路径关键路径法(Critical Path Method, CPM)最早出现于20世纪50年代,它是通过分析项目过程中哪个活动序列进度安排的总时差最少来预测项目工期的网络分析。
这种方法产生的背景是,在当时出现了许多庞大而复杂的科研和工程项目,这些项目常常需要运用大量的人力、物力和财力,因此如何合理而有效地对这些项目进行组织,在有限资源下以最短的时间和最低的成本费用下完成整个项目就成为一个突出的问题,这样CPM就应运而生了。
对于一个项目而言,只有项目网络中最长的或耗时最多的活动完成之后,项目才能结束,这条最长的活动路线就叫关键路径(Critical Path),组成关键路径的活动称为关键活动。
2.1.2关键路径特点关键路径上的活动持续时间决定了项目的工期,关键路径上所有活动的持续时间总和就是项目的工期。
关键路径上的任何一个活动都是关键活动,其中任何一个活动的延迟都会导致整个项目完工时间的延迟。
关键路径上的耗时是可以完工的最短时间量,若缩短关键路径的总耗时,会缩短项目工期;反之,则会延长整个项目的总工期。
但是如果缩短非关键路径上的各个活动所需要的时间,也不至于影响工程的完工时间。
关键路径上活动是总时差最小的活动,改变其中某个活动的耗时,可能使关键路径发生变化。
可以存在多条关键路径,它们各自的时间总量肯定相等,即可完工的总工期。
关键路径是相对的,也可以是变化的。
在采取一定的技术组织措施之后,关键路径有可能变为非关键路径,而非关键路径也有可能变为关键路径。
2.2关键路径实现过程2.2.1结构选取首先要选取建图的一种算法建立图,有邻接矩阵,邻接表,十字链表,邻接多重表等多种方法,要选取一种适当的方法建立图,才能提高算法效率,降低时间复杂度和空间复杂度。
两个相邻顶点与它们之间的边表示活动,边上的数字表示活动延续的时间。
对于给出的事件AOE网络,要求求出从起点到终点的所有路径,经分析、比较后找出长读最大的路径,从而得出求关键路径的算法,并给出计算机上机实现的源程序。
完成不同路径的活动所需的时间虽然不同,但只有各条路径上所有活动都完成了,这个工程才算完成。
2.2.2具体要解决的问题(1)将项目中的各项活动视为有一个时间属性的结点,从项目起点到终点进行排列;(2)用有方向的线段标出各结点的紧前活动和紧后活动的关系,使之成为一个有方向的网络图;(3)用正推法和逆推法计算出各个活动的最早开始时间,最晚开始时间,最早完工时间和最迟完工时间,并计算出各个活动的时差;(4)找出所有时差为零的活动所组成的路线,即为关键路径;(5)识别出准关键路径,为网络优化提供约束条件;2.2.3算法分析(1)求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径;(2)只有缩短关键活动的工期才有可能缩短工期;(3)若一个关键活动不在所有的关键路径上,减少它并不能减少工期;(4)只有在不改变关键路径的前提下,缩短关键活动才能缩短整个工期。
(5)关键路径:从源点到汇点的路径长度最长的路径叫关键路径。
(6)活动的最早开始时间e(i);(7)活动的最晚开始时间l(i);(8)定义e(i)=l(i)的活动叫关键活动;(9)事件的最早开始时间ve(i);(10)事件的最晚开始时间vl(i)。
设活动ai由弧<j,k>(即从顶点j到k)表示,其持续时间记为dut(<j,k>),则:e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)求ve(i)和vl(j)分两步:1.从ve(1)=0开始向前递推ve(j)=Max{ ve(i)+dut(<i,j>) }<i,j>T, 2<=j<=n其中,T是所有以j为弧头的弧的集合。
2.从vl(n)=ve(n)开始向后递推vl(i)=Min{ vl(j)-dut(<i,j>) }<i,j>S, 1<=i<=n-1其中,S是所有以i为弧尾的弧的集合。
两个公式是在拓扑有序和逆拓扑有序的前提下进行。
2.2.4 算法步骤(1)输入e条弧<j,k>,建立AOE网的存储结构。
(2)从源点v1出发,令ve(1)=0,求个点的最早开始时间ve(j)。
(3)从汇点vn出发,令vl(n)=最大值,求个点的最晚开始时间vl(j)。
(4)由于各结点的最早开始时间已求出来,所以各活动的最早开始时间即(每条弧s(活动)的最早开始时间)就等于该结点的最早开始时间,并由上可同时求出该活动的最晚开始时间l(j)。
(5)具体表达式为:e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)(6)当结点的最早开始时间ve(j)=最晚开始时间时vl(j),则该结点为关键结点。
(7)当活动的最早开始时间e(j)=最晚开始时间时l(j),则该结点为关键活动。
3 主要功能模块设计3.1程序模块栈部分模块Status InitStack(SqStack &S) //初始化栈Status DestroyStack(SqStack &S)//销毁栈Status ClearStack(SqStack &S)//清空栈Status StackEmpty(SqStack S)//判断是否为空Status StackEmpty(SqStack S)//判断是否为空Status Pop(SqStack &S,SElemType &e) //弹出元素Status GetElement(SqStack &S,int position,SElemType &e) //取元素,非弹出,i为要去元素位置无向图(AOE网)部分模块void CreateALGraph(ALGraph &graph)//初始化AOE网Status TopologicalSort(ALGraph &graph,SqStack &ToPoReverseSort) //求拓扑排序Status PutInfoToPoSort(SqStack temp,ALGraph graph) //输出拓扑顺序排序(当拓扑序列存在时)Status GetVeAndVl(ALGraph &graph,SqStack OrderSort,SqStack RevSort) //求出结点和活动的最晚开始时间和最早开始时间Status CriticalPath(ALGraph &graph,SqStack RevSort) //求出关键活动和关键事件并输出4 系统详细设计4.1主函数模块main函数首先调用SqStack ToPoSort;SqStack ToPoReverseSort;函数来定义栈,调用InitStack(ToPoSort);来初始化存拓扑排序的栈和InitStack(ToPoReverseSort);来初始化逆拓扑排序的栈。
其次调用CreateALGraph(ALGraph &graph)函数定义和初始化AOE网,调用TopologicalSor t(ALGraph &graph,SqStack &ToPoReverseSort) 函数求拓扑序列和调用PutInfoToPoSort(ToPoSort,graph);函数来输出输出拓扑顺序排序。
然后调用GetVeAndVl(graph,ToPoSort,ToPoReverseSort) 函数求结点和活动的最晚开始时间、最早开始时间并输出。
最后调用Status CriticalPath(ALGraph &graph,SqStack RevSort)函数来求关键活动、关键事件并输出。
4.2初始化模块初始化模块用来初始化图,要求用户自己输入数据,并程序构造AOE网。
本程序是用自己改进的邻接表来构造AOE网。
见图2-4-2图2-4-2图2-4-34.3求拓扑序列模块利用栈来存储入度为零的结点,然后逐个弹出,来进行与该结点的出度结点来比较,是否符合拓扑排序的规则,最后用ToPoReverseSort存放拓扑逆序序列来完成整个拓扑排序。
见图2-4-3。