2023年数据结构关键路径实验报告

一、实验目的批注[A1]:正文红色部分表达示例内容，供参考

1、巩固和加深对数据结构课程基本知识的理解，综合数据结构课程里学的理论知识，完毕对关键途径程序

的设计。

2、理解和掌握图的各种基本数据结构的定义、存储结构和相应的算法，并可以用c语言实现。

3、理解AOE网和拓扑排序、求关键途径的算法。

二、实验内容

对于给定的一个工程施工图，该图以边为单位从键盘输入，编写可以找出该图的关键途径的程序。

三、实验环境

1、硬件配置：Pentium(R)Dua1-Core9CUPE6500@2.93GHz,1.96的内存

2、软件环境：MicrosoftWindowsXPProfessionalServicePack3,MicrosoftVisual

C++6.0

四、需求分析

1、输入的形式和输入值的范围：根据题目规定与提醒输入所建图的顶点个数和边的个数，用空格间隔，并且

所输入的顶点和边的数目不超过定义好的VEX_NUM和ARC_NUM,然后输入顶点的信息和入度以空格为间隔，

最后输入每2个顶点以及边的权值。

2、输出的形式:输出A0E网的关键途径。

3、程序所能达成的功能：对于给定的一个工程施工图，该图以边为单位从键盘输入，该程序可以输出该

A0E网的关键途径。

4、测试数据：工程施工图如下：

输入顶点的个数和边的个数：911

输出的关键途径为：1-2-5-7-9^111-2-5-8-9

五、概要设计

为了实现上述操作，抽象数据图的定义如下：

structarcnode〃声明边表中结点结构

(

intadjvex;

intdut;//边上的权值

structarcnode*nextarc;

)；

structnode//声明头结点结构

(

»intdata;

intid;〃定点入度

structarcnode*firstarc;

)；

1、基本操作：

