数据结构关键路径实验报告文档格式.docx
《数据结构关键路径实验报告文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构关键路径实验报告文档格式.docx（16页珍藏版）》请在冰点文库上搜索。
五、概要设计
为了实现上述操作，抽象数据图的定义如下：
structarcnode//声明边表中结点结构
{
intadjvex;
intdut;
//边上的权值
structarcnode*nextarc;
};
structnode//声明头结点结构
intdata;
intid;
//定点入度
structarcnode*firstarc;
1、基本操作：
（1）voidcreate_ALgraph（ALgraphg,inte,intn）
建立AOE网的邻接表，e为弧的数目，n为顶点数
（2）voidoupe_ALgraph（ALgraphg,intn）
输出AOE网的邻接表
（3）intCriticalpath（ALgraphg,intn）
求AOE网的各个关键活动
2、本程序包含两个模块：
（1）主程序模块；
（2）建立AOE网的邻接表、输出AOE网的邻接表、求AOE网的各个关键活动；
（3）模块调用图：
主程序模块
建立AOE网的邻接表
输出AOE网的邻接表
求AOE网的各个关键活动
3、流程图
六、详细设计
1、存储类型，元素类型，结点类型：
元素类型为整形和指针型。
2、每个模块的分析：
（1）主程序模块：
main（）
ALgraphg;
inte,n;
inttag;
printf（"
\n请输入顶点的个数和边的个数，用空格间隔:
"
）;
scanf（"
%d%d"
&
n,&
e）;
create_ALgraph（g,e,n）;
//建立邻接表
\n输出邻接表信息:
\n"
oupe_ALgraph（g,n）;
//建立输出邻接表
\n输出AOE网的关键路径:
弧:
权值\n"
tag=Criticalpath（g,n）;
//找关键活动
if（!
tag）
printf（"
AOE网有回路\n"
}
（2）建立AOE网的邻接表函数模块
voidcreate_ALgraph（ALgraphg,inte,intn）
{//建立AOE网的邻接表，e为弧的数目，n为顶点数
structarcnode*p;
inti,j,k,w;
printf（"
请输入顶点的信息和入度，用空格间隔:
for（i=1;
i<
=n;
i++）//结点下标从1开始
{
scanf（"
g[i].data,&
g[i].id）;
//输入顶点信息和入度
g[i].firstarc=NULL;
}
for（k=1;
k<
=e;
k++）//建立边表
请输入边的两个顶点以及边上的权值，用空格间隔:
%d%d%d"
i,&
j,&
w）;
//输入有向边的两个顶点
p=（structarcnode*）malloc（sizeof（structarcnode））;
p->
adjvex=j;
dut=w;
nextarc=g[i].firstarc;
//插入下标为i的边表的第一个结点的位置
g[i].firstarc=p;
输出AOE网的邻接表函数模块
voidoupe_ALgraph（ALgraphg,intn）//输出AOE网的邻接表
inti;
n;
i++）
p=g[i].firstarc;
%d,%d->
g[i].data,g[i].id）;
while（p!
=NULL）
{
%3d%3d"
p->
adjvex,p->
dut）;
p=p->
nextarc;
//找下一个邻接点
}
求AOE网的各个关键活动函数模块
intCriticalpath（ALgraphg,intn）//求AOE网的各个关键活动
inti,j,k,count;
inttpord[VEX_NUM+1];
//顺序队列
intve[VEX_NUM+1],le[VEX_NUM+1];
inte[ARC_NUM+1],l[ARC_NUM+1];
intfront=0,rear=0;
//顺序队列的首尾指针初值为0
structarcnode*p;
for（i=1;
i++）//各事件最早发生事件初值为0
ve[i]=0;
if（g[i].id==0）//入度为0入队列
tpord[++rear]=i;
count=0;
while（front!
=rear）
front++;
j=tpord[front];
count++;
p=g[j].firstarc;
k=p->
adjvex;
g[k].id--;
if（ve[j]+p->
dut>
ve[k]）
ve[k]=ve[j]+p->
dut;
if（g[k].id==0）
tpord[++rear]=k;
if（count<
n）//该AOE网有回路
return0;
i++）//各事件的最迟发生事件赋初值
le[i]=ve[n];
for（i=n-1;
i>
=1;
i--）//按拓扑序列的逆序取顶点
j=tpord[i];
p=g[j].firstarc;
if（le[k]-p->
dut<
le[j]）
le[j]=le[k]-p->
i=0;
for（j=1;
j<
j++）
while（p!
=NULL）//计算各边<
Vj-1,Vk>
所代表的a（i+1）的e[i]和l[i]
{
k=p->
e[i]=ve[j];
l[i]=le[k]-p->
if（l[i]==e[i]）//输出关键活动
printf（"
<
v%d,v%d>
:
%d\n"
g[j].data,g[k].data,p->
p=p->
i++;
}
return1;
}
3）函数调用关系图
create_ALgraph（ALgraphg,inte,intn）
oupe_ALgraph（ALgraphg,intn）
Criticalpath（ALgraphg,intn）
3、完整的程序：
#include"
stdio.h"
stdlib.h"
#defineVEX_NUM10//定义最大顶点数
#defineARC_NUM20//定义最多边数
typedefintvertype;
typedefstructnodeALgraph[VEX_NUM+1];
七、程序使用说明及测试结果
1、程序使用说明
（1）本程序的运行环境为VC6.0。
（2）进入演示程序后即显示提示信息：
请输入顶点的个数和边的个数，用空格间隔：
（输入后）回车；
请输入顶点的信息和入度，用空格间隔（输入后）回车；
请输入边的两个顶点以及边上的权值，用空格间隔：
即得结果；
2、测试结果：
例如：
输入：
请输入顶点的个数和边的个数，用空格间隔：
3、调试中的错误及解决办法。
调试过程中，遇到了许多的问题，如关于图的存储结构使用邻接矩阵还是邻接表，然后是关于拓扑排序的算法的问题，通过查阅相关数据结构算法的书本解决了编程过程中遇到的问题。
运行界面
先输入911后，回车：
再输入102131415261718292后回车：
输入边的两个顶点以及边上的权值，用空格间隔：
回车即得结果：
八、实验小结：
首先通过数据结构老师在课堂上的讲解，对关键路径有了认识和了解，求关键路径的算法也了解和理解了，然后参考相关数据结构算法的书本，将求关键路径的算法运行后，遇到了一些小问题，通过查阅相关资料和向其他同学请教，解决遇到的问题，关于图的路径问题还有最短路径也是求图的路径的一种算法，感觉图的用途挺多的，能够解决实际生活中遇到的很多问题。
签名：
日期：
实验成绩：
批阅日期：
升级会员 