《数据结构课程设计报告关键路径的实现》由会员分享，可在线阅读，更多相关《数据结构课程设计报告关键路径的实现（18页珍藏版）》请在金锄头文库上搜索。
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的弧，谓词P（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(vexnumber*sizeof(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; Graphend-1.id +; p-nextedge =Graphbegin-1.firstedge ; Graphbegin-1.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
9、*(i+1), Graphi.data);Graphi.x=100;Graphi.y=50*(i+1);if(i%3=1|i=1) outtextxy(10,50*(i+1), Graphi.data);Graphi.x=10;Graphi.y=50*(i+1);if(i%3=2|i=2)outtextxy(200,50*i, Graphi.data);Graphi.x=200;Graphi.y=50*i;for(i=0;iadjvex.x,Graphp-adjvex.y);outtextxy(Graphi.x+Graphp-adjvex.x)/2,(Graphi.y+Graphp-adjve
10、x.y)/2,p-w+48);arw0=Graphp-adjvex.x+5;arw1=Graphp-adjvex.y-10;arw2=Graphp-adjvex.x;arw3=Graphp-adjvex.y;arw4=Graphp-adjvex.x+5;arw5=Graphp-adjvex.y+10;drawpoly(3,arw);p=p-nextedge;getch();closegraph(); 求解关键路径函数：int SearchMapPath(vexnode* Graph,int vexnumber,int arcnumber) int totaltime=0;int m=0; in
11、t i,j,k,t; char sv100; int front,rear; int *topology_queue,*vl,*ve,*el,*ee; front=rear=-1; t=0; topology_queue=(int*)malloc(vexnumber*sizeof(int); vl=(int*)malloc(vexnumber*sizeof(int); ve=(int*)malloc(vexnumber*sizeof(int); el=(int*)malloc(arcnumber*sizeof(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)
