数据结构图实验报告.docx

数据结构图实验报告.docx

《数据结构图实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构图实验报告.docx（13页珍藏版）》请在冰点文库上搜索。

数据结构图实验报告

数据结构教程

上机实验报告

实验七、图算法上机实现

一、实验目的：

1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。

2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接矩阵和邻接表的类型定义。

3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方法及其基本思想。

二、实验容：

1.建立无向图的邻接矩阵

2.图的深度优先搜索

3.图的广度优先搜索

三、实验步骤及结果：

1.建立无向图的邻接矩阵：

1）源代码：

#include"stdio.h"

#include"stdlib.h"

#defineMAXSIZE30

typedefstruct

{

charvertex[MAXSIZE];//顶点为字符型且顶点表的长度小于MAXSIZE

intedges[MAXSIZE][MAXSIZE];//边为整形且edges为邻近矩阵

}MGraph;//MGraph为采用邻近矩阵存储的图类型

voidCreatMGraph（MGraph*g,inte,intn）

{//建立无向图的邻近矩阵g->egdes，n为顶点个数，e为边数

inti,j,k;

printf（"Inputdataofvertexs（0~n-1）:

\n"）;

for（i=0;i

g->vertex[i]=i;//读入顶点信息

for（i=0;i

for（j=0;j

g->edges[i][j]=0;//初始化邻接矩阵

for（k=1;k<=e;k++）//输入e条边

{

printf（"Inputedgesof（i,j）:

"）;

scanf（"%d,%d",&i,&j）;

g->edges[i][j]=1;

g->edges[j][i]=1;

}

}

voidmain（）

{

inti,j,n,e;

MGraph*g;//建立指向采用邻接矩阵存储图类型指针

g=（MGraph*）malloc（sizeof（MGraph））;//生成采用邻接举证存储图类型的存储空间

printf（"InputsizeofMGraph:

"）;//输入邻接矩阵的大小

scanf（"%d",&n）;

printf（"Inputnumberofedge:

"）;//输入邻接矩阵的边数

scanf（"%d",&e）;

CreatMGraph（g,e,n）;//生成存储图的邻接矩阵

printf（"OutputMGraph:

\n"）;//输出存储图的邻接矩阵

for（i=0;i

{

for（j=0;j

printf（"%4d",g->edges[i][j]）;

printf（"\n"）;

}

}

2）运行结果：

2.图的深度优先搜索：

1）源代码：

#include"stdio.h"

#include"stdlib.h"

#defineMAXSIZE30

typedefstructnode//邻接表结点

{

intadjvex;//邻接点域

structnode*next;//指向下一个邻接边结点的指针域

}EdgeNode;//邻接表结点类型

typedefstructvnode//顶点表结点

{

intvertex;//顶点域

EdgeNode*firstedge;//指向邻接表第一个邻接边节点的指针域

}VertexNode;//顶点表结点类型

voidCreatAdjlist（VertexNodeg[],inte,intn）

{//建立无向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点

EdgeNode*p;

inti,j,k;

printf（"Inputdataofvetex（0~n-1）;\n"）;

for（i=0;i

{

g[i].vertex=i;//读入顶点i信息

g[i].firstedge=NULL;//初始化指向顶点i的邻接表表头指针

}

for（k=1;k<=e;k++）//输入e条边

{

printf（"Inputedgeof（i,j）:

"）;

scanf（"%d,%d",&i,&j）;

p=（EdgeNode*）malloc（sizeof（EdgeNode））;

p->adjvex=j;//在顶点vi的邻接表中添加邻接点为j的结点

p->next=g[i].firstedge;//插入是在邻接表表头进行的

g[i].firstedge=p;

p=（EdgeNode*）malloc（sizeof（EdgeNode））;

p->adjvex=i;//在顶点vj的邻接表中添加邻接点为i的结点

p->next=g[j].firstedge;//插入是在邻接表表头进行的

g[j].firstedge=p;

}

}

intvisited[MAXSIZE];//MAXSIZE为大于或等于无向图顶点个数的常量

voidDFS（VertexNodeg[],inti）

{

EdgeNode*p;

printf（"%4d",g[i].vertex）;//输出顶点i信息，即访问顶点i

visited[i]=1;

p=g[i].firstedge;//根据顶点i的指针firstedge查找其邻接表的第一个邻接边结点

while（p!

=NULL）

{

if（!

visited[p->adjvex]）//如果邻接的这个边结点未被访问过

DFS（g,p->adjvex）;//对这个边结点进行深度优先搜索

p=p->next;//查找顶点i的下一个邻接边结点

}

}

voidDFSTraverse（VertexNodeg[],intn）

{//深度优先搜索遍历以邻接表存储的图，其中g为顶点数，n为顶点个数

inti;

for（i=0;i

visited[i]=0;//访问标志置0

for（i=0;i

if（!

visited[i]）//当visited[i]等于0时即顶点i未访问过

DFS（g,i）;//从未访问过的顶点i开始遍历

}

voidmain（）

{

inte,n;

VertexNodeg[MAXSIZE];//定义顶点表结点类型数组g

printf（"Inputnumberofnode:

\n"）;//输入图中节点个数边的个数

scanf（"%d",&n）;

printf（"Inputnumberofedge:

\n"）;//输入图中边的个数

scanf（"%d",&e）;

printf（"Makeadjlist:

\n"）;

CreatAdjlist（g,e,n）;//建立无向图的邻接表

printf（"DFSTraverse:

\n"）;

DFSTraverse（g,n）;//深度优先遍历以邻接表存储的无向图

printf（"\n"）;

}

2）运行结果：

3.图的广度优先搜索：

