数据结构图实验报告.docx

1、数据结构图实验报告数据结构教程上机实验报告实验七、 图算法上机实现一、 实验目的：1. 了解熟知图的定义和图的基本术语，掌握图的几种存储结构。2. 掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接矩阵和邻接表的类型定义。3. 掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方法及其基本思想。二、 实验内容：1. 建立无向图的邻接矩阵2. 图的深度优先搜索3. 图的广度优先搜索三、实验步骤及结果：1. 建立无向图的邻接矩阵：1) 源代码：#include stdio.h#include stdlib.h#define MAXSIZE 30typedef struct char vert

2、exMAXSIZE;/顶点为字符型且顶点表的长度小于MAXSIZE int edgesMAXSIZEMAXSIZE;/边为整形且edges为邻近矩阵MGraph;/MGraph为采用邻近矩阵存储的图类型void CreatMGraph(MGraph *g,int e,int n)/建立无向图的邻近矩阵g-egdes，n为顶点个数，e为边数 int i,j,k; printf(Input data of vertexs(0n-1):n); for(i=0;ivertexi=i; /读入顶点信息 for(i=0;in;i+) for(j=0;jedgesij=0; /初始化邻接矩阵 for(k=1

3、;kedgesij=1; g-edgesji=1; void main() int i,j,n,e; MGraph *g; /建立指向采用邻接矩阵存储图类型指针 g=(MGraph*)malloc(sizeof(MGraph);/生成采用邻接举证存储图类型的存储空间 printf(Input size of MGraph:); /输入邻接矩阵的大小 scanf(%d,&n); printf(Input number of edge:); /输入邻接矩阵的边数 scanf(%d,&e); CreatMGraph(g,e,n); /生成存储图的邻接矩阵 printf(Output MGraph:n

4、);/输出存储图的邻接矩阵 for(i=0;in;i+) for(j=0;jedgesij); printf(n); 2) 运行结果：2. 图的深度优先搜索：1) 源代码：#include stdio.h#include stdlib.h#define MAXSIZE 30typedef struct node/邻接表结点 int adjvex;/邻接点域 struct node *next;/指向下一个邻接边结点的指针域EdgeNode; /邻接表结点类型typedef struct vnode/顶点表结点 int vertex;/顶点域 EdgeNode *firstedge; /指向邻接

5、表第一个邻接边节点的指针域VertexNode;/顶点表结点类型void CreatAdjlist(VertexNode g,int e,int n)/建立无向图的邻接表，n为顶点数，e为边数，g存储n个顶点表结点 EdgeNode *p; int i,j,k; printf(Input data of vetex(0n-1);n); for(i=0;in;i+)/建立有n个顶点的顶点表 gi.vertex=i; /读入顶点i信息 gi.firstedge=NULL; /初始化指向顶点i的邻接表表头指针 for (k=1;kadjvex=j; /在顶点vi的邻接表中添加邻接点为j的结点 p-n

6、ext=gi.firstedge; /插入是在邻接表表头进行的 gi.firstedge=p; p=(EdgeNode*)malloc(sizeof(EdgeNode); p-adjvex=i; /在顶点vj的邻接表中添加邻接点为i的结点 p-next=gj.firstedge; /插入是在邻接表表头进行的 gj.firstedge=p; int visitedMAXSIZE; /MAXSIZE为大于或等于无向图顶点个数的常量void DFS(VertexNode g,int i) EdgeNode *p; printf(%4d,gi.vertex); /输出顶点i信息，即访问顶点i visi

7、tedi=1; p=gi.firstedge; /根据顶点i的指针firstedge查找其邻接表的第一个邻接边结点 while(p!=NULL) if(!visitedp-adjvex) /如果邻接的这个边结点未被访问过 DFS(g,p-adjvex); /对这个边结点进行深度优先搜索 p=p-next; /查找顶点i的下一个邻接边结点 void DFSTraverse(VertexNode g,int n)/深度优先搜索遍历以邻接表存储的图，其中g为顶点数，n为顶点个数 int i; for(i=0;in;i+) visitedi=0; /访问标志置0 for(i=0;in;i+)/对n个顶

8、点的图查找未访问过的顶点并由该顶点开始遍历 if(!visitedi) /当visitedi等于0时即顶点i未访问过 DFS(g,i); /从未访问过的顶点i开始遍历void main() int e,n; VertexNode gMAXSIZE; /定义顶点表结点类型数组g printf(Input number of node:n);/输入图中节点个数边的个数 scanf(%d,&n); printf(Input number of edge:n);/输入图中边的个数 scanf(%d,&e); printf(Make adjlist:n); CreatAdjlist(g,e,n); /建

9、立无向图的邻接表 printf(DFSTraverse:n); DFSTraverse(g,n); /深度优先遍历以邻接表存储的无向图 printf(n);2) 运行结果：3. 图的广度优先搜索：1) 源代码：#include stdio.h#include stdlib.h#define MAXSIZE 30typedef struct node1/邻接表结点 int adjvex; /邻接点域 struct node1 *next;/指向下一个邻接边结点的指针域EdgeNode; /邻接表结点类型typedef struct vnode/顶点表结点 int vertex;/顶点域 Edge

10、Node *firstedge; /指向邻接表第一个邻接边结点的指针域VertexNode; /顶点表结点类型void CreatAdjlist(VertexNode g,int e,int n) /建立无向图的邻接表，n为顶点数，e为边数，g存储n个顶点表结点 EdgeNode *p; int i,j,k; printf(Input data of vetex(0n-1):n); for(i=0;in;i+) /建立有n个顶点的顶点表 gi.vertex=i; /读入顶点i信息 gi.firstedge=NULL; /初始化指向顶点i的邻接表表头指针 for(k=1;kadjvex=j;/在

11、定点vi的邻接表中添加邻接点为j的结点 p-next=gi.firstedge;/插入是在邻接表表头进行的 gi.firstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode); p-adjvex=i; /在顶点vj的邻接表中添加邻接点为i的结点 p-next=gj.firstedge; /插入是在邻接表表头进行的 gj.firstedge=p; typedef struct node int data; struct node *next;QNode; /链队列结点的类型typedef struct QNode *front,*rear; /将头、尾指针

12、纳入到一个结构体的链队列LQueue; /链队列类型void Init_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; /队尾指针指向头结点int Empty_LQueue(LQueue *q) /判队空 if(q-front=q-rear) /

13、队为空 return 1; else return 0;void In_LQueue(LQueue *q,int x) /入队 QNode *p; p=(QNode *)malloc(sizeof(QNode); /申请新链队列结点 p-data=x; p-next=NULL; /新结点作为队尾结点时其next 域为空 q-rear-next=p; /将新结点*p链到原队尾结点之后 q-rear=p; /使队尾指针指向新的队尾结点*pvoid Out_LQueue(LQueue *q,int *x) /出队 QNode *p; if(Empty_LQueue(q) printf(Queue i

14、s empty!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; int visitedMAXSIZE; /MAXSIZE为大于或等于无向图顶点个数的常量void BFS(VertexNode g,LQueue *Q,int i) /广度优先搜

15、索遍历邻接表存储的图，g为顶点表，Q为队指针，i为第i个顶点 int j,*x=&j; EdgeNode *p; printf(%4d,gi.vertex); /输出顶点i信息，即访问顶点i visitedi=1; /置顶点i为访问过标志 In_LQueue(Q,i); /顶点i入队Q while(!Empty_LQueue(Q) /当队Q非空时 Out_LQueue(Q,x); /对头顶点出队并送j（暂记为顶点j） p=gj.firstedge;/根据顶点j的表头指针查找其邻接表的第一个邻接边结点 while(p!=NULL) if(!visitedp-adjvex)/如果邻接的这个边结点未

16、被访问过 printf(%4d,gp-adjvex.vertex); /输出这个邻接边结点的顶点信息 visitedp-adjvex=1; /置该邻接边结点为访问过标志 In_LQueue(Q,p-adjvex); /将该邻接边结点送人队Q p=p-next;/在顶点j的邻接表中查找j的下一个邻接边结点 void main() int e,n; VertexNode gMAXSIZE;/定义顶点表结点类型数组g LQueue *q; printf(Input number of node:n); /输入图中结点个数 scanf(%d,&n); printf(Input number of edge:n);/输入图中边的个数 scanf(%d,&e); printf(Make adjlist:n ); CreatAdjlist(g,e,n);/建立无向图的邻接表 Init_LQueue(&q);/队列q初始化 printf(BFSTraverse:n); BFS(g,q,0); /广度优先遍历以邻接表存储的无向图 printf(n);2) 运行结果：三、 实验总结： 1通过本次试验让我对图的遍历以及图的深度和广度优先搜索有了更深刻的记忆和理解，将课本理论的知识得以实践。2. 此次试验在书中已经对它的各个运算有了分析和讲解，结合课本与实验让我理解了图的各个概念与重点知识点。