第8章查找.ppt

1、第8章 查 找,查找是数据处理中经常使用的一种重要运算，查找算法的优劣对系统运行效率的影响非常大。静态查找表、动态查找表和哈希表是主要的查找技术。本章要点 查找的基本概念； 几种常见的静态查找表的查找算法； 二叉排序树的创建、查找和删除算法； 平衡二叉树的基本操作； 哈希函数的构造方法和哈希表的查找算法。,章节安排,8.1查找的基本概念 8.2静态表的查找 8.3动态表的查找 8.4散列表,8.1查找的基本概念,查找：又称检索，是指在查找表中查找满足一定条件的结点或记录。 查找方法：静态查找、动态查找 衡量查找算法优劣指标：最大查找长度、平均查找长度如对n个记录进行查找时，平均查找长度可表示为

2、：,8.2静态表的查找,静态查找表可分为顺序表、有序表和索引顺序表三种。,顺序表的查找基本思想是：从顺序表的一端开始，逐个比较结点的关键字和给定值，若某个结点的关键字与给定值相等，则查找成功；若找遍整个顺序表都不相等，则查找失败。查找成功时，查找算法返回找到结点在顺序表中的位置，失败时返回1。,8.2.1顺序表的查找,下面的算法描述了顺序查找过程。 顺序表的存储结构定义如下： typedef struct KeyType key； /*关键字的数据类型*/ DataType； /*数据元素的类型*/ typedef struct DataType *data；/*顺序表data*/int le

3、n； /*顺序表的长度*/Stable；,【算法8.1】顺序表查找算法 int Stable_Search(Stable S，KeyType key) /*在顺序表S中查找关键字等于key的结点*/int i;S.data0.key=key； /*设置哨兵*/i=S.len; /*设置初始查找位置*/while (S.datai.key!=key) i-； /*从后往前找*/if (i=0) return 1； /*查找失败*/else return i； /* 查找成功*/顺序查找的平均查找长度为：,二分法查找（Binary Search）又称为折半查找，其基本思想是：首先取查找表中间位置上

4、的结点的关键字与给定值进行比较，若相等，则查找成功；否则，如果给定值比中间位置上的结点的关键字大，则把查找区间定为表的后半段，反之把查找区间定为表的前半段；然后在前半段或后半段采用同样的方法继续查找，如此继续，直到找到关键字等于给定值的结点，则查找成功；若出现查找区间的左右边界异常，则查找失败。,8.2.2有序表的查找,例：已知有11个关键字的有序表序列如下所示： 02，08，15，23，31，37，42，49，67，83，91当给定的k值为23和83时，折半查找的过程如图所示。图中用方括号表示当前的查找区间，用“”指向中间位置。,【算法8.2】二分法查找非递归算法int Binary_Sea

5、rch(Stable S，KeyType key) int low，mid，high； low=1；high=S.len； while(lowS.datamid.key) low=mid+1； else return mid ；return 1；,索引顺序查找又称为分块查找，是顺序查找的一种改进方法。在索引顺序查找法中，除表本身以外，还需要建立一个“索引表”。分块查找的基本思想：把顺序表分成若干块，每一块中结点的存放是任意的，但是块与块之间必须有序。假设块间按关键字值递增排序，以每块中的最大（小）关键字值建立一个索引表，存放每块的最大（小）关键字值和每块的起始位置。查找时需分两步走，首先在索引

6、表中采用顺序查找或折半查找算法查找给定值，确定给定值所在的块；然后在所确定的块中顺序查找。,8.2.3索引顺序表的查找,例8.2 设有一个顺序表共有20个结点，现将它分成四块，每块5个结点。以每块最大关键字值建立索引表，索引表包含最大关键字值和对应块的起始地址两个域，如图8.2所示。试查找关键字值为58的结点。图8.2 表及索引表结构图,分块查找的平均查找长度：ASLbs=ASLb+ASLwASLbs表示分块查找的平均查找长度，ASLb表示查找索引表以确定所在块的平均查找长度，ASLw表示在块中查找关键字的平均查找长度。,8.3动态表的查找,动态查找表的特点是：表结构本身是在查找过程中动态生成

