数据结构中查找的学习

第九章查找数据结构主讲：岳静

2第九章查找9.1静态查找表及查找算法顺序查找折半查找9.3哈希表及查找算法3几个基本概念查找表关键字查找静态查找动态查找由同一类型的数据元素（或记录）构成的集合只查找，不改变数据元素集合内的数据元素既查找，又改变（增减）集合内的数据元素记录中某个数据项的值，可用来识别一个记录查找成功→若表中存在特定元素，称查找成功查找不成功4几个基本概念(续)查找算法的性能查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。用比较次数的平均值来评估算法的优劣。平均查找长度ASL(AverageSearchLength)å=×=niPiASL1Ci5几个基本概念(续)ASL值越小，时间效率越高请同学们思考，如何利用ASL的结果判定查找算法的优劣å=×=niPiASL1Ci6静态查找表1顺序表查找2有序表查找9.2.1顺序查找法顺序查找法的特点是：用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。

212569102246√81顺序查找约定从表中最后一个记录开始查找，逐个将记录的关键字和给定值进行比较若存在某记录的关键字等于给定值查找成功：查找失败：

直至第一个记录，关键字都不与给定值相等9不设置监视哨的顺序查找算法intSeqSearch（RecordListl,KeyTypek）/*不用监视哨法，在顺序表中查找关键字等于k的元素*/{i=l.length;while(i>=1&&l.r[i].key!=k)i--;if(i>=1)return（i）elsereturn(0);}循环条件i>=1判断查找是否越界。设置哨岗2125691022466111顺序查找(续)算法9.1intSearch_Seq(SStableST,KeyTypekey){

ST.elem[0].key=key;for(i=ST.length;!EQ(ST.elem[i].key,key);--i);returni;}哨兵相对于传统顺序查找算法有何优势？顺序表给定值intSearch_Seq(SStableST,KeyTypekey){for(i=ST.length;i>=1;--i);if(EQ(ST.elem[i].key,key))break;returni;}121顺序查找(续)算法性能分析å=×=niPiASL1Ci假设n=ST.length，每个记录查找的概率相等查找成功ASL=(n+1)/2131顺序查找(续)当表中查找记录的概率不相同时，如何考虑提高顺序查找的效率？将记录按查找概率进行排序，将查找概率高的排在最靠近开始查找的一端141顺序查找(续)顺序查找算法的特点算法简单适应面广效率低152有序表查找折半查找(BinarySearch)51319213756请同学回忆折半查找(二分法)的查找算法查找给定值5616折半查找的算法开始Low=1High=l.lengthLow<=highMid=(low+high)/2k==l.r[mid].keyReturnmidYYReturn0Nk<l.r[mid].keyNHigh=mid-1low=mid+1YN17折半查找算法5131921375619193737565621513描述查找过程的判定树查找成功时比较的次数<=判定树的深度查找不成功的比较次数？18外部结点(5,13)(13,19)折半查找算法5131921375619193737565621513查找成功时比较的次数查找不成功的比较次数<=判定树的深度<5(19,21)(21,37)(37,56)>5619折半查找算法(续)ASL假设记录个数为n=2h-1折半查找的判定树为深度为h的满二叉树假设每个记录的查找概率相同h

表示二叉树的深度j

表示当前层次/查找过程中比较的次数20折半查找算法(续)特点查找效率较顺序查找高但只适合有序表，且限于顺序存储结构是否任何情况下都可用折半查找方法?哈希表基本思想建立关键字与其存储位置的对应关系，或者说，由关键字的值决定数据的存储地址。优点查找速度极快O(1)，查找效率与元素个数无关！22哈希表(续)例1：若将学生信息按如下方式存入计算机，如：将2001011810201的所有信息存入V[01]单元；将2001011810202的所有信息存入V[02]单元；

……

将2001011810231的所有信息存入V[31]单元。欲查找学号为2001011810216的信息，便可直接访问V[16]！23哈希表(续)

