6 查找

DotNetWalker 计算机考研资料 - 数据结构 1 k 10 15 24 6 12 35 40 98 55 64 0 1 2 3 4 5 6 7 8 9 i 查找方向 图 7-1 顺序查找示意 图 哨兵 [ r1 … … … rmid-1 ] rmid [ rmid+1 … … … rn ] （mid=(1+n)/2） 如果 krmid 查找右半区 图 7-2 折半查找的基本思想图解 k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 图 7-3 折半查找成功情况下的查找过程 high=13 设置初始区间 mid=7 high=6 low=1 查找区间为[1, 13] 取中点 mid=7 比较 r[7]与 k，将查找调整到左半区 mid=2 mid=3 low=1 high=2 查找区间为[1, 6] 取中点 mid=3 比较 r[3]与 k，将查找调整到左半区 mid=1 low=high=2 查找区间为[1, 2] 取中点 mid=1 比较 r[1]与 k，将查找调整到右半区 查找区间为[2, 2] 取中点 mid=2 比较 r[2]与 k，查找成功，返回 mid 的位置 2 low=1 DotNetWalker 计算机考研资料 - 图解数据结构 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 图 7-4 折半查找不成功情况下的查找过程 low=1 high=13 设置初始区间 high=4 low=5 mid=7 high=6 low=1 mid=3 low=4 high=6 mid=5 low=high=4 mid=4 查找区间为[1, 13] 取中点 mid=7 比较 r[7]与 k，将查找调整到左半区 查找区间为[1, 6] 取中点 mid=3 比较 r[3]与 k，将查找调整到右半区 查找区间为[4, 6] 取中点 mid=5 比较 r[5]与 k，将查找调整到左半区 查找区间为[4, 4] 取中点 mid=4 比较 r[4]与 k，将查找调整到右半区 查找区间为空，查找失败， 返回查找失败信息 0 10 8 5 3 1 9 11 6 4 7 2 －1 1－2 2－3 3－4 4－5 10－11 11－ 9－10 8－9 7－8 5－6 6－7 图 7-5 具有 11 个结点的判定树 (a) 按 63,55,90,58,70,42,10,45,83,67 (b) 按 55,42,10,70,63,58,83,67,90,45 的顺序构造的二叉排序树 的顺序构造的二叉排序树 图 7-6 二叉排序树示例 58 42 70 90 63 45 55 83 67 10 10 42 83 63 70 55 45 42 67 58 90 DotNetWalker 计算机考研资料 - 图解数据结构 3 (a) 二叉排序树 (b) 插入 98 后的二叉排序树 图 7-7 二叉排序树的插入示例 58 70 90 63 55 58 70 90 63 55 98 (a) 插入 63 (b) 插入 90 (c) 插入 70 (d) 插入 55 (e) 插入 67 (f) 插入 42 (g) 插入 98 图 7-8 从空树开始建立二叉排序树的过程 63 63 90 70 90 63 70 90 63 55 70 90 63 55 67 70 90 63 55 67 42 70 90 63 55 67 42 98 图 7-9 在二叉排序树中删除值最小的结点 s 10 5 21 9 f p fL f 图 7-10 在二叉排序树中删除叶子结点 fL DotNetWalker 计算机考研资料 - 图解数据结构 4 p f f p fR pL f f (a) 结点 p 只有左子树 (b) 结点 p 只有右子树 图 7-11 在二叉排序树中删除只有一个子树的结点 pL fR pR fR fR pR fR f p pL s (a) 一般情况 75 47 60 50 70 55 fR f p pL 75 50 60 55 70 (b) 特殊情况：p 的右孩子即是 pR中最小值结点 图 7-12 在二叉排序树中删除具有两个子树的结点 fR f p pL s 75 47 50 70 fR f p pL 75 50 70 DotNetWalker 计算机考研资料 - 图解数据结构 5 (a) 平衡二叉树 (b) 非平衡二叉树 图 7-13 平衡二叉树示例 2 0 0 0 0 1 -1 0 0 1 0 0 0 0 (a) (b) (c) 图 7-14 RR 型调整的例子 20 35 40 20 35 35 40 20 35 40 20 15 30 35 40 20 15 30 25 (a) 平衡状态 (b) 出现不平衡 30 35 20 15 40 25 35 40 30 20 15 25 (c) 第 1 次旋转 (d) 第 2 次旋转 图 7-15 LR 型调整的例子 DotNetWalker 计算机考研资料 - 图解数据结构 6 (a) 插入前 (b) 插入后，调整前 (c) 调整后 图 7-16 LL 型调整 x 1 BL h A B BR h 0 AR h 2 BL h A B BR h 1 AR h BL h B h AR A BR h 0 0 x 0 (a) 插入前 (b) 插入后，调整前 (c) 调整后 图 7-17 RR 型调整 x AL h A h BR B BL h 0 -1 AL h A h BR B BL h -1 -2 AL h B h+1 BR A BL h x 0 0 BL h BL B h-1 CR C CL h-1 h AR A x 1 2 -1 (a) 插入后，调整前 (b) 先逆时针旋转 (c) 再顺时针旋转 图 7-18 LR 型调整 h C h-1 CR B C CL h-1 h AR A x BL C CR B C CL h-1 h AR A x h-1 h 0 -1 (a) 插入后，调整前 (b) 先顺时针旋转 (c) 再逆时针旋转 图 7-19 RL 型调整 AL C CR A C CL h-1 h BR B x h-1 h 0 1 h BR B h-1 CR C CL h-1 h AL A x 1 -2 -1 h BR B h-1 CR C CL h-1 h AL A x 0 DotNetWalker 计算机考研资料 - 图解数据结构 7 (a) 插入 20 平衡 20 35 40 20 35 35 40 20 20 旋转 (b) 插入 35 平衡 (c) 插入 40 不平衡，RR 型调整 (c) 插入 40 不平衡，RR 型调整 -1 0 0 -1 -2 0 0 0 35 40 20 15 (d) 插入 15 平衡 0 1 1 0 35 40 20 15 30 (e) 插入 30 平衡 0 0 0 0 1 0 0 25 30 35 20 15 40 (g) 插入 38 不平衡，RL 型，需旋转两次 图 7-20 平衡二叉树构造过程示例 38 25 30 35 20 15 38 40 25 30 38 20 15 40 35 旋转 旋转 0 0 0 0 0 0 0 0 0 -1 -2 2 0 0 0 25 35 40 20 15 30 25 35 40 30 20 15 25 30 35 20 15 40 (f) 插入 25 不平衡，LR 型，需旋转两次 旋转 旋转 0 0 0 0 0 -1 -1 1 图 8-21 散列的基本思想示意图 关 键 码 集 合 k i ri H(k i) … … … … 散列函数 H DotNetWalker 计算机考研资料 - 图解数据结构 8 0 1 2 3 4 5 6 7 8 9 10 11 22 47 92 16 3 7 29 8 关键码 14 21 28 35 42 49 56 散列地址 14 0 7 14 14 7 14 10 30 50 70 80 90 0 1 2 3 4 5 6 7 8 9 图 7-22 用直接定址法构造的散列

