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

《数据结构课程设计报告：实现关键路径.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告：实现关键路径.docx（26页珍藏版）》请在第一文库网上搜索。

1、青岛理工大学数据构造课程设计汇报题目：关键途径的实现院（系）：计算机工程学院学生姓名:班级：学号:_起迄日期：2023期.19指导教师：张艳一、需求分析1问题描述找出实际工程中B关键途径，合理安排关键活动B施工次序。规定：(1)表达工程0图可以用邻接表或邻接矩阵存储；(2)应能以图形的方式输出图；(3)输出关键途径和关键活动。2 .基本功能用邻接表存储有向图并建立AOE网CreateGraphO；(2)用图形的形式输出有向图DiSPIay();(3)输出关键途径和关键活动SearchMapPathO；3 .输入输出输入：(1)有向图的顶点数和弧数，都是int型，中间用空格隔开；(2)图中的各个

2、顶点的值，char型；(3)图中弧的权值、起点、终点,都是int型，中间用空格隔开；输出：起点(Char)、终点(Char)、最早开始时间(int)、最迟开始时间(int),差值(int)、与否为关键活动、关键途径。二、概要设计1 .设计思绪：(1)输入图的顶点数和弧数。(2)输入这个图中每段弧的起始点和权值。用输入0数据建立AOE网。(4)用邻接表来存储图的这些信息。(5)用CreateGraphC)函数建立AOE图。用DiSPIay()函数输出AOE图。(7)用SearChM叩Path()函数求出最长途径，并输出关键途径。(8)编写程序。2 .数据构造设计：(1)逻辑构造采用图状B构造。图

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

4、存储构造。(3)抽象数据类型图的定义如下：ADTGraph数据对象V：V是具有相似特性的数据元素的集合，称为顶点集。数据关系R：R=VRVR=v,wV且P(V,w),表达从V到W的!弧,谓词P(v,w)定义了弧的意义或信息基本操作P：CreateGraph(&G,V,VR);初始条件：V是图0顶点集，VR是图中弧的集合。操作成果：按V和VR0定义构造图G。SearchMapPath(&G,V,VR)；初始条件：V是图0顶点集，VR是图中弧B集合。操作成果：求出最长途径，并输出关键途径。Disp1ay(&G,V,VR)；初始条件：V是图的顶点集，VR是图中弧的集合。操作成果：以图形的形式输出图。

5、DTGraph3 .软件构造设计:求关键路径三、详细设计1 .定义程序中所有用到的数据和其数据构造:邻接表0存储单元：typedefstructnodeintadjvex;intw;structnode*nextedge;edgenode;表头结点：typedefstructchardata;id;intint,y;顶点0横坐标、纵坐标edgenode*firstedge;vexnode;2 .主函数和其他函数的伪码算法：主函数：voidmain()intvexnumberzarenumber;Printf(请输入这个图中B节点数和弧数:)；scanf(%d%d,&vexnumbeG&arcn

6、umber);vexnode*Graph=(venode*)ma11oc(vexnumber*sizeof(vexnode);CreateGraph(GraphzVexnumbeGarcnumber);SearchMapPath(GraphzVexnumbeGarcnumber);)建立AOE网函数：voidCreateGraphfvexnode*GraphJntVexnumbecintarcnumber)intbegin,endzduttem;charch;edgenode*p;输入顶点信息存储在顶点表中，并初始化该顶点0便表。for(intj=O;ivexnumber;i+)Graphi.

7、id=0;Graphi.firstedge=NU11;)输入边所依附的两个顶点的序号i和j然后生成新0邻接点序号为j的边表结点,将该结点插入到第i个表头部。Printf(请输入这个图中0各个顶点B值:n“)；for(i=0;ivexnumber;i+)(scanf(%sch);Graphi.data=ch;)Printf(U请输入图中弧0权值、起点、终点：(中间用空格隔开)n“);for(intk=O;kadjvex=end-1;p-w=duttem;Graphend-1.id+;p-nextedge=Graphbegin-1.firstedge;Graphbegin-1.firstedge=

8、p;显示有向图函数：voidDisp1ay(venode*GraphJntVexnumberJntarcnumber)(inti;intarw6;edgenode*p;initgraph(400,600);for(i=0;ivexnumber;i+)(if(i%3=0i=0)outtextxy(100,50*(i+1)zGraphi.data);Graphi.x=100;Graphi.y=50*(i+1);)if(i%3=1i=1)outtextxy(10,50*(i+1),Graphi.data);Graphi.x=10;Graphi.y=50*(i+1);)if(i%3=2i=2)(out

9、tetxy(200z50*i,Graphi.data);Graphi.x=2OO;Graphi.y=50*i;)for(i=0;iadjve.,Graphp-adjve.y);outtetxy(Graphi.+Graphp-adjve.x)24Graphi.y+Graphp-adjvex.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;drawpo1

10、y(31arw);p=p-nextedge;)getch();c1osegraph();)求解关键途径函数：intSearchMapPath(venode*GraphJntVexnumberJntarcnumber)inttota1time=0;intm=0;intiJk,t;charsv100;intfront,rear;int*topo1ogy-queue,*v1z*ve,*e1z*ee;front=rear=-1;t=0;topo1ogy_queue=(int*)ma11oc(vexnumber*sizeof(int);v1=(int*)ma11oc(vexnumber*sizeof(i

11、nt);ve=(int*)ma11oc(vexnumber*sizeof(int);e1=(int*)ma11oc(arcnumber*sizeof(int);ee=(int*)ma11oc(arcnumber*sizeof(int);edgenode*p;for(i=0;ivexnumber;i+)vei=0;for(i=0;iadjvex;Graphk.id-;if(vej+p-wvek)vek=vej+p-w;if(Graphk.id=0)topo1ogy_queue+rear=k;p=p-nextedge;)if(mvexnumber)(Printf(Un该图中存在回路，不可计算出关键

12、途径！n();return0;)tota1time=vevexnumber-1;for(i=0;i=0;i-)j=topo1ogy_queuei;p=Graphj.firstedge;whi1e(p)k=p-adjvex;ifw)w;p=p-netedge;)printf(起点I终点I最早开始时间|最迟开始时间|差值|n);i=O;for(j=0;jadjve;ee+i=ve;e1i=v1k-p-w;printf(%4c%4c%12d%12d%4dzGraphj.data,Graphk.datazeei,e1i,e1i-eei);if(e1i=eei)printf(是关键活动);svt=Graphj.data;t+;)printf(n);p=p-nextedge;)Printf(关键途径为：);svt=Graphvexnumber-1.data;for(i=0;i=t;i+)printf(%czsvi);if(