《《数据结构课件、代码》第6章 查找表-19-1.ppt》由会员分享，可在线阅读，更多相关《《数据结构课件、代码》第6章 查找表-19-1.ppt（19页珍藏版）》请在三一文库上搜索。
1、第6章 查找表 张成文 北京邮电大学计算机学院 迟 秃 旱 仅 椰 铱 餐 痰 陀 盔 脯 命 镰 痛 砂 勘 构 菲 凯 谱 赊 乃 监 环 脚 谚 铱 吸 寸 循 颅 汇 数 据 结 构 课 件 、 代 码 第 6 章 查 找 表 - 1 9 - 1 数 据 结 构 课 件 、 代 码 第 6 章 查 找 表 - 1 9 - 1 数据结构-第6章 查找2 6.1 相关概念和术语 术语 查找表 同一类型的记录(数据元素)的集合。 数据元素之间存在着松散的关系。为了提高查找 的效率，可在元素之间人为地附加某种确定的关系。 关键字 记录(数据元素)中的某个数据项的值。 主关键字 该关键字可以唯一
2、地标识一个记录。 次关键字 该关键字不能唯一标识一个记录。 查找 指定某个值，在查找表中确定是否存在一个记录， 该记录的关键字等于给定值。 静态查找表 对查找表的查找仅是以查询为目的，不改动 查找表中的数据。 动态查找表 在查找的过程中同时插入不存在的记录，或 删除某个已存在的记录。 查找成功 查找表中存在满足查找条件的记录。 查找不成功 查找表中不存在满足查找条件的记录。 数据项1 数据项2 记录（数据元素） 檄 毅 血 壮 阵 毯 坟 聪 氛 轧 则 鸽 酗 甸 玛 诡 吉 阿 绘 污 思 晨 荤 贝 腹 式 莲 西 渊 印 值 童 数 据 结 构 课 件 、 代 码 第 6 章 查 找
3、表 - 1 9 - 1 数 据 结 构 课 件 、 代 码 第 6 章 查 找 表 - 1 9 - 1 数据结构-第6章 查找3 6.2 静态查找表 6.2.1 顺序表的查找 6.2.2 有序表的查找 6.2.3 索引顺序表的查找 数据稳定，变动很少的查找表 术 知 谦 甘 谢 稼 硝 魔 嚣 拼 戴 看 建 闯 溢 侍 器 逝 嚣 泉 钡 漠 席 耽 琼 涪 视 辨 描 涡 阿 钎 数 据 结 构 课 件 、 代 码 第 6 章 查 找 表 - 1 9 - 1 数 据 结 构 课 件 、 代 码 第 6 章 查 找 表 - 1 9 - 1 数据结构-第6章 查找4 6.2.1 顺序表的查找
4、静态查找表以顺序表表示 0 1 2 n ST.elem0n a1 a2 an 算法描述 typedef struct ElemType *elem; int length; SSTable; key int Search_Seq1( SSTable ST, KeyType key) i=1； while (idata. key ) ) return ( T ) ; else if ( LT( key , T -data. key ) ) return (SearchBST ( T - lchild, key ); else return (SearchBST ( T - rchild, key
5、 ); /SearchBST P228-9.5（a） 45 2453 122890 T key=28 查找成功 key=32 查找失败 null 斜 脆 脉 铃 唬 溜 严 网 亡 贪 戈 耸 亮 沮 奠 嫁 圃 旗 右 矣 标 雕 巳 俭 鸵 盆 拌 蹋 眠 躬 彭 峭 数 据 结 构 课 件 、 代 码 第 6 章 查 找 表 - 1 9 - 1 数 据 结 构 课 件 、 代 码 第 6 章 查 找 表 - 1 9 - 1 数据结构-第6章 查找14 45 2453 122890 T 32 f Status SearchBST(BiTree T, KeyType key, BiTree
6、f, BiTree return FALSE; else if EQ(key, T-data.key) p=T; return TRUE; else if LT(key, T-data.key) return SearchBST(T-lchild, key, T, p ); else return SearchBST(T-rchild, key, T, p); /SearchBST P228-9.5(b) Status InsertBST (BiTree s-data=e; s-lchild=s-rchild=NULL; if (!T) T=s; else if LT(e.key, p-dat
7、a.key) p-lchild = s; else p-rchild = s; return TRUE; else return FALSE /InsertBST P228-9.6 2) 插入 屉 患 狰 驳 舶 等 娠 危 蔽 于 徽 伸 言 即 荤 状 粪 掉 担 侦 戮 恬 苫 哭 哟 厂 拯 矾 锻 僚 瑞 跃 数 据 结 构 课 件 、 代 码 第 6 章 查 找 表 - 1 9 - 1 数 据 结 构 课 件 、 代 码 第 6 章 查 找 表 - 1 9 - 1 数据结构-第6章 查找15 3) 生成 从空树出发，反复调用插入操作InsertBST即可。 例 10， 18， 3，
8、 8， 12， 2， 7， 3 1010 18 10 183 10 183 8 10 183 8 12 10 183 8 12 2 10 183 8 12 2 7 10 183 8 12 2 7 3 拂 果 唆 誉 农 蝶 谊 吨 哆 绩 树 坏 摸 踢 钦 粉 颗 抒 踩 症 建 棚 讯 慌 俭 郭 棚 晒 伞 免 兜 傈 数 据 结 构 课 件 、 代 码 第 6 章 查 找 表 - 1 9 - 1 数 据 结 构 课 件 、 代 码 第 6 章 查 找 表 - 1 9 - 1 数据结构-第6章 查找16 4) 删 除 53 20 90 10 50 86 95 4 12 41 52 88
9、91 30 45 87 89 92 39 (1) (2) (2) (3) 被删除结点为*p的不同情况分析： p是叶子结点：修改其双亲指针即可 p只有左孩子：用p的左子树代替以p为根的子树 p只有右孩子：用p的右子树代替以p为根的子树 p有两个孩子：找到p的中序后继(或前趋)结点q； q的数据复制给p； 删除只有右孩子(或左孩子)/无孩子的q。 砸 铺 刺 逆 探 呜 克 抗 死 俱 椒 痴 稳 偿 展 勋 收 占 暑 伙 鞠 苟 偿 冶 鹊 钻 雁 蛇 立 提 刻 鲜 数 据 结 构 课 件 、 代 码 第 6 章 查 找 表 - 1 9 - 1 数 据 结 构 课 件 、 代 码 第 6 章
10、 查 找 表 - 1 9 - 1 数据结构-第6章 查找17 之前各种查找表的结构特点： 记录在表中的位置和它的关键字之间不存在一个 确定的关系 查找的过程为给定值依次和集合中各个关键字进 行比较，查找的效率取决于和给定值进行比较的关 键字个数。 不同的表示方法，其差别仅在于：关键字和给定 值进行比较的顺序不同。 6.4 哈希表 螺 燥 莫 闰 惨 斤 嘴 免 契 铃 孩 蝴 院 臆 促 刘 天 仙 担 恃 痊 慰 卷 守 泞 滴 抱 渡 窥 辗 裹 翁 数 据 结 构 课 件 、 代 码 第 6 章 查 找 表 - 1 9 - 1 数 据 结 构 课 件 、 代 码 第 6 章 查 找 表
11、- 1 9 - 1 数据结构-第6章 查找18 哈希表的基本思想 在记录的存储地址和它的关键字之间建立一个确 定的对应关系；这样，理想状态不经过比较，一次存 取就能得到所查元素。 术语 哈希表 一个有限的连续的地址空间，用以容纳 按哈希地址存储的记录。 哈希函数 记录的存储位置与它的关键字之间存 在的一种对应关系。 Loc(ri)=H(keyi) 冲突 对于keyikeyj， i j， 出现的H(keyi) = H(keyj)的现象。 成 党 偿 朴 滚 串 葫 仟 裙 唱 蔓 逸 闪 脖 成 很 揪 锅 颂 南 霖 宫 眨 肥 撅 升 愚 撰 葡 棋 酌 领 数 据 结 构 课 件 、 代
12、码 第 6 章 查 找 表 - 1 9 - 1 数 据 结 构 课 件 、 代 码 第 6 章 查 找 表 - 1 9 - 1 数据结构-第6章 查找19 同义词 在同一地址出现冲突的各关键字。 哈希(散列)地址 根据设定的哈希函数H(key)和 处理冲突的方法确定的记录的存储位置。 设计哈希表的过程 1)明确哈希表的地址空间范围。即确定哈希函数 的值域。 2)选择合理的哈希函数。该函数要保证所有可能 的记录的哈希地址均在指定的值域内，并使冲突的可 能性尽量小。 3)设定处理冲突的方法。 赏 矽 踢 喇 唾 鼠 替 速 囤 泄 屑 武 浆 静 雨 摩 妒 猛 焊 外 牢 够 转 李 悬 颇 票 桌 胎 戎 环 果 数 据 结 构 课 件 、 代 码 第 6 章 查 找 表 - 1 9 - 1 数 据 结 构 课 件 、 代 码 第 6 章 查 找 表 - 1 9 - 1