【精品数据结构】查找技术.ppt

《【精品数据结构】查找技术.ppt》由会员分享，可在线阅读，更多相关《【精品数据结构】查找技术.ppt（37页珍藏版）》请在三一文库上搜索。

1、第7章 查找技术 查找也叫检索，是根据给定的某个值，在表 中确定一个关键字等于给定值的记录或数据元素 关键字是数据元素中某个数据项的值，它可 以标识一个数据元素 查找方法评价 v查找速度 v占用存储空间多少 v算法本身复杂程度 v平均查找长度ASL(Average Search Length)：为确定 记录在表中的位置，需和给定值进行比较的关键字的 个数的期望值叫查找算法的 7.1 顺序查找 查找过程：从表的一端开始逐个进行记录的关键 字和给定值的比较 算法描述 Ch7_1.c i 例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88

2、 92 找64 64 iiii 比较次数=5 比较次数： 查找第n个元素： 1 查找第n-1个元素：2 . 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1 顺序查找方法的ASL 7.2 折半查找 查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现 v设表长为n，low、high和mid分别指向待查元素所在 区间的上界、下界和中点,k为给定值 v初始时，令low=1,high=n,mid=(low+high)/2 v让k与mid指向的记录比较 l若k=rmid.key，查找成功 l若krmid.key，则low=mid+1 v重复上述操

3、作，直至lowhigh时，查找失败 算法描述 lowhigh mid 例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找21 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 lowhighmid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 lowhighmid Ch7_2.c 例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low

4、high mid 找70 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 lowhighmid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high 11852 10741 93 6判

5、定树： 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 算法评价 v判定树：描述查找过程的二叉树叫 v有n个结点的判定树的深度为log2n+1 v折半查找法在查找过程中进行的比较次数最多不超过 其判定树的深度 v折半查找的ASL 7.3 分块查找 查找过程：将表分成几块，块内无序，块间有序 ；先确定待查记录所在块，再在块内查找 适用条件：分块有序表 算法实现 v用数组存放待查记录,每个数据元素至少含有关键字域 v建立索引表，每个索引表结点含有最大关键字域和指 向本块第一个结点的指针 算法描述 Ch7_3.c 1 2 3 4 5 6

6、 7 8 9 10 11 12 13 14 15 16 17 18 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53 22 48 86 1 7 13 索引表 查38 分块查找方法评价 ASL最大最小两者之间 表结构有序表、无序表 有序表分块有序表 存储结构顺序存储结构 线性链表 顺序存储结构 顺序存储结构 线性链表 查找方法比较 顺序查找折半查找 分块查找 二叉排序树 v定义：二叉排序树或是一棵空树，或是具有下列性质 的二叉树： l若它的左子树不空，则左子树上所有结点的值均小于它的根 结点的值 l若它的右子树不空，则右子树上所有结点的值均大

7、于或等于 它的根结点的值 l它的左、右子树也分别为二叉排序树 v二叉排序树的插入 l插入原则：若二叉排序树为空，则插入结点应为新的根结点 ；否则，继续在其左、右子树上查找，直至某个叶子结点的 左子树或右子树为空为止，则插入结点应为该叶子结点的左 孩子或右孩子 l二叉排序树生成：从空树出发，经过一系列的查找、插入操 作之后，可生成一棵二叉排序树 l 插入算法 例 10， 18， 3， 8， 12， 2， 7， 3 1010 18 10 18 3 10 18 3 8 10 18 3 8 12 10 183 8 12 2 10 183 8 12 2 7 10 18 3 8 12 2 7 3 中序遍历

8、二叉排序树可得到一个关键字的有序序列 Ch5_9.c v二叉排序树的删除 要删除二叉排序树中的p结点，分三种情况： lp为叶子结点，只需修改p双亲f的指针f-lchild=NULL f-rchild=NULL lp只有左子树或右子树 up只有左子树，用p的左孩子代替p (1)(2) up只有右子树，用p的右孩子代替p (3)(4) lp左、右子树均非空 u沿p左子树的根C的右子树分支找到S，S的右子树为空 ，将S的左子树成为S的双亲Q的右子树，用S取代p (5) u若C无右子树，用C取代p (6) S Q PL P 中序遍历：Q S PL P S QPL 中序遍历：Q S PL (2) S P

9、 PL Q 中序遍历：PL P S Q S PLQ 中序遍历：PL S Q (1) 中序遍历：P PR S Q S PRQ 中序遍历：PR S Q (3) S P PR Q 中序遍历：Q S P PR S QPR 中序遍历：Q S PR (4) S Q PR P F P CPR CLQ QL S SL 中序遍历：CL C QL Q SL S P PR F F S CPR CLQ QL SL 中序遍历：CL C QL Q SL S PR F (5) F P CPR CL 中序遍历：CL C P PR F F C PRCL 中序遍历：CL C PR F (6) l删除算法 例 80 50120 6

10、0 110 150 5570 53 删除50 80 60120 110 150 5570 53 删除60 80 55120 110 150 5370 10 425 813 5 4 删除10 8 425 513 4 删除5 8 425 413 Ch5_10.c 7.4 哈希查找 基本思想：在记录的存储地址和它的关键字之间 建立一个确定的对应关系；这样，不经过比较， 一次存取就能得到所查元素的查找方法 定义 v哈希函数在记录的关键字与记录的存储地址之间 建立的一种对应关系叫 l哈希函数是一种映象，是从关键字空间到存储地址空间的一 种映象 l哈希函数可写成：addr(ai)=H(ki) uai是表中

11、的一个元素 uaddr(ai)是ai的存储地址 uki是ai的关键字 关键字 集合 存储地址 集合 hash v哈希表应用哈希函数，由记录的关键字确定记录 在表中的地址，并将记录放入此地址，这样构成的表 叫 v哈希查找又叫散列查找，利用哈希函数进行查找 的过程叫 例 30个地区的各民族人口统计表 编号 地区别 总人口 汉族 回族. 1 北京 2 上海 . . 以编号作关键字， 构造哈希函数：H(key)=key H(1)=1 H(2)=2 以地区别作关键字，取地区 名称第一个拼音字母的序号 作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19 从例子

12、可见： l哈希函数只是一种映象，所以哈希函数的设定很灵活，只要 使任何关键字的哈希函数值都落在表长允许的范围之内即可 l冲突：key1key2，但H(key1)=H(key2)的现象叫 l同义词：具有相同函数值的两个关键字，叫该哈希函数的 l哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽 量减少；同时，冲突发生后，应该有处理冲突的方法 哈希函数的构造方法 v直接定址法 l构造：取关键字或关键字的某个线性函数作哈希地址，即 H(key)=key 或 H(key)=akey+b l特点 u直接定址法所得地址集合与关键字集合大小相等，不会 发生冲突 u实际中能用这种哈希函数的情况很少 v数字分

13、析法 l构造：对关键字进行分析，取关键字的若干位或其组合作哈 希地址 l适于关键字位数比哈希地址位数大，且可能出现的关键字事 先知道的情况 例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数 8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5 . . 分析： 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机 所以：取任意两位或两位 与另两位的叠加作哈希地址 v除留余数法

14、 l构造：取关键字被某个不大于哈希表表长m的数p除后所得余 数作哈希地址，即H(key)=key MOD p，pm l特点 u简单、常用，可与上述几种方法结合使用 up的选取很重要；p选的不好，容易产生同义词 v随机数法 l构造：取关键字的随机函数值作哈希地址，即 H(key)=random(key) l适于关键字长度不等的情况 v选取哈希函数，考虑以下因素： l计算哈希函数所需时间 l关键字长度 l哈希表长度（哈希地址范围） l关键字分布情况 l记录的查找频率 处理冲突的方法 v开放定址法 l方法：当冲突发生时，形成一个探查序列；沿此序列逐个地 址探查，直到找到一个空位置（开放的地址），将发

15、生冲突 的记录放到该地址中，即Hi=(H(key)+di)MOD m， i=1,2,k(km-1) 其中：H(key)哈希函数 m哈希表表长 di增量序列 l分类 u线性探测再散列：di=1,2,3,m-1 u伪随机探测再散列：di=伪随机数序列 例 表长为11的哈希表中已填有关键字为17，60，29的记录， H(key)=key MOD 11,现有第4个记录，其关键字为38， 按处理冲突的方法，将它填入表中 0 1 2 3 4 5 6 7 8 9 10 60 17 29 (1) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5+2) MOD 11

