数据结构实验五报告.docx
《数据结构实验五报告.docx》由会员分享，可在线阅读，更多相关《数据结构实验五报告.docx（26页珍藏版）》请在冰点文库上搜索。
数据结构实验五报告
实验报告
实验五图的遍历及其应用实现
一、实验目的
1．熟悉图常用的存储结构。
2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。
3．会用图的遍历解决简单的实际问题。
二、实验内容
[题目一]：
从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列.试设计程序实现上述图的类型定义和基本操作,完成上述功能。
该程序包括图类型以及每一种操作的具体的函数定义和主函数。
[题目二]：
在图G中求一条从顶点i到顶点s的简单路径
设计要求：
1、上机前，认真学习教材，熟练掌握图的构造和遍历算法,图的存储结构也可使用邻接矩阵等其他结构.
2、上机前，认真独立地写出本次程序清单，流程图。
图的构造和遍历算法分别参阅讲义和参考教材事例
三、实验步骤
㈠、数据结构与核心算法的设计描述
#defineMAX_VERTEX_NUM20
//变量声明
typedefstructArcNode
//弧结点定义
{
intadjvex;//该弧所指向的顶点的位置
structArcNode*nextarc;//指向下一条弧的指针
//InfoType*info;
}ArcNode;
typedefstructVNode
//顶点结点定义
{
chardata;//顶点信息
ArcNode*firstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct
//图的定义
{
AdjListvertices;
intvexnum,arcnum;//图的当前顶点数和弧数
intkind;//图的种类标志
}ALGraph;
ALGraphG;//定义图变量
boolvisited[MAX_VERTEX_NUM];//访问标志数组
typedefstructQueueNode
//队列结点类型定义
{
intdata;//结点中所存值
QueueNode*next;//指向下一个结点
}QueueNode;
typedefstruct
//队列定义
{
QueueNode*first;//队列的头指针
QueueNode*rear;//队列的尾指针
}QueueLink;
相关函数声明：
voidCreateGraph（MGraph&G）
//输入图的顶点和边的信息,建立图
voidDFSTraverse（GraphG,intv）
//深度优先搜索遍历图
voidBFSTraverse（GraphG,intv）
//广度优先搜索遍历图
intLocateVertices（ALGraphG,chara）
//查找字符a在图中的位置
intFirstAdjVex（ALGraphG,intv）
//查找图中位置v的第一个邻接点在图中所在的位置
intNextAdjVex（ALGraphG,intv,intw）
//查找相对于图中位置v的邻接点w的下一邻接点在图中的位置
voidDestroyGraph（ALGraph&G）
//销毁图
voidDFS（ALGraphG,intv）
//利用递归实现对图中一个极大强连通分量的遍历
voidDFSTraverse（ALGraphG）
//深度遍历访问图
voidInitQueue（QueueLink&Queue）
//初始化队列
voidEnQueue（QueueLink&Queue,inti）
//元素i入队列
voidDeQueue（QueueLink&Queue,int&i）
//队列头元素出队
intQueueEmpty（QueueLinkQueue）
//判断队列是否为空，若为空则返回1，否则返回0
voidDestroyQueue（QueueLink&Queue）
//销毁队列
voidBFSTraverse（ALGraphG）
//利用队列实现图的广度优先遍历
㈡、函数调用及主函数设计
㈢程序调试及运行结果分析
在调试过程中，LocateVertices（ALGraphG,chara）函数中少了一个return-1语句，经过修改得到正确的结果。
㈣实验总结
这次的实验使得我对图的定义及其操作更加地了解，运用起来更加地顺手，了解了图的数据结构及算法，还有其表示与实现的存储结构类型，能根据具体情况来选择合适的存储结构实现所需的操作，掌握了深度优先遍历图的递归算法的书写，利用队列实现广度优先遍历图的算法与分析问题的能力，让我能够对以前的知识有所复习，例如：
队列的使用。
对以前的知识用了更深入的理解，例如：
对图的深度优先遍历是二叉树先序遍历的推广，广度优先遍历是二叉树层序遍历的推广，但是这几者之间又有所不同。
这是我收获最大的地方。
四、主要算法流程图及程序清单
1、主要算法流程图：
（部分）
利用邻接表存储结构构造有向图voidCreateGraph（ALGraph&G）
否
是
查找图中位置v的第一个邻接点在图中所在的位置
intFirstAdjVex（ALGraphG,intv）
是
否
查找相对于图中位置v的邻接点w的下一邻接点在图中的位置
intNextAdjVex（ALGraphG,intv,intw）
是
否
是
否
深度遍历访问图voidDFSTraverse（ALGraphG）
否
是
利用队列实现图的广度优先遍历voidBFSTraverse（ALGraphG）
是
否
否
是
是
否
2、程序清单
题目一：
#include
#include
#defineMAX_VERTEX_NUM20
typedefstructArcNode
//弧结点定义
{
intadjvex;//该弧所指向的顶点的位置
structArcNode*nextarc;//指向下一条弧的指针
//InfoType*info;
}ArcNode;
typedefstructVNode
//顶点结点定义
{
chardata;//顶点信息
ArcNode*firstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct
//图的定义
{
AdjListvertices;
intvexnum,arcnum;//图的当前顶点数和弧数
intkind;//图的种类标志
}ALGraph;
ALGraphG;//定义图变量
boolvisited[MAX_VERTEX_NUM];//访问标志数组
typedefstructQueueNode
//队列结点类型定义
{
intdata;//结点中所存值
QueueNode*next;//指向下一个结点
}QueueNode;
typedefstruct
//队列定义
{
QueueNode*first;//队列的头指针
QueueNode*rear;//队列的尾指针
}QueueLink;
intLocateVertices（ALGraphG,chara）
//查找字符a在图中的位置
{
for（inti=0;iif（G.vertices[i].data==a）
returni;
return-1;
}
voidCreateGraph（ALGraph&G）
//利用邻接表存储结构构造有向图
{
inta,b;
chars;
ArcNode*p;
cout<cout<<"请输入顶点个数和图中弧的个数"<cin>>G.vexnum>>G.arcnum;
cout<<"请输入各个顶点的值，顶点的值类型为字符类型"<for（inti=0;i{
cin>>G.vertices[i].data;
G.vertices[i].firstarc=NULL;
}
cout<<"请输入图中各个弧"<for（i=1;i<=G.arcnum;i++）
{
cin>>s;
a=LocateVertices（G,s）;
cin>>s;
b=LocateVertices（G,s）;
p=newArcNode;
if（!
p）
return;
p->adjvex=b;
p->nextarc=G.vertices[a].firstarc;
G.vertices[a].firstarc=p;
}
}
intFirstAdjVex（ALGraphG,intv）
//查找图中位置v的第一个邻接点在图中所在的位置
{
if（G.vertices[v].firstarc）
returnG.vertices[v].firstarc->adjvex;
return-1;
}
intNextAdjVex（ALGraphG,intv,intw）
//查找相对于图中位置v的邻接点w的下一邻接点在图中的位置
{
ArcNode*p;
p=G.vertices[v].firstarc;
while（p->adjvex!
=w）
p=p->nextarc;
if（p->nextarc）
returnp->nextarc->adjvex;
return-1;
}
voidDestroyGraph（ALGraph&G）
//销毁图
{
ArcNode*p,*p1;
for（inti=0;i{
p=G.vertices[i].firstarc;
if（p）
p1=p->nextarc;
while（p）
{
deletep;
p=p1;
if（p1）
p1=p1->nextarc;
}
}
}
///////////////////////////////////////////////////////
voidDFS（ALGraphG,intv）
//利用递归实现对图中一个极大强连通分量的遍历
{
visited[v]=true;
cout<for（intw=FirstAdjVex（G,v）;w>=0;w=NextAdjVex（G,v,w））
if（!
visited[w]）
DFS（G,w）;
}
voidDFSTraverse（ALGraphG）
//深度遍历访问图
{
for（inti=0;ivisited[i]=false;
for（i=0;iif（!
visited[i]）
DFS（G,i）;
}
voidInitQueue（QueueLink&Queue）
//初始化队列
{
Queue.rear=Queue.first=newQueueNode;
Queue.rear->next=NULL;
}
voidEnQueue（QueueLink&Queue,inti）
//元素i入队列
{
QueueNode*p;
p=newQueueNode;
p->data=i;
p->next=NULL;
Queue.rear->next=p;
Queue.rear=p;
}
voidDeQueue（QueueLink&Queue,int&i）
//队列头元素出队
{
QueueNode*p;
p=Queue.first->next;
i=p->data;
if（p==Queue.rear）
Queue.rear=Queue.first;
Queue.first->next=p->next;
free（p）;
}
intQueueEmpty（QueueLinkQueue）
//判断队列是否为空，若为空则返回1，否则返回0
{
if（Queue.first==Queue.rear）
return1;
return0;
}
voidDestroyQueue（QueueLink&Queue）
//销毁队列
{
inti;
while（!
QueueEmpty（Queue））
DeQueue（Queue,i）;
free（Queue.first）;
}
voidBFSTraverse（ALGraphG）
//利用队列实现图的广度优先遍历
{
inti,v,u,w;
QueueLinkQueue;
for（i=0;ivisited[i]=false;
InitQueue（Queue）;
for（v=0;vif（!
visited[v]）
{
visited[v]=true;
cout<EnQueue（Queue,v）;
while（!
QueueEmpty（Queue））
{
DeQueue（Queue,u）;
for（w=FirstAdjVex（G,u）;w>=0;w=NextAdjVex（G,u,w））
if（!
visited[w]）
{
visited[w]=true;
cout<EnQueue（Queue,w）;
}
}
}
DestroyQueue（Queue）;
}
voidmain（）
{
CreateGraph（G）;
cout<"<DFSTraverse（G）;
cout<"<BFSTraverse（G）;
cout<DestroyGraph（G）;
}
题目二：
#include
#include
#defineMAX_VERTEX_NUM20
typedefstructArcNode
{
intadjvex;//该弧所指向的顶点的位置
structArcNode*nextarc;//指向下一条弧的指针
//InfoType*info;
}ArcNode;
typedefstructVNode
{
chardata;//顶点信息
ArcNode*firstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct
{
AdjListvertices;
intvexnum,arcnum;//图的当前顶点数和弧数
intkind;//图的种类标志
}ALGraph;
ALGraphG;//定义图变量
boolvisited[MAX_VERTEX_NUM];//访问标志数组
structnode1
{
inta;
node1*next;
};
node1*path;
boolfound=false;
intLocateVertices（ALGraphG,chara）
//查找字符a在图中的位置
{
for（inti=0;iif（G.vertices[i].data==a）
returni;
return-1;
}
voidCreateGraph（ALGraph&G）
//利用邻接表存储结构构造有向图
{
inta,b;
chars;
ArcNode*p;
cout<cout<<"请输入顶点个数和图中弧的个数"<cin>>G.vexnum>>G.arcnum;
cout<<"请输入各个顶点的值，顶点的值类型为字符类型"<for（inti=0;i{
cin>>G.vertices[i].data;
G.vertices[i].firstarc=NULL;
}
cout<<"请输入图中各个弧"<for（i=1;i<=G.arcnum;i++）
{
cin>>s;
a=LocateVertices（G,s）;
cin>>s;
b=LocateVertices（G,s）;
p=newArcNode;
if（!
p）
return;
p->adjvex=b;
p->nextarc=G.vertices[a].firstarc;
G.vertices[a].firstarc=p;
}
}
intFirstAdjVex（ALGraphG,intv）
//查找图中位置v的第一个邻接点在图中所在的位置
{
if（G.vertices[v].firstarc）
returnG.vertices[v].firstarc->adjvex;
return-1;
}
intNextAdjVex（ALGraphG,intv,intw）
//查找相对于图中位置v的邻接点w的下一邻接点在图中的位置
{
ArcNode*p;
p=G.vertices[v].firstarc;
while（p->adjvex!
=w）
p=p->nextarc;
if（p->nextarc）
returnp->nextarc->adjvex;
return-1;
}
voidDestroyGraph（ALGraph&G）
//销毁图
{
ArcNode*p,*p1;
for（inti=0;i{
p=G.vertices[i].firstarc;
if（p）
p1=p->nextarc;
while（p）
{
deletep;
p=p1;
if（p1）
p1=p1->nextarc;
}
}
}
///////////////////////////////////////////////////////
voidDFS（ALGraphG,intv）
{
visited[v]=true;
cout<for（intw=FirstAdjVex（G,v）;w>=0;w=NextAdjVex（G,v,w））
if（!
visited[w]）
DFS（G,w）;
}
voidDFSTraverse（ALGraphG）
//深度优先遍历图
{
for（inti=0;ivisited[i]=false;
for（i=0;iif（!
visited[i]）
DFS（G,i）;
}
////////////////////////////////////////////////////////////
voidAppend（intv）
//将v插入到path链表中
{
node1*p,*p1;
p=path;
while（p&&p->next）
p=p->next;
p1=newnode1;
p1->a=v;
p1->next=NULL;
p->next=p1;
}
voidDelete（intv）
//将v从path中删除
{
node1*p,*p1;
p=path;
p1=p->next;
while（p1&&p1->a!
=v）
{
p=p->next;
p1=p1->next;
}
if（p1）
p->next=p1->next;
deletep1;
}
voidDFSearch（ALGraphG,inti,ints）
//查找从i到s之间的一条简单路径，并存入path中
{
intw;
for（intx=0;xvisited[x]=false;
visited[i]=true;
Append（i）;
for（w=FirstAdjVex（G,i）;w>=0&&!
found;w=NextAdjVex（G,i,w））
{
if（w==s）
{
found=true;
visited[s]=true;
Append（w）;
}
elseif（!
visited[w]）
DFSearch（G,w,s）;
}
if（!
found）
Delete（i）;
}
voidmain（）
{
chara,b;
path=newnode1;
path->next=NULL;
CreateGraph（G）;
cout<"<DFSTraverse（G）;
cout<cout<<"请输入要求的是哪两个顶点之间的路径"<cin>>a>>b;
DFSearch（G,LocateVertices（G,a）,LocateVertices（G,b））;
node1*p;
p=NULL;
p=path->next;
cout<<"这两点之间的路径为：
"<while（p）
{
升级会员 