数据结构课程设计报告---关键路径.doc

数 据 结 构课 程 设 计 报 告理论成绩实践成绩总成绩院系： 信息管理学院 专业： 软件工程 班级： 软件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)。 关键路径可以很方便的让我们估算出某个工程最短的时间开销，以及这个工程中哪些活动，即哪些项目是主要的，是影响工程进度的关键，从而让我们对工程的实施做出更好的时间安排，并且可以分清主次，抓住核心工程，做到有的放矢。总的来说，正因为关键路径可以帮助我们对工程进行非常有必要的估算，让我们得以看清全局，作出更为优化的安排，所以可见关键路径的求出对一项工程而言是非常必要的。2、需求分析：建立工程网络图：采用邻接表的算法来建立图，即顺序+链式存储结构。计算出各事件及活动的的相关信息：如每个事件的最早和最迟开始时间，每项活动的最早最迟开始时间以及完成此活动所需的时间输出工程图的相关信息：用户可根据自己需要查看相关信息拓扑排序：以此来判断图中是否有回路，因为图中如果有回路，工程就无法进行找出关键活动并输出找出关键路径并输出3、概要设计： 相关说明：设某一活动的起点为i, 中点为j，完成该活动所需时间为time; 源点和汇点分别表示整个工程的开始事件和结束事件ve：任一事件的最早可发生时间, 其值为源点到该点所有路径长度的最大值；vl：在不影响整个工程进度的情况下各事件的最晚可发生时间，其值为该点到汇点的最长路径之差；e：各项活动的最早开始时间，若以表示该活动，则e(i,j) = ve(i)；l：各项活动的最晚开始时间，若以表示该活动，则v(i,j) = vl(j)-time；d：在不增加整个工程所需总时间的情况下，某项活动可以拖延的时，其值为e-l； 采用邻接表的方式建立工程图 对AOE网进行排序, 若发现回路，则提醒用户数据错误，让其重新输入 对于源点，对于源点，置其ve = 0，依次计算出各事件的ve；对于汇点，置其vl = ve, 然后依次计算出各事件的vl；再计算出各活动的e, l, d; 找出关键活动和关键路径 4、详细设计： 1、数据结构： typedef struct/顶点类型 char num; /顶点编号 int out_d; /顶点出度 int in_d; /顶点入度 int ve; /顶点所表示的事件的最早发生时间 int vl; /顶点所表示的事件的最迟发生时间Vertex;typedef struct arcnode/弧的结点结构类型 char start; /该弧的起点, 表示此弧所代表的活动开始事件 char end; /该弧的终点，表示此弧所代表的活动的结束事件 int vp; /该弧的终点在邻接表中的位置 int time; /完成该弧所表示的活动所需的时间 int e; /该弧所代表的活动的最早开始时间 int l; /该弧所代表的活动的最迟开始时间 int d; /该弧所代表的活动可以拖延的时间, 当d = 0时表示此活动为关键活动 struct arcnode *nextarc; /指向下一条弧的指针ArcNode;typedef struct/邻接表头结点的类型 Vertex data; /该顶点的相关信息 ArcNode *firstarc; /指向第一条弧 VNode;typedef struct int n, e;/图中顶点数和边数 VNode adjlistMAXV; /邻接链表ALGraph;2、创建有向图的邻接链表：void CreateGraph(ALGraph *g) /创建有向图的邻接链表ArcNode *p; int i, j, k, n, e, t, sign;coutn请输入事件总数和活动总数：ne;if (n = 0) | (e n-1)cout数据有误，请检查后重新输入!n = n;g-e = e; for( i = 0; i adjlisti.data.num = i+65; g-adjlisti.firstarc = NULL;g-adjlisti.data.in_d = g-adjlisti.data.out_d = 0;g-adjlisti.data.ve = g-adjlisti.data.vl = 0;coutn请输入各项活动的开始事件和结束事件的编号及所需时间：n;for( k = 1; k = e; k+)cout第kijt;p = new ArcNode;p-start = i+65; p-end = j+65;p-vp = j;p-time = t;g-adjlisti.data.out_d+;g-adjlistj.data.in_d+; p-nextarc = g-adjlisti.firstarc;g-adjlisti.firstarc = p;3、计算出各事件及活动的的相关信息：void EventInfo(ALGraph *g) /计算各事件及活动的相关信息 ArcNode *p = new ArcNode; int i, k; g-adjlist0.data.ve = 0; /对于源点，置其ve = 0 for (i = 0; i n; i +) /计算各顶点所表示事件的最早发生时间ve p = g-adjlisti.firstarc; while (p != NULL) k = p-vp; if (g-adjlistk.data.ve != 0) /如果该事件的ve已经有值，则取源点到该事件的所有路径长度的最大值 g-adjlistk.data.ve = Max(g-adjlistk.data.ve, g-adjlisti.data.ve + p-time); else /否则就取当前计算出来的值 g-adjlistk.data.ve = g-adjlisti.data.ve + p-time; p = p-nextarc; g-adjlistg-n-1.data.vl = g-adjlistg-n-1.data.ve; /对于汇点，置其vl = ve for (i = g-n - 1; i = 0; i -) /计算各顶点所表示事件的最迟发生时间vl p = g-adjlisti.firstarc; while (p != NULL) k = p-vp; if (g-adjlisti.data.vl != 0) /如果该事件的vl已经有值，则取该事件到汇点的最长路径之差 g-adjlisti.data.vl = Min(g-adjlisti.data.vl, g-adjlistk.data.vl - p-time); else /否则就取当前计算出来的值 g-adjlisti.data.vl = g-adjlistk.data.vl - p-time; p = p-nextarc; for (i = 0; i n; i +) /计算各弧所代表的活动最早开始e、最迟开始l以及可以拖延的时间d p = g-adjlisti.firstarc; while (p != NULL) k = p-vp; p-e = g-adjlisti.data.ve; /某活动的最早开始时间是该活动的起点所表示的事件的最早发生时间：e = ve p-l = g-adjlistk.data.vl - p-time; /某活动的最迟开始时间l是该活动的终点所表示的事件的最迟开始时间与该活动的所需时间之差：l = vl-time p-d = p-l - p-e; /某活动可以推迟的时间是其最迟开始时间与最早开始时间之差 p = p-nextarc; 4、输出工程图的相关信息：void OutputGraph(ALGraph *g) /输出工程图的相关信息couteventt ve:t vlendl;for (int i = 0; i n; i +)coutadjlisti.data.numt adjlisti.data.vet adjlisti.data.vlendl; coutendl;for (i = 0; i n; i+)ArcNode *p = g-adjlisti.firstarc;while (p != NULL)cout(start,end);couttt et lt d t timeendl;couttt e t l t d t timenextarc;coutendl;5、判断图中是否有回路：int TopSort(ALGraph *g) /用来判断图中是否有回路int i, j, sum = 0; /sum用来记录输出的顶点数，以判断途中是否有回路int stMAXV, top = -1; /栈st的指针为topArcNode *p;for (i = 0; i n; i +)if (g-adjlisti.data.in_d = 0) /入度为0的顶点入栈top +;sttop = i;while (top -1) /栈不为空时就循环i = sttop; top-; /出栈/coutchar(i+65)adjlisti.firstarc; /找第一个相邻顶点while (p != NULL)j = p-vp;g-adjlistj.data.in_d -;if (g-adjlistj.data.in_d = 0) /入度为0的相邻顶点入栈top +;sttop = j;p = p-nextarc; /找下一个相邻顶点coutn);6、计算并输出关键活动：void KeyActs(ALGraph *g) /计算并输出关键活动ArcNode *p;coutn关键活动有：endl;for (int i = 0; i n; i+)p = g-adjlisti.firstarc;while (p != NULL)if (p-d = 0) /如果p指向的活动是关键活动，就将此活动输出cout (startendnextarc;coutendl;7、计算并输出关键路径：void KeyPath(ALGraph *g) /计算并输出关键路径ArcNode tMAXV, *p; /tMAVX数组用来存放代表关键活动的边的信息int j = 0; /j指示t数组下标int count = 0; /记录关键路径的条数coutn关键路径有：endl;for (int i = 0; i n; i +) p = g-adjlisti.firstarc;while (p != NULL)if (p-d = 0) tj.start = p-start;tj.end = p-end; j+;if (p-end = g-adjlistg-n-1.data.num) /当某活动的结束事件就是整个工程的结束事件时就出现一条关键路径count +; p = p-nextarc;int sign; /sign用来标记关键路径在哪个位置有分叉int flag; /一条关键路径计算完的标志int k = 0; /用于一条关键路径计算完以后从新计算下一条关键路径的入口char num; /当发生分叉时用于交换的中间变量while(count 0)flag = 0;k = 0;while (flag != 1)if (k = 0 | tk.start = tsign.end) /如果活动源点或是上一活动的结束事件此次活动的开始事件则输出couttk.start ;sign = k;if (tk.end = g-adjlistg-n-1.data.num)couttk.endendl;flag = 1;count -;k+;if (tk.start = tsign.start) /如果有分叉即两活动的开始事件相同、结束事件不同时就将两项活动 /的结束事件交换，以便计算下一条路径时不发生重复num = tk-1.end;tk-1.end = tk.end;tk.end = num; 8、所有操作的入口：void Interface() /所有操作的入口，主函数通过调用此函数来完成相关操作char choose1, choose2, ch;int flag1, flag2;docout|-欢迎使用!-|endl;cout| |endl;cout S - 退出 - Q -|endl;cout| |endl;cout|-|endl;coutchoose1;if (choose1 = S | choose1 = s)ALGraph *G = new ALGraph;do flag1 = 1;CreateGraph(G);if (!TopSort(G)cout图中有回路!请检查后重新输入!endl;flag1 = 0; while (!flag1); EventInfo(G);cout Y - No any key - ch; if (ch = Y | ch = y )OutputGraph(G);coutn工程的最短工期为：adjlistG-n-1.data.vl天endl;KeyActs(G);KeyPath(G);cout Y - 退出系统 any key -choose2;if (choose2 = Y | choose2 = y)flag2 = 1;else coutn- 谢谢使用!欢迎再次使用! -endl;flag2 = 0;coutendlendl;else if (choose1 = Q | choose1 = q)coutn- 谢谢使用!欢迎再次使用! -endl;exit(1);else coutn操作有误! 请重新选择：nendl; while (flag2);三、系统实现： 1、源代码见报告尾部； 2、调试分析，测试数据及界面如下：四、设计总结：由于上学期时间紧张，关键路径这块基本上没有理解，通过这次课程设计，我选了这个课题，一是为了让自己能很好的掌握这个知识点，二是为了在得分的压力下把输出多条关键路径的这个算法写出来。但是在做的过程中才真正发现这个算法并不是那么简单，我花了几乎一天半的时间就为了把它写出来，但是一直无果，然后又在图书馆查阅大量书籍，虽然还是没有找到相关算法，但是在查阅的过程中我学习到了很多算法思想，这应该是我这次课程设计最大的收获吧。这个算法的实现其实来的很突然，我在草稿纸上不停地画图分析以及上机实验，就在不知不觉中这个算法就实现了，这我从中明白：任何事不能只想不做，要善于分析和勤于动手，才有可能达到我们期望的效果。我从这次课程设计中所得的另外一个很大的收获是：不能因为问题难就逃避它，只有勇于尝试才可能解决根本问题。数据结构这门课程对我们学习好这个专业很重要，在以后，我会尽量利用我的空闲时间把以前不熟的和掌握不牢固的知识点再学习一遍，让它成为一门为我所用的课程。五、附件（完整源代码）：#include #include #define MAXV 50typedef struct/顶点类型char num; /顶点编号int out_d; /顶点出度int in_d; /顶点入度int ve; /顶点所表示的事件的最早发生时间int vl; /顶点所表示的事件的最迟发生时间Vertex;typedef struct arcnode/弧的结点结构类型char start; /该弧的起点, 表示此弧所代表的活动开始事件char end; /该弧的终点，表示此弧所代表的活动的结束事件int vp; /该弧的终点在邻接表中的位置int time; /完成该弧所表示的活动所需的时间int e; /该弧所代表的活动的最早开始时间int l; /该弧所代表的活动的最迟开始时间int d; /该弧所代表的活动可以拖延的时间, 当d = 0时表示此活动为关键活动struct arcnode *nextarc; /指向下一条弧的指针ArcNode;typedef struct/邻接表头结点的类型 Vertex data; /该顶点的相关信息ArcNode *firstarc; /指向第一条弧 VNode;typedef struct int n, e;/图中顶点数和边数VNode adjlistMAXV; /邻接链表ALGraph;int Max(int x, int y)return (x y ? x : y);int Min(int x, int y)return (x y ? x : y);void CreateGraph(ALGraph *g) /创建有向图的邻接链表ArcNode *p; int i, j, k, n, e, t, sign;coutn请输入事件总数和活动总数：ne;if (n = 0) | (e n-1)cout数据有误，请检查后重新输入!n = n;g-e = e; for( i = 0; i adjlisti.data.num = i+65; g-adjlisti.firstarc = NULL;g-adjlisti.data.in_d = g-adjlisti.data.out_d = 0;g-adjlisti.data.ve = g-adjlisti.data.vl = 0;coutn请输入各项活动的开始事件和结束事件的编号及所需时间：n;for( k = 1; k = e; k+)cout第kijt;p = new ArcNode;p-start = i+65; p-end = j+65;p-vp = j;p-time = t;g-adjlisti.data.out_d+;g-adjlistj.data.in_d+; p-nextarc = g-adjlisti.firstarc;g-adjlisti.firstarc = p;void EventInfo(ALGraph *g) /计算各事件及活动的相关信息ArcNode *p = new ArcNode; int i, k;g-adjlist0.data.ve = 0; /对于源点，置其ve = 0for (i = 0; i n; i +) /计算各顶点所表示事件的最早发生时间vep = g-adjlisti.firstarc;while (p != NULL) k = p-vp;if (g-adjlistk.data.ve != 0) /如果该事件的ve已经有值，则取源点到该事件的所有路径长度的最大值g-adjlistk.data.ve = Max(g-adjlistk.data.ve, g-adjlisti.data.ve + p-time);else /否则就取当前计算出来的值g-adjlistk.data.ve = g-adjlisti.data.ve + p-time;p = p-nextarc;g-adjlistg-n-1.data.vl = g-adjlistg-n-1.data.ve; /对于汇点，置其vl = vefor (i = g-n - 1; i = 0; i -) /计算各顶点所表示事件的最迟发生时间vlp = g-adjlisti.firstarc;while (p != NULL) k = p-vp;if (g-adjlisti.data.vl != 0) /如果该事件的vl已经有值，则取该事件到汇点的最长路径之差g-adjlisti.data.vl = Min(g-adjlisti.data.vl, g-adjlistk.data.vl - p-time);else /否则就取当前计算出来的值g-adjlisti.data.vl = g-adjlistk.data.vl - p-time;p = p-nextarc;for (i = 0; i n; i +) /计算各弧所代表的活动最早开始e、最迟开始l以及可以拖延的时间dp = g-adjlisti.firstarc;while (p != NULL)k = p-vp;p-e = g-adjlisti.data.ve; /某活动的最早开始时间是该活动的起点所表示的事件的最早发生时间：e = vep-l = g-adjlistk.data.vl - p-time; /某活动的最迟开始时间l是该活动的终点所表示的事件的最迟开始时间与该活动的所需时间之差：l = vl-timep-d = p-l - p-e; /某活动可以推迟的时间是其最迟开始时间与最早开始时间之差p = p-nextarc;void OutputGraph(ALGraph *g) /输出工程图的相关信息couteventt ve:t vlendl;for (int i = 0; i n; i +)coutadjlisti.data.numt adjlisti.data.vet adjlisti.data.vlendl; coutendl;for (i = 0; i n; i+)ArcNode *p = g-adjlisti.firstarc;while (p != NULL)cout(start,end);couttt et lt d t timeendl;couttt e t l t d t timenextarc;coutendl;coutnumt ve:t vlendl;for (i = 0; i n; i +)coutadjlisti.data.numt adjlisti.data.vet adjlisti.data.vlendl; int TopSort(ALGraph *g) /用来判断图中是否有回路int i, j, sum = 0; /sum用来记录输出的顶点数，以判断途中是否有回路int stMAXV, top = -1; /栈st的指针为topArcNode *p;for (i = 0; i n; i +)if (g-adjlisti.data.in_d = 0) /入度为0的顶点入栈top +;sttop = i;while (top -1) /栈不为空时就循环i = sttop; top-; /出栈/coutchar(i+65)adjlisti.firstarc; /找第一个相邻顶点while (p != NULL)j = p-vp;g-adjlistj.data.in_d -;if (g-adjlistj.data.in_d = 0) /入度为0的相邻顶点入栈top +;sttop = j;p = p-nextarc; /找下一个相邻顶点coutn);void KeyActs(ALGraph *g) /计算并输出关键活动ArcNode *p;coutn关键活动有：endl;for (int i = 0; i n; i+)p = g-adjlisti.firstarc;while (p != NULL)if (p-d = 0) /如果p指向的活动是关键活动，就将此活动输出cout (startendnextarc;coutendl;void KeyPath(ALGraph *g) /计算并输出关键路径ArcNode tMAXV, *p; /tMAVX数组用来存放代表关键活动的边的信息int j = 0; /j指示t数组下标int count = 0; /记录关键路径的条数coutn关键路径有：endl;for (int i = 0; i n; i +) p = g-adjlisti.firstarc;while (p != NULL)if (p-d = 0) tj.start = p-start;tj.end = p-end; j+;if (p-end = g-adjlistg-n-1.data.num) /当某活动的结束事件就是整个工程的结束事件时就出现一条关键路径count +; p = p-nextarc;int sign