云南大学软件学院报告.docx
《云南大学软件学院报告.docx》由会员分享，可在线阅读，更多相关《云南大学软件学院报告.docx（29页珍藏版）》请在冰点文库上搜索。
云南大学软件学院报告
云南大学软件学院实验报告
课程：
数据结构实验学期：
2014-2015学年第一学期任课教师：
专业：
信息安全学号：
姓名：
成绩：
实验5图基础实验
一、实验目的
1.掌握图的存储结构及其遍历。
二、实验软硬件环境（CPU、OS、IDE）：
三、实验任务（要求写出核心代码，并对运行结果截图）
1）使用邻接矩阵和邻接表储表示分别实现如下给定的图1、图2、图3所示图的物理存储结构。
2）在1）所建立的图形存储结构上分别实现深度优先搜索遍历和广度优先搜索遍历，并给出遍历结果（序列）。
实验代码：
#include
#include
#defineMAXVEX20
#defineOK1
#defineERROR0
#defineOVERFLOW-1
#defineINFINITY65535
#defineQueueSize20//队列中最大元素个数
typedefintQElemType;//队列的元素的类型
typedefintVertexType;
typedefintEdgeType;
typedefenum{False,True}Boolean;//Boolean是布尔类型，其值是ture或false
Booleanvisited[MAXVEX];//访问标志的数组。
typedefstruct
{
VertexTypevexs[MAXVEX];
EdgeTypearc[MAXVEX][MAXVEX];
intnumVertexes,numEdges;
}MGraph;//邻接矩阵。
typedefstructEdgeNode//边表结点。
{
intadjvex;
structEdgeNode*next;
}EdgeNode;
typedefstructVertexNode//顶点表结点。
{
intdata;
EdgeNode*firstedge;
}VertexNode,AdjList[MAXVEX];
typedefstruct
{
AdjListadjlist;
intnumVertexes,numEdges;//图中当前顶点数边数。
}GraphAdjList;
typedefstructNode//队列结点。
{
QElemTypedata;
structNode*next;
}Node,*QNode;
typedefstruct//队列的顺序存储结构。
{
QNodefront;
QNoderear;
intcount;
}SqQueue;
intInitqueue（SqQueue*Q）//初始化一个空队列。
{
Q->front=Q->rear=（QNode）malloc（sizeof（Node））;
if（!
Q->front）returnERROR;
else
Q->front->next=NULL;
Q->count=0;
returnOK;
}
intEnQueue（SqQueue*Q,QElemTypee）//若队列未满，则插入新的元素在队尾。
{
if（Q->count==QueueSize）
returnERROR;
else
Q->count++;
QNodep=（QNode）malloc（sizeof（Node））;
if（!
p）exit（OVERFLOW）;
p->data=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
returnOK;
}
intDeQueue（SqQueue*Q,int*e）//取队列队头的元素
{
QNodep;
if（Q->count==0）
returnERROR;
else
p=Q->front->next;
Q->front->next=p->next;
if（Q->rear==p）
Q->rear=Q->front;
*e=p->data;
Q->count--;
free（p）;
returnOK;
}
intQueueEmpty（SqQueue*Q）//队列是否为空的判断。
{
if（Q->front==Q->rear）return1;
elsereturn0;
}
intCreateMGraph（MGraph*G）//创建邻接矩阵。
{
inti,j,k,w,n;
VertexTypea,b;
printf（"输入顶点数和边数（空格隔开、回车结束）：
\n"）;
fflush（stdin）;
scanf（"%d%d",&G->numVertexes,&G->numEdges）;
printf（"输入各个顶点的值（空格隔开、回车结束）：
\n"）;
for（i=0;inumVertexes;i++）
{
getchar（）;
scanf（"%d",&G->vexs[i]）;
}
for（i=0;inumVertexes;i++）
{
for（j=0;jnumVertexes;j++）
{
G->arc[i][j]=0;
}
}
printf（"请选择创建有向图（输入1）还是无向图（输入0）（回车结束）：
"）;
scanf（"%d",&n）;
if（n==0）
{
for（k=0;knumEdges;k++）
{
printf（"请输入第%d条边的顶点序号（空格隔开、回车结束）：
",k+1）;
fflush（stdin）;
scanf（"%d%d",&a,&b）;
for（i=0;a!
=G->vexs[i];i++）;
for（j=0;b!
=G->vexs[j];j++）;
G->arc[i][j]=1;
G->arc[j][i]=1;
}
printf（"\n输出创建的无向图邻接矩阵：
\n\n"）;
printf（""）;
for（i=0;inumVertexes;i++）
{
printf（"%d",i+1）;
}
printf（"\n\n"）;
for（i=0;inumVertexes;i++）
{
printf（"%d",i+1）;
for（j=0;jnumVertexes;j++）
{
if（G->arc[i][j]==1）
printf（"1"）;
else
printf（"0"）;
}
printf（"\n"）;
}
printf（"\n"）;
}
if（n==1）
{
for（k=0;knumEdges;k++）
{
printf（"请输入第%d条边的顶点序号（空格隔开、回车结束）：
",k+1）;
fflush（stdin）;
scanf（"%d%d",&a,&b）;
for（i=0;a!
=G->vexs[i];i++）;
for（j=0;b!
=G->vexs[j];j++）;
G->arc[i][j]=1;
}
printf（"\n输出创建的有向图邻接矩阵：
\n\n"）;
printf（""）;
for（i=0;inumVertexes;i++）
{
printf（"%d",i+1）;
}
printf（"\n\n"）;
for（i=0;inumVertexes;i++）
{
printf（"%d",i+1）;
for（j=0;jnumVertexes;j++）
{
if（G->arc[i][j]==1）
printf（"1"）;
else
printf（"0"）;
}
printf（"\n"）;
}
printf（"\n"）;
}
if（n!
=0&&n!
=1）
{
printf（"\n输入错误！
！
将得到错误结果\n"）;
return0;
}
}
voidDFS（MGraph*G,inti）//邻接矩阵的深度优先遍历算法。
{
intj;
visited[i]=True;
printf（"v%d",G->vexs[i]）;//打印顶点。
for（j=0;jnumVertexes;j++）
{
if（G->arc[i][j]==1&&!
visited[j]）
DFS（G,j）;//对于未访问的邻接顶点使用递归调用。
}
}
voidDFSTraverse（MGraph*G）//邻接矩阵的深度遍历操作。
{
inti;
for（i=0;inumVertexes;i++）
visited[i]=False;
for（i=0;inumVertexes;i++）
{
if（!
visited[i]）
DFS（G,i）;
}
}
voidBFSTraverse（MGraph*G）//邻接矩阵的广度优先遍历。
{
inti,j;
SqQueueQ;
for（i=0;inumVertexes;i++）
visited[i]=False;
Initqueue（&Q）;
for（i=0;inumVertexes;i++）
{
if（!
visited[i]）
{
visited[i]=True;
printf（"v%d",G->vexs[i]）;
EnQueue（&Q,i）;
while（!
QueueEmpty（&Q））
{
DeQueue（&Q,&i）;
for（j=0;jnumVertexes;j++）
{
if（G->arc[i][j]==1&&!
visited[j]）
{
visited[j]=True;
printf（"v%d",G->vexs[j]）;
EnQueue（&Q,j）;
}
}
}
}
}
}
intLocateVex（GraphAdjList*G1,intv）//返回节点v在图中的位置
{
inti;
for（i=1;i<=G1->numVertexes;i++）
{
if（G1->adjlist[i].data==v）
break;
else
continue;
}
if（i<=G1->numVertexes）
returni;
else
return-1;
}
intFirstAdjvex（GraphAdjListG1,intv）//返回G中第v个顶点的第1个邻接点的序号。
如果v无邻接点，返回0。
{
if（G1.adjlist[v].firstedge）
returnG1.adjlist[v].firstedge->adjvex;
elsereturn0;
}
intNextAdjvex（GraphAdjListG1,intv,intw）//返回G中第v个顶点的相对于顶点w的下一个邻接点的序号。
//如果v无相对于顶点w的下一个邻接点，返回0。
{
EdgeNode*p;
intflag=0;
p=G1.adjlist[v].firstedge;
while（p）
{
if（p->adjvex==w）
{
flag=1;
break;
}
p=p->next;
}
if（flag&&p->next）
returnp->next->adjvex;
else
return0;
}
intCreateALGraph（GraphAdjList*G1）//创建邻接表。
{
inti,j,k,n,x,y;
EdgeNode*e,*p,*q;
p=（EdgeNode*）malloc（sizeof（EdgeNode））;
printf（"输入顶点数和边数（空格隔开、回车结束）：
\n"）;
scanf（"%d%d",&G1->numVertexes,&G1->numEdges）;
printf（"输入顶点（空格隔开、回车结束）：
\n"）;
for（i=1;i<=G1->numVertexes;i++）
{
getchar（）;
scanf（"%d",&G1->adjlist[i].data）;
G1->adjlist[i].firstedge=NULL;
}
printf（"请选择创建有向图（输入1）还是无向图（输入0）：
"）;
scanf（"%d",&n）;
if（n==0）
{
for（k=1;k<=G1->numEdges;k++）
{
printf（"请输入第%d条边的顶点序号（空格隔开、回车结束）：
",k）;
fflush（stdin）;
scanf（"%d%d",&x,&y）;
i=LocateVex（G1,x）;
j=LocateVex（G1,y）;
e=（EdgeNode*）malloc（sizeof（EdgeNode））;
e->adjvex=j;
e->next=NULL;
if（!
G1->adjlist[i].firstedge）
{
G1->adjlist[i].firstedge=e->next;;
G1->adjlist[i].firstedge=e;
}
else
{
for（p=G1->adjlist[i].firstedge;p->next;p=p->next）
{
p->next=p->next;
}
p->next=e->next;
p->next=e;
}
e=（EdgeNode*）malloc（sizeof（EdgeNode））;//申请边表结点的一个空间
e->adjvex=i;
e->next=NULL;
if（!
G1->adjlist[j].firstedge）
{
G1->adjlist[j].firstedge=e->next;;
G1->adjlist[j].firstedge=e;
}
else
{
for（p=G1->adjlist[j].firstedge;p->next;p=p->next）
{
p->next=p->next;
}
p->next=e->next;
p->next=e;
}
}
printf（"\n输出创建的无向图的邻接表：
\n\n"）;//输出创建的无向图的邻接表
for（i=1;i<=G1->numVertexes;i++）
{
printf（"v%d",G1->adjlist[i].data）;
q=G1->adjlist[i].firstedge;
while（q）
{
printf（"->v%d",q->adjvex）;
q=q->next;
}
printf（"\n"）;
}
printf（"\n"）;
}
if（n==1）
{
for（k=1;k<=G1->numEdges;k++）
{
printf（"请输入第%d条边的顶点序号（空格隔开、回车结束）：
",k）;
fflush（stdin）;
scanf（"%d%d",&x,&y）;
i=LocateVex（G1,x）;
j=LocateVex（G1,y）;
e=（EdgeNode*）malloc（sizeof（EdgeNode））;
e->adjvex=j;
e->next=NULL;
if（!
G1->adjlist[i].firstedge）
{
G1->adjlist[i].firstedge=e->next;;
G1->adjlist[i].firstedge=e;
}
else
{
for（p=G1->adjlist[i].firstedge;p->next;p=p->next）
{
p->next=p->next;
}
p->next=e->next;
p->next=e;
}
}
printf（"\n输出创建的有向图的邻接表：
\n\n"）;//输出创建的有向图的邻接表。
for（i=1;i<=G1->numVertexes;i++）
{
printf（"v%d",G1->adjlist[i].data）;
q=G1->adjlist[i].firstedge;
while（q）
{
printf（"->v%d",q->adjvex）;
q=q->next;
}
printf（"\n"）;
}
printf（"\n"）;
}
if（n!
=0&&n!
=1）
{
printf（"\n输入错误！
！
将得到错误结果\n"）;
returnERROR;
}
}
voidDFSAdjlist（GraphAdjListG1,inti）//邻接表的深度优先遍历算法。
{
intw;
visited[i]=True;//将该结点置为访问过的状态True。
printf（"v%d",G1.adjlist[i].data）;//打印结点。
for（w=FirstAdjvex（G1,i）;w>=1;w=NextAdjvex（G1,i,w））
{
if（!
visited[w]）
DFSAdjlist（G1,w）;
}
}
voidDFSTraverseAdjlist（GraphAdjListG1）//邻接表的深度优先遍历操作。
{
inti;
for（i=1;i<=G1.numVertexes;i++）
visited[i]=False;//初始化所有结点为未访问过的状态。
for（i=1;i<=G1.numVertexes;i++）
{
if（!
visited[i]）//如果该节点未访问过，则调用DFSAdjlist。
DFSAdjlist（G1,i）;
}
}
voidBFSTraverseAdjlist（GraphAdjListG1）//邻接表的广度优先遍历算法。
{
VertexTypee;
inti,w;
EdgeNode*p;
SqQueueQ;
for（i=1;i<=G1.numVertexes;i++）
visited[i]=False;//将所有结点置为未访问过状态。
Initqueue（&Q）;//队列初始化。
for（i=1;i<=G1.numVertexes;i++）
{
if（!
visited[i]）
{
visited[i]=True;
printf（"v%d",G1.adjlist[i].data）;//打印结点。
EnQueue（&Q,i）;//结点入队列。
while（!
QueueEmpty（&Q））//当队列不为空时。
{
DeQueue（&Q,&i）;//出队列。
for（w=FirstAdjvex（G1,i）;w>=1;w=NextAdjvex（G1,i,w））
if（!
visited[w]）
{
visited[w]=True;
printf（"v%d",G1.adjlist[w].data）;
EnQueue（&Q,w）;
}
}
}
}
}
intmain（）
{
intm;
MGraphG;
GraphAdjListG1;
while（m!
=0）
{
printf（"\n如果你想创建邻接矩阵请输入1，如果你想创建邻接表请输入2，如果你想退出请输入0:
\n"）;
scanf（"%d",&m）;
if（m==1）
{
CreateMGraph（&G）;
printf（"输出邻接矩阵的深度优先遍历的结果：
\n"）;
DFSTraverse（&G）;
printf（"\n输出邻接矩阵的广度优先遍历的结果：
\n"）;
BFSTraverse（&G）;
printf（"\n"）;
}
elseif（m==2）
{
CreateALGraph（&G1）;
printf（"输出邻接表的深度优先遍历的结果：
\n"）;
DFSTraverseAdjlist（G1）;
printf（"\n输出邻接表的广度优先遍历的结果：
\n"）;
BFSTraverseAdjlist（G1）;
printf（"\n"）;
}
}
return0;
}
实验截图：
图一无向图的邻接矩阵和邻接表及其遍历：
图二无向图的邻接矩阵和邻接表及其遍历：
图三有向图的邻接矩阵和邻接表及其遍历：
四、实验总结与收获
●感觉这次的实验比较难一点，用了很多以前学过的东西，也有一些函数需要自己去构造，在实验中就顺便复习了以前学过的队列。
●本次实验其实很早就把大致的框架写出来了，但是很多小细节没有注意到，调试了很久，最后还是在机房找出了问题，在创建邻接表的时候，边表结点没有建好，头结点指向了它的第一个邻接结点，但是头结点的其他邻接结点没有与第一个邻接结点连上，由此造成了后来的遍历总是出现错误，在进行了断点调试之后，找到了问题。
●本次实验还有一个问题就是for循环之后没有中括号，导致会执行下一步
升级会员 