图的存储结构与遍历 数据结构实验.docx
《图的存储结构与遍历 数据结构实验.docx》由会员分享，可在线阅读，更多相关《图的存储结构与遍历 数据结构实验.docx（22页珍藏版）》请在冰点文库上搜索。
图的存储结构与遍历数据结构实验
实验报告
June11
2015
姓名：
陈斌学号：
E11314079专业：
13计算机科学与技术
数据结构第七次实验
学号E11314079专业计算机科学与技术姓名陈斌
实验日期2015.06.11教师签字成绩
实验报告
【实验名称】图的存储结构与遍历
【实验目的】
（1）掌握图的相关概念；
（2）掌握图的存储结构；
（3）掌握图的遍历算法并编程实现。
【实验内容】
编写一个程序，实现图的相关运算，并在此基础上设计一个主程序，完成如下功能：
（1）建立如教材图7.9所示的有向图G的邻接矩阵，并分别输出顶点表和邻接矩阵。
（2）由有向图G的邻接矩阵产生邻接表，并依次输出每一顶点和其邻接表。
（3）再由
（2）的邻接表产生对应的邻接矩阵，并输出该矩阵。
（4）在图G的邻接矩阵存储表示基础上，输出从顶点V1开始的深度优先遍历序列（递归算法）。
（5）在图G的邻接表存储表示基础上，输出从顶点V1开始的广度优先遍历序列。
（6）利用非递归算法重解任务（4）（选做）。
源代码：
head.h:
#include
#include
#include//malloc（）
#include//INT,MAX
#include//EOF,NULL
#include//atoi（）
#include//eof（）
#include//floor（）,ceil（）,abs（）
#include//exit（）
#include//cout,cin
//函数结果状态代码
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
//OVERFLOW在math.h中已定义为3
typedefintStatus;
typedefintBoolean;//布尔类型
main.cpp:
#include"head.h"
#defineMAX_NAME5/*顶点字符串的最大长度+1*/
#defineMAX_INFO20/*相关信息字符串的最大长度+1*/
typedefintVRType;
typedefintInfoType;
typedefcharVertexType[MAX_NAME];
#defineINFINITYINT_MAX/*用整型最大值代替∞*/
#defineMAX_VERTEX_NUM20/*最大顶点个数*/
typedefenum{DG,DN,AG,AN}GraphKind;/*{有向图,有向网,无向图,无向网}*/
/*图的数组（邻接矩阵）存储表示*/
typedefstruct
{
VRTypeadj;/*顶点关系类型。
对无权图，用1（是）或0（否）表示相邻否;对带权图，c则为权值类型*/
InfoType*info;/*该弧相关信息的指针（可无）*/
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
VertexTypevexs[MAX_VERTEX_NUM];/*顶点向量*/
AdjMatrixarcs;/*邻接矩阵*/
intvexnum,arcnum;/*图的当前顶点数和弧数*/
GraphKindkind;/*图的种类标志*/
}MGraph;
/*图的邻接表存储表示*/
typedefstructArcNode
{
intadjvex;/*该弧所指向的顶点的位置*/
structArcNode*nextarc;/*指向下一条弧的指针*/
InfoType*info;/*该弧相关信息的指针*/
}ArcNode;/*表结点*/
typedefstruct
{
VertexTypedata;/*顶点信息*/
ArcNode*firstarc;/*第一个表结点的地址,指向第一条依附该顶点的弧的指针*/
}VNode,AdjList[MAX_VERTEX_NUM];/*头结点*/
typedefstruct
{
AdjListvertices;
intvexnum,arcnum;/*图的当前顶点数和弧数*/
intkind;/*图的种类标志*/
}ALGraph;
intLocateVex（MGraphG,VertexTypeu）
{/*初始条件:
图G存在,u和G中顶点有相同特征*/
/*操作结果:
若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/
for（inti=0;iif（strcmp（u,G.vexs[i]）==0）
returni;
return-1;
}
StatusCreateDG（MGraph&G）
{/*采用数组（邻接矩阵）表示法,构造有向图G*/
inti,j,k;
VertexTypeva,vb;
VRTypew;
cout<<"请输入有向图G的顶点数弧数（用空格隔开）:
";
cin>>G.vexnum>>G.arcnum;
cout<<"请输入"<\n";
for（i=0;icin>>G.vexs[i];
for（i=0;ifor（j=0;j{
G.arcs[i][j].adj=INFINITY;/*图*/
G.arcs[i][j].info=NULL;
}
cout<<"请输入"<\n";
for（k=0;k{
cin>>va>>vb>>w;
i=LocateVex（G,va）;
j=LocateVex（G,vb）;
G.arcs[i][j].adj=w;
}
G.kind=DG;
returnOK;
}
voidPrintAdjMatrix（MGraphG）//输出邻接矩阵
{
charch='*';
cout<<"-----------------------"<cout<<"";
for（inti=0;icout<cout<for（i=0;i{
cout<for（intj=0;j{
if（G.arcs[i][j].adj==INFINITY）
cout<else
cout<}
cout<}
cout<<"-----------------------"<}
voiddisplay（MGraphG）//输出顶点表和邻接矩阵
{
cout<<"-----------------------"<cout<<"顶点表:
\n";
for（inti=0;icout<cout<<"\n-----------------------"<cout<<"\n邻接矩阵（'*'代表无穷大）:
\n";
PrintAdjMatrix（G）;
}
voidCreateMGtoDN（ALGraph&G2,MGraph&G）
{
//由有向图G的邻接矩阵产生邻接表
ArcNode*p;
G2.kind=G.kind;
G2.vexnum=G.vexnum;
G2.arcnum=G.arcnum;
for（inti=0;i{//构造表头向量
strcpy（G2.vertices[i].data,G.vexs[i]）;
G2.vertices[i].firstarc=NULL;//初始化指针
}
for（i=0;ifor（intj=0;jif（G.arcs[i][j].adj!
=INFINITY）
{
p=（ArcNode*）malloc（sizeof（ArcNode））;
p->adjvex=j;
p->nextarc=G2.vertices[i].firstarc;
p->info=G.arcs[i][j].info;
G2.vertices[i].firstarc=p;
}
}
voidPrintAdjList（ALGraphG）//输出邻接表
{
cout<<"-----------------------"<for（inti=0;i{
ArcNode*p=G.vertices[i].firstarc;
cout<while（p）
{
cout<<"→"<adjvex].data;
p=p->nextarc;
}
cout<}
cout<<"-----------------------"<}
voidCreateDNtoMG（MGraph&G3,ALGraph&G2）
{//由邻接表产生对应的邻接矩阵
inti,j;
ArcNode*p;
G3.kind=GraphKind（G2.kind）;
G3.vexnum=G2.vexnum;
G3.arcnum=G2.arcnum;
for（i=0;istrcpy（G3.vexs[i],G2.vertices[i].data）;
for（i=0;i{
p=G2.vertices[i].firstarc;
while（p）
{
G3.arcs[i][p->adjvex].adj=1;
p=p->nextarc;
}//while
for（j=0;jif（G3.arcs[i][j].adj!
=1）
G3.arcs[i][j].adj=INFINITY;
}//for
}
Booleanvisited[MAX_VERTEX_NUM];/*访问标志数组（全局量）*/
void（*VisitFunc）（char*v）;/*函数变量（全局量）*/
//从第v个顶点出发递归地深度优先遍历图G。
/*查找第1个邻接点*/
intFirstAdjVex（MGraph&G,intv）
{
for（intm=0;mif（G.arcs[v][m].adj!
=INFINITY）
returnm;
return-1;
}
/*查找下一个邻接点*/
intNextAdjVex（MGraph&G,intv,intw）
{
for（intj=w+1;jif（G.arcs[v][j].adj!
=INFINITY）
returnj;
return-1;
}
voidDFS（MGraph&G,intv）
{//从第v个顶点出发递归地深度优先遍历图G
cout<visited[v]=TRUE;
for（intw=FirstAdjVex（G,v）;w>=0;w=NextAdjVex（G,v,w））//访问第W个顶点
if（!
visited[w]）//对v的尚未访问的邻接点w递归调用DFS
DFS（G,w）;
}
voidvisits（MGraph&G,int&v）
{//判断结点是否已经访问过
v=-1;
for（inti=0;iif（!
visited[i]）
v=i;
}
voidDFSTraverse（MGraphG,intv）
{//对图G作深度优先遍历
for（inti=0;ivisited[i]=FALSE;//访问标志数组初始化
while（v>=0&&v{
DFS（G,v）;
visits（G,v）;
}
}
/*栈的顺序存储表示*/
typedefintSElemType;/*栈类型*/
#defineSTACK_INIT_SIZE10/*存储空间初始分配量*/
#defineSTACKINCREMENT2/*存储空间分配增量*/
typedefstructSqStack
{
SElemType*base;/*在栈构造之前和销毁之后，base的值为NULL*/
SElemType*top;/*栈顶指针*/
intstacksize;/*当前已分配的存储空间，以元素为单位*/
}SqStack;/*顺序栈*/
StatusInitStack（SqStack&S）
{/*构造一个空栈S*/
S.base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
if（!
S.base）
exit（OVERFLOW）;/*存储分配失败*/
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}
StatusStackEmpty（SqStack&S）
{/*若栈S为空栈，则返回TRUE，否则返回FALSE*/
if（S.top==S.base）
returnTRUE;
else
returnFALSE;
}
StatusPush（SqStack&S,SElemTypee）
{/*插入元素e为新的栈顶元素*/
if（S.top-S.base>=S.stacksize）/*栈满，追加存储空间*/
{
S.base=（SElemType*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（SElemType））;
if（!
S.base）
exit（OVERFLOW）;/*存储分配失败*/
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*（S.top）++=e;
returnOK;
}
StatusPop（SqStack&S,SElemType&e）
{/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
if（S.top==S.base）
returnERROR;
e=*--S.top;
returnOK;
}
voidDFSTraverse2（MGraphG,intv）
{//对图G作深度优先遍历（非递归算法）
SqStacks;
InitStack（s）;
for（inti=0;ivisited[i]=FALSE;//访问标志数组初始化
Push（s,v）;
while（!
StackEmpty（s））//对尚未访问的顶点调用DFS
{
intflag=0;
Pop（s,v）;
if（!
visited[v]）
{
cout<visited[v]=TRUE;
}
for（intj=0;jif（（!
visited[j]）&&（G.arcs[v][j].adj!
=INFINITY））
{
Push（s,j）;
flag=1;
break;
}
if（!
flag）
{
visits（G,v）;
if（v>=0&&vPush（s,v）;
else
break;
}
}
}
typedefintQElemType;/*队列类型*/
/*单链队列－－队列的链式存储结构*/
typedefstructQNode
{
QElemTypedata;
structQNode*next;
}QNode,*QueuePtr;
typedefstruct
{
QueuePtrfront,rear;/*队头、队尾指针*/
}LinkQueue;
StatusInitQueue（LinkQueue&Q）
{/*构造一个空队列Q*/
Q.front=Q.rear=（QueuePtr）malloc（sizeof（QNode））;
if（!
Q.front）
exit（OVERFLOW）;
Q.front->next=NULL;
returnOK;
}
StatusQueueEmpty（LinkQueue&Q）
{/*若Q为空队列,则返回TRUE,否则返回FALSE*/
if（Q.front==Q.rear）
returnTRUE;
else
returnFALSE;
}
StatusEnQueue（LinkQueue&Q,QElemTypee）
{/*插入元素e为Q的新的队尾元素*/
QueuePtrp=（QueuePtr）malloc（sizeof（QNode））;
if（!
p）/*存储分配失败*/
exit（OVERFLOW）;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
returnOK;
}
StatusDeQueue（LinkQueue&Q,QElemType&e）
{/*若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR*/
QueuePtrp;
if（Q.front==Q.rear）
returnERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if（Q.rear==p）
Q.rear=Q.front;
free（p）;
returnOK;
}
intLocateVex（ALGraphG,VertexTypeu）
{/*初始条件:
图G存在,u和G中顶点有相同特征*/
/*操作结果:
若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/
inti;
for（i=0;iif（strcmp（u,G.vertices[i].data）==0）
returni;
return-1;
}
VertexType*GetVex（ALGraphG,intv）
{/*初始条件:
图G存在,v是G中某个顶点的序号。
操作结果:
返回v的值*/
if（v>=G.vexnum||v<0）
exit（ERROR）;
return&G.vertices[v].data;
}
intFirstAdjVex（ALGraphG,VertexTypev）
{/*初始条件:
图G存在,v是G中某个顶点*/
/*操作结果:
返回v的第一个邻接顶点的序号。
若顶点在G中没有邻接顶点,则返回-1*/
ArcNode*p;
intv1;
v1=LocateVex（G,v）;/*v1为顶点v在图G中的序号*/
p=G.vertices[v1].firstarc;
if（p）
returnp->adjvex;
else
return-1;
}
intNextAdjVex（ALGraphG,VertexTypev,VertexTypew）
{/*初始条件:
图G存在,v是G中某个顶点,w是v的邻接顶点*/
/*操作结果:
返回v的（相对于w的）下一个邻接顶点的序号。
*/
/*若w是v的最后一个邻接点,则返回-1*/
ArcNode*p;
intv1,w1;
v1=LocateVex（G,v）;/*v1为顶点v在图G中的序号*/
w1=LocateVex（G,w）;/*w1为顶点w在图G中的序号*/
p=G.vertices[v1].firstarc;
while（p&&p->adjvex!
=w1）/*指针p不空且所指表结点不是w*/
p=p->nextarc;
if（!
p||!
p->nextarc）/*没找到w或w是最后一个邻接点*/
return-1;
else/*p->adjvex==w*/
returnp->nextarc->adjvex;/*返回v的（相对于w的）下一个邻接顶点的序号*/
}
voidBFSTraverse（ALGraphG,void（*Visit）（char*））
{/*按广度优先非递归遍历图G。
使用辅助队列Q和访问标志数组visited。
算法7.6*/
intv,u,w;
VertexTypeu1,w1;
LinkQueueQ;
for（v=0;vvisited[v]=FALSE;/*置初
升级会员 