文件名称：数据结构实验报告三
文件大小：933KB
文件格式：DOC
更新时间：2015-03-11 11:27:13
数据结构 实验报告
(1) 掌握树、图的抽象数据类型的特征。 (2) 掌握树和图的抽象数据类型在计算机中的实现方法。 (3) 学会使用树和图结构解决一些设计问题。 描述你在进行实现时，主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明你设计的巧妙之处。 主要函数及算法： void CreatGraph(VNode A[MAX]);//创建邻接表 void DFS(VNode A[MAX]);//实现深度优先搜索 内部算法：确定起始顶点 v 后, 由 v 出发, 访问它的任一邻接顶点 w1; 再从 w1 出发,访问与 w1邻接但还没有访问过的顶点 w2; 然后再从 w2 出发, 进行类似的访问, 如此进行下去, 直至到达所有的邻接顶点都被访问过的顶点 u 为止。接着, 退回一步, 退到前一次刚访问过的顶点, 看是否还有其它没有被访问的邻接顶点。如果有, 则访问此顶点, 之后再从此顶点出发, 进行与前述类似的访问; 如果没有, 就再退回一步进行查找。 void BFS(VNode A[MAX]);//实现广度优先搜索 内部算法：在访问了起始顶点 v 之后, 由 v 出发, 依次访问 v 的各个未被访问过的邻接顶点 w1, w2, …, wt, 然后再顺序访问 w1, w2, …, wt 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，… 如此做下去，直到图中所有顶点都被访问到为止。