1）源代码：

#include"stdio.h"

#include"stdlib.h"

#defineMAXSIZE30

typedefstructnode1//邻接表结点

{

intadjvex;//邻接点域

structnode1*next;//指向下一个邻接边结点的指针域

}EdgeNode;//邻接表结点类型

typedefstructvnode//顶点表结点

{

intvertex;//顶点域

EdgeNode*firstedge;//指向邻接表第一个邻接边结点的指针域

}VertexNode;//顶点表结点类型

voidCreatAdjlist（VertexNodeg[],inte,intn）

{//建立无向图的邻接表，n为顶点数，e为边数，g[]存储n个顶点表结点

EdgeNode*p;

inti,j,k;

printf（"Inputdataofvetex（0~n-1）:

\n"）;

for（i=0;i

{

g[i].vertex=i;//读入顶点i信息

g[i].firstedge=NULL;//初始化指向顶点i的邻接表表头指针

}

for（k=1;k<=e;k++）//输入e条边

{

printf（"Inputedgeof（i,j）:

"）;

scanf（"%d,%d",&i,&j）;

p=（EdgeNode*）malloc（sizeof（EdgeNode））;

p->adjvex=j;//在定点vi的邻接表中添加邻接点为j的结点

p->next=g[i].firstedge;//插入是在邻接表表头进行的

g[i].firstedge=p;

p=（EdgeNode*）malloc（sizeof（EdgeNode））;

p->adjvex=i;//在顶点vj的邻接表中添加邻接点为i的结点

p->next=g[j].firstedge;//插入是在邻接表表头进行的

g[j].firstedge=p;

}

}

typedefstructnode

{

intdata;

structnode*next;

}QNode;//链队列结点的类型

typedefstruct

{

QNode*front,*rear;//将头、尾指针纳入到一个结构体的链队列

}LQueue;//链队列类型

voidInit_LQueue（LQueue**q）//创建一个带头结点的空队列

{

QNode*p;

*q=（LQueue*）malloc（sizeof（LQueue））;//申请带头、尾指针的链队列

p=（QNode*）malloc（sizeof（QNode））;//申请链队列的头结点

p->next=NULL;//头结点的next指针置为空

（*q）->front=p;//队头指针指向头结点

（*q）->rear=p;//队尾指针指向头结点

}

intEmpty_LQueue（LQueue*q）//判队空

{

if（q->front==q->rear）//队为空

return1;

else

return0;

}

voidIn_LQueue（LQueue*q,intx）//入队

{

QNode*p;

p=（QNode*）malloc（sizeof（QNode））;//申请新链队列结点

p->data=x;

p->next=NULL;//新结点作为队尾结点时其next域为空

q->rear->next=p;//将新结点*p链到原队尾结点之后

q->rear=p;//使队尾指针指向新的队尾结点*p

}

voidOut_LQueue（LQueue*q,int*x）//出队

{

QNode*p;

if（Empty_LQueue（q））

printf（"Queueisempty!

\n"）;//对空，出队失败

else

{

p=q->front->next;//指针p指向链队列第一个数据结点（即对头结点）

q->front->next=p->next;//头结点的next指针指向链队列第二个数据结点（即删除第一个数据结点）

*x=p->data;//将删除的对头结点数据经由x返回

free（p）;

if（q->front->next==NULL）//出队后队为空，则置为空队列

q->rear=q->front;

}

}

intvisited[MAXSIZE];//MAXSIZE为大于或等于无向图顶点个数的常量

voidBFS（VertexNodeg[],LQueue*Q,inti）

{//广度优先搜索遍历邻接表存储的图，g为顶点表，Q为队指针，i为第i个顶点

intj,*x=&j;

EdgeNode*p;

printf（"%4d",g[i].vertex）;//输出顶点i信息，即访问顶点i

visited[i]=1;//置顶点i为访问过标志

In_LQueue（Q,i）;//顶点i入队Q

while（!

Empty_LQueue（Q））//当队Q非空时

{

Out_LQueue（Q,x）;//对头顶点出队并送j（暂记为顶点j）

p=g[j].firstedge;//根据顶点j的表头指针查找其邻接表的第一个邻接边结点

while（p!

=NULL）

{

if（!

visited[p->adjvex]）//如果邻接的这个边结点未被访问过

{

printf（"%4d",g[p->adjvex].vertex）;//输出这个邻接边结点的顶点信息

visited[p->adjvex]=1;//置该邻接边结点为访问过标志

In_LQueue（Q,p->adjvex）;//将该邻接边结点送人队Q

}

p=p->next;//在顶点j的邻接表中查找j的下一个邻接边结点

}

}

}

voidmain（）

{

inte,n;

VertexNodeg[MAXSIZE];//定义顶点表结点类型数组g

LQueue*q;

printf（"Inputnumberofnode:

\n"）;//输入图中结点个数

scanf（"%d",&n）;

printf（"Inputnumberofedge:

\n"）;//输入图中边的个数

scanf（"%d",&e）;

printf（"Makeadjlist:

\n"）;

CreatAdjlist（g,e,n）;//建立无向图的邻接表

Init_LQueue（&q）;//队列q初始化

printf（"BFSTraverse:

\n"）;

BFS（g,q,0）;//广度优先遍历以邻接表存储的无向图

printf（"\n"）;

}

2）运行结果：

三、实验总结：

1．通过本次试验让我对图的遍历以及图的深度和广度优先搜索有了更深刻的记忆和理解，将课本理论的知识得以实践。

2.此次试验在书中已经对它的各个运算有了分析和讲解，结合

课本与实验让我理解了图的各个概念与重点知识点。