[工学]数据结构复习1.ppt

一维数组存储方式 ，二维数组存储方式 ，地址的计算。 特殊矩阵 稀疏矩阵， 随机稀疏矩阵的压缩存储方法: 三元组顺序表 行逻辑联接的顺序 十字链表 方法二：快速转置运算 广义表 构造存储结构的两种分析方法: 性质1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 　(i≥1) 性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k≥1） 性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1 性质 4 ： 具有 n 个结点的完全二叉树的深度为 ? log2n? +1 性质 5 ： 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：(1) 若 i=1，则该结点是二叉树的根，无双亲, 　 否则，编号为 ?i/2? 的结点为其双亲结点;(2) 若 2in，则该结点无左孩子， 　否则，编号为 2i 的结点为其左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点， 　否则，编号为2i+1 的结点为其右孩子结点 6.5 线索二叉树 6.6 树和森林的表示方法 6.8 哈 夫 曼 树 与 哈 夫 曼 编 码 最优树的定义 如何构造最优树 前缀编码 二、图的邻接表存储表示 7.6 拓扑排序 7.7 两点之间的最短路径问题 三、索引顺序表 例如 二叉排序树的插入算法 根据动态查找表的定义，“插入”操作在查找不成功时才进行; 二、二叉平衡树 何谓“二叉平衡树”？ 先看一个具体的情况，假设：n=11 分析折半查找的平均查找长度 6 3 9 1 4 2 5 7 8 10 11 判定树 1 2 2 3 3 3 3 4 4 4 4 在n50时，可得近似结果 一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。因此具有n个结点的判定树的深度为? ? +1。为了方便起见，以满二叉树为例，树中层次为1的结点有1个，层次为2的结点有2个，层次为h的结点有2h－1个. 以索引顺序表表示静态查找表，search操作可用分块查找来实现。 分块查找又称索引顺序查找，这是顺序查找的一种改进方法。在此查找方法中，除表本身以外，尚需建立一个“索引表”。 表中含有18个元素，可分成三个子表。对每个子表（或称块）建立一个索引项，其中包括两项内容：关键字项（其值为该子表内的最大关键字）和项指针（指示该子表的第一个元素在表中位置）。 索 引 表 ?  最大关键字 起始地址 ? 13 7 1 86 48 22 53 86 49 74 58 60 48 24 38 44 42 33 20 9 8 13 12 22 索引顺序查找的平均查找长度 = 查找“索引”的平均查找长度 + 查找“顺序表”的平均查找长度 分块查找方法评价 当 时，ASL取最小值 +1 9.2 动 态 查 找 表 一、二叉排序树（二叉查找树） 二、二叉平衡树 三、B - 树 四、B+树 一、二叉排序树 （二叉查找树） 1．定义 2．查找算法 3．插入算法 4．删除算法 5．查找性能的分析 （1）若它的左子树不空，则左子树上 所有结点的值均小于根结点的值； 1．定义： 二叉排序树或者是一棵空树；或者 是具有如下特性的二叉树： （3）它的左、右子树也都分别是二叉 排序树。 （2）若它的右子树不空，则右子树上 所有结点的值均大于根结点的值； （1）若它的左子树不空，则左子树上 所有结点的值均小于根结点的值； 1．定义： 二叉排序树或者是一棵空树；或者 是具有如下特性的二叉树： （3）它的左、右子树也都分别是二叉 排序树。 （2）若它的右子树不空，则右子树上 所有结点的值均大于根结点的值； 从上述查找过程可见， 在查找过程中，生成了一条查找路径: 从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点; 或者 从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。 ——查找成功 ——查找不成功 二叉排序树是一种动态树表，其特点是，树的结构通常不是一次生成的，而是在查找的过程中，当树中不存在关键字等于给定值的结点时进行插入。 新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子