7、的，即对于给定值key，若表中存在关键字等于key的结点，则查找成功；否则插入关键字为key的结点。,二叉排序树又称二叉查找树，它或者是一棵空 树，或者是具有以下性质的二叉树：若任一结点的左子树非空，则左子树中的所有 结点的值都不大于根结点的值；若任一结点的右子树非空，则右子树中的所有 结点的值都不小于根结点的值。,8.3.1二叉排序树,例如：图8.3所示为一棵二叉排序树（结点内的数为数据元素的关键字）。其中序遍历序列为：15，55，65，75，79，95，100，120，200，230，240。,图8.3 二叉排序树,二叉排序树一般采用二叉链表作为存储结构，可定义如下：typedef str

8、uct BSTNodeDataType data； /*数据元素字段*/ struct BSTNode *lchild，*rchild； /*左、右指针字段*/ NodeType；,【算法8.3】二叉排序树查找算法 int BST_Search (NodeType *T，KeyType key,NodeType *p,NodeType *q) if (T) *p=T；*q=NULL;while(*p) if(key(*p)-data.key) *q=*p ；(*p)= (*p)-rchild； elseif(keydata.key) *q=*p ；(*p)= (*p)-lchild； else

9、 return 1 ； return 0； ,二叉排序树的插入和生成过程如下：(1) 若二叉排序树为空，则把待插入的结点作为根结点插入到空树中。(2) 若二叉排序树非空，则将待插入的结点关键字和根结点的关键字进行比较，若两者相等，表示该结点已在二叉排序树中，无需插入；若待插入的结点关键字小于根结点的关键字，将待插入的结点插入到根的左子树中，否则插入到右子树中。(3) 子树中的插入过程和树中的插入过程相同，如此插入下去，直到把待插入的结点作为叶子插入到二叉排序树中。,【算法8.4】二叉排序树的插入算法int InsertNode (NodeType *t，KeyType key) NodeTyp

10、e *p, *q，*s;if(!BST_Search (*t， key, s-data.key=key； s-lc=NULL；s-rc=NULL；if(!p) t=s； else if(keyp-data.key) p-rchild=s； else p-lchild=s； return 1；return 0；,例如，给定关键字序列53，80，69，45，58，30，88，则构造相对应的一棵二叉排序树的过程如图8.5所示：,图8.5 二叉排序树的插入过程 (a)空树；（b）插入53；(c)插入90；(d)插入69；(e)插入45；(f)插入58；(g)插入30；(h)插入88；,二叉排序树的删除

11、设待删结点的为p，p的双亲结点为d，若p的左右孩子分别为pl和pr，则删除操作可分以下三种情况进行讨论：（1）若结点p为叶子结点，则pl和pr均为空二叉树。由于删除叶子结点不会破坏整棵树的结构，则根据p是d的左子树还是右子树，将d的左孩子或右孩子指针域置空即可。删除过程如图8.6所示。,（2）若结点p只有左子树pl或右子树pr时，则用p的左子树的根结点pl或右子树的根结点pr取代被删除的结点即可。删除过程如图8.7所示。,（3）若结点p同时有左右子树pl和Pr时，则用被删除结点的左子树的根取代被删除的结点，将被删除结点的右子树移动到被删除结点的左子树的最右下方，即用结点pl取代结点p，将Pr及

12、其子树移动到pl的右子树的最右下方，如图8.8所示。,【算法8.5】二叉排序树的删除算法 int DeleteNode(NodeType *t，KeyType key) /* 在二叉排序树t中若存在关键字值为key的结点则删除，函数返回1，否则返回0*/ NodeType *p,*d，*s; if(BST_Search (*t，key，/*被删除结点无左子树，将其右子树作为删除此结点后的树*/,（续） else /*被删除结点有左子树，将其左子树作为根结点*/*t=p-lchild;s=*t;/*寻找被删除结点左子树的最右下结点*/while (s-rchild!=NULL) s=s-rchi

13、ld;s-rchildp-rchild; else if(!p-lchild) /*待删结点不是根结点，且其左子树为空，重接它的右子树*/ s=p； p=p-rchild； free(s)；,（续） else if(!p-rchild) /*待删结点的右子树为空，重接它的左子树*/ s=p； p=p-lchild； free(s)；else /*待删结点的左右子树均不空，将其右子树挂到左子树的最右下方*/s=p-lchild；while (s-rchild) s=s-rchild；/*找到左子树最右下的结点*/s-rchild=p-rchild; /*将被删除结点的右子树作为s的右子树*/ s

14、=p；p=p-lchild；free(s)；/*用被删除结点的左子树的根取代被删除结点*/ retrun 1； return 0； ,平衡二叉树又称AVL树，其性质是：(1)、或者是一棵空树，或者是满足下列性质的二叉树；(2)、树的左子树和右子树的深度之差的绝对值不大于1且左右子树也需满足上述性质。,*8.3.2 平衡二叉树,如图8.9所示，结点左边的数字为该结点的平衡因子，图(a)为非平衡二叉树，图(b)为平衡二叉树。,动态平衡技术的基本思想：在构造二叉排序树的过程中，每当插入一个结点时，首先检查插入之后是否破坏了树的平衡性，若是则找出其中离插入结点最近的不平衡子树，在保持二叉排序树特性的前

15、提下，调整不平衡子树中各结点之间的关系，以达到新的平衡。设离插入结点最近的不平衡子树的根结点为r，则对该子树进行的平衡化调整，归纳起来有以下四种情况：,1. RR型调整(逆时针),2. LL型调整(顺时针),3. LR型调整(先逆后顺),4RL型调整(先顺后逆),1. B树的定义 一棵m阶的B树满足下列条件： (1) 树中每个结点至多有m棵子树； (2) 除根结点和叶子结点外，其他每个结点至少有m/2 棵子树； (3) 根结点至少有两个子树(B树只有一个结点除外)； (4) 所有的叶子结点都在同一层，且叶结点不包含任何信息；,*8-3-3 B_树和B+树,(5) 有j个孩子的非叶子结点恰好有个

16、关键字， 该结点包含的信息为 P0 ,K1 ,P1 ,K2 ,P2 ,Pj-1 ,Kj-1 , Pj-1 其中，Ki为关键字，且满足KiKi+1；Pi为指 向子树根结点的指针，且Pi-1所指子树中所有 结点的关键字都小于Ki，Pi所指子树中所有结 点的关键字都大于Ki。,例如，下图为一个6阶的B树。,B树的查找在B树上的查找给定的关键字Key的方法是：首先根据给定的B树的指针取出根结点，在根结点所包含的关键字中按顺序或二分法查找给定的关键字，若Ki=Key，则查找成功；否则一定可以找到Ki-1和Ki，使得Ki-1KeyKi，取指针Pi所指的结点继续查找，重复上述过程，直到找到或指针Pi为空，查

17、找失败。整个查找过程中访问外存的次数不超过B树的深度。,B+树的定义B+树是B树的一个变形树，它和B树的区别在于：(1) 有n棵子树的结点中包含有n个关键字；(2) 所有的叶子结点中包含了全部关键字的信息，以及指向含这些关键字记录的指针，且叶子结点按关键字大小顺序链接。(3) 所有分支结点可看成是索引部分，结点中仅包含其子树中最大(或最小)关键字。,如下图所示为一棵3阶的B+树。为便于查找提供了两个头指针(root和head指针)。,*8-3-4 键树,键树又称为数字查找树（Digital Search Tree）或Trie树(trie为retrieve中间4个字符)。它是一棵度2的树，树中的

18、每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。,例如：JAN，FEB，MAR，APR，MAY，JUN，JUL，AGU，SEP，OCT，NOV，DEC可用图8.16所示的键树表示。,图8.16 关键字符集的一棵键树,键树的查找过程为：从根结点出发，沿和给定值相应的指针逐层向下，直到叶子结点；若叶子结点中的关键字和给定值相等，则查找成功；若分支结点中与给定值相应的指针为空，或叶子结点中的关键字和给定值不相等，则查找失败。,哈希表查找基本思想： 根据结点的键值从而确定结点的存储位置。即以 待查的结点关键字K为自变量，通过一个确定的 函数H，计算出对应的函数值H(K)，并以这个函 数

19、值作为该结点的存储地址，将结点存入H(K)所 指的存储位置上。查找时再根据要查找的关键字 K为自变量，用同样的函数计算地址，然后到相 应的单元里去取要查找的结点。上述的函数H称为哈希函数，H(K)称为哈希地址。,8-4-1哈希表,1. 数字分析法当关键字的位数比哈希表的地址码位数多时，对关键字的各位数字进行分析，丢掉数字分布不均匀的位，取分布均匀的位作为地址。,8.4.2哈希函数的构造方法,例如，有80个结点，其关键字为8位十进制数。若哈希表的表长为100，则可取两位十进制数组成哈希地址，地址编号为099。设这80个关键字中的一部分如图8.17所示。,2. 平方取中法该方法是先计算出关键字K的

20、平方值K2，然后 再取K2值的中间几位或几位的组合作为哈希地 址，取的位数由哈希表的表长决定。例如，关键字为3632，则36322=13191424。 若表长为1000，则可以取第四位到第六位为哈 希地址，即H(3632)=914。,3. 折叠法将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取这几部分的叠加和(舍去进位)作为哈希地址，这方法称为折叠法。例如，key=978 750 835 150，哈希表的长度为1000，则应把关键字分成3位一段，分别进行移位叠加和折叠叠加，求得哈希地址为713和921，如图8-18所示。,图8-18 由折叠法求哈希地址 (a)移位叠加法(b)

21、折叠叠加法,4除余法(亦称为除留余数法)选择一个适当的正整数P，用P去除关键 字，取其余数作为哈希地址，即H(key)=key % P+b (b为常数),5伪随机数法采用一个伪随机函数作哈希函数，即H(key)=random(key)。在实际应用中，应根据具体情况选用不同的方法。通常考虑以下因素：（1）计算哈希函数所需要的时间。（2）关键字的长度。（3）哈希表的大小。（4）关键字的分布情况。（5）查找结点的频率。,1. 开放地址法基本思想是：当哈希地址I=H(key)出现冲突时，以I为基础，产生另一个哈希地址I1；若P1仍然冲突，再以I1为基础，产生下一个哈希地址I2，直到找出一个不冲突的哈希

22、地址为止。这种方法的一般哈希函数的形式为：Hi+1=(Hi(key)+di) MOD m i=1,2,k(km-1),8.4.3处理冲突的方法,其中，H(key)为哈希函数；m为哈希表表长；di为增量序列，通常有三种取法： （1）di =1，2，3，m-1，称为线性探测再散列； （2）di =12，-12，22，-22，k2,-k2(km/2)，称为二次探测再散列； （3）di =伪随机数序列，称为伪随机探测再散列。,2再哈希法 这种方法是构造多个哈希函数： Hi=RHi(key) i=1，2，k （式8.12）当哈希地址H1= RH1(key)发生冲突时，再计算H2= RH2(key)，直到

23、没有冲突发生。这种方法不容易产生聚集，但增加了计算时间。,3链地址法 这种方法的基本思想是将所有关键字为同义词的结点存储在同一个线性链表中，形成一同义词链。,例8.4 已知一组关键字为（21，40，37，67，86，45，43，84，76，54），若哈希表表长为11，取哈希函数H(key)=key MOD 11，则用链地址法法处理冲突的结果如图8.21所示。,图8.21 链地址法处理冲突的哈希表,4建立公共溢出区这也是处理冲突的一种常用方法。基本思想是将哈希表分为基本表和溢出表两部分，凡与基本表发生冲突的结点一律存入溢出表。,8-4-4哈希表的查找,哈希表的查找过程与哈希表的构造过程是一致的。

24、对于给定值key，先哈希函数计算出哈希地址。若哈希地址单元中没有结点，说明查找失败，则插入关键字为key的结点；否则，哈希地址单元中的结点的关键字值与key相等，则查找成功，反之则发生冲突，需要反复执行以下冲突处理过程：按照冲突处理方法计算“下一地址”，直到哈希表中某个存储单元为“空”或表中所填结点的关键字等于给定值时为止。,下面以线性探测再散列为例，给出哈希表的查找算法。开放定址哈希表的存储结构如下：#define MAXSIZE 99 /*哈希表的最大长度*/ typedef structDataType *elem; /*结点存储基址，动态分配数组*/int count; /*当前结点个

25、数*/int sizeindex; /*哈希表当前的容量*/HashTable;,【算法8.6】线性探测再散列查找算法int Hash_search(HashTable HT, DataType r)/*HT为哈希表，r为待查找或插入的结点*/int p,n; p=H(r.key);n=p-1;while(Tp.key!=NULL) /*插入*/,8-4-5哈希表的查找效率分析,1线性探测再散列法查找成功时的平均查找长度为：查找失败时的平均查找长度为：,2链地址法查找成功时的平均查找长度为：查找失败时的平均查找长度为：,3伪随机探测再散列法、二次探测再散列法及再哈希法查找成功时的平均查找长度为：查找失败时的平均查找长度为：,见教材习题,习题,