数据结构图实验报告

1、数据结构教程计算机实验报告实验7。图形算法在计算机上的实现一、实验目的：1.理解知名图形的定义和基本术语，掌握图形的几种存储结构。2.掌握邻接矩阵和邻接表的定义和特点，通过实例分析掌握邻接矩阵和邻接表的类型定义。3.掌握图遍历的定义、复杂性分析和应用，掌握图遍历方法及其基本思想。二、实验内容：1.建立无向图的邻接矩阵2.图形的深度优先搜索3.图的广度优先搜索Iii .实验步骤和结果：1.建立无向图的邻接矩阵；1)源代码：#包括“stdio.h”#包括 stdlib.h #定义MAXSIZE 30typedef结构char顶点MAXSIZE；/顶点是字符类型，顶点表的长度小于最大尺寸int ed

2、gesMAXSIZEMAXSIZE；/边是成形的，边是相邻的矩阵 MGraph/MGraph是由相邻矩阵存储的图形类型void CreatGraph(MgRaph * g，int e，int n)/建立无向图的邻接矩阵g-egdes，其中N是顶点数，E是边数I，j，k；printf( vertex的输入数据(0 n-1): n )；对于(I=0；I vertexI=I；/读入顶点信息对于(I=0；IED gesIj=0；/初始化邻接矩阵对于(k=1；k=e。K )/输入E边printf(“(I，j):”的输入边)；scanf(%d，%d ，I，j)；g边Ij=1；g边jI=1；void mai

3、n()I，j，n，e；g。/建立一个指向邻接矩阵存储的图形类型的指针g=(MgRaph *)malloc(sizeof(MgRaph)；/生成相邻证明存储图类型的存储空间printf(“图形：的输入大小”)；/输入邻接矩阵的大小scanf(“% d”，n)；printf(“输入边数：”)；/输入邻接矩阵的边数scanf(“% d”，e)；创建图形(g，e，n)；/生成存储图的邻接矩阵printf(“输出图形： n”)；/输出存储图的邻接矩阵对于(I=0；IED gesIj)；printf( n )；2)运行结果：2.图形的深度优先搜索：1)源代码：#包括“stdio.h”#包括 stdlib.

4、h #定义MAXSIZE 30Typedef结构节点/相邻表节点int adjvex/邻近点字段结构节点*下一步；/指向下一个相邻边缘节点的指针字段边缘节点；/相邻表的节点类型Typedef结构vnode/顶点表节点int顶点；/顶点字段EdgeNode * firstedge/指向相邻表的第一个相邻边缘节点的指针字段顶点节点；/顶点表的节点类型void CreatAdjlist(顶点g，点e，点n)/创建无向图的邻接表，其中N是顶点数，E是边数，g存储N个顶点表节点edge node * p；I，j，k；printf( vetex的输入数据(0 n-1)； n )；对于(I=0；iadjve

5、x=j；/在顶点vi的邻接表中添加带有相邻点j的节点p-next=gi。firstedge/插入是在相邻的表头执行的gi。first edge=p；p=(EdgeNode *)malloc(size of(EdgeNode)；p-adj vex=I；/在顶点vj的邻接表中添加具有相邻点I的节点p-next=gj。firstedge/插入是在相邻的表头执行的gj。first edge=p；int已访问MAXSIZE；/MAXSIZE是一个大于或等于无向图顶点数的常数void DFS(顶点g，点I)edge node * p；printf(M ，gi。顶点)；/输出顶点一信息，即访问顶点一访问次数

6、I=1；p=gi。firstedge/根据顶点I的指针第一条边，找到其邻表的第一个邻边节点同时(p！=空)如果(！已访问p-调整)/如果没有访问过相邻的边缘节点，外勤部(g，p-adj vex)；/对该边缘节点进行深度优先搜索p=p-下一个；/找到顶点1的下一个相邻边节点void DFSTraverse(VertexNode g，int n)/深度优先搜索遍历存储在邻接表中的图，其中G是顶点数，N是顶点数int I；对于(I=0；iadjvex=j；/在固定点vi的邻接表中添加带有邻接点j的节点p-next=gi。firstedge/插入是在相邻的表头执行的gi。first edge=p；p=

7、(EdgeNode *)malloc(size of(EdgeNode)；p-adj vex=I；/在顶点vj的邻接表中添加具有相邻点I的节点p-next=gj。firstedge/插入是在相邻的表头执行的gj。first edge=p；typedef结构节点int数据；结构节点*下一步； QNode/链队列节点的类型typedef结构QNode *前，*后；/将头指针和尾指针放入结构的链队列中 LQueue/链队列类型空初始化_ lxue(lxue * * q)/用头节点创建一个空队列QNode *p。* q=(Lqueue *)malloc(sizeof(Lqueue)；/应用带有前导指针

8、和尾随指针的链队列p=(Qnode *)malloc(sizeof(Qnode)；/应用程序链队列的头节点p-next=空；/头节点的下一个指针被设置为空(* q)-前端=p；/团队领导指针指向头节点(* q)-后部=p。/尾部指针指向头部节点intempty _ lxue(lxue * q)/判断团队为空团队如果(q-前端=q-后端)/为空返回1；其他返回0；空in _ lxue(lxue * q，int x)/加入团队QNode *p。p=(Qnode *)malloc(sizeof(Qnode)；/申请新的链队列节点p-数据=x；p-next=空；/当新节点用作队列尾节点时，其下一个字段

9、为空q-后-下一个=p；/将新节点*p链接到原始团队的末端节点q-后=p；/使尾部指针指向新的尾部节点*p清空_ lxue(lxue * q，int * x)/离开团队QNode *p。if(空_LQueue(q)printf(队列为空！ n )；/空，离开团队失败其他p=q-前-后；/指针P指向链队列的第一个数据节点(即头节点)q-front-next=p-next；/头节点的下一个指针指向链队列的第二个数据节点(即删除第一个数据节点)* x=p-数据；/通过x返回删除的头节点数据免费(p)；如果(q-front-next=NULL) /如果队列在离开队列后为空，它将被设置为空队列q-后=q

10、-前；int已访问MAXSIZE；/MAXSIZE是一个大于或等于无向图顶点数的常数void BFS(顶点g，LQueue *Q，int i)/广度优先搜索遍历邻接表中存储的图，其中g是顶点表，q是团队指针，I是第I个顶点int j，* x=j；edge node * p；printf(M ，gi。顶点)；/输出顶点一信息，即访问顶点一访问次数I=1；/将顶点I设置为访问标志队列中(Q，I)；/顶点1加入团队q同时(！当队列q不为空时，输出队列(Q，x)；/出列在头的顶部并发送J(暂时指定为顶部J)p=gj。firstedge/根据顶点J的头指针找到其相邻表的第一个相邻边节点同时(p！=空)如果(！已访问p-调整)/如果没有