数据结构查找.ppt

《数据结构查找.ppt》由会员分享，可在线阅读，更多相关《数据结构查找.ppt（54页珍藏版）》请在课桌文档上搜索。

1、2023年3月2日,1,8.1 基本概念与术语 8.2 静态查找表 8.3 动态查找表 8.4 哈希表查找 8.5 小结与习题,第八章 查找,本章主要内容,本章主要学习静态查找和动态查找方法。静态查找包括顺序查找、二分查找和分块索引查找等，动态查找包括二叉排序树、B树等。作为重点内容本章还介绍了哈希查找及相关知识。查找是数据结构中的重要操作，好的查找方法会大大提高执行效率。通过本章学习，应掌握以下内容：查找的有关概念；静态查找；动态查找；哈希查找。,2023年3月2日,2,2023年3月2日,3,8.1 基本概念与术语,查找就是指在给定的一组数据中对某个数值进行查询的过程。关键字是数据元素（或

2、记录）中某个项或组合项的数值，它可以标识一个数据元素或记录。主关键字将能唯一确定一个数据元素（或记录）的关键字。查找表是由具有相同类型的数据元素（或记录）组成的集合。分为静态查找表和动态查找表两大类。,如果查找表中能够找到满足条件的记录，称为查找成功，否则称为查找不成功。,2023年3月2日,4,静态查找表：在对查找表进行操作时，不改变表的结构，只进行查找操作；动态查找表：在对查找表进行操作时，可以改变该查找表的结构，既可以进行查找操作，又可以进行插入、删除等操作。,8.2 静态查找表,8.2.1 静态查找表结构 静态查找表是由数据元素组成的线性表。其存储结构分为顺序存储和链式存储两种。可以用

3、顺序表或线性链表来表示静态查找表。,2023年3月2日,5,8.2.1 静态查找表结构,typedef int KeyType;typedef struct KeyType key;ElemType;typedef struct ElemType elemMAXSIZE+1；int length；SST；,typedef struct NODE ElemType data；/*结点的数据域*/struct NODE*next；/*指针域*/NodeType；,静态查找表的顺序存储结构定义,静态查找表的链式存储结构定义,2023年3月2日,6,8.2.2 顺序查找 顺序查找又称线性查找，它思路简

4、单、容易实现，是一种最基本的查找方法。其查找过程为：从查找表的一端开始，逐个进行关键字与查找值的比较，若某个记录的关键字值与给定值相等，则查找成功，给出数据元素在查找表中的位置；若将整个表查找完，仍未找到与给定值相同的关键字，则查找失败，给出提示信息。,2023年3月2日,7,【算法8.1】顺序查找int Search_Seq(SST ST，KeyType x)ST.elem0.key=x;/*设置监护哨*/i=ST.length;while(ST.elemi.key!=x)i-;/*返回找到记录的下标或者0(查找不成功)*/return i;/*Search_Seq*/,将查找过程中给定值和

5、关键字比较的次数称为查找长度。通常用平均查找长度ASL来衡量查找算法的优劣。,算法分析：,2023年3月2日,8,平均查找长度：在查找成功时，平均查找长度ASL是指为确定数据元素在表中位置所进行关键字比较次数的期望值。对一个含n个数据元素的表，查找成功时,Pi为表中第i个数据元素的查找概率，Ci为表中第i个数据元素的关键字与给定值x相等时，需要比较的次数。,设查找表长度为n，查找元素x和表中第i个元素关键字相等时，需要比较的次数为n-i+1，则平均查找长度为：,2023年3月2日,9,设查找表中各元素的查找概率相等，即 Pi=1/n，则上面的式子表示为：,当查找成功时，顺序查找的时间复杂度就是

6、O(n)。当查找失败时，关键字与给定值的比较次数总是n+1次。,8.2.3二分查找 二分查找，也称为折半查找，是对有序表进行的一种高效率的线性查找。有序表是指数据元素按给定的关键字已经是升序（或者是降序）的查找表。,2023年3月2日,10,假设各记录的关键字是由小到大排序的，算法的实现过程为：在待查找的有序表中，将中间元素首先与给定值进行比较，若相等，则表示查找成功；若给定值小于中间元素的关键字，则在左边的区域中继续查找；若给定值大于中间元素的关键字，则在右边的区域中继续查找。重复上述过程，直到查找成功或者查找失败，查找的过程随之结束。,例在给定的序列A=6，13，17，20，24，28，3

7、0，36，39，44，48，51，55中查找给定值13和52这两个数据。查找关键字为13的过程,2023年3月2日,11,第一次 low=1 mid=7 high=13因x30，下一步继续在左半区查找，即：,0 1 2 3 4 5 6 7 8 9 10 11 12 13,第二次 low=1 mid=3 high=6因x17，下一步继续在左半区查找，即：,0 1 2 3 4 5 6 7 8 9 10 11 12 13,2023年3月2日,12,因x6，下一步继续在右半区查找。此时，low=2,high=2,mid=(2+2)/2=2。由于x=13,查找成功，所找到的记录序号为2。,查找关键字为5

8、2的过程,第一次 low=1 mid=7 high=13因x30，下一步继续在右半区查找，即：,0 1 2 3 4 5 6 7 8 9 10 11 12 13,第二次 low=8 mid=10 high=13 因x44，下一步继续在右半区查找，即：,0 1 2 3 4 5 6 7 8 9 10 11 12 13,2023年3月2日,13,第三次 low=11 high=13 mid=12因x51，下一步继续在右半区查找，即：,0 1 2 3 4 5 6 7 8 9 10 11 12 13,第四次 low=mid=high=13因xhigh，所以查找失败。,0 1 2 3 4 5 6 7 8 9

9、 10 11 12 13,2023年3月2日,14,【算法8.2】二分查找int Search_Bin(SST ST，KeyType x)low=1；high=ST.length；while(lowST.elemmid.key)low=mid+1；/*查找区间缩小到右边区域*/else return mid;return ERROR;,2023年3月2日,15,算法分析：对于有序查找表，可采用建立二叉树的方法：将表的中间元素作为二叉树的根结点，比中间值小的所有结点全部在二叉树的左子树中，比中间值大的所有结点全部在二叉树的右子树中。按照这种思路建立的二叉树称为判定二叉树。如图所示。,2023年3

10、月2日,16,时间复杂度：该算法的时间复杂度取决于该二叉树中从根结点到该查找元素所在的结点的路径上与中间结点的比较次数，即该元素结点在树中的所在的层数。对于n个结点的判定树，树高为h，则有2h-1-1n2h-1，即h-1log2(n+1)h，所以h=int(log2(n+1)(int为取整函数)。,二分查找的平均查找长度（ASL）为：,=120+221+h2h-1=(n+1)n*log2(n+1)-1log2(n+1)-1,所以，二分查找的时间复杂度为O(log2n)。,2023年3月2日,17,8.2.4 分块查找二分查找适用于顺序存储的有序表查找，但并不是所有的查找表都是有序的。,分块查找

11、又称索引顺序查找，其思想是先将查找表中的数据分成若干个块，并为这若干个块建立相应的索引表，查找时通过将表分块操作而提高效率。,索引表的值包括两个部分：关键字和指针，其中关键字部分存放的是某子表中的最大关键字值，指针部分存放的是对应子表的起始位置，索引表中的表项必须以关键字字段有序排列。查找过程：首先查找索引表，确定关键字记录所在的块，然后在块中顺序查找。,2023年3月2日,18,【例8-2】设关键字集合为：96，40，12，33，81，4，58，45，39，64，18，85，17，57按关键字值33，58，96分为三个块建立的查找表及其索引表。,说明：在分块查找算法中，索引表中关键字的选取将

12、对算法的优劣度起到相当大的作用，若能够使各子表中纪录个数基本项等，则可以提高算法效率。,2023年3月2日,19,8.3 动态查找表,动态查找表将在查找的过程中对记录的关键字进行了插入或删除等修改操作。,8.3.1二叉排序树 二叉排序树属动态查找方法。可根据相应的二叉排序树，实现对结点的查找。,1二叉排序树定义二叉排序树又称为二叉查找树，其定义是一个递归过程：它或者是一棵空树；或者是具有下列性质定义的二叉树：,2023年3月2日,20,若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于或等于根结点的值。左右子树都分别是一棵二叉排序树。,8.3.2二

13、叉排序树的建立1.二叉排序树的建立：由空集为初始状态，将结点按关键字依次插入到排序二叉树中去。先将第一个结点作为二叉树的根结点，插入其它结点时，若结点的值小于根结点的值，则插入左子树，否则插入右子树，该过程依次进行，直到整个过程结束。,2023年3月2日,21,2.二叉排序树的操作二叉排序树的主要操作包括插入、查找、删除等。(1)插入结点二叉排序树插入结点的过程和二叉树的建立过程中各结点的插入相似，即将一个元素插入到二叉排序树中。,(2)查找结点根据前面的定义可知，二叉排序树的查找是一个递归的过程，具体如下：若二叉排序树为空，则查找失败，输出相关信息。若二叉查找树不为空，将给定值x与查找树的根

14、结点关键字进行比较。,2023年3月2日,22,否则，完成下面的判断：(i)若给定的值x小于根结点关键字的值，查找将按照递归的方式在左子树上进行。(ii)若给定的值x大于根结点关键字的值，查找将按照递归的方式在右子树上进行。(iii)重复以上过程，直到查找结束（成功或者失败）。,若比较结果为相等，则查找成功，整个查找结束。,2023年3月2日,23,(3)删除结点：当删除一个结点之后，原二叉树的结构可能发生变化，需要将其进行相应的调整。使其保持二叉排序树的性质。设准备删除的结点为p，其双亲结点为f，以下分三种情况进行讨论。,(1)若结点p为叶子结点，删去叶子结点后不影响整棵树的特性，所以，只需

15、将被删除结点的双亲结点相应指针域改为空指针。,2023年3月2日,24,(2)若结点p为非叶子结点，假设只有右子树pr或只有左子树pl，此时，只需将pr或pl替换f结点的p结点即可。如图8-5所示。,2023年3月2日,25,(3)若结点p既有左子树pl又有右子树pr，可按中序遍历保持有序的原则进行调整。,调整方法有：直接令pl为*r相应的子树，以pr为pl中序遍历的最后一个结点pk的右子树；令p结点的直接前驱pr或直接后继（对pl子树中序遍历的最后一个结点pk）替换p结点，再按的方法删去pr或pk。对给定序列建立二叉排序树时，若左右子树分布均匀，则能提高查找效率。因此，对均匀的二叉排序树进行

16、插入或删除结点后，应对其进行调整，使其依然保持均匀。,2023年3月2日,26,(a),（3）若结点p既有左子树pl又有右子树pr，如图（a）所示，可按照中序遍历保持有序的原则进行调整。调整方法有以下两种：1）直接使左子树pl为f的左子树，再使pr为子树pl中序遍历最后一个结点的右子树，如图（b）所示。2）,2023年3月2日,27,将p结点的直接前驱（或直接后继）替换结点p，然后再从二叉排序树中删除它的直接前驱（或直接后继），如图（c）所示。,2023年3月2日,28,【例8-3】记录的关键字序列为：60，94，74，57，69，41，99，85，13，48，59，则构造一棵二叉排序树的过程

17、如图所示。,2023年3月2日,29,【算法8.3】二叉排序树的查找BTNode*BST_search(BTNode*t,int x)/*二叉排序树的查找*/BTNode*p=t;/*t为根结点*/f=NULL;while(p!=NULL)if(x=p-key)return p;/*查找结束*/else if(xkey)f=p;p=p-lchild;/*在左子树上查找*/else f=p;p=p-rchild;/*在右子树上查找*/return NULL;,2023年3月2日,30,【算法8.4】二叉排序树的建立BTNode*BST_Insert(BTNode*t,int x)/*在二叉排序树

18、上执行插入操作*/BTNode*s,*p=BST_search(t,x);if(p=NULL)s=(BTNode*)malloc(sizeof(BTNode);s-key=x;s-lchild=s-rchild=NULL;if(t=NULL)t=s;else if(xkey)f-lchild=s;/*生成左孩子*/else f-rchild=s;/*生成右孩子*/return t;,2023年3月2日,31,8.3.3平衡二叉树（AVL树）平衡二叉树(Balanced Binary Tree)指的是形态匀称的二叉树，其定义是一个递归过程：,它或是一棵空树，或者是具有下列性质的二叉排序树：它的左

19、子树和右子树都是平衡二叉树，且左子树和右子树高度之差的绝对值不超过1。,2023年3月2日,32,对于非平衡二叉排序树，希望通过适当调整，使其成为平衡二叉树，设A结点为失去平衡的最小子树根结点，对该子树进行平衡化调整归纳起来有以下四种情况：,1.LL型平衡旋转 当在A的左子树上插入结点，使A的平衡因子由1增至2而失去平衡，因此需要进行一次顺时针旋转操作。如图8-9(a)所示。,2023年3月2日,33,2.RR型平衡旋转 由于在A的右子树上插入结点，使A的平衡因子由-1增至-2而失去平衡，因此需要进行一次逆时针旋转操作。如图所示。,2023年3月2日,34,3.LR型平衡旋转由于在A的左子树的

20、右子树上插入结点，使A的平衡因子由1增至2而失去平衡，因此需要进行两次旋转（先逆时针旋转，再顺时针旋转）操作。如图8-9(c)所示。,2023年3月2日,35,4.RL型平衡旋转由于在A的右子树的左子树上插入结点，使A的平衡因子由-1增至-2而失去平衡，因此需要进行两次旋转（先顺时针旋转，再逆时针旋转）操作。如图8-9(d)所示。,2023年3月2日,36,【例8-4】设有数据序列63，90，70，55，67，42，98，试用这组数建立平衡二叉排序树，如图8-10所示。,(e)(f)(g)失去平衡,2023年3月2日,37,(h)调整平衡(i)结束,平衡二叉树的查找分析：在查找过程中将给定值进

21、行比较的关键字个数不超过树的深度。因此，在平衡树上进行查找的时间复杂度为O(log2n)。(等概率的提前下进行的),2023年3月2日,38,8.3.4 B树如果查找需要在外存储器上进行，需要使用外部查找方法。,1.B树的定义 一棵m阶的B树，或者为空树，或为满足下列特性的m叉树：树中每个结点至多有m棵子树；除非根结点为叶子结点，否则至少有两棵子树；除根结点之外的所有非终端结点至少有m/2 棵子树；所有的非终端结点中包含以下信息数据：（n，A0，K1，A1，K2，Kn，An）,2023年3月2日,39,其中：Ki（i=1,2,n）为关键字，且KiKi+1，Ai为指向子树根结点的指针(i=0,1

22、,n)，且指针Ai-1所指子树中所有结点的关键字均小于Ki(i=1,2,n)，An所指子树中所有结点的关键字均大于Kn，m/2 1nm 1，n为关键字的个数。,所有的叶子结点都出现在同一层次上，并且不带信息。,2023年3月2日,40,2B树基本操作 B树的基本操作也是查找、插入和删除等操作。现以B树查找为例做简单介绍。B树的查找类似二叉排序树的查找，所不同的是B树每个结点上是多关键字的有序表，在到达某个结点时，先在有序表中查找，若找到，则查找成功；否则，按照对应的指针信息指向的子树中去查找，当到达叶子结点时，则说明树中没有对应的关键字，查找失败。,可见，B树上进行查找的过程是一个顺指针查找结

23、点和在结点的关键字中进行查找交叉进行的过程。,2023年3月2日,41,8.4 哈希表查找,8.4.1 哈希表与哈希方法前面介绍的查找算法基本上都是建立在“比较”的基础上。而数据元素的存储位置与关键字之间不存在确定的关系，查找效率由每次比较缩小的查找范围决定。,哈希表（Hash）是由哈希函数生成的表示关键字与存储位置之间关系的表。哈希函数是一个以关键字值为自变量，在关键字值与记录存储位置之间建立确定关系的函数。哈希函数的值，就是指定关键字对应的存储地址。,2023年3月2日,42,【例8-5】设有11个记录的关键字，其值分别为 6，37，12，21，69，31，16，33，41，13，51。选

24、取关键字与记录位置间的函数为 Hash(key)=key%11建立的哈希查找表如下：,对于n个数据元素的集合，总能找到关键字与存放地址一一对应的函数。但当key1key2，而Hash(key1)=Hash(key2)时，即将不同的关键字映射到同一个哈希地址上，这种现象称为冲突，映射到同一哈希地址上的关键字称为同义词。可以说，冲突是不可能避免的，只能尽可能减少。因此选取适当的哈希函数很关键。,2023年3月2日,43,8.4.2 常用的哈希函数1.直接定址法 Hash(key)=a*key+b(a、b为常数)直接地址法取关键字的某个线性函数值为哈希地址。,【例8-6】解放后，某农作物年产量(单位

25、：吨)序列为下表：,若选取哈希函数：Hash(key)=key-1950，其中key取“年份”，则建立的哈希查找表如下：,2023年3月2日,44,2.除留余数法 Hash(key)=key%p(p是一个整数)即取关键字除以p的余数作为哈希地址。使用除留余数法，选取合适的p很重要，若哈希表表长为m，一般选取pm的质数。,【例8-7】关键字集合为34，21，78，52，16，46，33，构造哈希函数。选取哈希函数为 Hash(key)=key%7，则存放如下：,2023年3月2日,45,3.数字分析法 设关键字集合中，每个关键字均由m位组成，每位上可能有r种不同的符号。数字分析法根据r种不同的符

26、号，在各位上的分布情况，选取某几位，组合成哈希地址。所选的位应使各种符号在该位上出现的频率大致相同。,【例8-8】有一组关键字如下：2 7 4 0 3 6 4 2 7 6 1 4 8 7 2 7 5 2 4 9 6 2 7 5 5 4 7 0 2 7 5 7 3 0 5,分析：第1、2位均是“2和7”，第3位也只有“4、5、6”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。,2023年3月2日,46,4.平方取中法对关键字平方后，按哈希表大小，取中间的若干位作为哈希地址。【例8-9】设有如下关键字序列0100，0110，1010，1001，0111，采用平方取中法建立哈希表。,

27、关键字 平方 取值 0100 0010000 100 0110 0012100 121 1010 1020100 201 1001 1002001 020 0111 0012321 123则该关键字序列对应的地址值分别为100，121，201，020，123。,2023年3月2日,47,8.4.3 处理冲突的方法1.开放定址法：当由关键字得到的哈希地址发生了冲突，即该地址已经存放了某数据元素时，就自动寻找下一个空的内存地址，只要哈希表足够大，总能找到一个位置，将数据元素存入。,(1)线性探测法 Hi=(Hash(key)+di)%m(1i m)其中：Hash(key)为哈希函数，m为哈希表长度

28、，di 为增量序列 1，2，m-1，且di=i,【例8-11】关键字集为 47，7，29，11，16，92，22，8，3，哈希表表长为11，Hash(key)=key%11，用线性探测法处理冲突，如下所示：0 1 2 3 4 5 6 7 8 9 10,2023年3月2日,48,存储元素47、7后，再存储29时，Hash(29)=7，哈希地址上冲突，由H1=(Hash(29)+1)%11=8，哈希地址8为空，将29存入；,线性探测法可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，因此，可能出现很多元素在相邻的哈希地址上“堆

29、积”起来，大大降低了查找效率。可采用二次探测法，或双哈希函数探测法，以改善“堆积”问题。,0 1 2 3 4 5 6 7 8 9 10,2023年3月2日,49,(2)二次探测法 Hi=(Hash(key)di)mod m其中：Hash(key)为哈希函数，m为哈希表长度，通常取m为4k+3的质数，di 为增量序列 12，-12，22，-22，q2，-q2且q(m-1)/2,当对例8-11使用二次探测法处理冲突时，如果已经将前8个数都存入相应的位置，其结果如下所示：0 1 2 3 4 5 6 7 8 9 10,当存入最后一个元素3时，Hash(3)=3，哈希地址上冲突，由H1=(Hash(3)

30、+12)mod 11=4，仍然冲突；H2=(Hash(3)-12)mod 11=2找到空的哈希地址，将元素3存入该位置。,2023年3月2日,50,(3)双哈希函数探测法 Hi=(Hash(key)+i*ReHash(key)%m(i=1,2,，m-1)其中：Hash(key)，ReHash(key)是两个哈希函数，m为哈希表长度，其方法是：先用第一个函数Hash(key)对关键字计算哈希地址，一旦产生地址冲突，再用第二个函数ReHash(key)确定移动的步长因子，最后，通过步长因子序列由探测函数寻找空哈希地址。,如，Hash(key)=a时产生地址冲突，就计算ReHash(key)=b，则

31、探测的地址序列为 H1=(a+b)%m，H2=(a+2b)%m，Hm-1=(a+(m-1)b)%m,2023年3月2日,51,2.拉链法 设哈希函数得到的哈希地址域在区间0，m-1上，以每个哈希地址作为一个指针，指向一个链，即分配指针数组ElemType*eptrm，建立m个空链表，由哈希函数对关键字转换后，映射到同一哈希地址。i的同义词均加入到*eptri指向的链表中。,【例8-12】关键字序列为 47,7,29,11,16,92,22,8,3,50,37,89,21，哈希函数为 Hash(key)=key mod 11用拉链法处理冲突，如图8-13所示。,2023年3月2日,52,拉链法处

32、理冲突时的哈希表,47,7,29,11,16,92,22,8,3,50,37,89,21,Hash(key)=key mod 11,2023年3月2日,53,哈希表的查找过程基本上和表的生成过程相同。首先一些关键字可通过哈希函数转换的地址直接找到，如果某关键字在哈希函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。查找过程中，关键字的比较次数，取决于产生冲突的次数，冲突次数越少，查找效率越高。因此，影响冲突次数的因素，也就是影响查找效率的因素。,2023年3月2日,54,小 结,1.掌握顺序表和有序表的查找方法。.熟练掌握二叉排序树的构造和查找方法。.掌握二叉平衡树的维护平衡方法。.理解B树的特点以及建树过程。.熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。,