《数据结构图实验报告.doc》由会员分享，可在线阅读，更多相关《数据结构图实验报告.doc（16页珍藏版）》请在三一办公上搜索。
1、数据结构教程上机实验报告实验七、 图算法上机实现一、 实验目的：1. 了解熟知图的定义和图的基本术语，掌握图的几种存储结构。2. 掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接矩阵和邻接表的类型定义。3. 掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方法及其基本思想。二、 实验内容：1. 建立无向图的邻接矩阵2. 图的深度优先搜索3. 图的广度优先搜索三、实验步骤及结果：1. 建立无向图的邻接矩阵：1) 源代码：#include stdio.h#include stdlib.h#define MAXSIZE 30typedef struct char vertexMAXSIZE
2、;/顶点为字符型且顶点表的长度小于MAXSIZEint 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;kedgesij=1;g-ed
3、gesji=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);/输出存储图的邻接矩阵for(i=0;in;i+)
4、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; /指向邻接表第一个邻接边节点的指针域VertexNode;/顶点表结点类型voi
5、d 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-next=gi.firstedge; /插入是在邻接表表头进行的gi.firstedge
6、=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信息，即访问顶点ivisitedi=1;p=gi.firstedge; /根据顶点i的指针firstedge查找其邻接表的第一个邻
7、接边结点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; /访问标志置0for(i=0;in;i+)/对n个顶点的图查找未访问过的顶点并由该顶点开始遍历if(!visitedi) /当visitedi等于0时即顶点i未访问过DFS(
8、g,i); /从未访问过的顶点i开始遍历void main()int e,n;VertexNode gMAXSIZE; /定义顶点表结点类型数组gprintf(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); /建立无向图的邻接表printf(DFSTraverse:n);DFSTraverse(g,n); /深度优先遍历以邻接表存储的无向图printf
9、(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;/顶点域EdgeNode *firstedge; /指向邻接表第一个邻接边结点的指针域VertexNode; /顶点表结点类型void CreatAdjlist(Verte
10、xNode 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-next=gi.firstedge;/插入是在邻接表表头进行的gi.firstedge=p;p=(EdgeNode *)mall
11、oc(sizeof(EdgeNode);p-adjvex=i; /在顶点vj的邻接表中添加邻接点为i的结点p-next=gj.firstedge; /插入是在邻接表表头进行的 gj.firstedge=p;typedef struct node int data;struct node *next;QNode; /链队列结点的类型typedef structQNode *front,*rear; /将头、尾指针纳入到一个结构体的链队列LQueue; /链队列类型void Init_LQueue(LQueue *q) /创建一个带头结点的空队列QNode *p;*q=(LQueue *)mall
12、oc(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) /队为空return 1;elsereturn 0;void In_LQueue(LQueue *q,int x) /入队QNode *p;p=(QNode *)malloc(sizeof(QNode)
13、; /申请新链队列结点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 is empty!n);/对空，出队失败elsep=q-front-next; /指针p指向链队列第一个数据结点（即对头结点）q-front-next=p-next;/头结点的next指针指向链队列第二个数据结点（即删除第一个
14、数据结点）*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) /广度优先搜索遍历邻接表存储的图，g为顶点表，Q为队指针，i为第i个顶点 int j,*x=&j;EdgeNode *p;printf(%4d,gi.vertex); /输出顶点i信息，即访问顶点ivisitedi=1; /置顶点i为访问过标志In_L
15、Queue(Q,i); /顶点i入队Qwhile(!Empty_LQueue(Q) /当队Q非空时Out_LQueue(Q,x); /对头顶点出队并送j（暂记为顶点j）p=gj.firstedge;/根据顶点j的表头指针查找其邻接表的第一个邻接边结点while(p!=NULL)if(!visitedp-adjvex)/如果邻接的这个边结点未被访问过printf(%4d,gp-adjvex.vertex); /输出这个邻接边结点的顶点信息visitedp-adjvex=1; /置该邻接边结点为访问过标志In_LQueue(Q,p-adjvex); /将该邻接边结点送人队Qp=p-next;/在顶
16、点j的邻接表中查找j的下一个邻接边结点void main()int e,n;VertexNode gMAXSIZE;/定义顶点表结点类型数组gLQueue *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. 此次试验在书中已经对它的各个运算有了分析和讲解，结合课本与实验让我理解了图的各个概念与重点知识点。
