资源描述：
《数据结构与算法实验——图的基本操作.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、.图的基本操作实验报告范文..图的基本操作实验报告实验名称图的基本操作实验目的1.掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表的存储结构；2.遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历的算法，复习栈和队列的应用；3.掌握以邻接矩阵作为存储结构的生成图的最小生成树的普利姆算法；实验内容编制一个演示图的邻接表的创建、深度遍历、广度遍历操作的程序。问题描述用数据结构相关知识，实现邻接表的定义和操作。该程序包括图的邻接表的结点类型定义以及对图操作的具体的函数定义（包括：建立图的邻接表、深度优先遍历图、广度优先
2、遍历图）。问题分析该实验是基于C语言和数据结构知识基础的对图的基本操作的检验，无需设计复杂的算法，程序语句也相对简单。因此，我直接按要求定义了对图操作的具体函数，并于主函数中实现对应的功能调用。范文..实验步骤1．需求分析 本演示程序用VC++编写，完成图的邻接表的生成、遍历基本操作。 ①输入的形式和输入值的范围：在输入邻接表顶点信息前，必须先确定该信息能正确创建邻接表。 ② 输出的形式：在所有三种操作中都显示操作是否正确以及操作后图的内容。 ③ 程序所能达到的功能：完成图的邻接表的生成、深度优先遍历、广度优先遍历基本操作。 ④ 测
3、试数据：创建操作中依次输入7,7作为顶点数和边数，以（0,1）（0,2）（1,3）（1,5）（3,4）（3,6）（4,5）作为各顶点信息生成一个邻接表。 2．概要设计 1）为了实现上述程序功能，需要定义二叉树的抽象数据类型： ADT Graph { 数据对象：顶点的有穷非空集合和边的集合数据关系：结点具有相同的数据类型及层次结构 基本操作： VoidInitGraph(ALGraph*G) 初始条件：无 操作结果：初始化图 VoidDFSTraverse(ALGraph*G) 初始条件：图Graph已存在
4、范文.. 操作结果：按深度优先遍历图的邻接表VoidBFSTraverse(ALGraph*G) 初始条件：图Graph已存在 操作结果：按广度优先遍历图的邻接表2）本程序包含7个函数： ①主函数main() ② 建立一个图的邻接表函数CreateGraphAL() ③深度优先遍历图DFS()④广度优先遍历BFS()函数说明#include#include#defineMaxVertexNum100#defineQueueSize30typedefenum{FALSE,TRUE
5、}Boolean;Booleanvisited[MaxVertexNum];typedefcharVertexType;typedefintEdgeType;typedefstructnode//边表结点{intadjvex;//邻接点域structnode*next;//域链//若是要表示边上的权,则应增加一个数据域}EdgeNode;typedefstructvnode//顶点边结点{VertexTypevertex;//顶点域EdgeNode*firstedge;//边表头指针}VertexNode;typedefVertexNo
6、deAdjList[MaxVertexNum];//AdjList是邻接表类型typedefstruct{AdjListadjlist;//邻接表intn,e;//图中当前顶点数和边数}ALGraph;voidCreateGraphAL(ALGraph*G)范文..{inti,j,k;EdgeNode*s;printf("请输入顶点数和边数(输入格式为:顶点数,边数)：");scanf("%d,%d",&(G->n),&(G->e));//读入顶点数和边数printf("请输入顶点信息(输入格式为:顶点号)每个顶点以回车作为
7、结束:");for(i=0;in;i++)//立有n个顶点的顶点表{scanf("%c",&(G->adjlist[i].vertex));//读入顶点信息G->adjlist[i].firstedge=NULL;//点的边表头指针设为空}printf("请输入边的信息(输入格式为:i,j)：");for(k=0;ke;k++)//建立边表{scanf("%d,%d",&i,&j);//读入边的顶点对应序号s=newEdgeNode;//生成新边表结点ss->adjvex=j;//邻接点序号
8、为js->next=G->adjlist[i].firstedge;//将新边表结点s插入到顶点Vi的边表头部G->adjlist[i].firstedge=s;s=newEdgeNode;s->adjve
