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

《数据结构课程设计报告--关键路径的实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计报告题目：关键路径的实现院（系）：计算机工程学院学生姓名:班级：学号:一、需求分析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)

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

4、联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序映象的存储结构，因此采用链式的存储结构。（3）抽象数据类型图的定义如下：ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={

5、v,w∈V且P（v,w）,表示从v到w的弧，谓词P（v,w）定义了弧的意义或信息}基本操作P：CreateGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。SearchMapPath(&G,V,VR)

6、；初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：求出最长路径，并输出关键路径。Display(&G,V,VR)；初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：以图形的形式输出图。}ADTGraph3.软件结构设计：三、详细设计1.定义程序中所有用到的数据及其数据结构:邻接表的存储单元:typedefstructnode{intadjvex;intw;structnode*nextedge;}edgenode;表头结点:typedefstruct{chardata;intid;intx,y;//顶点的横坐标、纵坐标edgenod

7、e*firstedge;}vexnode;2．主函数和其他函数的伪码算法:主函数：voidmain(){intvexnumber,arcnumber;printf("请输入这个图中的节点数和弧数:");scanf("%d%d",&vexnumber,&arcnumber);vexnode*Graph=(vexnode*)malloc(vexnumber*sizeof(vexnode));CreateGraph(Graph,vexnumber,arcnumber);SearchMapPath(Graph,vexnumber,arcnumber);}

8、建立AOE网函数：voidCreateGraph(vexnode*Graph,intvexnumber,intarcnumber){intbegin,end,duttem;charch;edgenode*p;//输入顶点信息存储在顶点表中，并初始化该顶点的便表。for(inti=0;i

9、n");for(i=0;i