《数据结构CHAP》PPT课件.ppt

何 谓 查 找 表 ？ 查 找 表 是 由 同 一 类 型 的 数 据 元 素(或 记 录 )构 成 的 集 合 。 由 于 “ 集 合 ” 中 的 数 据 元 素 之 间 存 在着 松 散 的 关 系 ， 因 此 查 找 表 是 一 种 应 用灵 便 的 结 构 。 对 查 找 表 经 常 进 行 的 操 作 : 1） 查 询 某 个 “ 特 定 的 ” 数 据 元 素 是否 在 查 找 表 中 ； 2） 检 索 某 个 “ 特 定 的 ” 数 据 元 素 的各 种 属 性 ； 3） 在 查 找 表 中 插 入 一 个 数 据 元 素 ； 4） 从 查 找 表 中 删 去 某 个 数 据 元 素 。 仅 作 查 询 和 检 索 操 作 的 查 找 表 。静 态 查 找 表有 时 在 查 询 之 后 ， 还 需 要 将 “ 查 询 ” 结果 为 “ 不 在 查 找 表 中 ” 的 数 据 元 素 插 入到 查 找 表 中 ； 或 者 ， 从 查 找 表 中 删 除 其“ 查 询 ” 结 果 为 “ 在 查 找 表 中 ” 的 数 据元 素 。动 态 查 找 表查 找 表 可 分 为 两 类 : 是 数 据 元 素 （ 或 记 录 ） 中 某 个 数 据 项的 值 ， 用 以 标 识 （ 识 别 ） 一 个 数 据 元素 （ 或 记 录 ） 。关 键 字 若 此 关 键 字 可 以 识 别 唯 一 的 一 个 记录 ， 则 称 之 谓 “ 主 关 键 字 ” 。 若 此 关 键 字 能 识 别 若 干 记 录 ， 则 称之 谓 “ 次 关 键 字 ” 。 根 据 给 定 的 某 个 值 ， 在 查 找 表 中 确 定 一 个其 关 键 字 等 于 给 定 值 的 数 据 元 素 或 （ 记 录 ） 查 找 若 查 找 表 中 存 在 这 样 一 个 记 录 ， 则 称“ 查 找 成 功 ” ， 查 找 结 果 ： 给 出 整 个 记 录的 信 息 ， 或 指 示 该 记 录 在 查 找 表 中 的 位 置 ； 否 则 称 “ 查 找 不 成 功 ” ， 查 找 结 果 ： 给出“ 空 记 录 ” 或 “ 空 指 针 ” 。 由 于 查 找 表 中 的 数 据 元 素 之 间 不 存 在 明显 的 组 织 规 律 ， 因 此 不 便 于 查 找 。 为 了 提 高 查 找 的 效 率 ， 需 要 在 查 找 表 中的 元 素 之 间 人 为 地 附 加 某 种 确 定 的 关 系 ，换 句 话 说 ， 用 另 外 一 种 结 构 来 表 示 查 找 表 。如 何 进 行 查 找 ？查 找 的 方 法 取 决 于 查 找 表 的 结 构 。 9.1 静 态 查 找 表9.2 动 态 查 找 树 表9.3 哈 希 表 9.1 静 态 查 找 表 数 据 对 象 D：数 据 关 系 R： D是 具 有 相 同 特 性 的 数据 元 素 的 集 合 。 每 个 数据 元 素 含 有 类 型 相 同 的关 键 字 ， 可 唯 一 标 识 数据 元 素 。 数 据 元 素 同 属 一 个 集 合 。ADT StaticSearchTable Create(Destroy(Search(ST, key);Traverse(ST, Visit();基 本 操 作 P： next ADT StaticSearchTable 构 造 一 个 含 n 个 数 据 元 素的 静 态 查 找 表 ST。 Create(操 作 结 果 ： 销 毁 表 ST。Destroy(初 始 条 件 ：操 作 结 果 ： 静 态 查 找 表 ST存 在 ； 若 ST 中 存 在 其 关 键 字 等 于 kval 的 数 据 元 素 ， 则 函 数 值为 该 元 素 的 值 或 在 表 中 的 位置 ， 否 则 为 “ 空 ” 。 Search(ST, kval);初 始 条 件 ：操 作 结 果 ： 静 态 查 找 表 ST存 在 ， kval 为 和 查 找 表 中 元 素 的 关 键 字类 型 相 同 的 给 定 值 ； 按 某 种 次 序 对 ST的 每 个 元素 调 用 函 数 Visit()一 次 且 仅一 次 ， 一 旦 Visit()失 败 ， 则操 作 失 败 。Traverse(ST, Visit();初 始 条 件 ：操 作 结 果 ： 静 态 查 找 表 ST存 在 ， Visit是 对 元 素 操 作 的 应 用 函 数 ； 假 设 静 态 查 找 表 的 顺 序 存 储 结 构 为typedef struct *elem; / 数 据 元 素 存 储 空 间 基 址 ， 建 表 时 / 按 实 际 长 度 分 配 ， 0号 单 元 留 空 int length; / 表 的 长 度 SSTable;ElemType 数 据 元 素 类 型 的 定 义 为 :typedef struct keyType key; / 关 键 字 域 / 其 它 属 性 域 ElemType ; , TElemType ; 一 、 顺 序 查 找 表二 、 有 序 查 找 表三 、 静 态 查 找 树 表四 、 索 引 顺 序 表 以 顺 序 表 或 线 性 链 表表 示 静 态 查 找 表一 、 顺 序 查 找 表 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elem 回 顾 顺 序 表 的 查 找 过 程 ：假 设 给 定 值 e = 64,要 求 ST.elemi = e, 问 : i = ?i i6 i int location( SqList L, ElemType p = L.elem; while ( i=L.length if ( i= L.length) return i; else return 0; /location 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elem i 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elem i60 ikval = 64kval = 60 i64 int Search_Seq(SSTable ST, KeyType kval) / 在 顺 序 表 ST中 顺 序 查 找 其 关 键 字 等 于 / key的 数 据 元 素 。 若 找 到 ， 则 函 数 值 为 / 该 元 素 在 表 中 的 位 置 ， 否 则 为 0。 ST.elem0.key = kval; / 设 置 “ 哨 兵 ” for (i=ST.length; -i); / 从 后 往 前 找 return i; / 找 不 到 时 ， i为 0 / Search_Seq ST.elemi.key!=kval; 分 析 顺 序 查 找 的 时 间 性 能 。 定 义 ： 查 找 算 法 的 平 均 查 找 长 度 (Average Search Length) 为 确 定 记 录 在 查 找 表 中 的 位 置 ， 需 和 给 定 值 进 行 比 较 的 关 键 字 个 数 的 期 望 值 ni iiCPASL 1其 中 : n 为 表 长 ， Pi 为 查 找 表 中 第 i个 记 录 的 概 率 ， 且 Ci为 找 到 该 记 录 时 ， 曾 和 给 定 值 比 较 过 的 关 键 字 的 个 数11 ni iP 顺 序 表 查 找 的 平 均 查 找 长 度 为 ：对 顺 序 表 而 言 ， Ci = n-i+12111 1 n)i(nnASL nissASL = nP1 +(n-1)P2 + +2Pn-1+PnnPi 1在 等 概 率 查 找 的 情 况 下 ， 若 查 找 概 率 无 法 事 先 测 定 ， 则 查 找过 程 采 取 的 改 进 办 法 是 ， 在 每 次 查 找 之后 ， 将 刚 刚 查 找 到 的 记 录 直 接 移 至 表 尾的 位 置 上 。在 不 等 概 率 查 找 的 情 况 下 ， ASLss 在 Pn Pn-1 P2 P1时 取 极 小 值 上 述 顺 序 查 找 表 的 查 找 算 法 简 单 ， 但 平 均 查 找 长 度 较 大 ， 特 别 不 适 用于 表 长 较 大 的 查 找 表 。二 、 有 序 查 找 表 若 以 有 序 表 表 示 静 态 查 找 表 ， 则查 找 过 程 可 以 基 于 “ 折 半 ” 进 行 。 05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elem ST.length例 如 : key = 64 的 查 找 过 程 如 下low highmid low mid high midlow 指 示 查 找 区 间 的 下 界 ;high 指 示 查 找 区 间 的 上 界 ;mid = (low+high)/2。 int Search_Bin ( SSTable ST, KeyType kval ) low = 1; high = ST.length; / 置 区 间 初 值 while (low = high) mid = (low + high) / 2; if （ kval = ST.elemmid.key ) return mid; / 找 到 待 查 元 素 else if ( kval 50 时 ， 可 得 近 似 结 果 关 键 字 : A B C D E Pi: 0.2 0.3 0.05 0.3 0.15 Ci: 2 3 1 2 3三 、 静 态 查 找 树 表 在 不 等 概 率 查 找 的 情 况 下 ， 折 半 查 找不 是 有 序 表 最 好 的 查 找 方 法例 如 :此 时 ASL=20.2+30.3+10.05+20.3+30.15=2.4若 改 变 Ci的 值 2 1 3 2 3则 ASL=20.2+10.3+30.05+20.3+30.15=1.9 使 达 最 小 的 判 定 树 称 为 最 优 二 叉 树 ，其 中 : 111 ni iCiqni iCipASL 11 11 ni ini i qp 定 义 : 为 计 算 方 便 ， 令 wi = pi选 择 二 叉 树 的 根 结 点 ，使 达 最 小 111 ij jhij ji wwP介 绍 一 种 次 优 二 叉 树 的 构 造 方 法 :为 便 于 计 算 ， 引 入 累 计 权 值 和 ij ji wsw 1并 设 wl-1 = 0 和 swl-1 = 0， 11)( iilhi swswswswP则 推 导 可 得 j 0 1 2 3 4 5 6 7w j 0 2 1 5 3 4 3 5sw j p j key A B C D E F G 0 2 3 8 11 15 18 23例 如 : l h21 18 12 4 3 10 18h9 6 0 8 E21A h 5 3l G EC GA B D F所 得 次 优 二 叉 树 如 下 所 示 : 查 找 比 较 “ 总 次 数 ” = 32+41+25+33 +14+33+25 = 52 查 找 比 较 “ 总 次 数 ” = 32+21+35+13 +34+23+35 = 59和 折 半 查 找 相 比 较DBA C FE G Status SecondOptimal(BiTree T-data = Ri; / 生 成 结 点构 造 次 优 二 叉 树 的 算 法 if (i=low) T-lchild = NULL; / 左 子 树 空else SecondOptimal(T-lchild, R, sw, low, i-1); / 构 造 左 子 树 if (i=high) T-rchild = NULL; / 右 子 树 空 else SecondOptimal(T-rchild, R, sw, i+1, high); / 构 造 右 子 树 return OK; / SecondOptimal 次 优 查 找 树 采 用 二 叉 链 表 的 存 储 结 构Status CreateSOSTre(SOSTree else FindSW(sw, ST); / 按 照 有 序 表 ST 中 各 数 据 元 素 / 的 weight 值 求 累 计 权 值 表 SecondOpiamal(T, ST.elem, sw, 1, ST.length); return OK; / CreatSOSTree 四 、 索 引 顺 序 表在 建 立 顺 序 表 的 同 时 ， 建 立 一 个 索 引 。0 1 2 3 4 5 6 7 8 9 10 11 12 13 17 08 21 19 14 31 33 22 25 40 52 61 78 46 21 0 40 5 78 10 例 如 ：索 引 顺 序 表 = 索 引 + 顺 序 表顺 序 表索 引 typedef struct KeyType maxkey; int stadr;indexItem; / 索 引 项typedef struct indexItem *elem; int stadr;indexTable; / 索 引 表 索 引 顺 序 表 的 查 找 过 程 ：1） 由 索 引 确 定 记 录 所 在 区 间 ；2） 在 顺 序 表 的 某 个 区 间 内 进 行 查 找 。可 见 ， 索 引 顺 序 查 找 的 过 程 也 是 一 个“ 缩 小 区 间 ” 的 查 找 过 程 。 顺 序 表 有 序 表表 的 特 性 无 序 有 序存 储 结 构 顺 序 或 链 式 顺 序插 删 操 作 易 于 进 行 需 移 动 元 素ASL的 值 大 小对 比 顺 序 表 和 有 序 表 的 查 找 性 能 ： 索 引 顺 序 查 找 的 平 均 查 找 长 度 = 查 找 “ 索 引 ” 的 平 均 查 找 长 度 + 查 找 “ 顺 序 表 ” 的 平 均 查 找 长 度注 意 ： 索 引 可 以 根 据 查 找 表 的 特 点 来 构 造 。 ADT DynamicSearchTable 抽 象 数 据 类 型 动 态 查 找 表 的 定 义 如 下 ：数 据 对 象 D：数 据 关 系 R： 数 据 元 素 同 属 一 个 集 合 。D是 具 有 相 同 特 性 的 数 据元 素 的 集 合 。每 个 数 据 元 素 含 有 类 型 相同 的 关 键 字 ， 可 唯 一 标 识数 据 元 素 。 InitDSTable(InsertDSTable(DeleteDSTable(TraverseDSTable(DT, Visit();nextADT DynamicSearchTable 操 作 结 果 ：构 造 一 个 空 的 动 态 查 找 表 DT。InitDSTable( 销 毁 动 态 查 找 表 DT。DestroyDSTable(初 始 条 件 ： 操 作 结 果 ： 动 态 查 找 表 DT存 在 ； 若 DT 中 存 在 其 关 键 字 等 于 kval的 数 据 元 素 ， 则 函 数 值为 该 元 素 的 值 或 在 表 中 的 位置 ， 否 则 为 “ 空 ” 。SearchDSTable(DT, kval);初 始 条 件 ：操 作 结 果 ： 动 态 查 找 表 DT 存 在 ， kval为 和 关 键 字 类 型 相 同 的 给定 值 ； 动 态 查 找 表 DT 存 在 ， e 为 待 插 入 的 数 据 元 素 ；InsertDSTable(初 始 条 件 ：操 作 结 果 ： 若 DT 中 不 存 在 其 关 键 字等 于 e.key 的 数 据 元 素 ，则 插 入 e 到 DT。 动 态 查 找 表 DT存 在 ， kval为 和 关 键 字 类 型 相 同 的 给定 值 ；DeleteDSTable(初 始 条 件 ：操 作 结 果 ： 若 DT中 存 在 其 关 键 字 等于 kval的 数 据 元 素 ， 则 删除 之 。 动 态 查 找 表 DT存 在 ， Visit是 对 结 点 操 作 的 应 用 函 数 ；TraverseDSTable(DT, Visit();初 始 条 件 ：操 作 结 果 ： 按 某 种 次 序 对 DT的 每 个 结点 调 用 函 数 Visit() 一 次 且 至多 一 次 。 一 旦 Visit() 失 败 ，则 操 作 失 败 。 9.2 动 态 查 找 树 表 (n)(1)(n)(1)(nlogn)综 合 上 一 节 讨 论 的 几 种 查 找 表 的 特 性 ：查 找 插 入 删 除无 序 顺 序 表 无 序 线 性 链 表有 序 顺 序 表 有 序 线 性 链 表 静 态 查 找 树 表 (n)(n)(logn)(n)(logn) (1)(1)(n)(1)(nlogn) 1） 从 查 找 性 能 看 ， 最 好 情 况 能 达 (logn)， 此 时 要 求 表 有 序 ；2） 从 插 入 和 删 除 的 性 能 看 ， 最 好 情 况 能 达 (1)， 此 时 要 求 存 储 结 构 是 链 表 。可 得 如 下 结 论 ： 一 、 二 叉 排 序 树 （ 二 叉 查 找 树 ）二 、 二 叉 平 衡 树三 、 B - 树四 、 B+树五 、 键 树 一 、 二 叉 排 序 树（ 二 叉 查 找 树 ）1 定 义2 查 找 算 法3 插 入 算 法4 删 除 算 法5 查 找 性 能 的 分 析 （ 1） 若 它 的 左 子 树 不 空 ， 则 左 子 树 上 所 有 结 点 的 值 均 小 于 根 结 点 的 值 ；1 定 义 ： 二 叉 排 序 树 或 者 是 一 棵 空 树 ； 或 者是 具 有 如 下 特 性 的 二 叉 树 ：（ 3） 它 的 左 、 右 子 树 也 都 分 别 是 二 叉 排 序 树 。（ 2） 若 它 的 右 子 树 不 空 ， 则 右 子 树 上 所 有 结 点 的 值 均 大 于 根 结 点 的 值 ； 5030 8020 9010 8540352523 88例 如 : 是 二 叉 排 序 树 。66不 通 常 ， 取 二 叉 链 表 作 为二 叉 排 序 树 的 存 储 结 构typedef struct BiTNode / 结 点 结 构 struct BiTNode *lchild, *rchild; / 左 右 孩 子 指 针 BiTNode, *BiTree;TElemType data; 2 二 叉 排 序 树 的 查 找 算 法 ： 1） 若 给 定 值 等 于 根 结 点 的 关 键 字 ，则 查 找 成 功 ； 2） 若 给 定 值 小 于 根 结 点 的 关 键 字 ，则 继 续 在 左 子 树 上 进 行 查 找 ； 3） 若 给 定 值 大 于 根 结 点 的 关 键 字 ，则 继 续 在 右 子 树 上 进 行 查 找 。否 则若 二 叉 排 序 树 为 空 ， 则 查 找 不 成 功 ； 5030 8020 90854035 8832例 如 : 二 叉 排 序 树查 找 关 键 字= 50 , 35 , 90 , 95 , 从 上 述 查 找 过 程 可 见 ，在 查 找 过 程 中 ， 生 成 了 一 条 查 找 路 径 : 从 根 结 点 出 发 ， 沿 着 左 分 支 或 右 分 支逐 层 向 下 直 至 关 键 字 等 于 给 定 值 的 结 点 ;或 者 从 根 结 点 出 发 ， 沿 着 左 分 支 或 右 分 支逐 层 向 下 直 至 指 针 指 向 空 树 为 止 。 查 找 成 功 查 找 不 成 功 算 法 描 述 如 下 ：Status SearchBST (BiTree T, KeyType kval, BiTree f, BiTree / SearchBST 否 则 表 明 查 找 不 成 功 ， 返 回 / 指 针 p 指 向 查 找 路 径 上 访 问 的 最 后 一 个 结 点 ， / 并 返 回 函 数 值 为 FALSE, 指 针 f 指 向 当 前 访 问 / 的 结 点 的 双 亲 ， 其 初 始 调 用 值 为 NULL if (!T)else if ( EQ(kval, T-data.key) ) else if ( LT(kval, T-data.key) ) else p = f; return FALSE; / 查 找 不 成 功 p = T; return TRUE; / 查 找 成 功return SearchBST (T-lchild, kval, T, p ); / 在 左 子 树 中 继 续 查 找return SearchBST (T-rchild, kval, T, p ); / 在 右 子 树 中 继 续 查 找 f T设 key = 48 f Tf T22 pfT fT TTT f ffp 302010 40352523 根 据 动 态 查 找 表 的 定 义 ， “ 插 入 ”操 作 在 查 找 不 成 功 时 才 进 行 ;3 二 叉 排 序 树 的 插 入 算 法 若 二 叉 排 序 树 为 空 树 ， 则 新 插 入 的结 点 为 新 的 根 结 点 ； 否 则 ， 新 插 入的 结 点 必 为 一 个 新 的 叶 子 结 点 ， 其插 入 位 置 由 查 找 过 程 得 到 。 Status Insert BST(BiTree 否 则 ， 不 进 行 插 入 并 返 回 FALSE if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BST s = new BiTNode; / 为 新 结 点 分 配 空 间s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插 入 s 为 新 的 根 结 点else if ( LT(e.key, p-data.key) ) p-lchild = s; / 插 入 *s 为 *p 的 左 孩 子else p-rchild = s; / 插 入 *s 为 *p 的 右 孩 子return TRUE; / 插 入 成 功 （ 1） 被 删 除 的 结 点 是 叶 子 ； （ 2） 被 删 除 的 结 点 只 有 左 子 树 或 者 只 有右 子 树 ； （ 3） 被 删 除 的 结 点 既 有 左 子 树 ， 也 有 右子 树 。4 二 叉 排 序 树 的 删 除 算 法可 分 三 种 情 况 讨 论 ： 和 插 入 相 反 ， 删 除 在 查 找 成 功 之 后 进 行 ， 并且 要 求 在 删 除 二 叉 排 序 树 上 某 个 结 点 之 后 ， 仍然 保 持 二 叉 排 序 树 的 特 性 。 5030 8020 90854035 8832（ 1） 被 删 除 的 结 点 是 叶 子 结 点例 如 : 被 删 关 键 字 = 2088其 双 亲 结 点 中 相 应 指 针 域 的 值 改 为 “ 空 ” 5030 8020 90854035 8832（ 2） 被 删 除 的 结 点 只 有 左 子 树或 者 只 有 右 子 树 其 双 亲 结 点 的 相 应 指 针 域 的 值 改 为 “ 指 向 被 删 除 结 点 的 左 子 树 或 右 子 树 ” 。被 删 关 键 字 = 408 5030 8020 90854035 8832（ 3） 被 删 除 的 结 点 既 有 左 子 树 ， 也 有 右 子 树4 以 其 前 驱 替 代 之 ， 然后 再 删 除 该 前 驱 结 点被 删 结 点前 驱 结 点 被 删 关 键 字 = 50 Status DeleteBST (BiTree / 不 存 在 关 键 字 等 于 kval的 数 据 元 素 else / DeleteBST算 法 描 述 如 下 ： if ( EQ (kval, T-data.key) ) / 找 到 关 键 字 等 于 key的 数 据 元 素else if ( LT (kval, T-data.key) ) else Delete (T); return TRUE; return DeleteBST ( T-lchild, kval ); / 继 续 在 左 子 树 中 进 行 查 找return DeleteBST ( T-rchild, kval ); / 继 续 在 右 子 树 中 进 行 查 找 void Delete ( BiTree p = p-lchild; delete(q);pq q / 左 子 树 为 空 树 只 需 重 接 它 的 右 子 树q = p; p = p-rchild; delete(q);p pq q q = p; s = p-lchild;while (s-rchild) q = s; s = s-rchild; / s 指 向 被 删 结 点 的 前 驱/ 左 右 子 树 均 不 空p-data = s-data;if (q != p ) q-rchild = s-lchild; else q-lchild = s-lchild; / 重 接 *q的 左 子 树delete(s); pqs 5 查 找 性 能 的 分 析 对 于 每 一 棵 特 定 的 二 叉 排 序 树 ，均 可 按 照 平 均 查 找 长 度 的 定 义 来 求 它的 ASL 值 ， 显 然 ， 由 值 相 同 的 n 个 关键 字 ， 构 造 所 得 的 不 同 形 态 的 各 棵 二叉 排 序 树 的 平 均 查 找 长 度 的 值 不 同 ，甚 至 可 能 差 别 很 大 。 由 关 键 字 序 列 3， 1， 2， 5， 4构 造 而 得 的 二 叉 排 序 树由 关 键 字 序 列 1， 2， 3， 4， 5构 造 而 得 的 二 叉 排 序 树 ，例 如 ： 21 3 4 53 541 2ASL =（ 1+2+3+4+5） / 5 = 3ASL =（ 1+2+3+2+3） / 5 = 2.2 下 面 讨 论 平 均 情 况 : 不 失 一 般 性 ， 假 设 长 度 为 n 的 序 列 中 有 k 个 关 键 字 小 于 第 一 个 关 键 字 ， 则 必 有 n-k-1 个 关 键 字 大 于 第 一 个 关 键 字 ,由 它 构 造 的 二叉 排 序 树 n-k-1k的 平 均 查 找 长 度 是 n 和 k 的 函 数P(n, k) ( 0 k n-1 ) 假 设 n 个 关 键 字 可 能 出 现 的 n! 种 排 列的 可 能 性 相 同 ， 则 含 n 个 关 键 字 的 二 叉排 序 树 的 平 均 查 找 长 度 10 ),(1)( nk knPnnPASL ni ini ii CnCpknP 11 1),(在 等 概 率 查 找 的 情 况 下 ， R iL irootni i CCCnCnknP 11),( 1 )1)1()(1()1)(11 knPknkPkn )1()1()(11 knPknkPkn 由 此可 类 似 于 解 差 分 方 程 ， 此 递 归 方 程 有 解 ： CnnnnP log12)( 10 )1()1()(111)( nk knPknkPknnnP 112 )(21 nk kPkn 二 、 二 叉 平 衡 树 何 谓 “ 二 叉 平 衡 树 ” ？ 二 叉 平 衡 树 的 查 找 性 能 分 析 如 何 构 造 “ 二 叉 平 衡 树 ” 二 叉 平 衡 树 是 二 叉 查 找 树 的 另 一 种 形 式 ，其 特 点 为 ： 树 中 每 个 结 点 的 左 、 右 子 树 深 度之 差 的 绝 对 值 不 大 于 1 。例 如 : 1 RL hh54 82 54 821是 平 衡 树 不 是 平 衡 树 构 造 二 叉 平 衡 （ 查 找 ） 树 的 方 法 是 ：在 插 入 过 程 中 ， 采 用 平 衡 旋 转 技 术 。例 如 :依 次 插 入 的 关 键 字 为 5, 4, 2, 8, 6, 9542 42 5 86 65 842向 右 旋 转一 次 先 向 右 旋 转再 向 左 旋 转 42 65 8 9 42 6 8 95向 左 旋 转 一 次继 续 插 入 关 键 字 9 在 平 衡 树 上 进 行 查 找 的 过 程 和 二 叉排 序 树 相 同 ， 因 此 ， 查 找 过 程 中 和 给 定值 进 行 比 较 的 关 键 字 的 个 数 不 超 过 平 衡 树 的 深 度 。平 衡 树 的 查 找 性 能 分 析 ： 问 ： 含 n 个 关 键 字 的 二 叉 平 衡 树可 能 达 到 的 最 大 深 度 是 多 少 ？ n = 0空 树最 大 深 度 为 0 n = 1最 大 深 度 为 1 n = 2最 大 深 度 为 2n = 4最 大 深 度 为 3 n = 7 最 大 深 度 为 4先 看 几 个 具 体 情 况 : 反 过 来 问 ， 深 度 为 h 的 二 叉 平 衡 树 中所 含 结 点 的 最 小 值 Nh 是 多 少 ？h = 0 N0 = 0 h = 1h = 2 h = 3一 般 情 况 下 ， N1 = 1N2 = 2 N3 = 4Nh = Nh-1 + Nh-2 + 1利 用 归 纳 法 可 证 得 ， Nh = Fh+2 - 1 因 此 ， 在 二 叉 平 衡 树 上 进 行 查 找 时 ，查 找 过 程 中 和 给 定 值 进 行 比 较 的 关 键 字的 个 数 和 log(n) 相 当 。 由 此 推 得 ， 深 度 为 h 的 二 叉 平 衡 树中 所 含 结 点 的 最 小 值 Nh = h+2/5 - 1 反 之 ， 含 有 n 个 结 点 的 二 叉 平 衡 树 能达 到 的 最 大 深 度 hn = log(5 (n+1) - 2 三 、 B - 树1 定 义2 查 找 过 程3 插 入 操 作4 删 除 操 作5 查 找 性 能 的 分 析 1 B-树 的 定 义B-树 是 一 种 平 衡 的 多 路 查 找 树 ： root 50 15 71 84 3 8 20 26 43 56 62 78 89 96 在 m 阶 的 B-树 上 ， 每 个 非 终 端 结 点 可 能含 有 ： n 个 关 键 字 Ki（ 1 in） nm n 个 指 向 记 录 的 指 针 Di（ 1in） n+1 个 指 向 子 树 的 指 针 Ai（ 0in） ;多 叉 树 的 特 性 typedef struct BTNode int keynum; / 结 点 中 关 键 字 个 数 ， 结 点 大 小 struct BTNode *parent; / 指 向 双 亲 结 点 的 指 针 KeyType keym+1; / 关 键 字 （ 0号 单 元 不 用 ） struct BTNode *ptrm+1; / 子 树 指 针 向 量 Record *recptrm+1; / 记 录 指 针 向 量 BTNode, *BTree; / B树 结 点 和 B树 的 类 型B-树 结 构 的 C语 言 描 述 如 下 : 非 叶 结 点 中 的 多 个 关 键 字 均 自 小 至 大 有序 排 列 ， 即 ： K1 K2 keynum; i=Search(p, K); / 在 p-key1.keynum中 查 找 i ， p-keyi=Kkeyi+1 if (i0 else q=p; p=p-ptri; / q 指 示 p 的 双 亲 if (found) return (p,i,1); / 查 找 成 功 else return (q,i,0); / 查 找 不 成 功 在 查 找 不 成 功 之 后 ， 需 进 行 插 入 。显 然 ， 关 键 字 插 入 的 位 置 必 定 在 最 下层 的 非 叶 结 点 ， 有 下 列 几 种 情 况 ：3 插 入1） 插 入 后 ， 该 结 点 的 关 键 字 个 数 nsymbol 其 中 : p 指 向 双 链 树 中 某 个 结 点 ， 0 i K.num-1 初 始 状 态 : p=T-first; i = 0;若 ( p i+;若 ( p 若 ( p 3. Trie树 以 多 重 链 表 作 存 储 结 构 实 现 的 键 树结 点 结 构 :分 支 结 点 叶 子 结 点指 向 记 录的 指 针0 1 2 3 4 5 24 25 26 关 键 字指 向 下 层 结 点 的 指 针每 个 域 对 应 一 个 “ 字 母 ” 0 1(A) 3 4 5(E) 9(I) 268(H)4(D) 19(S) 22(V) 0 18(R) 7(G) 190 5(E)THAD HAS HAVE HE HER HEREHIGH HIS 叶 子 结 点分 支 结 点 指 向 记 录的 指 针 typedef struct TrieNode NodeKind kind; / 结 点 类 型 union struct KeyType K; Record *infoptr lf; / 叶 子 结 点 (关 键 字 和 指 向 记 录 的 指 针 ) struct TrieNode *ptr27; int num bh; / 分 支 结 点 (27个 指 向 下 一 层 结 点 的 指 针 ) TrieNode, *TrieTree; / 键 树 类 型结 点 结 构 的 C 语 言 描 述 : 在 Trie 树 中 查 找 记 录 的 过 程 :假 设 : T 为 指 向 Trie 树 根 结 点 的 指 针 ， K.ch0.K.num-1 为 待 查 关 键 字 (给 定 值 )。则 查 找 过 程 中 的 基 本 操 作 为 ： 搜 索 和 对 应 字 母 相 应 的 指 针 :若 p 不 空 ， 且 p 所 指 为 分 支 结 点 ，则 p = p-bh.Ptrord(K.Chi) ; ( 其 中 : 0 i K.num-1 ) 初 始 状 态 : p=T; i = 0;若 ( p i+;其 中 ， ord 为 求 字 符 在 字 母 表 中 序 号 的 函 数若 ( p 一 、 哈 希 表 是 什 么 ？二 、 哈 希 函 数 的 构 造 方 法三 、 处 理 冲 突 的 方 法 四 、 哈 希 表 的 查 找 五 、 哈 希 表 的 删 除 操 作 六 、 对 静 态 查 找 表 ， 。 。 。9.3 哈 希 表 以 上 两 节 讨 论 的 表 示 查 找 表 的 各 种 结 构的 共 同 特 点 ： 记 录 在 表 中 的 位 置 和 它 的 关键 字 之 间 不 存 在 一 个 确 定 的 关 系 ，一 、 哈 希 表 是 什 么 ？ 查 找 的 过 程 为 给 定 值 依 次 和 关 键 字 集合 中 各 个 关 键 字 进 行 比 较 ， 查 找 的 效 率 取 决 于 和 给 定 值 进 行 比 较的 关 键 字 个 数 。 用 这 类 方 法 表 示 的 查 找 表 ， 其平 均 查 找 长 度 都 不 为 零 不 同 的 表 示 方 法 ， 其 差 别 仅 在 于 ：关 键 字 和 给 定 值 进 行 比 较 的 顺 序 不同 。 只 有 一 个 办 法 ： 预 先 知 道 所 查 关 键字 在 表 中 的 位 置 ， 对 于 频 繁 使 用 的 查 找 表 ，希 望 ASL = 0。 即 ， 要 求 ： 记 录 在 表 中 位 置 和 其 关键 字 之 间 存 在 一 种 确 定 的 关 系 。 若 以 下 标 为 000 999 的 顺 序 表 表 示 之 。例 如 ： 为 每 年 招 收 的 1000 名 新 生 建 立一 张 查 找 表 ， 其 关 键 字 为 学 号 ， 其 值 的范 围 为 xx000 xx999 (前 两 位 为 年 份 )。则 查 找 过 程 可 以 简 单 进 行 ： 取 给 定 值（ 学 号 ） 的 后 三 位 ， 不 需 要 经 过 比 较便 可 直 接 从 顺 序 表 中 找 到 待 查 关 键 字 。 但 是 ， 对 于 动 态 查 找 表 而 言 ，因 此 在 一 般 情 况 下 ， 需 在 关 键 字 与 记 录在 表 中 的 存 储 位 置 之 间 建 立 一 个 函 数 关系 ， 以 f(key) 作 为 关 键 字 为 key 的 记 录在 表 中 的 位 置 ， 通 常 称 这 个 函 数 f(key) 为 哈 希 函 数 。1) 表 长 不 确 定 ；2) 在 设 计 查 找 表 时 ， 只 知 道 关 键 字 所 属 范 围 ， 而 不 知 道 确 切 的 关 键 字 。 Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei 例 如 ： 对 于 如 下 9 个 关 键 字设 哈 希 函 数 f(key) = (Ord(第 一 个 字 母 ) -Ord(A)+1)/2 0 1 2 3 4 5 6 7 8 9 10 1 12 13Chen ZhaoQianSunLi WuHan YeDei问 题 : 若 添 加 关 键 字 Zhou , 怎 么 办 ？能 否 找 到 另 一 个 哈 希 函 数 ？ 1) 哈 希 (Hash)函 数 是 一 个 映 象 ， 即 ： 将 关 键 字 的 集 合 映 射 到 某 个 地 址 集 合 上 ， 它 的 设 置 很 灵 活 ， 只 要 这 个 地 址 集 合 的 大 小 不 超 出 允 许 范 围 即 可 ;从 这 个 例 子 可 见 ，2) 由 于 哈 希 函 数 是 一 个 压 缩 映 象 ， 因 此 ，在 一 般 情 况 下 ， 很 容 易 产 生 “ 冲 突 ” 现象 ， 即 ： key1 key2， 而 f(key1) = f(key2)。 3) 很 难 找 到 一 个 不 产 生 冲 突 的 哈 希 函 数 。一 般 情 况 下 ， 只 能 选 择 恰 当 的 哈 希 函 数 ，使 冲 突 尽 可 能 少 地 产 生 。 因 此 ， 在 构 造 这 种 特 殊 的 “ 查 找 表 ” 时 ， 除 了 需 要 选 择 一 个 “ 好 ” (尽 可 能少 产 生 冲 突 )的 哈 希 函 数 之 外 ;还 需 要找 到 一 种 “ 处 理 冲 突 ” 的 方 法 。 哈 希 表 的 定 义 : 根 据 设 定 的 哈 希 函 数 H(key) 和 所 选 中的 处 理 冲 突 的 方 法 ， 将 一 组 关 键 字 映 象到 一 个 有 限 的 、 地 址 连 续 的 地 址 集 (区间 ) 上 ， 并 以 关 键 字 在 地 址 集 中 的 “ 象 ”作 为 相 应 记 录 在 表 中 的 存 储 位 置 ， 如 此构 造 所 得 的 查 找 表 称 之 为 “ 哈 希 表 ” 。 二 、 构 造 哈 希 函 数 的 方 法 对 数 字 的 关 键 字 可 有 下 列 构 造 方 法 : 若 是 非 数 字 关 键 字 ， 则 需 先 对 其 进 行数 字 化 处 理 。1. 直 接 定 址 法3. 平 方 取 中 法 5. 除 留 余 数 法4. 折 叠 法6. 随 机 数 法2. 数 字 分 析 法 哈 希 函 数 为 关 键 字 的 线 性 函 数 H(key) = key 或 者 H(key) = a key + b1. 直 接 定 址 法此 法 仅 适 合 于 ：地 址 集 合 的 大 小 = = 关 键 字 集 合 的 大 小 此 方 法 仅 适 合 于 ： 能 预 先 估 计 出 全 体 关 键 字 的 每 一 位 上各 种 数 字 出 现 的 频 度 。2. 数 字 分 析 法 假 设 关 键 字 集 合 中 的 每 个 关 键 字 都 是由 s 位 数 字 组 成 (u1, u2, , us)， 分 析 关键 字 集 中 的 全 体 ， 并 从 中 提 取 分 布 均 匀的 若 干 位 或 它 们 的 组 合 作 为 地 址 。 以 关 键 字 的 平 方 值 的 中 间 几 位 作 为 存储 地 址 。 求 “ 关 键 字 的 平 方 值 ” 的 目 的是 “ 扩 大 差 别 ” ， 同 时 平 方 值 的 中 间 各位 又 能 受 到 整 个 关 键 字 中 各 位 的 影 响 。3. 平 方 取 中 法 此 方 法 适 合 于 : 关 键 字 中 的 每 一 位 都 有 某 些 数 字 重 复出 现 频 度 很 高 的 现 象 。 将 关 键 字 分 割 成 若 干 部 分 ， 然 后 取 它们 的 叠 加 和 为 哈 希 地 址 。 有 两 种 叠 加 处理 的 方 法 ： 移 位 叠 加 和 间 界 叠 加 。4. 折 叠 法 此 方 法 适 合 于 : 关 键 字 的 数 字 位 数 特 别 多 。 5. 除 留 余 数 法 设 定 哈 希 函 数 为 : H(key) = key MOD p 其 中 ， pm (表 长 ) 并 且 p 应 为 不 大 于 m 的 素 数 或 是 不 含 20 以 下 的 质 因 子 给 定 一 组 关 键 字 为 : 12, 39, 18, 24, 33, 21，若 取 p=9, 则 他 们 对 应 的 哈 希 函 数 值 将 为 : 3, 3, 0, 6, 6, 3例 如 ：为 什 么 要 对 p 加 限 制 ？ 可 见 ， 若 p 中 含 质 因 子 3, 则 所 有 含 质 因子 3 的 关 键 字 均 映 射 到 “ 3 的 倍 数 ” 的 地址 上 ， 从 而 增 加 了 “ 冲 突 ” 的 可 能 。 6.随 机 数 法设 定 哈 希 函 数 为 : H(key) = Random(key)其 中 ， Random 为 伪 随 机 函 数 通 常 ， 此 方 法 用 于 对 长 度 不 等 的 关 键字 构 造 哈 希 函 数 。 实 际 造 表 时 ， 采 用 何 种 构 造 哈 希函 数 的 方 法 取 决 于 建 表 的 关 键 字 集 合的 情 况 (包 括 关 键 字 的 范 围 和 形 态 )，总 的 原 则 是 使 产 生 冲 突 的 可 能 性 降 到尽 可 能 地 小 。 三 、 处 理 冲 突 的 方 法 “处 理 冲 突 ” 的 实 际 含 义 是 ：为 产 生 冲 突 的 地 址 寻 找 下 一 个 哈 希 地 址1. 开 放 定 址 法2. 链 地 址 法 为 产 生 冲 突 的 地 址 H(key) 求 得 一 个地 址 序 列 ： H0, H1, H2, , Hs 1 sm-1其 中 ： H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, , s1. 开 放 定 址 法 对 增 量 di 有 三 种 取 法 ： 1) 线 性 探 测 再 散 列 di = c i 最 简 单 的 情 况 c=1 2) 平 方 探 测 再 散 列 di = 12, -12, 22, -22, , 3) 随 机 探 测 再 散 列 di 是 一 组 伪 随 机 数 列 或 者 d i=i H 2(key) (又 称 双 散 列 函 数 探 测 ) 即 ： 产 生 的 Hi 均 不 相 同 ， 且 所 产 生 的 s(m-1)个 Hi 值 能 覆 盖 哈 希 表 中 所 有 地 址 。 则 要 求 ： 注 意 ： 增 量 di 应 具 有 “ 完 备 性 ” 随 机 探 测 时 的 m 和 di 没 有 公 因 子 。 平 方 探 测 时 的 表 长 m 必 为 形 如 4j+3 的 素 数 （ 如 : 7, 11, 19, 23, 等 ） ； 例 如 : 关 键 字 集 合 19, 01, 23, 14, 55, 68, 11, 82, 36 设 定 哈 希 函 数 H(key) = key MOD 11 ( 表 长 =11 ) 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 1901 23 1455 68 1901 23 14 68若 采 用 线 性 探 测 再 散 列 处 理 冲 突若 采 用 二 次 探 测 再 散 列 处 理 冲 突11 82 3655 1182361 1 2 1 3 6 2 5 1 H 2(key) 是 另 设 定 的 一 个 哈 希 函 数 ，它 的 函 数 值 应 和 m 互 为 素 数 。若 m 为 素 数 ， 则 H 2(key) 可 以 是 1 至 m-1 之 间 的 任 意 数 ; 若 m 为 2 的 幂 次 ， 则 H 2(key) 应 是 1 至 m-1 之 间 的 任 意 奇 数 。例 如 ， 当 m=11时 ， 可 设 H2(key)=(3 key) MOD 10+1 0 1 2 3 4 5 6 7 8 9 10190123 14 5568 11 82 362 1 1 1 2 1 2 1 3 将 所 有 哈 希 地 址 相 同 的 记 录都 链 接 在 同 一 链 表 中 。 2. 链 地 址 法0123456 11 19 826855 14 36 01 23 ASL=(6 1+2 2+3)/9=13/9例 如 :同 前 例 的 关 键字 ， 哈 希 函 数 为 H(key)=key MOD 7 查 找 过 程 和 造 表 过 程 一 致 。 假 设 采 用开 放 定 址 处 理 冲 突 ， 则 查 找 过 程 为 : 四 、 哈 希 表 的 查 找 对 于 给 定 值 K, 计 算 哈 希 地 址 i = H(K)若 ri = NULL 则 查 找 不 成 功若 ri.key = K 则 查 找 成 功否 则 “ 求 下 一 地 址 Hi” ， 直 至 rHi = NULL (查 找 不 成 功 ) 或 rHi.key = K (查 找 成 功 ) 为 止 。 int hashsize = 997, . ; typedef struct ElemType *elem; int count; / 当 前 数 据 元 素 个 数 int sizeindex; / hashsizesizeindex为 当 前 容 量 HashTable;#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE -1/- 开 放 定 址 哈 希 表 的 存 储 结 构 - Status SearchHash (HashTable H, KeyType K, int / 求 得 哈 希 地 址while ( H.elemp.key != NULLKEY / 求 得 下 一 探 查 地 址 pif (EQ(K, H.elemp.key) return SUCCESS; / 查 找 成 功 ， 返 回 待 查 数 据 元 素 位 置 pelse return UNSUCCESS; / 查 找 不 成 功 Status InsertHash (HashTable if ( HashSearch ( H, e.key, p, c ) = SUCCESS ) return DUPLICATE; / 表 中 已 有 与 e 有 相 同 关 键 字 的 元 素else H.elemp = e