数据结构-王红梅-第7章 查找技术

数据结构（C+版）第2版清华大学出版社第 7 章 查 找 技 术本 章 的 主 要 内 容 是 :查 找 的 基 本 概 念线 性 表 的 查 找 技 术树 表 的 查 找 技 术散 列 表 的 查 找 技 术 数据结构（C+版）第2版清华大学出版社查 找 的 基 本 概 念p 关 键 码 ： 可 以 标 识 一 个 记 录 的 某 个 数 据 项 。 p 键 值 ： 关 键 码 的 值 。p 主 关 键 码 ： 可 以 唯 一 地 标 识 一 个 记 录 的 关 键 码 。p 次 关 键 码 ： 不 能 唯 一 地 标 识 一 个 记 录 的 关 键 码 。7.1 概 述 50女李 爽0005 25女齐 梅0004 47女刘 楠0003 25男张 亮0002 38男王 刚0001 年 龄性 别姓 名职 工 号 1972.92003.71979.92003.71990.4工 作 时 间 数据结构（C+版）第2版清华大学出版社查 找 的 基 本 概 念p 查 找 ： 在 具 有 相 同 类 型 的 记 录 构 成 的 集 合 中 找 出满 足 给 定 条 件 的 记 录 。 p 给定的查找条件可能是多种多样的，为便于讨论，把查找条件限制为“匹配”，即查找关键码等于给定值的记录。 7.1 概 述p 查 找 的 结 果 ： 若 在 查 找 集 合 中 找 到 了 与 给 定 值 相匹 配 的 记 录 ， 则 称 查 找 成 功 ； 否 则 ， 称 查 找 失 败 。 数据结构（C+版）第2版清华大学出版社p 静 态 查 找 ： 不 涉 及 插 入 和 删 除 操 作 的 查 找 。p 动 态 查 找 ： 涉 及 插 入 和 删 除 操 作 的 查 找 。 7.1 概 述查 找 的 基 本 概 念静 态 查 找 适 用 于 ： 查 找 集 合 一 经 生 成 ， 便 只 对 其 进 行查 找 ， 而 不 进 行 插 入 和 删 除 操 作 ， 或 经 过 一 段 时 间 的查 找 之 后 ， 集 中 地 进 行 插 入 和 删 除 等 修 改 操 作 ；动 态 查 找 适 用 于 ： 查 找 与 插 入 和 删 除 操 作 在 同 一 个 阶段 进 行 ， 例 如 当 查 找 成 功 时 ， 要 删 除 查 找 到 的 记 录 ，当 查 找 不 成 功 时 ， 要 插 入 被 查 找 的 记 录 。 数据结构（C+版）第2版清华大学出版社7.1 概 述查 找 的 基 本 概 念查 找 结 构 ： 面 向 查 找 操 作 的 数 据 结 构 ， 即 查 找 基 于 的数 据 结 构 。查 找 结 构 查 找 方 法 集 合 中 元 素 之 间 不 存 在 明 显 的 组 织 规 律 ， 不 便 查 找 。集 合 线 性 表 树 表 散 列 表 数据结构（C+版）第2版清华大学出版社本 章 讨 论 的 查 找 结 构 ： 线 性 表 ： 适 用 于 静 态 查 找 ， 主 要 采 用 顺 序 查 找 技 术和 折 半 查 找 技 术 。 树 表 ： 适 用 于 动 态 查 找 ， 主 要 采 用 二 叉 排 序 树 的 查找 技 术 。 散 列 表 ： 静 态 查 找 和 动 态 查 找 均 适 用 ， 主 要 采 用 散列 技 术 。 7.1 概 述查 找 结 构 ： 面 向 查 找 操 作 的 数 据 结 构 ， 即 查 找 基 于 的数 据 结 构 。查 找 的 基 本 概 念 数据结构（C+版）第2版清华大学出版社查 找 算 法 的 性 能 查 找 算 法 时 间 性 能 通 过 关 键 码 的 比 较 次 数 来 度 量 。7.1 概 述关 键 码 的 比 较 次 数 与 哪 些 因 素 有 关 呢 ？平 均 查 找 长 度 ： 将 查 找 算 法 进 行 的 关 键 码 的 比 较 次 数的 数 学 期 望 值 定 义 为 平 均 查 找 长 度 ， 即 ： 其 中 ： n： 问 题 规 模 ， 查 找 集 合 中 的 记 录 个 数 ； p i： 查 找 第 i个 记 录 的 概 率 ； ci： 查 找 第 i个 记 录 所 需 的 关 键 码 的 比 较 次 数 。ASL = =ni ii cp1 数据结构（C+版）第2版清华大学出版社查 找 算 法 的 性 能 查 找 算 法 时 间 性 能 通 过 关 键 码 的 比 较 次 数 来 度 量 。7.1 概 述关 键 码 的 比 较 次 数 与 哪 些 因 素 有 关 呢 ？平 均 查 找 长 度 ： 将 查 找 算 法 进 行 的 关 键 码 的 比 较 次 数的 数 学 期 望 值 定 义 为 平 均 查 找 长 度 ， 即 ： ASL = =ni ii cp1c i取 决 于 算 法 ； pi与 算 法 无 关 ， 取 决 于 具 体 应 用 。 如 果 pi是 已 知 的 ， 则 平 均 查 找 长 度 只 是 问 题 规 模 的 函 数 。 数据结构（C+版）第2版清华大学出版社顺 序 查 找 （ 线 性 查 找 ）基 本 思 想 ： 从 线 性 表 的 一 端 向 另 一 端 逐 个 将 关 键 码 与给 定 值 进 行 比 较 ， 若 相 等 ， 则 查 找 成 功 ， 给 出 该 记 录在 表 中 的 位 置 ； 若 整 个 表 检 测 完 仍 未 找 到 与 给 定 值 相等 的 关 键 码 ， 则 查 找 失 败 ， 给 出 失 败 信 息 。 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i7.2 线 性 表 的 查 找 技 术例 ： 查 找 k 35 iii 数据结构（C+版）第2版清华大学出版社顺 序 查 找 （ 线 性 查 找 ）7.2 线 性 表 的 查 找 技 术int SeqSearch1(int r , int n, int k)/数 组 r1 rn存 放 查 找 集 合 i = n; while (i 0 return i; 数据结构（C+版）第2版清华大学出版社基 本 思 想 ： 设 置 “ 哨 兵 ” 。 哨 兵 就 是 待 查 值 ， 将 它 放在 查 找 方 向 的 尽 头 处 ， 免 去 了 在 查 找 过 程 中 每 一 次 比较 后 都 要 判 断 查 找 位 置 是 否 越 界 ， 从 而 提 高 查 找 速 度。 7.2 线 性 表 的 查 找 技 术改 进 的 顺 序 查 找 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i例 ： 查 找 k 35 iii 哨 兵 35 查 找 方 向 数据结构（C+版）第2版清华大学出版社基 本 思 想 ： 设 置 “ 哨 兵 ” 。 哨 兵 就 是 待 查 值 ， 将 它 放在 查 找 方 向 的 尽 头 处 ， 免 去 了 在 查 找 过 程 中 每 一 次 比较 后 都 要 判 断 查 找 位 置 是 否 越 界 ， 从 而 提 高 查 找 速 度。 7.2 线 性 表 的 查 找 技 术改 进 的 顺 序 查 找 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i例 ： 查 找 k 25 ii25 查 找 方 向 iiiiiii 数据结构（C+版）第2版清华大学出版社int SeqSearch2(int r , int n, int k) /数 组 r1 rn存 放 查 找 集 合 r0 = k; i = n; while (ri != k) i-; return i; 7.2 线 性 表 的 查 找 技 术改 进 的 顺 序 查 找ASL= =ni i cp1 +-=ni i inp1 )1(i = (n+1)/2=O(n) 数据结构（C+版）第2版清华大学出版社平 均 查 找 长 度 较 大 ， 特 别 是 当 待 查 找 集 合 中 元 素 较 多时 ， 查 找 效 率 较 低 。7.2 线 性 表 的 查 找 技 术顺 序 查 找 的 缺 点 ：对 表 中 记 录 的 存 储 没 有 任 何 要 求 ， 顺 序 存 储 和 链 接存 储 均 可 ；对 表 中 记 录 的 有 序 性 也 没 有 要 求 ， 无 论 记 录 是 否 按关 键 码 有 序 均 可 。顺 序 查 找 的 优 点 ： 算 法 简 单 而 且 使 用 面 广 。 数据结构（C+版）第2版清华大学出版社折 半 查 找使 用 条 件 ：线 性 表 中 的 记 录 必 须 按 关 键 码 有 序 ；必 须 采 用 顺 序 存 储 。基 本 思 想 ： 在 有 序 表 中 ， 取 中 间 记 录 作 为 比 较 对 象 ，若 给 定 值 与 中 间 记 录 的 关 键 码 相 等 ， 则 查 找 成 功 ； 若给 定 值 小 于 中 间 记 录 的 关 键 码 ， 则 在 中 间 记 录 的 左 半区 继 续 查 找 ； 若 给 定 值 大 于 中 间 记 录 的 关 键 码 ， 则 在中 间 记 录 的 右 半 区 继 续 查 找 。 不 断 重 复 上 述 过 程 ， 直到 查 找 成 功 ， 或 所 查 找 的 区 域 无 记 录 ， 查 找 失 败 。7.2 线 性 表 的 查 找 技 术 数据结构（C+版）第2版清华大学出版社折 半 查 找 的 基 本 思 想7.2 线 性 表 的 查 找 技 术 r1 rmid-1 rmid rmid+1 rn 如 果 krmid 查 找 左 半 区 查 找 右 半 区k（ mid=(1+n)/2） 数据结构（C+版）第2版清华大学出版社例 ： 查 找 值 为 14的 记 录 的 过 程 ： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52low=1 high=13mid=7 high=6 mid=3 high=2 mid=1 311418147221822low=4mid=4 21high 数据结构（C+版）第2版清华大学出版社int BinSearch1(int r , int n, int k) /数 组 r1 rn存 放 查 找 集 合 low = 1; high = n; while (low = high) mid = (low + high) / 2; if (k rmid) low = mid + 1; else return mid; return 0; 7.2 线 性 表 的 查 找 技 术折 半 查 找 非 递 归 算 法 数据结构（C+版）第2版清华大学出版社int BinSearch2(int r , int low, int high, int k) /数 组 r1 rn存 放 查 找 集 合 if (low high) return 0; else mid = (low + high) / 2; if (k rmid) return BinSearch2(r, mid+1, high, k); else return mid; 7.2 线 性 表 的 查 找 技 术折 半 查 找 递 归 算 法 数据结构（C+版）第2版清华大学出版社折 半 查 找 判 定 树 判 定 树 ： 折 半 查 找 的 过 程 可 以 用 二 叉 树 来 描 述 ， 树 中的 每 个 结 点 对 应 有 序 表 中 的 一 个 记 录 ， 结 点 的 值 为 该记 录 在 表 中 的 位 置 。 通 常 称 这 个 描 述 折 半 查 找 过 程 的二 叉 树 为 折 半 查 找 判 定 树 ， 简 称 判 定 树 。7.2 线 性 表 的 查 找 技 术 数据结构（C+版）第2版清华大学出版社 当 n=0时 ， 折 半 查 找 判 定 树 为 空 ； 当 n 0时 ， 折 半 查 找 判 定 树 的 根 结 点 是 有 序 表 中序 号 为 mid=(n+1)/2的 记 录 ， 根 结 点 的 左 子 树 是 与 有序 表 r1 rmid-1相 对 应 的 折 半 查 找 判 定 树 ， 根 结点 的 右 子 树 是 与 rmid+1 rn相 对 应 的 折 半 查 找 判定 树 。 7.2 线 性 表 的 查 找 技 术判 定 树 的 构 造 方 法 数据结构（C+版）第2版清华大学出版社7.2 线 性 表 的 查 找 技 术 1 1 2 2 33 44 5 10 11 119 108 97 85 66 7内 部 结 点 外 部 结 点3 6 9 10 117 84 51 2判 定 树 的 构 造 方 法 数据结构（C+版）第2版清华大学出版社具 有 n个 结 点 的 折 半 查 找 判 定 树 的 深 度 为 查 找 成 功 ： 在 表 中 查 找 任 一 记 录 的 过 程 ， 即 是 折 半 查找 判 定 树 中 从 根 结 点 到 该 记 录 结 点 的 路 径 ， 和 给 定 值的 比 较 次 数 等 于 该 记 录 结 点 在 树 中 的 层 数 。查 找 不 成 功 ： 查 找 失 败 的 过 程 就 是 走 了 一 条 从 根 结点 到 外 部 结 点 的 路 径 ， 和 给 定 值 进 行 的 关 键 码 的 比较 次 数 等 于 该 路 径 上 内 部 结 点 的 个 数 。7.2 线 性 表 的 查 找 技 术 。 1log2 +n折 半 查 找 性 能 分 析 数据结构（C+版）第2版清华大学出版社二 叉 排 序 树二 叉 排 序 树 （ 也 称 二 叉 查 找 树 ） ： 或 者 是 一 棵 空 的 二叉 树 ， 或 者 是 具 有 下 列 性 质 的 二 叉 树 ： 若 它 的 左 子 树 不 空 ， 则 左 子 树 上 所 有 结 点 的 值 均小 于 根 结 点 的 值 ； 若 它 的 右 子 树 不 空 ， 则 右 子 树 上 所 有 结 点 的 值 均大 于 根 结 点 的 值 ； 它 的 左 右 子 树 也 都 是 二 叉 排 序 树 。7.3 树 表 的 查 找 技 术二 叉 排 序 树 的 定 义 采 用 的 是 递 归 方 法 。 数据结构（C+版）第2版清华大学出版社二 叉 排 序 树 非 二 叉 排 序 树二 叉 排 序 树 7.3 树 表 的 查 找 技 术63 905542 5810 45 67 8370 63 605582 5810 45 67 8370中 序 遍 历 二 叉 排 序 树 可 以 得 到 一 个 按 关 键 码 有 序 的 序 列 数据结构（C+版）第2版清华大学出版社二 叉 排 序 树 的 存 储 结 构以 二 叉 链 表 形 式 存 储 ， 类 声 明 如 下 ：class BiSortTree public: BiSortTree(int a , int n); BiSortTree( ); void InsertBST(BiNode *root , BiNode *s); void DeleteBST(BiNode *p, BiNode *f ); BiNode *SearchBST(BiNode *root, int k); private: BiNode *root; ; 7.3 树 表 的 查 找 技 术 数据结构（C+版）第2版清华大学出版社二 叉 排 序 树 的 插 入分 析 ： 若 二 叉 排 序 树 为 空 树 ， 则 新 插 入 的 结 点 为 新的 根 结 点 ； 否 则 ， 新 插 入 的 结 点 必 为 一 个 新 的 叶 子结 点 ， 其 插 入 位 置 由 查 找 过 程 得 到 。7.3 树 表 的 查 找 技 术void InsertBST(BiNode *root , BiNode *s); 数据结构（C+版）第2版清华大学出版社例 ： 插 入 值 为 98的 结 点7.3 树 表 的 查 找 技 术6355 9058 70 98 55 63root 9058 70 98 sroot 数据结构（C+版）第2版清华大学出版社void BiSortTree:InsertBST(BiNode *root, BiNode *s) if (root = NULL) root = s; else if (s-data data) InsertBST(root-lchild, s); else InsertBST(root-rchild, s); 7.3 树 表 的 查 找 技 术二 叉 排 序 树 的 插 入 算 法 数据结构（C+版）第2版清华大学出版社二 叉 排 序 树 的 构 造从 空 的 二 叉 排 序 树 开 始 ， 依 次 插 入 一 个 个 结 点 。例 ： 关 键 码 集 合 为63， 90， 70， 55， 58，二 叉 排 序 树 的 构 造 过 程 为 ： 7.3 树 表 的 查 找 技 术 6355 9058 70 数据结构（C+版）第2版清华大学出版社BiSortTree:BiSortTree(int r , int n) for (i = 0; i n; i+) s = new BiNode; s-data = ri; s-lchild = s-rchild = NULL; InsertBST(root, s); 7.3 树 表 的 查 找 技 术二 叉 排 序 树 的 构 造 算 法 数据结构（C+版）第2版清华大学出版社 一 个 无 序 序 列 可 以 通 过 构 造 一 棵 二 叉 排 序 树 而变 成 一 个 有 序 序 列 ; 每 次 插 入 的 新 结 点 都 是 二 叉 排 序 树 上 新 的 叶 子结 点 ; 找 到 插 入 位 置 后 ， 不 必 移 动 其 它 结 点 ， 仅 需 修改 某 个 结 点 的 指 针 ； 在 左 子 树 /右 子 树 的 查 找 过 程 与 在 整 棵 树 上 查找 过 程 相 同 ； 新 插 入 的 结 点 没 有 破 坏 原 有 结 点 之 间 的 关 系 。小 结 ： 7.3 树 表 的 查 找 技 术 数据结构（C+版）第2版清华大学出版社二 叉 排 序 树 的 删 除在 二 叉 排 序 树 上 删 除 某 个 结 点 之 后 ， 仍 然 保 持 二 叉 排序 树 的 特 性 。分 三 种 情 况 讨 论 ：被 删 除 的 结 点 是 叶 子 ；被 删 除 的 结 点 只 有 左 子 树 或 者 只 有 右 子 树 ；被 删 除 的 结 点 既 有 左 子 树 ， 也 有 右 子 树 。7.3 树 表 的 查 找 技 术 数据结构（C+版）第2版清华大学出版社情况1被删除的结点是叶子结点7.3 树 表 的 查 找 技 术503020 80 9085 88403532 503020 80 9085403532操作：将双亲结点中相应指针域的值改为空。 数据结构（C+版）第2版清华大学出版社情况2被删除的结点只有左子树或者只有右子树操作：将双亲结点的相应指针域的值指向被删除结点的左子树（或右子树）。7.3 树 表 的 查 找 技 术503020 80 9085 88403532 503020 9085 88403532 数据结构（C+版）第2版清华大学出版社情况3被删除的结点既有左子树也有右子树操作：以其左子树中的最大值结点（或右子树中的最小值结点）替代之，然后再删除该结点。7.3 树 表 的 查 找 技 术503020 80 9085 88403532 403020 80 9085 883532 数据结构（C+版）第2版清华大学出版社1. 若 结 点 p是 叶 子 ， 则 直 接 删 除 结 点 p；2. 若 结 点 p只 有 左 子 树 ， 则 只 需 重 接 p的 左 子 树 ； 若 结 点 p只 有 右 子 树 ， 则 只 需 重 接 p的 右 子 树 ； 3. 若 结 点 p的 左 右 子 树 均 不 空 ， 则 3.1 查 找 结 点 p的 右 子 树 上 的 最 左 下 结 点 s及 其 双 亲 结 点 par； 3.2 将 结 点 s数 据 域 替 换 到 被 删 结 点 p的 数 据 域 ； 3.3 若 结 点 p的 右 孩 子 无 左 子 树 ， 则 将 s的 右 子 树 接 到 par的 右 子 树 上 ； 否 则 ， 将 s的 右 子 树 接 到 结 点 par的 左 子 树 上 ； 3.4 删 除 结 点 s；7.3 树 表 的 查 找 技 术二 叉 排 序 树 的 删 除 算 法 伪 代 码 数据结构（C+版）第2版清华大学出版社二 叉 排 序 树 的 查 找在 二 叉 排 序 树 中 查 找 给 定 值 k的 过 程 是 ： 若 root是 空 树 ， 则 查 找 失 败 ； 若 k root-data， 则 查 找 成 功 ； 否 则 若 k root-data， 则 在 root的 左 子 树 上 查 找 ； 否 则 在 root的 右 子 树 上 查 找 。 上 述 过 程 一 直 持 续 到 k被 找 到 或 者 待 查 找 的 子 树 为空 ， 如 果 待 查 找 的 子 树 为 空 ， 则 查 找 失 败 。二 叉 排 序 树 的 查 找 效 率 在 于 只 需 查 找 二 个 子 树 之 一 。7.3 树 表 的 查 找 技 术 数据结构（C+版）第2版清华大学出版社例：在二叉排序树中查找关键字值为35，95的过程：7.3 树 表 的 查 找 技 术503020 80 9085 88403532二 叉 排 序 树 的 查 找 503020 80 9085 88403532 数据结构（C+版）第2版清华大学出版社BiNode *BiSortTree:SearchBST(BiNode *root, int k) if (root = NULL) return NULL； else if (root-data = k) return root; else if (k data) return SearchBST(root-lchild, k); else return SearchBST(root-rchild, k); 7.3 树 表 的 查 找 技 术二 叉 排 序 树 的 查 找 数据结构（C+版）第2版清华大学出版社二 叉 排 序 树 的 查 找 性 能 分 析由 序 列 3, 1, 2, 5, 4得 到 二 叉 排 序 树 ：由 序 列 1, 2, 3, 4, 5得 到 二 叉 排 序 树 ：ASL =（1+2+3+4+5）/ 5= 3ASL =（ 1+2+3+2+3） / 5 = 2.2二 叉 排 序 树 的 查 找 性 能 取 决 于 二 叉 排 序 树 的 形 状 ，在 O(log 2n)和 O(n)之 间 。 7.3 树 表 的 查 找 技 术 1 2 3 4 531 2 54 数据结构（C+版）第2版清华大学出版社平 衡 二 叉 树 ： 或 者 是 一 棵 空 的 二 叉 排 序 树 ， 或 者 是 具有 下 列 性 质 的 二 叉 排 序 树 ： 根 结 点 的 左 子 树 和 右 子 树 的 深 度 最 多 相 差 1; 根 结 点 的 左 子 树 和 右 子 树 也 都 是 平 衡 二 叉 树 。 平 衡 因 子 ： 结 点 的 平 衡 因 子 是 该 结 点 的 左 子 树 的 深 度与 右 子 树 的 深 度 之 差 。 平 衡 二 叉 树 7.3 树 表 的 查 找 技 术 数据结构（C+版）第2版清华大学出版社54 82 54 82 1是 平 衡 树 非 平 衡 树7.3 散 列 表 的 查 找 技 术平 衡 二 叉 树在 平 衡 树 中 ， 结 点 的 平 衡 因 子 可 以 是 1， 0， -1。结 点 的 平 衡 因 子 HL-HR 数据结构（C+版）第2版清华大学出版社最 小 不 平 衡 子 树 ： 在 平 衡 二 叉 树 的 构 造 过 程 中 ， 以 距离 插 入 结 点 最 近 的 、 且 平 衡 因 子 的 绝 对 值 大 于 1的 结点 为 根 的 子 树 。 7.3 树 表 的 查 找 技 术542 81平 衡 二 叉 树 数据结构（C+版）第2版清华大学出版社构 造 平 衡 二 叉 树 的 基 本 思 想 ： 每 插 入 一 个 结 点 ，（ 1） 从 插 入 结 点 开 始 向 上 计 算 各 结 点 的 平 衡 因 子 ，如 果 某 结 点 平 衡 因 子 的 绝 对 值 超 过 1， 则 说 明 插 入 操作 破 坏 了 二 叉 排 序 树 的 平 衡 性 ， 需 要 进 行 平 衡 调 整 ；否 则 继 续 执 行 插 入 操 作 。（ 2） 如 果 二 叉 排 序 树 不 平 衡 ， 则 找 出 最 小 不 平 衡 子树 的 根 结 点 ， 根 据 新 插 入 结 点 与 最 小 不 平 衡 子 树 根 结点 之 间 的 关 系 判 断 调 整 类 型 。（ 3） 根 据 调 整 类 型 进 行 相 应 的 调 整 ， 使 之 成 为 新 的平 衡 子 树 。 7.3 树 表 的 查 找 技 术平 衡 二 叉 树 数据结构（C+版）第2版清华大学出版社例 ： 设 序 列 20， 35， 40， 15， 30， 25 ， 构 造 平 衡 树 。20 35 407.3 树 表 的 查 找 技 术3520 4015 3025 数据结构（C+版）第2版清华大学出版社例 ： 设 序 列 20， 35， 40， 15， 30， 25 ， 构 造 平 衡 树 。7.3 树 表 的 查 找 技 术3520 4015 3025 20 2515 35 4030 35 403020 2515 数据结构（C+版）第2版清华大学出版社设 结 点 A为 最 小 不 平 衡 子 树 的 根 结 点 ， 对 该 子 树 进 行平 衡 调 整 归 纳 起 来 有 以 下 四 种 情 况 ： 1. LL型 2. RR型 3. LR型 4. RL型 7.3 树 表 的 查 找 技 术平 衡 二 叉 树 数据结构（C+版）第2版清华大学出版社插 入 前 插 入 后 ， 调 整 前 调 整 后7.3 树 表 的 查 找 技 术平 衡 二 叉 树 LL型A 1B Lh BRh0 AR hB h2BLh BRh1 ARABX h+1BL hARBRh 00B AX旋 转 ： 扁 担 原 理 ； 冲 突 ： 旋 转 优 先 数据结构（C+版）第2版清华大学出版社6 12例 :LL型 7.3 树 表 的 查 找 技 术1087 9 12 9 10 12876 数据结构（C+版）第2版清华大学出版社平 衡 二 叉 树 RR型7.3 树 表 的 查 找 技 术插 入 前 插 入 后 ， 调 整 前 调 整 后A -1B Lh BRh0ALh B XA -2BLh BRh0ALh B BALh BLh0 BR h+1A X0 数据结构（C+版）第2版清华大学出版社 插 入 后 ， 调 整 前 先 顺 时 针 旋 转 再 逆 时 针 旋 转7.3 树 表 的 查 找 技 术平 衡 二 叉 树 LR型A 2CLh-1BLh -1 AR hB CCR h-1X X ACL h-1CB CRh-1AR hBLh AR hC ACRh-1BCLh-1 X 0 -10BLh 数据结构（C+版）第2版清华大学出版社 插 入 后 ， 调 整 前 先 顺 时 针 旋 转 再 逆 时 针 旋 转7.3 树 表 的 查 找 技 术平 衡 二 叉 树 RL型 XACLh-1 BR hC BCRh-1ALhA -2CLh-1 BR h1ALh BCCRh-1X BR hC BCRh-1AALh CLh-1 X0 01 数据结构（C+版）第2版清华大学出版社课堂练习：设有关键码序列5, 4, 2, 8, 6, 9，构造平衡树542 7.3 树 表 的 查 找 技 术LL型 42 5 86 数据结构（C+版）第2版清华大学出版社8642 5 6 842 5 85 642课堂练习：设有关键码序列5, 4, 2, 8, 6, 9，构造平衡树7.3 树 表 的 查 找 技 术RL型旋 转 1次RL型 旋 转 2次 数据结构（C+版）第2版清华大学出版社85 642 9 RR型 84 652 97.3 树 表 的 查 找 技 术课堂练习：设有关键码序列5, 4, 2, 8, 6, 9，构造平衡树 数据结构（C+版）第2版清华大学出版社7.3 散 列 表 的 查 找 技 术顺 序 查 找 、 折 半 查 找 、 二 叉 排 序 树 查 找 等 。这 些 查 找 技 术 都 是 通 过 一 系 列 的 给 定 值 与 关 键 码 的比 较 ， 查 找 效 率 依 赖 于 查 找 过 程 中 进 行 的 给 定 值 与关 键 码 的 比 较 次 数 。查 找 操 作 要 完 成 什 么 任 务 ？待 查 值 k 确 定 k在 存 储 结 构 中 的 位 置我 们 学 过 哪 些 查 找 技 术 ？ 这 些 查 找 技 术 的 共 性 ？在 存 储 位 置 和 关 键 码 之 间 建 立 一 个 确 定 的 对 应 关 系能 否 不 用 比 较 ， 通 过 关 键 码 直 接 确 定 存 储 位 置 ？ 数据结构（C+版）第2版清华大学出版社概 述散 列 的 基 本 思 想 ： 在 记 录 的 存 储 地 址 和 它 的 关 键 码 之间 建 立 一 个 确 定 的 对 应 关 系 。 这 样 ， 不 经 过 比 较 ， 一次 读 取 就 能 得 到 所 查 元 素 的 查 找 方 法 。7.3 散 列 表 的 查 找 技 术关键码集合 k i riH (ki) H 数据结构（C+版）第2版清华大学出版社散 列 表 ： 采 用 散 列 技 术 将 记 录 存 储 在 一 块 连 续 的 存储 空 间 中 ， 这 块 连 续 的 存 储 空 间 称 为 散 列 表 。概 述 7.3 散 列 表 的 查 找 技 术关键码集合 k i riH (ki) H 散 列 表数 组 数据结构（C+版）第2版清华大学出版社散 列 函 数 ： 将 关 键 码 映 射 为 散 列 表 中 适 当 存 储 位 置的 函 数 。概 述 7.3 散 列 表 的 查 找 技 术 散 列 表关键码集合 k i riH (ki) H散 列 函 数 数 组 数据结构（C+版）第2版清华大学出版社散 列 地 址 ： 由 散 列 函 数 所 得 的 存 储 地 址 。概 述 7.3 散 列 表 的 查 找 技 术 散 列 表关键码集合 k i riH (ki) H散 列 函 数散 列 地 址下 标 数 组 数据结构（C+版）第2版清华大学出版社概 述 7.3 散 列 表 的 查 找 技 术散 列 技 术 仅 仅 是 一 种 查 找 技 术 吗 ？散 列 既 是 一 种 查 找 技 术 ， 也 是 一 种 存 储 技 术 。散 列 只 是 通 过 记 录 的 关 键 码 定 位 该 记 录 ， 没 有 完整 地 表 达 记 录 之 间 的 逻 辑 关 系 ， 所 以 ， 散 列 主 要是 面 向 查 找 的 存 储 结 构 。散 列 是 一 种 完 整 的 存 储 结 构 吗 ？ 数据结构（C+版）第2版清华大学出版社散 列 技 术 一 般 不 适 用 于 允 许 多 个 记 录 有 同 样 关 键 码的 情 况 。 散 列 方 法 也 不 适 用 于 范 围 查 找 ， 换 言 之 ，在 散 列 表 中 ， 我 们 不 可 能 找 到 最 大 或 最 小 关 键 码 的记 录 ， 也 不 可 能 找 到 在 某 一 范 围 内 的 记 录 。概 述 7.3 散 列 表 的 查 找 技 术散 列 技 术 适 合 于 哪 种 类 型 的 查 找 ？散 列 技 术 最 适 合 回 答 的 问 题 是 ： 如 果 有 的 话 ，哪 个 记 录 的 关 键 码 等 于 待 查 值 。 数据结构（C+版）第2版清华大学出版社散 列 技 术 的 关 键 问 题 ： 散 列 函 数 的 设 计 。 如 何 设 计 一 个 简 单 、 均 匀 、 存储 利 用 率 高 的 散 列 函 数 。 冲 突 的 处 理 。 如 何 采 取 合 适 的 处 理 冲 突 方 法 来 解决 冲 突 。 7.3 散 列 表 的 查 找 技 术概 述 数据结构（C+版）第2版清华大学出版社冲 突 ： 对 于 两 个 不 同 关 键 码 kikj， 有 H (ki) H (kj)，即 两 个 不 同 的 记 录 需 要 存 放 在 同 一 个 存 储 位 置 ,ki和 kj相 对 于 H 称 做 同 义 词 。 7.3 散 列 表 的 查 找 技 术概 述 关键码集 合 ki riH (ki)kj H (kj) 数据结构（C+版）第2版清华大学出版社散 列 函 数 7.3 散 列 表 的 查 找 技 术设 计 散 列 函 数 一 般 应 遵 循 以 下 原 则 ： 计 算 简 单 。 散 列 函 数 不 应 该 有 很 大 的 计 算 量 ， 否则 会 降 低 查 找 效 率 。 函 数 值 即 散 列 地 址 分 布 均 匀 。 函 数 值 要 尽 量 均 匀散 布 在 地 址 空 间 ， 这 样 才 能 保 证 存 储 空 间 的 有 效 利用 并 减 少 冲 突 。 数据结构（C+版）第2版清华大学出版社散 列 函 数 直 接 定 址 法散 列 函 数 是 关 键 码 的 线 性 函 数 ， 即 ：H (key) = a key + b （a，b为常数）例 ： 关 键 码 集 合 为 10, 30, 50, 70, 80, 90， 选 取 的 散列 函 数 为 H (key)=key/10， 则 散 列 表 为 ： 0 1 2 3 4 5 6 7 8 910 30 50 70 80 90适 用 情 况 ？事 先 知 道 关 键 码 ， 关 键 码 集 合 不 是 很 大 且 连 续 性 较 好 。 7.3 散 列 表 的 查 找 技 术 数据结构（C+版）第2版清华大学出版社散 列 函 数 为 ：H (key)=key mod p 7.3 散 列 表 的 查 找 技 术散 列 函 数 除 留 余 数 法 1470147014散 列 地 址 56494235282114 关 键 码如 何 选 取 合 适 的 p， 产 生 较 少 同 义 词 ？例 ： p 21 3 7 数据结构（C+版）第2版清华大学出版社7.3 散 列 表 的 查 找 技 术散 列 函 数 除 留 余 数 法一 般 情 况 下 ， 选 p为 小 于 或 等 于 表 长 （ 最 好 接 近 表 长 ）的 最 小 素 数 或 不 包 含 小 于 20质 因 子 的 合 数 。 除 留 余 数 法 是 一 种 最 简 单 、 也 是 最 常 用 的 构 造 散 列函 数 的 方 法 ， 并 且 不 要 求 事 先 知 道 关 键 码 的 分 布 。 适 用 情 况 ？ 数据结构（C+版）第2版清华大学出版社根 据 关 键 码 在 各 个 位 上 的 分 布 情 况 ， 选 取 分 布 比 较均 匀 的 若 干 位 组 成 散 列 地 址 。 例 ： 关 键 码 为 8位 十 进 制 数 ， 散 列 地 址 为 2位 十 进 制 数8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 7.3 散 列 表 的 查 找 技 术散 列 函 数 数 字 分 析 法 数据结构（C+版）第2版清华大学出版社适 用 情 况 :能 预 先 估 计 出 全 部 关 键 码 的 每 一 位 上 各 种 数 字 出 现的 频 度 ， 不 同 的 关 键 码 集 合 需 要 重 新 分 析 。7.3 散 列 表 的 查 找 技 术散 列 函 数 数 字 分 析 法 数据结构（C+版）第2版清华大学出版社对 关 键 码 平 方 后 ， 按 散 列 表 大 小 ， 取 中 间 的 若 干 位 作为 散 列 地 址 （ 平 方 后 截 取 ） 。 7.3 散 列 表 的 查 找 技 术散 列 函 数 平 方 取 中 法事 先 不 知 道 关 键 码 的 分 布 且 关 键 码 的 位 数 不 是 很 大 。适 用 情 况 :例 ： 散 列 地 址 为 2位 ， 则 关 键 码 123的 散 列 地 址 为 ：(1234)2 1522756 数据结构（C+版）第2版清华大学出版社将 关 键 码 从 左 到 右 分 割 成 位 数 相 等 的 几 部 分 ， 将 这 几部 分 叠 加 求 和 ， 取 后 几 位 作 为 散 列 地 址 。 7.3 散 列 表 的 查 找 技 术散 列 函 数 折 叠 法例 ： 设 关 键 码 为 2 5 3 4 6 3 5 8 7 0 5， 散 列 地 址 为 三 位 。 2 5 3 4 6 3 5 8 7 + 0 5 1 3 0 8 移 位 叠 加 2 5 3 3 6 4 5 8 7 + 5 0 1 2 5 4 间 界 叠 加 适 用 情 况 :关 键 码 位 数 很 多 ， 事 先不 知 道 关 键 码 的 分 布 。 数据结构（C+版）第2版清华大学出版社处 理 冲 突 的 方 法 开 放 定 址 法由 关 键 码 得 到 的 散 列 地 址 一 旦 产 生 了 冲 突 ， 就 去 寻 找下 一 个 空 的 散 列 地 址 ， 并 将 记 录 存 入 。 如 何 寻 找 下 一 个 空 的 散 列 地 址 ?7.3 散 列 表 的 查 找 技 术（ 1） 线 性 探 测 法（ 2） 二 次 探 测 法（ 3） 随 机 探 测 法 数据结构（C+版）第2版清华大学出版社线 性 探 测 法当 发 生 冲 突 时 ， 从 冲 突 位 置 的 下 一 个 位 置 起 ， 依 次寻 找 空 的 散 列 地 址 。 对 于 键 值 key， 设 H (key)=d， 闭 散 列 表 的 长 度 为 m，则 发 生 冲 突 时 ， 寻 找 下 一 个 散 列 地 址 的 公 式 为 ： H i=(H (key) di) % m （ di=1， 2， ， m-1） 7.3 散 列 表 的 查 找 技 术用 开 放 定 址 法 处 理 冲 突 得 到 的 散 列 表 叫 闭 散 列 表 。 数据结构（C+版）第2版清华大学出版社例 ： 关 键 码 集 合 为 47, 7, 29, 11, 16, 92, 22, 8, 3， 散列 表 表 长 为 11， 散 列 函 数 为 H (key)=key mod 11， 用线 性 探 测 法 处 理 冲 突 ， 则 散 列 表 为 ：47 72911 1692 2922 22 8 83 3 3 3堆 积 ： 在 处 理 冲 突 的 过 程 中 出 现 的 非 同 义 词 之 间 对同 一 个 散 列 地 址 争 夺 的 现 象 。7.3 散 列 表 的 查 找 技 术线 性 探 测 法 0 1 2 3 4 5 6 7 8 9 10 数据结构（C+版）第2版清华大学出版社在 线 性 探 测 法 构 造 的 散 列 表 中 查 找 算 法 伪 代 码 1. 计算散列地址j; 2. 若htj等于k，则查找成功，返回记录在散列表中的下标； 否则执行第3步； 3. 若htj为空或整个散列表探测一遍，则查找失败，转4； 否则，j指向下一单元，转2； 4. 若整个散列表探测一遍，则表满，抛出溢出异常； 否则，将待查值插入；7.3 散 列 表 的 查 找 技 术 数据结构（C+版）第2版清华大学出版社int HashSearch1(int ht , int m, int k) j = H(k); /计算散列地址 if (htj = k) return j; /没有发生冲突，比较一次查找成功 else if (htj = Empty) htj = k; return 0; /查找不成功，插入 i = (j + 1) % m; /设置探测的起始下标 while (hti != Empty /发生冲突，比较若干次查找成功 else i = (i + 1) % m; /向后探测一个位置 if (i = j) throw 溢出; else hti = k; return 0; /查找不成功，插入 7.3 散 列 表 的 查 找 技 术在 线 性 探 测 法 构 造 的 散 列 表 中 查 找 算 法 C+描 述 数据结构（C+版）第2版清华大学出版社二 次 探 测 法当 发 生 冲 突 时 ， 寻 找 下 一 个 散 列 地 址 的 公 式 为 ： H i=(H (key) di)% m（ di=12， 12， 22， 22， ， q2， q2且 q m/2） 7.3 散 列 表 的 查 找 技 术 数据结构（C+版）第2版清华大学出版社47 72911 1692 2922 22 8 833 3例 ： 关 键 码 集 合 为 47, 7, 29, 11, 16, 92, 22, 8, 3， 散列 表 表 长 为 11， 散 列 函 数 为 H (key)=key mod 11， 用二 次 探 测 法 处 理 冲 突 ， 则 散 列 表 为 ：二 次 探 测 法 7.3 散 列 表 的 查 找 技 术 0 1 2 3 4 5 6 7 8 9 10 数据结构（C+版）第2版清华大学出版社随 机 探 测 法当 发 生 冲 突 时 ， 下 一 个 散 列 地 址 的 位 移 量 是 一 个 随机 数 列 ， 即 寻 找 下 一 个 散 列 地 址 的 公 式 为 ： H i=(H (key)+di)% m （ di是 一 个 随 机 数 列 ， i=1， 2， ， m-1）7.3 散 列 表 的 查 找 技 术计 算 机 中 产 生 随 机 数 的 方 法 通 常 采 用 线 性 同 余 法 ，其 中 ， d称 为 随 机 种 子 。 当 b、 c和 m的 值 确 定 后 ，给 定 一 个 随 机 种 子 ， 产 生 确 定 的 随 机 数 序 列 。 0 =da =+= - 1, 2,Lmod)( 1 nmcbaa nn 数据结构（C+版）第2版清华大学出版社p 基 本 思 想 ： 将 所 有 散 列 地 址 相 同 的 记 录 ， 即 所 有 同义 词 记 录 存 储 在 一 个 单 链 表 中 （ 称 为 同 义 词 子 表 ） ，在 散 列 表 中 存 储 的 是 所 有 同 义 词 子 表 的 头 指 针 。 p 用 拉 链 法 处 理 冲 突 构 造 的 散 列 表 叫 做 开 散 列 表 。p 开 散 列 表 不 会 出 现 堆 积 现 象 。 p 设 n个 记 录 存 储 在 长 度 为 m的 散 列 表 中 ， 则 同 义 词子 表 的 平 均 长 度 为 n / m。7.3 散 列 表 的 查 找 技 术处 理 冲 突 的 方 法 拉 链 法 （ 链 地 址 法 ） 数据结构（C+版）第2版清华大学出版社例 ： 关 键 码 集 合 47, 7, 29, 11, 16, 92, 22, 8, 3， 散 列函 数 为 H (key)=key mod 11， 用 拉 链 法 处 理 冲 突 ， 构造 的 开 散 列 表 为 ： 7.3 散 列 表 的 查 找 技 术 0 1 2 3 4 5 6 7 8 910 11 22 47 3 92 16 7 29 8 数据结构（C+版）第2版清华大学出版社在 拉 链 法 构 造 的 散 列 表 查 找 算 法 伪 代 码1. 计 算 散 列 地 址 j； 2. 在 第 j个 同 义 词 子 表 中 顺 序 查 找 ； 3. 若 查 找 成 功 ， 则 返 回 结 点 的 地 址 ； 否 则 ， 将 待 查 记 录 插 在 第 j个 同 义 词 子 表 的 表 头 。7.3 散 列 表 的 查 找 技 术 数据结构（C+版）第2版清华大学出版社Node *HashSearch2(Node *ht , int m, int k) j = H(k); p = htj; while (p != NULL if (p-data = k) return p; else q = new Node; q-data = k; q-next = htj; htj = q; 7.3 散 列 表 的 查 找 技 术在 拉 链 法 构 造 的 散 列 表 查 找 算 法 C+描 述 数据结构（C+版）第2版清华大学出版社散 列 查 找 的 性 能 分 析 p 由 于 冲 突 的 存 在 ， 产 生 冲 突 后 的 查 找 仍 然 是 给 定值 与 关 键 码 进 行 比 较 的 过 程 。p 在 查 找 过 程 中 ， 关 键 码 的 比 较 次 数 取 决 于 产 生 冲突 的 概 率 。 影 响 冲 突 产 生 的 因 素 有 ： （ 1） 散 列 函 数 是 否 均 匀 （ 2） 处 理 冲 突 的 方 法 （ 3） 散 列 表 的 装 载 因 子 7.3 散 列 表 的 查 找 技 术表中填入的记录数 散列表的长度= 数据结构（C+版）第2版清华大学出版社几 种 处 理 冲 突 方 法 的 平 均 查 找 长 度7.3 散 列 表 的 查 找 技 术 散列表的平均查找长度是装填因子的函数，而不是查找集合 中记录个数n的函数。在很多情况下，散列表的空间都比查找集合大，此时虽然浪费了一定的空间，但换来的是查找效率。 数据结构（C+版）第2版清华大学出版社开 散 列 表 与 闭 散 列 表 的 比 较7.3 散 列 表 的 查 找 技 术不 产 生产 生 有没 有堆 积 现 象 结 构 开 销 插 入 /删 除 查 找 效 率开散列表闭散列 表 效 率 高效 率 低 效 率 高效 率 低 估 计 容 量不 需 要需 要 数据结构（C+版）第2版清华大学出版社本 章 总 结查 找 技 术静 态 查 找 动 态 查 找线 性表 的查 找技 术 树 表的查 找技 术散 列表 的查 找技 术 顺 序 查 找 折 半 查 找 二 叉 排 序 树 平 衡 二 叉 树散 列 函 数 处 理 冲 突 开 放 定 址 法 线 性 探 测 法 二 次 探 测 法 随 机 探 测 法 拉 链 法 直 接 定 址 法 除 留 余 数 法 数 字 分 析 法 平 方 取 中 法 折 叠 法