完整word版图的应用的实验报告.docx
《完整word版图的应用的实验报告.docx》由会员分享，可在线阅读，更多相关《完整word版图的应用的实验报告.docx（19页珍藏版）》请在冰点文库上搜索。
完整word版图的应用的实验报告
实验六图的应用及其实现
一、实验目的1．进一步功固图常用的存储结构。
2．熟练掌握在图的邻接表实现图的基本操作。
3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。
二、实验内容
[题目一]：
从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列.试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。
测试数据：
教材图7.28
[题目二]：
从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。
试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。
测试数据：
教材图7.29
三、实验步骤
㈠、数据结构与核心算法的设计描述
基本数据结构：
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码，如OK等*/
#defineINFINITYINT_MAX//定义无穷大∞
#defineMAX_VERTEX_NUM20
typedefintVertexType;
typedefintInfoType;
typedefstructArcNode//表结点定义
{
InfoTypeinfo;
intadjvex;//邻接点域，存放与Vi邻接的点在表头数组中的位置
ArcNode*nextarc;//链域，指示依附于vi的下一条边或弧的结点，
}ArcNode;
typedefstructVNode//表头结点
{
intdata;//存放顶点信息
structArcNode*firstarc;//指示第一个邻接点
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct{//图的结构定义
顶点向量//vertices;AdjList
intvexnum,arcnum;
intIsquan;//是否含有权值
}MGraph;
typedefstruct
{
int*top;
int*base;
intstacksize;
}Sqstack;
typedefintElemType;
StatusInitstack（Sqstack&s）
{
s.base=（int*）malloc（sizeof（int）*25）;
if（!
s.base）
returnERROR;
s.top=s.base;
s.stacksize=25;
returnOK;
}
intindegree[MAX_VERTEX_NUM];
intve[MAX_VERTEX_NUM];//e各顶点的最早发生时间
intvl[MAX_VERTEX_NUM];//各顶点发生的最晚发生时间
调用的函数
StatusInitstack（Sqstack&s）
StatusPop（Sqstack&s,int&e）
//若栈不空，则删除S的栈顶元素，
//用e返回其值，并返回OK；否则返回ERROR
intPush（Sqstack&s,int&e）
intStackEmpty（Sqstacks）//若栈为空栈，则返回TRUE,否则返回FLASE
StatusCreateGraph（MGraph&G）
voidDisplay（MGraph&G）/*输出图G的信息*/
voidFindDegree（MGraphg,intindegree[]）//对=图中的各个顶点的入度进行统计，并将第i
//个顶点的入度数放入indegree[i]
intLocateVex（MGraphG,VertexTypeu）
/*初始条件:
图G存在,u和G中顶点有相同特征*/
/*操作结果:
若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/
StatusToopologicalSort（MGraphg）//对图进行拓扑排序，并输出拓扑排序的结果
StatusToopologicalOrder（MGraphg,Sqstack&T）//拓扑序列
关键路径StatusCriticalPath（MGraphg,SqstackT）//可用函数的调用关系图说明）㈡、函数调用及主函数设计（．
voidmain（）
{
MGraphg;
SqstackT;
函Main:
\n;潣瑵?
创建图
CreateGraph（g）;
创建图:
\n;输出图的信息潣瑵?
Display（g）;
:
\n;拓扑排序潣瑵?
求最小路径ToopologicalSort（g）;输出图信息拓扑排序
\n;潣瑵?
求关键历经：
ToopologicalOrder（g,T）;
CriticalPath（g,T）;
}
程序调试及运行结果分析㈢）在创建图的过程中需要考虑输入的方便，这就需要标记根据用户选择是（1否需要输入权值，选择不需要权值时就不会有关权值信息的操作。
所以这就在图表示无权值，其他表示有权值）标记（的结构体中加ISquan0（）函数调用过程就是一个对邻接表遍历的过程，在遍历FindIndegree
（2）『』数Indegree过程中需要将弧指向的结点进行入度数组的标记。
便定义了一个组。
，）在求关键路径时，需要两次用到拓扑排序（其中一次是逆拓扑排序）（3在拓扑排序时还需要注意看看是否有环，若有环则输出提示信息。
实验总结㈣
通过对拓扑排序和求最小路径的操作，首先加强了对图的存储结构和图的遍历的进一步的熟悉和应用，在拓扑排序中还让我们去应用到以前学习的栈的知识，温故的同时也在实践的新的理论。
对图的应用是在生活中应用很广泛，同时图的知识点和算法也是我们这学期学习的精华，例如求关键路径，用到栈，拓扑排序等经典算法，让我们受益匪浅。
四、主要算法流程图及程序清单、主要算法流程图：
1
创建图拓扑排序
开始
开
输入顶点数和边的压入将入度
输入顶点信为
创建顶点向量的数
弹出栈顶元素，输出结点信息并将其
接结点入度减一，入度的入
输入弧的信
创建了图的邻接表结束结束
2、程序清单程序过长，可附主要部分）
#include
#include/*malloc（）等*/
#include/*INT_MAX等*/
#include
#include/*exit（）*/
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码，如OK等*/
#defineINFINITYINT_MAX//定义无穷大∞
#defineMAX_VERTEX_NUM20
typedefintVertexType;
typedefintInfoType;
typedefstructArcNode//表结点定义
{
InfoTypeinfo;
intadjvex;//邻接点域，存放与Vi邻接的点在表头数组中的位置
ArcNode*nextarc;//链域，指示依附于vi的下一条边或弧的结点，
}ArcNode;
typedefstructVNode//表头结点
{intdata;//存放顶点信息
structArcNode*firstarc;//指示第一个邻接点
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct
{//图的结构定义
AdjListvertices;//顶点向量
intvexnum,arcnum;
intIsquan;//是否含有权值
}MGraph;
intindegree[MAX_VERTEX_NUM];
intve[MAX_VERTEX_NUM];//e各顶点的最早发生时间
intvl[MAX_VERTEX_NUM];//各顶点发生的最晚发生时间
/*图的邻接表存储（存储结构定义）的基本操作*/
intLocateVex（MGraphG,VertexTypeu）
{
/*初始条件:
图G存在,u和G中顶点有相同特征*/
/*操作结果:
若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/
inti;
for（i=0;iif（u==G.vertices[i].data）
returni;
return-1;
};
StatusCreateGraph（MGraph&G）
{inti,j,k;
InfoTypevc;
VertexTypeva,vb;
ArcNode*p;
潣瑵?
请输入图的顶点数,边数:
;
cin>>G.vexnum>>G.arcnum;
潣瑵?
请输入<\n;
for（i=0;i{
cin>>G.vertices[i].data;
G.vertices[i].firstarc=NULL;
}
潣瑵?
是否含有权值：
（若不含权值请输入0，否则输入1）\n;
cin>>G.Isquan;
if（!
G.Isquan）
潣瑵?
请顺序输入每条弧的弧尾弧头<else
潣瑵?
请顺序输入每条弧的弧尾弧头以及弧的信息（以空格作为间隔）:
\n;
for（k=0;k{
if（!
G.Isquan）
cin>>va>>vb;
else
cin>>va>>vb>>vc;
i=LocateVex（G,va）;/*弧尾*/
j=LocateVex（G,vb）;/*弧头*/
p=（ArcNode*）malloc（sizeof（ArcNode））;
p->adjvex=j;
if（G.Isquan）
p->info=vc;
else
p->info=0;
p->nextarc=G.vertices[i].firstarc;/*插在表头*/
G.vertices[i].firstarc=p;
}returnOK;
}
voidDisplay（MGraph&G）
{/*输出图G的信息*/
inti;
ArcNode*p;
潣瑵?
?
敶湸浵?
尼个顶点：
\n;
for（i=0;icout<cout<\n;
for（i=0;i{
p=G.vertices[i].firstarc;
while（p）
{cout<<adjvex].data<p=p->nextarc;
}
}
//system（pause）;
}
////////////////////////////////////////////////////////////////////
//
//建立栈相关的数据结构和函数//
typedefstruct
{
int*top;
int*base;
intstacksize;
}Sqstack;
typedefintElemType;
StatusInitstack（Sqstack&s）
{s.base=（int*）malloc（sizeof（int）*25）;
if（!
s.base）
returnERROR;
s.top=s.base;
s.stacksize=25;
returnOK;
}
intPush（Sqstack&s,int&e）
{//向栈输入元素
if（s.top-s.base>=s.stacksize）
{
s.base=（ElemType*）realloc（s.base,（s.stacksize+10）*sizeof（ElemType））;
if（!
s.base）return0;
else
{s.top=s.base+s.stacksize;
s.stacksize+=10;
}
}
*s.top=e;
s.top++;
returnOK;
}
StatusPop（Sqstack&s,int&e）
{
//若栈不空，则删除S的栈顶元素，
//用e返回其值，并返回OK；否则返回ERROR
if（s.top==s.base）
returnERROR;
e=*--s.top;
returnOK;
}//Pop;
intStackEmpty（Sqstacks）
{
//若栈为空栈，则返回TRUE,否则返回FLASE
if（s.top==s.base）
return1;
elsereturn0;
}
/////////////////////////////////////////////////////////////////////////////
voidFindDegree（MGraphg,intindegree[]）
{
//对=图中的各个顶点的入度进行统计，并将第i个顶点的入度数放入indegree[i]
ArcNode*p;
inti;
for（i=0;iindegree[i]=0;
潣瑵?
李星运是个SB<for（intj=0;jfor（p=g.vertices[j].firstarc;p!
=NULL;p=p->nextarc）
indegree[p->adjvex]++;
}
//对图进行拓扑排序，并输出拓扑排序的结果
StatusToopologicalSort（MGraphg）
{Sqstacks;
inti;
intcount=0;
FindDegree（g,indegree）;
Initstack（s）;
for（i=0;iif（indegree[i]==0）
Push（s,i）;//将入度为0的顶点序号压入零入度栈
while（!
StackEmpty（s））//如果零入度栈中还有结点
{Pop（s,i）;
潣瑵?
第?
椼?
结点<<\<count++;
for（ArcNode*p=g.vertices[i].firstarc;p;p=p->nextarc）
{intk=p->adjvex;
if（!
（--indegree[k]））
Push（s,k）;
}
}
if（count{
潣瑵?
不是连通图！
<returnERROR;
}
else
returnOK;
}
//拓扑序列
StatusToopologicalOrder（MGraphg,Sqstack&T）
{
Sqstacks;
inti;
intcount=0;
FindDegree（g,indegree）;
Initstack（s）;//用于存放零入度的结点栈
Initstack（T）;//若g不为空，则用T存放柘扑序列
for（i=0;iif（indegree[i]==0）
Push（s,i）;
//初始化数组各结点的最早时间为0
for（i=0;ive[i]=0;
while（!
StackEmpty（s））
{
Pop（s,i）;//将零入度结点栈中的结点弹出一个结点
Push（T,i）;//将弹出的结点序列压入拓扑序列栈T中
count++;
for（ArcNode*p=g.vertices[i].firstarc;p;p=p->nextarc）
{
intk=p->adjvex;
if（!
（--indegree[k]））
Push（s,k）;//将入度为0的结点压入零入度栈中
if（ve[i]+（p->info）>ve[k]）
ve[k]=ve[i]+（p->info）;
}
}
if（countreturnERROR;
else
returnOK;
}
//关键路径
StatusCriticalPath（MGraphg,SqstackT）
{
inti;
ArcNode*p;
if（!
ToopologicalOrder（g,T））
{
潣瑵?
拓扑排序不成功！
\n;
returnERROR;
}
for（i=0;ivl[i]=ve[i];//将各顶点的最晚发生时间都赋值为最早发生时间
while（!
StackEmpty（T））
for（Pop（T,i）,p=g.vertices[i].firstarc;p;p=p->nextarc）
{
intk=p->adjvex;
intdut=p->info;
if（vl[k]-dutvl[i]=vl[k]-dut;//如果顶点的最晚时间大于前一个顶点的最晚时间和其间权值的差
}
for（intj=0;jfor（p=g.vertices[i].firstarc;p;p=p->nextarc）
{intk=p->adjvex;
intdut=p->info;
intee=ve[j],el=vl[k]-dut;
cout<<}
returnOK;
}
voidmain（）
{
MGraphg;
SqstackT;
:
\n;
创建图潣瑵?
CreateGraph（g）;
潣瑵?
各条弧的信息:
\n;
Display（g）;
潣瑵?
拓扑排序:
\n;
ToopologicalSort（g）;
潣瑵?
求关键历经：
\n;
ToopologicalOrder（g,T）;
CriticalPath（g,T）;
}
升级会员 