数据结构第五次实验报告.docVIP

题目：图的遍历 学生姓名：杨锦涛 学生学号：201208070122 专业班级：智能1201 指导老师：骆嘉伟老师 完成日期：2014.5.2 需求分析 1、首先输入顶点的数量，然后是各顶点对应的字母，再输入各条弧（权值都置为1）。 2、输出从首个顶点开始的广度优先遍历序列和深度先遍历序列。 3、?设图的顶点大于1个，不超过30个，每个顶点用一个编号表示（如果一个图有n个顶点，则它们的编号分别为0, 1, 2, 3, …, n-1）。 4、求有向图的遍历问题，采用邻接表存储图，实现图的基本操作，并编写DFS和BFS程序。 5、测试数据 ?????? 输入 输入顶点数和弧数:8 9 输入8个顶点. 输入顶点0:a 输入顶点1:b 输入顶点2:c 输入顶点3:d 输入顶点4:e 输入顶点5:f 输入顶点6:g 输入顶点7:h 输入9条弧. 输入弧0:a b 1 输入弧1:b d 1 输入弧2:b e 1 输入弧3:d h 1 输入弧4:e h 1 输入弧5:a c 1 输入弧6:c f 1 输入弧7:c g 1 输入弧8:f g 1 输出 深度优先遍历: a b d h e c f g 广度优先遍历: a b c d e f g h 二、概要设计 抽象数据类型 为实现上述程序的功能，先用邻接表实现储存图的信息，邻接表的表头是一个包含一个字符和下一个结点的指针的结构体，表中其他元素是一个包含一编号和下一结点指针的结构体。最后依次输出深度优先遍历和广度优先遍历的序号。 算法的基本思想 根据题目要求，1把图中顶点和边的信息，存储到邻接表中：建立一个长度为顶点总数的邻接表数组，并在相应位置添加结点。2深度优先遍历或广度优先遍历时，实例化一个下标标示是否被访问到的数组。 3深度优先遍历利用函数的递归调用实现，广度优先遍历利用队列的先进先出实现。 程序的流程 程序由三个模块组成： （1）输入模块：输入顶点数、边数、各个顶点的字母、边的两端的字母 （2）计算模块：如后面的步骤说明所示 （3）输出模块：输出深度优先遍历和广度优先遍历的字母序列！ 三、详细设计 物理数据类型 题目要求输入的数为正整数时使用整型变量来存储；输入字符时，用字符来储存。 输入 输入顶点数和弧数: 输入顶点i： 输入弧i： 输出 广度优先遍历: 深度优先遍历: 程序的基本步骤 1、图的信息利用邻接表来储存的程序流程图如下： 输入顶点数目 输入顶点数目vexnum和边数目arcnum vertices=new vertices=new struct Vlist [vexnum]; int i=0; ivexnum;输入顶点字母vertices[i].data;vertices[i].nextarc=NULL ; ivexnum; 输入顶点字母vertices[i].data; vertices[i].nextarc=NULL ; i++; 是 i=0; i=0; iarcnum; iarcnum; 否 输入边的两个顶点ch1和ch2 输入边的两个顶点ch1和ch2 v1=GetVex(ch1); v2=GetVex(ch2); v1=GetVex(ch1); v2=GetVex(ch2); v1vexnumv2vexnum v1vexnum v2vexnum P=new struct ArcNode;Q=new struct ArcNode;P-vex = v2; Q-vex = v1; i++;P-nextarc=vertices[v1].nextarc;Q-nextarc=vertices[v2].nextarc;vertices[v1].nextarc = P;vertices[v2].nextarc = Q; P=new struct ArcNode; Q=new struct ArcNode; P-vex = v2; Q-vex = v1; i++; P-nextarc=vertices[v1].nextarc; Q-nextarc=vertices[v2].nextarc; vertices[v1].nextarc = P; vertices[v2].nextarc = Q; 图的信息储存完毕 图的信息储存完毕 2、图的深度遍历和广度遍历，用流程图难以表达，所以可参照 图的遍历.cpp代码！ 五、测试结果 输入 输入顶点数和弧数:8 9 输入8个顶点. 输入顶点0:a 输入顶点1:b 输入顶点2:c 输入顶点3: