《数据结构课程设计报告 关键路径的实现》由会员分享，可在线阅读，更多相关《数据结构课程设计报告 关键路径的实现（12页珍藏版）》请在金锄头文库上搜索。
1、青岛理工大学数据结构课程设计报告题目： 关键路径的实现院（系）：计算机工程学院 学生姓名: 班级： 学号:起迄日期： 2014。7.82014.7.19指导教师： 张艳 一、需求分析1.问题描述 找出实际工程中的关键路径，合理安排关键活动的施工顺序。要求：（1)表示工程的图可以用邻接表或邻接矩阵存储；(2）应能以图形的方式输出图；(3）输出关键路径和关键活动。2。基本功能 (1)用邻接表存储有向图并建立AOE网 CreateGraph（）； (2）用图形的形式输出有向图Display（)； （3)输出关键路径和关键活动 SearchMapPath（)； 3.输入输出 输入： （1）有向图的顶点
2、数和弧数,都是int型，中间用空格隔开； (2)图中的各个顶点的值,char型; (3）图中弧的权值、起点、终点，都是int型，中间用空格隔开； 输出： 起点（char）、终点(char) 、最早开始时间(int)、最迟开始时间(int)、差值（int）、是否为关键活动、关键路径。二、 概要设计1.设计思路：（1) 输入图的顶点数和弧数.(2) 输入这个图中每段弧的起始点及权值。 （3) 用输入的数据建立AOE网。（4） 用邻接表来存储图的这些信息. (5） 用CreateGraph（ )函数建立AOE图.（6)用Display()函数输出AOE图.(7） 用SearchMapPath （ ）
3、函数求出最长路径,并输出关键路径。（8) 编写程序。 2。数据结构设计：（1）逻辑结构采用图状的结构。图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素(即其孩子结点）相关，但只能和上一层中一个元素（即其双亲结点）相关;而在图形结构中,结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关.而由于本程序的操作对象是有向图,所以必须采用图状的结构。（2)存储结构采用链式的结构。由于图的结构比较复杂，任意两个顶点之间都可能存在联系
4、，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序映象的存储结构，因此采用链式的存储结构.(3）抽象数据类型图的定义如下:ADT Graph 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R: R=VR VR=|v,wV且P（v，w）,v,w表示从v到w的弧，谓词P(v,w）定义了弧v,w的意义或信息基本操作P：CreateGraph(&G，V，VR ）;初始条件：V是图的顶点集，VR是图中弧的集合。操作结果:按V和VR的定义构造图G。 SearchMapPath （&G，V,VR ）；初始条件:V是图的顶点集,VR是图中弧的集合.操作结果：求出最长
5、路径，并输出关键路径.Display(G,V，VR）;初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：以图形的形式输出图。ADT Graph3. 软件结构设计：三、 详细设计 1. 定义程序中所有用到的数据及其数据结构: 邻接表的存储单元: typedef struct node int adjvex; int w； struct node *nextedge； edgenode; 表头结点: typedef struct char data； int id;int x,y; /顶点的横坐标、纵坐标 edgenode *firstedge; vexnode； 2 主函数和其他函数的伪码
6、算法:主函数:void main（) int vexnumber,arcnumber； printf（请输入这个图中的节点数和弧数:”）； scanf（d %d，&vexnumber,&arcnumber）； vexnode Graph=(vexnode）malloc(vexnumbersizeof(vexnode); CreateGraph(Graph,vexnumber，arcnumber）； SearchMapPath(Graph，vexnumber,arcnumber）； 建立AOE网函数：void CreateGraph(vexnode Graph,int vexnumber，int
7、 arcnumber) int begin,end，duttem； char ch; edgenode p; /输入顶点信息存储在顶点表中,并初始化该顶点的便表. for（int i=0;ivexnumber；i+） Graphi.id =0； Graphi.firstedge =NULL; /输入边所依附的两个顶点的序号i和j然后生成新的邻接点序号为j的/边表结点,将该结点插入到第i个表头部。printf（”请输入这个图中的各个顶点的值：n); for(i=0；ivexnumber;i+） scanf(”s,&ch); Graphi。data=ch； printf（请输入图中弧的权值、起点、
8、终点:（中间用空格隔开）n)； for(int k=0；kadjvex =end-1; p-w =duttem； Graphend1.id +； pnextedge =Graphbegin-1.firstedge ； Graphbegin1.firstedge =p; 显示有向图函数：void Display（vexnode* Graph，int vexnumber,int arcnumber)int i;int arw6;edgenode p；initgraph(400, 600）;for（i=0；ivexnumber;i+）if（i%3=0|i=0） outtextxy（100，50*（i
9、+1）, Graphi。data);Graphi.x=100；Graphi.y=50(i+1)；if(i3=1|i=1) outtextxy(10，50(i+1）, Graphi.data）;Graphi.x=10；Graphi。y=50（i+1）;if(i3=2|i=2）outtextxy（200，50i， Graphi.data);Graphi。x=200；Graphi.y=50*i；for（i=0;iadjvex.y)；outtextxy(（Graphi。x+Graphpadjvex。x）/2,（Graphi。y+Graphp-adjvex.y）/2,p-w+48)；arw0=Graph
10、p-adjvex.x+5；arw1=Graphpadjvex.y10;arw2=Graphpadjvex.x；arw3=Graphpadjvex.y；arw4=Graphp-adjvex.x+5;arw5=Graphpadjvex.y+10；drawpoly(3，arw)；p=p-nextedge；getch()；closegraph(); 求解关键路径函数：int SearchMapPath（vexnode Graph,int vexnumber，int arcnumber） int totaltime=0；int m=0; int i，j,k，t; char sv100； int fron
11、t，rear; int *topology_queue,vl，ve,*el,*ee； front=rear=1; t=0; topology_queue=(int）malloc(vexnumbersizeof（int）； vl=（int*)malloc(vexnumbersizeof（int）; ve=（int)malloc（vexnumber*sizeof(int); el=（int*)malloc（arcnumbersizeof(int）; ee=（int*)malloc(arcnumber*sizeof(int）; edgenode *p； for(i=0；ivexnumber;i+） vei=0； for（i=0；ivexnumber；i+） if(Graphi.id=0) topology_queue+rear=i; m+； while(front!=rear） front+； j=topology_queuefront； m+; p=Graphj。firstedge ; while(p) k=p-adjvex; Graph