有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H(k)＝k，请画出存储结构图。H(k)称为散列函数解：根据散列函数H（k）＝k，可知元素14应当存入地址为14的单元，元素23应当存入地址为23的单元，……，对应散列存储表（哈希表）如下：地址…9…11…14…232425…39…内显缺点：空间效率低24哈希表(续)哈希函数的构造方法直接定址法数字分析法折叠法除留余数法随机法…哈希表：根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表就称为哈希表，这一映像过程称为哈希造表或散列，所得地址为哈希地址或散列地址。25哈希函数的构造方法直接定址法Hash(key)=a·key+b(a、b为常数)优点：以关键字key的某个线性函数值为哈希地址，不会产生冲突.缺点：要占用连续地址空间，空间效率低。26哈希函数的构造方法数字分析法特点：选用关键字的某几位组合成哈希地址。选用原则是：各种符号在该位上出现的频率大致相同。2734705243491487348269634852703486305349805834796713473919例：有一组（例如80个）关键字，其样式如下：讨论：①第1、2位均是“3和4”，第3位也只有“

7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。位号：①②③④⑤⑥⑦②若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。数字分析法（举例）28哈希函数的构造方法除留余数法Hash(key)=keymodp(设哈希表长度为m)特点：以关键字除以p的余数作为哈希地址。关键：如何选取合适的m？技巧：取p≤m且为质数（一般取不大于m的最大质数）29哈希表(续)有6个元素的关键码分别为：（14，23，39，9，25，11）。选取关键码与元素位置间的函数为H(k)=kmod7通过哈希函数对6个元素建立哈希表：253923914110123456例有冲突！30哈希表(续)冲突的解决冲突不可避免，只能尽可能减少1构造一个较好的哈希函数函数简单，以便提高转换速度所选函数对关键字计算出的地址，应在哈希表中并大致均匀分布，以减少空间浪费2制定一个较好的解决冲突的方案31哈希表(续)哈希冲突的解决方法开放定址法（开地址法）链地址法（拉链法）再哈希法（双哈希函数法）建立一个公共溢出区32哈希冲突的解决方法1开放定址法（开地址法）设计思路：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。33具体实现：Hi=(Hash(k)+di)modm(1≤i<m)

其中：

Hash(k)为哈希函数

m为哈希表长度

di

为增量序列1，2，…m-1

（1）线性探测法含义：一旦冲突，就找附近（下一个）空地址存入。开放定址法（开地址法）34关键码集为{47，7，29，11，16，92，22，8，3}，设：哈希表表长为m=11；哈希函数为Hash(key)=keymod11；拟用线性探测法处理冲突。建哈希表如下：012345678910291116922283例47735线性探测法的优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素；线性探测法的缺点：可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。解决方案：可采用二次探测法或伪随机探测法，以改善“堆积”问题。讨论：36仍举上例，改用二次探测法处理冲突，建表如下：012345678910112234792167298△▲△△注：只有3这个关键码的冲突处理与上例不同，Hash(3)=3，哈希地址上冲突，由H1=(Hash(3)+12)mod11=4，仍然冲突；H2=(Hash(3)-12)mod

11=2，找到空的哈希地址，存入。（2）二次探测法Hi=(Hash(k)±di)modm其中：Hash(k)为哈希函数

di为增量序列

12，-12，22，-22，…37哈希冲突的解决方法2链地址法（拉链法）基本思想：将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。38

设{47,7,29,11,16,92,22,8,3,50,37,89}的哈希函数为：Hash(key)=keymod11，用拉链法处理冲突，则建表如右图所示。

例：

01234567891022118934737922971650810有冲突的元素可以插在表尾,也可以插在表头。链地址法（拉链法）39哈希冲突的解决方法3再哈希法（双哈希函数法）Hi=RHi(key)i=1,2,…，kRHi均是不同的哈希函数，当产生冲突时就计算另一个哈希函数，直到冲突不再发生。优点：不易产生聚集；缺点：增加了计算时间。40哈希冲突的解决方法4建立一个公共溢出区思路：除设立哈希基本表外，另设立一个溢出向量表。 所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的地址是什么，一旦发生冲突，都填入溢出表。41哈希表的查找及分析明确：散列函数没有“万能”通式，要根据元素集合的特性而分别构造。讨论：哈希查找的速度是否为真正的O（1）？不是。由于冲突的产生，使得哈希表的查找过程仍然要进行比较，仍然要以平均查找长度ASL来衡量。一般地，ASL依赖于哈希表的装填因子,它标志着哈希表的装满程度。装填因子：哈希表中已经被占用的空间（哈希表中的记录数）与哈希表整个空间（哈希表的长度）的比。即：0≤≤1越大，表中记录数越