数据结构课程设计报告关键路径实现

《数据结构课程设计报告关键路径实现》由会员分享，可在线阅读，更多相关《数据结构课程设计报告关键路径实现（11页珍藏版）》请在装配图网上搜索。

1、-理工大学数据构造课程设计报告题目： 关键路径的实现院系：计算机工程学院学生:班级：*:起迄日期: 2021.7.19指导教师: 艳 一、需求分析1.问题描述 找出实际工程中的关键路径，合理安排关键活动的施工顺序。要求：(1)表示工程的图可以用邻接表或邻接矩阵存储；(2)应能以图形的方式输出图；(3)输出关键路径和关键活动。2.根本功能 (1)用邻接表存储有向图并建立AOE网 CreateGraph； (2)用图形的形式输出有向图Display(); (3)输出关键路径和关键活动 SearchMapPath；3.输入输出输入: (1)有向图的顶点数和弧数，都是int型，中间用空格隔开； (2)

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.

3、数据构造设计：1逻辑构造采用图状的构造。图是一种较线性表和树更为复杂的数据构造。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形构造中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素即其孩子结点相关，但只能和上一层中一个元素即其双亲结点相关；而在图形构造中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。而由于本程序的操作对象是有向图，所以必须采用图状的构造。2存储构造采用链式的构造。由于图的构造比拟复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序

4、映象的存储构造，因此采用链式的存储构造。3抽象数据类型图的定义如下：ADT Graph 数据对象V：V是具有一样特性的数据元素的集合，称为顶点集。数据关系R： R=VR VR=|v,wV且Pv,w,表示从v到w的弧，谓词Pv,w定义了弧的意义或信息根本操作P：CreateGraph(&G,V,VR );初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。 SearchMapPath (&G,V,VR )；初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：求出最长路径，并输出关键路径。Display(&G,V,VR)；初始条件：V是图的顶点集，VR是图中弧的集