表

关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf

图 7-23 p=21 的散列地址示例 (a) 关键码(第一行是关键码的位数) (b) 关键码及对应的散列地址 图 7-24 数字分析法示例 ① ② ③ ④ ⑤ ⑥ ⑦ 3 4 7 0 5 2 4 3 4 8 2 6 9 6 3 4 8 5 2 7 0 3 4 8 6 3 0 5 3 4 9 8 0 5 8 3 4 7 9 6 7 1 3 4 7 3 9 1 9 关键码 散列地址 3 4 7 0 5 2 4 24 3 4 8 2 6 9 6 96 3 4 8 5 2 7 0 70 3 4 8 6 3 0 5 05 3 4 9 8 0 5 8 58 3 4 7 9 6 7 1 71 3 4 7 3 9 1 9 19 253 364 587 + 50 ─── 1254 H(key)=254 (b) 间界叠加 253 463 587 + 05 ─── 1308 H(key)=308 (a) 移位叠加 图 7-25 折叠法示例 图 7-26 线性探测法构造的闭散列表 DotNetWalker 计算机考研资料 - 图解数据结构 9 图 7-27 二次探测法构造的闭散列表 11 22 3 47 92 16 7 29 8 0 1 2 3 4 5 6 7 8 9 10 ∧ ∧ ∧ ∧ ∧ 0 1 2 3 4 5 6 7 8 9 10 22 3 11 ∧ 47 ∧ 92 ∧ 16 ∧ 29 7 ∧ 8 ∧ 图 7-28 拉链法处理冲突时的散列表 11 47 92 16 7 8 0 1 2 3 4 5 6 7 8 9 10 29 22 3 (a) 基本表 (b) 溢出表 图 7-29 公共溢出区方法处理冲突示例 0 1 2 3 4 5 6 7 8 9 10 DotNetWalker 计算机考研资料 - 图解数据结构 10 P' Q P B' A B B Q' (a) 一条河、两城市 A 和 B 以及城市间的一条道路 (b) A 和 B 之间的最短路径 AP-PQ-QB 图 7-30 问

题

快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题

描述及解答示意图 A