(Ovoidcreate_ALgraph(ALgraphg,inte,intn)

建立AOE网的邻接表，e为弧的数目，n为顶点数

(2)voidoupeALgraph(ALgraphg,intn)

输出AOE网的邻接表

(3)intCriticalpath(ALgraphg,intn)

求AOE网的各个关键活动

2、本程序包含两个模块：

(I)主程序模块；

(2)建立A0E网的邻接表、输出AOE网的邻接表、求AOE网的各个关键活动；

(3)模块调用图:

主程序模块

建立AOE网的邻接表输出AOE网的邻接表求A0E网的各个关键活动

3、随程图:批注[A2]:重点内容

开始

结束

六、具体设计

1、存储类型，元素类型，结点类型：

structarcnode〃声明边表中结点结构

(

intadjvex;

intdut;〃边上的权值

structarcnode*nextare;

｝；

structnode〃声明头结点结构

(

®intdata；

intid;//定点入度

structarenode*firstarc;

)；

元素类型为整形和指针型。

2、每个模块的分析：

(1)主程序模块：

main()

(

ALgraphg;

ainte,n;

®inttag;

。printf(〃\n请输入顶点的个数和边的个数,用空格间隔：”)；

scanf(飞d%d",&n,&e)；

create_ALgraph(g,e,n);〃建立邻接表

。printf("\n输出邻接表信息：\n")；

。OUpe_ALgraph(g,n);//建立输出邻接表

。printf("\n输出AOE网的关键途径:\n");

printf("弧:权值\nM);

。tag=Criticalpath(g,n);〃找关键活动

。if(!tag)

gprintf("AOE网有回路\n");

)

(2)建立AOE网的邻接表函数模块

voidcreateALgraph(ALgraphg,inte,intn)

{//建立AOE网的邻接表，e为弧的数目，n为顶点数

structarcnode*p;

inti,j,k,w；

printf(〃请输入顶点的信息和入度，用空格间隔：")；

for(i=1;i<=n;i++)//结点下标从1开始

{

scanf("%d%d〃,&g[i].data,&g[i].id);//输入顶点信息和入度

g[i].firstarc=NULL;

)

for(k=1；k<=e；k++)//建立边表

{

Prinlf(〃请输入边的两个顶点以及边上的权值,用空格间隔：”)；

。scanf(z，%d%d%d'\&i,&w);//输入有向边的两个顶点

»p=(structarcnode*)ma11oc(sizeof(structarcnode));

p->adjvex=j：

p->dut=w;

，p->nextarc=g[i].firstarc;//插入下标为i的边表的第一个结点的位置

。g[i].firstarc=p;

)

)

输出AOE网的邻接表函数模块

voidoupe_ALgraph(ALgraphg,intn)〃输出AOE网的邻接表

(

•inti；

structarcnode*p;

®for(i=1;i<n；i++)

#{

ap=g[i].firstarc；

printf("%d,%d—g[i].data,g[i].id)；

while(p!=NULL)

。(

gprintf("%3d%3d”,p->adjvex,p->dut);

8p=p—>nextarc；〃找下一个邻接点

时

aprintf(〃\n");

)

求AOE网的各个关键活动函数模块

intCriticalpath(ALgraphg,intn)//求AOE网的各个关键活动

(

»inti,j,k,count；

inttpord[VEX_NUM+l];//顺序队列

intve[VEX_NUM+1],le[VEX_NUM+1];

«inte[ARC_NUM+1],1[ARCNUM+1]：

•intfronI=0,rear=0;〃顺序队列的首尾指针初值为0

structarcnode*p；

ofor(i=l;i<=n;i++)〃各事件最早发生事件初值为0

ve[i]=0;

for(i=1;i<=n;i++)

aif(g[i].id=O)〃入度为0人队列

tpord[++rear]=i;

®count=0;

®while(front!=rear)

(

。front++;

j=tpord[front]；

ocount++;

P=g[j].firstarc;

owhi1e(p!=NULL)

。(

。k=p->adjvex；

g[k].id-—;

if(ve[j]+p->dut>ve[k])

<»ve[k]=ve[j]+p->dut;

8if(g[k].id-0)

gtpord[++rear]=k;

。P=P->nextarc;

g}

)

»if(count<n)〃该AOE网有叵1路

®return0;

。for(i=1;i<=n;i++)〃各事件的最迟发生事件赋初值

gle[i]=ve[n];

。for(i=n—1;i>=1;i—)//按拓扑序列的逆序取顶点

{

j=tpord[i];

p=g[j].firstarc;

while(p!=NULL)

8k=p->adjvex;

*if(le[k]-p->dut<1e[j])

g1e[j]=le[k]-p—>dut：

。p=p->nextarc;

)

®}

i=0；

for(j=1;j<=n;j++)

(

。P=g[j].firstare：

8while(p!=NULL)//计算各边<Vj-1,Vk>所代表的a(i+l)的e[i]和l[i]g

。(

。k=p->adjvex；

。e[i]=ve[j];

»l[i]=le[k]-p->dut：

-if(l[i]==e[i])〃输出关键活动

3printf(*<v%d,v%d〉:%d\n”,g[j].data,g[k].data,p->dut);

o。p=p->nextarc;

i++；

06}

)

return1；

)

3)函数调用关系图

main()

create_ALgraph(ALg

oupeALgraph(ALgraphg,Criticalpath(ALgraphg,int

raphg,inte,int

intn)n)

n)

3、完整的程序：

#include"stdio.h"

#inc1ude"stdlib.h"

^defineVEX_NUM10//定义最大顶点数

#defineARC_NUM20〃定义最多边数

typedefintvertype;

structarcnode〃声明边表中结点结构

(

intadjvex;

intdut；//边上的权值

struetarcnode*nextarc;

)；

structnode//声明头结点结构

(

®intdata;

◎intid:〃定点入度

structarenode*firstarc；

)；

typedefstructnodeALgraph[VEX_NUM+1];

voidcreate_ALgraph(Al.graphg,inte,intn)

{//建立AOE网的邻接表,e为弧的数目，n为顶点数

structarcnode*p;

inti,j,k,w；

printf(〃请输入顶点的信息和入度,用空格间隔:〃);

for(i=1；i<=n；i++)//结点下标从1开始

(

scanf(*%d%dn,&g[i].data,&g[i].id);//输入顶点信息和入度

g[i].firstarc=NULL;

)

for(k=1;k<=e;k++)〃建立边表

(

。printf("请输入边的两个顶点以及边上的权值，用空格间隔:〃)；

。scanf("%d%d%d\&i,&j,&w);//输入有向边的两个顶点

p=(structarcnode*)ma1loc(sizeof(structarcnode));

°p—>adjvex=j;

p->dut=w;

p->nextarc=g[i].firstarc;〃插入下标为i的边表的第一个结点的位置

og[i].firstarc=p;

)

)

voidoupe_ALgraph(ALgraphg,intn)〃输出AOE网的邻接表

(

inti;

^structarcnode*p;

for(i=1;i<n;i++)

p=g[i].firstarc；

oprintf(*%d,g[i].data,g[i].id);

while(p!二NULL)

ft{

gprintf(飞3d%3d",p->adjvex,p->dut);

»p=p—>nextarc；〃找下一个邻接点

。}

。printf("\n");

)

intCriticaIpath(ALgraphg,intn)〃求AOE网的各个关键活动

。inti,j,k,count:

inttpord[VEX_NUM+1];〃顺序队列

intve[VEX_NUM+1],1e[VEX_NUM+1];

inte[ARC_NUM+1],1[ARC_NUM+1]；

intfront=0,rear=0;〃顺序队列的首尾指针初值为0

structarcnode*p；

。for(i=l;i<=n;i++)〃各事件最早发生事件初值为0

。ve[i]=0;

for(i=l;iV=n;i++)

if(g[i].id==0)〃入度为0入队列

»tpord[++rear]=i；

»count=0;

®whi1e(front!=rear)

*{

front++;

。j=tpord[front];

。count++；

P=g[j].firstarc;

。while(p!=NULL)

®{

8k=p->adjvex;

g[k].id—;

°if(ve[j]+p->dut>ve[k])

»ve[k]=ve[j]+p->dut;

。if(g[k].id=0)

tpord[4-+rear]=k：

p=p->nextarc;

)

»if(count<n)〃该AOE网有回路

8return0;

for(i=l;i<=n;i++)//各事件的最迟发生事件赋初值

，le[i]=ve[n];

»for(i=n-1；i>=1；i--)〃按拓扑序列的逆序取顶点

O(

j=tpord[i];

06P=g[j].firstare;

。whi1e(p!=NULL)

(

，k=p>adjvex；

。if(1e[k]-p->dut<1e[j])

1e[j]=1e[k]-p->dut；

。P=p->nextarc;

)

•}

i=0;

for(j=1;j<=n;j++)

a(

8P=g[jl.firstarc;

gwhile(p!=NULL)〃计算各边VVj-1,Vk>所代表的a(i+1)的e[i]和1[i]

8{

。k=p->adjvex;

，e[i]=ve[j];

s1[i]=1e[k]-p->dut;

-if(l[i]==e[i])〃输出关键活动

«>printf(11<v%d,v%d>d\n”,g[j].data,g[k].(1ata,p->dut);

gP=p->nextarc;

。i++；

»)

)

I'eturn1;

)

main()

(

ALgraphg：

inte,n；

inttag；

。printf("\n请输入顶点的个数和边的个数，用空格间隔:“)；

oscanf("%d%d”,&n,&e);

。ereate_ALgraph(g,e,n);//建立邻接表

。printf("\n输出邻接表信息:\n*);

®oupe_ALgraph(g,n);〃建立输出邻接表

Printf(〃\n输出AOE网的关键途径：\n");

printf("弧:权值\n");

tag=Criticalpath(g,n);//找关键活动

if(!tag)

。printf("AOE网有同路\n〃)；

}

七、程序使用说明及测试结果

1、程序使用说明

(1)本程序的运营环境为VC6,Oo

(2)进入演示程序后即显示提醒信息：

请输入顶点的个数和边的个数，用空格间隔：(输入后)回车；

请输入顶点的信息和入度，用空格间隔(输入后)回车；

请输入边的两个顶点以及边上的权值，用空格间隔：（输入后）回车；

即得结果；

2、测试结果：

例如:输入：

请输入顶点的个数和边的个数，用空格间隔：911

输出的关键途径为：1-2-5-7—9和1-2-5-8-9

3、调试中的错误及解决办法。

调试过程中,碰到了许多的问题，如关于图的存储结构使用邻接矩阵还是邻接表,然后是关于拓扑排序的算法

的问题，通过查阅相关数据结构算法的书本解决了编程过程中碰到的问题。

运营界面

先输入911后，回车：

再输入102131415261718292后回车:

输入边的两个顶点以及边上的权值,用空格间隔:

S3"C:\Users\Lenovo\Deslctop\JRc\ftS\Debug\Textl.exe"