5、合。操作结果：以图形的形式输出图。ADT Graph3. 软件构造设计：三、详细设计1. 定义程序中所有用到的数据及其数据构造: 邻接表的存储单元: typedef struct node int adjve*; int w; struct node *ne*tedge; edgenode; 表头结点: typedef struct char data; int id;int *,y; /顶点的横坐标、纵坐标 edgenode *firstedge; ve*node; 2 主函数和其他函数的伪码算法:主函数：void main() int ve*number,arumber; printf(请

6、输入这个图中的节点数和弧数:); scanf(%d %d,&ve*number,&arumber); ve*node* Graph=(ve*node*)malloc(ve*number*sizeof(ve*node); CreateGraph(Graph,ve*number,arumber); SearchMapPath(Graph,ve*number,arumber); 建立AOE网函数：void CreateGraph(ve*node* Graph,int ve*number,int arumber) int begin,end,duttem; char ch; edgenode *p;

7、/输入顶点信息存储在顶点表中，并初始化该顶点的便表。 for(int i=0;ive*number;i+) Graphi.id =0; Graphi.firstedge =NULL; /输入边所依附的两个顶点的序号i和j然后生成新的邻接点序号为j的/边表结点,将该结点插入到第i个表头部。printf(请输入这个图中的各个顶点的值:n); for(i=0;ive*number;i+) scanf(%s,&ch); Graphi.data=ch; printf(请输入图中弧的权值、起点、终点:中间用空格隔开n); for(int k=0;kadjve* =end-1; p-w =duttem; G

8、raphend-1.id +; p-ne*tedge =Graphbegin-1.firstedge ; Graphbegin-1.firstedge =p; 显示有向图函数：void Display(ve*node* Graph,int ve*number,int arumber)int i;int arw6;edgenode *p;initgraph(400, 600);for(i=0;ive*number;i+)if(i%3=0|i=0) outte*t*y(100,50*(i+1), Graphi.data);Graphi.*=100;Graphi.y=50*(i+1);if(i%3=

9、1|i=1) outte*t*y(10,50*(i+1), Graphi.data);Graphi.*=10;Graphi.y=50*(i+1);if(i%3=2|i=2)outte*t*y(200,50*i, Graphi.data);Graphi.*=200;Graphi.y=50*i;for(i=0;iadjve*.*,Graphp-adjve*.y);outte*t*y(Graphi.*+Graphp-adjve*.*)/2,(Graphi.y+Graphp-adjve*.y)/2,p-w+48);arw0=Graphp-adjve*.*+5;arw1=Graphp-adjve*.y-

10、10;arw2=Graphp-adjve*.*;arw3=Graphp-adjve*.y;arw4=Graphp-adjve*.*+5;arw5=Graphp-adjve*.y+10;drawpoly(3,arw);p=p-ne*tedge;getch();closegraph(); 求解关键路径函数：int SearchMapPath(ve*node* Graph,int ve*number,int arumber) int totaltime=0;int m=0; int i,j,k,t; char sv100; int front,rear; int *topology_queue,*v

11、l,*ve,*el,*ee; front=rear=-1; t=0; topology_queue=(int*)malloc(ve*number*sizeof(int); vl=(int*)malloc(ve*number*sizeof(int); ve=(int*)malloc(ve*number*sizeof(int); el=(int*)malloc(arumber*sizeof(int); ee=(int*)malloc(arumber*sizeof(int); edgenode *p; for(i=0;ive*number;i+) vei=0; for(i=0;iadjve*; Gr

12、aphk.id -; if(vej+p-w vek) vek=vej+p-w ; if(Graphk.id =0) topology_queue+rear=k; p=p-ne*tedge ; if(mve*number) printf(n该图中存在回路，不可计算出关键路径！n); return 0; totaltime=veve*number-1; for(i=0;i=0;i-) j=topology_queuei; p=Graphj.firstedge; while(p) k=p-adjve* ; if(vlk-p-w )w; p=p-ne*tedge; printf(| 起点 | 终点 |

13、 最早开场时间 | 最迟开场时间 | 差值 | n); i=0; for(j=0;jadjve* ; ee+i=vej; eli=vlk-p-w; printf(| %4c | %4c | %12d | %12d | %4d |,Graphj.data ,Graphk.data ,eei,eli,eli-eei); if(eli=eei) printf( 是关键活动 ); svt=Graphj.data;t+; printf(n); p=p-ne*tedge; printf(关键路径为：); svt=Graphve*number-1.data; for(i=0;i=t;i+) printf(%

14、c,svi);if(svi!=Graphve*number-1.data)printf(); printf(n); return 1; 3. 主要函数的程序流程图： 4. 画出函数之间的调用关系图:四、 调试分析1.实际完成的情况说明: 本程序完成的功能是：显示用户从键盘输入的有向图，并计算出其关键路径。支持用户输入char型的顶点值，int型的弧数和顶点数，int型的权值；2.程序的性能分析：本程序的时间复杂度为O(n),空间复杂度为O1。3.上机过程中出现的问题及其解决方案：1有向图的存储。存储时，由于对邻接表的具体代码实现不了解，导致在写这局部程序的过程中遇到不少麻烦，比方如何在结点里添

15、加指向下一邻接结点的指针等，后来查阅了教材，解决了这一局部的问题。2有向图的显示。如何在屏幕上以图形的形式输出图，困惑了我好久。通过在网上查找资料及寻找帮助，明白了需在头文件里添加graphics.h文件，并使用该库里的line()函数和outte*t*y()函数。接着是如何显示带箭头的直线，由于graphics.h库里不含有画带箭头的直线的函数，于是，我使用了画多边形的函数drawpoly()来实现箭头，但是这个函数的第二个形参类型是数组型的，需用数组来存储三个点的坐标信息。3关键路径的求解。由于对关键路径的根本算法不了解，所以特地查阅了这一方面的书籍，了解了关键路径的根本算法。4.程序中可

16、以改良的地方说明：有向图的显示里，箭头无法随直线的斜率的变化而变化，顶点值与箭头重合，看不清箭头的方向。5.程序中可以扩大的功能及设计实现假想：应能显示多个有向图，能求解多个有向图的关键路径，关键活动。界面可以做成可视化，人性化的界面。五、 测试结果1输入一组可以构成AOE网的顶点与弧的数据（2） 输入一组不可构成AOE网的顶点与弧的数据即存在回路六、 用户手册(1) 输入图中的节点数与弧数 2输入图中各个顶点的值3输入图中弧的权值、起点、终点4按回车键（5） 按回车键6按任意键七、体会与自我评价通过本次课程设，掌握了邻接表的存储构造，图形显示的一些函数的使用以及关键路径的求法。在实验过程中出

17、现了不少的问题，通过查阅资料，向教师、同学寻求帮助，解决了出现的问题。从这次的课程设计任务中我深刻地体会到：任何事情并不像我们想的那样困难。刚开场拿到这个课设任务时，对于关键路径很是发怵，因为之前对这一局部的知识运用的少，再加上任务书上还要求以图形的形式显示有向图，在这次课设之前，我从来没有接触过图形处理的函数。然而，俗话说世上无难事，只怕有心人，通过积极地查阅书籍，上网查找资料，这些困难都一个个的迎刃而解。并且在解决这些困难的同时，自己也复习并掌握了这些知识。本次课设遇到了很多理论课上所没有遇到过的问题，也让理论课上所学的理论得到验证和使用，通过实际操作，扎实了理论知识，开拓了自己的算法思想

18、。通过本次课设，更让我意识到团队合作的力量，通过小组成员的讨论和互相解惑，学到很多自己没有遇到过的问题的解决方法，学会了如何在团队合作中互帮互助，共同进步。但是自己的程序仍存在一些缺乏，比方在有向图的显示方面，箭头与顶点值重合了，导致无法清晰识别弧的方向。这次课设让我明白了只有扎扎时时的学习知识才能解决实际生活中的实际问题，以后要多了解相关知识,更多的做一些实践动手活动，将知识运用到实际问题中。同时，增加自己的动手能力，这样才能便于我们更好的解决问题。为今后打下好的根底。课外时间应该多扩展一些编程方面的知识，提高自己的编程能力。八、 参考文献1严蔚敏，数据构造C语言，清华大学，20072邱建华，C语言程序设计教程，东软电子，20213汝佳，算法竞赛入门经典，清华大学，2021. z