数据结构C语言描述第8章

第8章 查找 第第8章 查找章 查找 8 1 查找的基本概念查找的基本概念 8 2 基于线性表的查找法基于线性表的查找法 8 3 基于树的查找法基于树的查找法 8 4 计算式查找法计算式查找法 哈希法哈希法 第8章 查找 8 1 查找的基本概念查找的基本概念 列表 列表 由同一类型的数据元素 或记录 构成的集合 可利用任意数据结构实现 关键字 关键字 数据元素的某个数据项的值 用它可以标识列表 中的一个或一组数据元素 如果一个关键字可以唯一标识列表 中的一个数据元素 则称其为主关键字 否则为次关键字 当数据元素仅有一个数据项时 数据元素的值就是关键字 第8章 查找 查找 查找 根据给定的关键字值 在特定的列表中确定一个 其关键字与给定值相同的数据元素 并返回该数据元素在列表 中的位置 若找到相应的数据元素 则称查找是成功的 否 则称查找是失败的 此时应返回空地址及失败信息 并可根据 要求插入这个不存在的数据元素 显然 查找算法中涉及到三 类参量 查找对象K 找什么 查找范围L 在哪 找 K在L中的位置 查找的结果 其中 为输入 参量 为输出参量 在函数中 输入参量必不可少 输出 参量也可用函数返回值表示 第8章 查找 平均查找长度 平均查找长度 为确定数据元素在列表中的位置 需和给 定值进行比较的关键字个数的期望值 称为查找算法在查找成 功时的平均查找长度 对于长度为n的列表 查找成功时的平 均查找长度为 n i iinn CPCPCPCPASL 1 2211 其中Pi为查找列表中第i个数据元素的概率 Ci为找到列表中第 i个数据元素时 已经进行过的关键字比较次数 由于查找算 法的基本运算是关键字之间的比较操作 所以可用平均查找长 度来衡量查找算法的性能 第8章 查找 查找的基本方法查找的基本方法可以分为两大类 即比较式查找法比较式查找法和计 算式查找法 计 算式查找法 其中比较式查找法比较式查找法又可以分为基于线性表的查 找法 基于线性表的查 找法和基于树的查找法基于树的查找法 而计算式查找法计算式查找法也称为HASH 哈 希 查找法 哈 希 查找法 第8章 查找 8 2 基于线性表的查找法基于线性表的查找法 8 2 1 顺序查找法 顺序查找法 顺序查找法的特点是 用所给关键字与线性表中各元素的 关键字逐个比较 直到成功或失败 存储结构通常为顺序结 构 也可为链式结构 下面给出顺序结构有关数据类型的定 义 define LIST SIZE 20 typedef struct KeyType key 第8章 查找 OtherType other data RecordType typedef struct RecordType r LIST SIZE 1 r 0 为工作单元 int length RecordList 第8章 查找 基于顺序结构的算法如下 int SeqSearch RecordList l KeyType k 在顺序表l中顺序查找其关键字等于k的元素 若找到 则函数值为该元 素在表中的位置 否则为0 l r 0 key k i l length while l r i key KG 2 k i return i 第8章 查找 算法 算法8 1 设置监视哨的顺序查找法 设置监视哨的顺序查找法 其中l r 0 称为监视哨 可以起到防止越界的作用 不用监视 哨的算法如下 int SeqSearch RecordList l KeyType k 不用监视哨法 在顺序表中查找关键字等于k的元素 l r 0 key k i l length while i 1 if i 1 return i else return 0 第8章 查找 算法 算法8 2 不设置监视哨的顺序查找法 不设置监视哨的顺序查找法 其中 循环条件 i 1 判断查找是否越界 利用监视哨可省去 这个条件 从而提高查找效率 下面用平均查找长度来分析一下顺序查找算法的性能 假 设列表长度为n 那么查找第i个数据元素时需进行n i 1次比 较 即Ci n i 1 又假设查找每个数据元素的概率相等 即 Pi 1 n 则顺序查找算法的平均查找长度为 n i n i i n i ii nin n C n CPASL 111 1 2 1 1 11 第8章 查找 8 2 2 折半查找法折半查找法 折半查找法又称为二分法查找法 这种方法要求待查找的 列表必须是按关键字大小有序排列的顺序表 其基本过程是 将表中间位置记录的关键字与查找关键字比较 如果两者相 等 则查找成功 否则利用中间位置记录将表分成前 后两个 子表 如果中间位置记录的关键字大于查找关键字 则进一 步查找前一子表 否则进一步查找后一子表 重复以上过程 直到找到满足条件的记录 使查找成功 或直到子表不存在为 止 此时查找不成功 图8 1给出了用折半查找法查找12 50 的具体过程 其中mid low high 2 当high low时 表示不 存在这样的子表空间 查找失败 第8章 查找 612151822252835465860 1234567891011 low 1mid 6high 11 612151822252835465860 1234567891011 low 1mid 3high 5 612151822252835465860 1234567891011 low 1 mid 1 high 2 612151822252835465860 1234567891011 low 2 mid 2 high 2 a 用折半查找法查找12的过程 612151822252835465860 1234567891011 low 1mid 6high 11 612151822252835465860 1234567891011 low 7mid 9high 11 612151822252835465860 1234567891011 low 10 mid 10 high 11 612151822252835465860 1234567891011 low 10high 9 b 用折半查找法查找50的过程 图8 1 折半查找示意 第8章 查找 折半查找的算法如下 int BinSrch SqList l KeyType k 在有序表l中折半查找其关键字等于k的元素 若找到 则函数值为该元 素在表中的位置 low 1 high l length 置区间初值 while low high 第8章 查找 mid low high 2 if k l r mid key return mid 找到待查元 素 else if k key key s lchild NULL s rchild NULL bst s else if key key InsertBST 将s插入左子树 else if key bst key InsertBST 将s插入右子树 第8章 查找 算法 算法8 4 二叉排序树的插入 二叉排序树的插入 假若给定一个元素序列 我们可以利用上述算法创建一 棵二叉排序树 首先 将二叉排序树初始化为一棵空树 然 后逐个读入元素 每读入一个元素 就建立一个新的结点并 插入到当前已生成的二叉排序树中 即调用上述二叉排序树 的插入算法将新结点插入 生成二叉排序树的算法如下 void CreateBST BSTree bst 从键盘输入元素的值 创建相应的二叉排序树 KeyType key bst NULL scanf d while key KG 2 ENDKEY ENDKEY为自定义常数 InsertBST bst key scanf d 第8章 查找 算法 算法8 5 创建二叉排序树 图 创建二叉排序树 图8 4 二叉排序树的建立过程二叉排序树的建立过程 902812 2453 45 g 插入90 2812 2453 45 f 插入28 12 2453 45 e 插入12 2453 45 d 插入53 24 45 c 插入24 45 b 插入45 a 空树 第8章 查找 图8 5 输入顺序不同所建立的不同二叉排序树 9028 45 1253 24 第8章 查找 2 二叉排序树的删除 二叉排序树的删除 从二叉排序树中删除一个结点 不能把以该结点为根的 子树都删去 只能删掉该结点 并且还应保证删除后所得 的二叉树仍然满足二叉排序树的性质不变 也就是说 在二 叉排序树中删去一个结点相当于删去有序序列中的一个结点 删除操作首先要查找 已确定被删结点是否在二叉排序 树中 若不在 则不做任何操作 否则 假设要删除的结 点为p 结点p的双亲结点为f 并假设结点p是结点f的左孩 子 右孩子的情况类似 第8章 查找 下面分三种情况讨论 1 若 p 为 叶 子 结 点 则 可 直 接 将 其 删 除 f lchild NULL free p 2 若p结点只有左子树 或只有右子树 则可将p的左 子树或右子树直接改为其双亲结点f的左子树 即 f lchild p lchild 或f lchild p rchild free p 3 若p既有左子树 又有右子树 如图8 6 a 所示 此时有两种处理方法 第8章 查找f PLPR P F f p a P的左右子树均不空 QLSL C F f p d 将原P结点的值改为S结点的值 删除原 S结点并将原S的左子树改为Q的右子树 Q q CL S PR c SLPR C f c 将P的左子树改为F的左子树 将P的 右子树改为S的右子树 S CL F c QL SL C F p Q q CL P PR c S s b S为P的直接前驱 图图8 6 二叉排二叉排序树删除序树删除示意示意 第8章 查找 方法方法1 首先找到p结点在中序序列中的直接前驱s结点 如图8 6 b 所示 然后将p的左子树改为f的左子树 而将p的 右子树改为s的右子树 f lchild p lchild s rchild p rchild free p 结果如图8 6 c 所示 方法方法2 首先找到p结点在中序序列中的直接前驱s结 点 如图8 6 b 所示 然后用s结点的值替代p结点的值 再 将s结点删除 原s结点的左子树改为s的双亲结点q的右子树 p data s data q rchild s lchild free s 结果如图8 6 d 所示 第8章 查找 综上所述 可以得到下面的在二叉排序树中删去一个结点的算法 BSTNode DelBST BSTree t KeyType k 在二叉排序树t中删去关键字为k的结点 BSTNode p f s q p t f NULL while p 查找关键字为k的待删结点p if p key k break 找到 则跳出查找循环 f p f指向p结点的双亲结点 if p key k p p lchild else p p rchild if p NULL return t 若找不到 返回原来的二叉排序树 if p lchild NULL p无左子树 if f NULL t p rchild p是原二叉排序树的根 第8章 查找 else if f lchild p p是f的左孩子 f lchild p rchild 将p的右子树链到f的左链上 else p是f的右孩子 f rchild p rchild 将p的右子树链到f的右链上 free p 释放被删除的结点p else p有左子树 q p s p lchild while s rchild 在p的左子树中查找最右下结点 q s s s rchild if q p q lchild s lchild 将s的左子树链到q上 else q rchild s lchild p key s key 将s的值赋给p free s return t DelBST 第8章 查找 算法 算法8 6 在二叉排序树中删除结点 在二叉排序树中删除结点 3 二叉排序树的查找 二叉排序树的查找 因为二叉排序树可看作是一个有序表 所以在二叉排 序树上进