16、=7 冲突 H3=(5+3) MOD 11=8 不冲突 38 (2) H(38)=38 MOD 11=5 冲突 设伪随机数序列为9，则： H1=(5+9) MOD 11=3 不冲突 38 v链地址法 l方法：将所有关键字为同义词的记录存储在一个单链表中， 并用一维数组存放头指针 例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 用链地址法处理冲突 0 1 2 3 4 5 6 7 8 9 10 11 12 14 12779 6855 1984 20 2310 11 v哈希查找过程 给定k值 计算H(k)

17、此地址为空 关键字=k 查找失败 查找成功 按处理冲突 方法计算Hi Y N Y N l哈希查找过程仍是一个给定值与关键字进行比较的过程 l评价哈希查找效率仍要用ASL l哈希查找过程与给定值进行比较的关键字的个数取决于： u哈希函数 u处理冲突的方法 u哈希表的填满因子=表中填入的记录数/哈希表长度 1.线性探查法的性能分析 由于线性探查法解决冲突是线性地查找空闲位置的，平 均查找长度与表的大小m无关，只与所选取的散列函数H及装 填因子的值和该处理方法有关，这时的成功的平均查找长 度为ASL=1/2 (1+1/(1- ) 2.拉链法查找的性能分析 由于拉链法查找就是在单链表上查找，查找单链表

18、中第一个 结点的次数为1，第二个结点次数为2，其余依次类推。它的 平均查找长度ASL=1+/2 例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 哈希表长为m=16， 设每个记录的查找概率相等 (1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m H(55)=3 冲突，H1=(3+1)MOD16=4 冲突，H2=(3+2)MOD16=5 H(79)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 冲突，H4=(

19、1+4)MOD16=5 冲突，H5=(1+5)MOD16=6 冲突，H6=(1+6)MOD16=7 冲突，H7=(1+7)MOD16=8 冲突，H8=(1+8)MOD16=9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ASL=(1*6+2+3*3+4+9)/12=2.5 14 1 68 27 55 19 20 84 79 23 11 10 H(19)=6 H(14)=1 H(23)=10 H(1)=1 冲突，H1=(1+1) MOD16=2 H(68)=3 H(20)=7 H(84)=6 冲突，H1=(6+1)MOD16=7 冲突，H2=(6+2)MOD16=

20、8 H(27)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 H(11)=11 H(10)=10 冲突，H1=(10+1)MOD16=11 冲突，H2=(10+2)MOD16=12 (2) 用链地址法处理冲突 0 1 2 3 4 5 6 7 8 9 10 11 12 14 12779 6855 1984 20 2310 11 ASL=(1*6+2*4+3+4)/12=1.75 关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希查找算法实现 v用线性探测再散列法处理冲突 l实现 u查找过程：

21、同前 u删除：只能作标记，不能真正删除 u插入：遇到空位置或有删除标记的位置就可以插入 l算法描述： v用外链表处理冲突算法 Ch7_4.c Ch7_5.c 例给定关键字序列11，78，10，1，3，2，4，21， 试分别用顺序查找、二分查找、二叉排序树查找、 、散列查找(用线性探查法和拉链法)来实现查找，试 画出它们的对应存储形式(顺序查找的顺序表，二分 查找的判定树，二叉排序树查找的二叉排序树，两 种散列查找的散列表)，并求出每一种查找的成功平 均查找长度。散列函数H(k)=k%11。 顺序查找的顺序表（一维数组）如图1所示， 从图1可以得到顺序查找的成功平均查找长度为： ASL=(1+2

22、+3+4+5+6+7+8)/8=4.5； 二分查找的判定树（中序序列为从小到大排列的有序序 列）如图2所示， 从图2可以得到二分查找的成功平均查找长度为： ASL=(1+2*2+3*4+4)/8=2.625； 二叉排序树（关键字顺序已确定，该二叉排序树应唯一 ）如图 8-3所示， 从图3可以得到二叉排序树查找的成功平均查找长度为： ASL=(1+2*2+3*2+4+5*2)=3.125； 线性探查法解决冲突的散列表如图4所示， 从图4可以得到线性探查法的成功平均查找长度为： ASL=（1+1+2+1+3+2+1+8）/8=2.375； 拉链法解决冲突的散列表如图5所示。 从图5可以得到拉链法的成功平均查找长度为： ASL=(1*6+2*2)/8=1.25。