数据结构第七章-查找课件.ppt

《数据结构第七章-查找课件.ppt》由会员分享，可在线阅读，更多相关《数据结构第七章-查找课件.ppt（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章 数据结构何谓查找表？查找表是由同一类型同一类型的数据元素（或记录）构成的集合集合 由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种灵便的结构。对查找表经常进行的操作：1.查找某个特定的数据元素是否在查找表中；2.检索某个特定的数据元素的各种属性。3.在查找表中插入一个元素。4.从查找表中删除某个数据元素。查找表可分为两类：静态查找表仅作查找和检索操作的查找表。动态查找表在查询之后，还需要将查询结果为不在查询表中的数据元素插入到查询表中；或者从查询表中删除其查询结果为在查找表中的数据元素。7.1查找的定义根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记

2、录）若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”，查找结果：给出“空记录”或“空指针”。如何进行查找？查找的方法取决于查找表的结果 由于查找表的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需在查找表中的元素之间认为的附加某种确定的关系，即用另外一种结构来表是查找表。7.2 静态查找算法7.3 动态查找算法7.4 哈希表假设静态查找表静态查找表的顺序存储结构顺序存储结构为typedef struct ElemType*elem;/数据元素存储空间基址，建表时 /按实际长度分配，0号单元留空

3、 int TableLen;/表的长度 SSTable;typedef struct keyType key;/关键字域 /其它属性域 ElemType;一、顺序查找一、顺序查找二、折半查找二、折半查找三、分块顺序表三、分块顺序表ST.elemiST.elemi60ikval=64kval=60i64改进：改进：在ST.elem0处设立监视哨，可以减少查找时间分析顺序查找的时间性能。定义：定义：查找算法的平均查找长度平均查找长度 (Average Search Length)为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的平均值 其中:n 为表长，Pi 为查找表中第i个记录的概率

4、，且 Ci为找到该记录时，曾和给定值 比较过的关键字的个数顺序表查找的平均查找长度为：对顺序表顺序表而言，Ci=n-i+1ASL=nP1+(n-1)P2+2Pn-1+Pn在等概率查找的情况下，n+1查找不成功时的比较次数：查找不成功时的比较次数：ST.elemST.length例如例如:key=64:key=64 的查找过程如下lowhighmidlow mid high midlow 指示查找区间的下界;high 指示查找区间的上界;mid=(low+high)/2。折半查找算法：折半查找算法：假设有一序列存在数组 r 中，指针low和high分别指示查找范围的下界和上界，mid指示区间的中

5、间位置，即 mid=(low+high)/2首先令rmid.key与给定值k相比较，如果(1)rmid.key=k，则查找成功。（退出）(2)k rmid.key，则在mid+1,high范围内查找int Binary_Search(SSTable L,ElemType key)/在有序表L上查找关键字为key的元素，若存在则返回/其位置，不存在则返回-1 int low=0,high=L.TableLen-1,mid;while(low key)high=mid-1;/从前半部分继续查找 else low=mid+1;/从后半部分继续查找 return-1;/顺序表中不存在待查元素/Bina

6、ry_Search先看一个具体的情况，假设：n=11分析折半查找折半查找的平均查找长度6391425781011判定树12233334444ASLbs=(1*1+2*2+3*4+4*4)/11=33/11=3假设假设 n=2h-1 并且查找概率相等并且查找概率相等则则 在 n50 时，可得近似结果 一般情况下，表长为 n 的折半查找的判定树深度与含有 n 个结点的完全二叉树的深度相同。查找成功的比较次数至多为 log2n +1。查找不成功时的比较次数也不超过 log2n +1。n 表长表长(18)s 块长块长(6)b 块数块数(3)查找过程分两步进行：查找过程分两步进行：(1)确定待查记录所在

7、的块。确定待查记录所在的块。(2)在相应的块内查找在相应的块内查找若不能均匀划分线性表，则索引表中应增加子表长度信息。22 5 13 8 9 20 33 42 44 38 24 48 60 58 74 47 86 5322 48 86 1 7 13索引表索引表关键字项关键字项指针项指针项 ASLbs=Lb +LS 索引表的平均查找长度索引表的平均查找长度 块内的平均查找长度块内的平均查找长度如整个表长为n，均匀地分成 b 块，每块含有 s 个记录，即 b=n/s。假设表中每个记录的查找概率相等，则(1)每块的查找概率是1/b。(2)块内每个记录的查找概率为1/s。若都采用顺序查找，则 ASLb

8、s=Lb+Ls =+=(b+1)/2+(s+1)/2=(b+s)/2+1=当s取 时，ASLbs取最小值。如果n=400,则b=20,s=20时，查找性能最佳。一、二叉排序树（二叉查找树）一、二叉排序树（二叉查找树）二、二叉平衡树二、二叉平衡树一、二叉排序树1定义定义2查找算法查找算法3插入算法插入算法4删除算法删除算法5查找性能的分析查找性能的分析通常，取二叉链表作为通常，取二叉链表作为二叉排序树的存储结构二叉排序树的存储结构typedef struct BiTNode /结点结构结点结构 struct BiTNode *lchild,*rchild;/左右孩子指针 BiTNode,*BiT

9、ree;TElemType data;/数据域50308020908540358832例如例如:二叉排序树二叉排序树查找关键字查找关键字=50,505035,503040355090,50809095,从上述查找过程可见，从上述查找过程可见，在查找过程中，生成了一条查找路径查找路径:从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点逐层向下直至关键字等于给定值的结点;从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。逐层向下直至指针指向空树为止。查找成功查找成功 查找失败查找失败算法描述如下：算法描述如

10、下：BSTNode*BST_Search(BiTree T,ElemType key,BSTNode*&p)/查找函数返回指向关键字为key的结点指针，若不存在，返回NULL p=NULL;/p指向被查找结点的双亲，用于插入和删除操作中 while(T!=NULL&key!=T-data)p=T;if(keydata)T=T-lchild;else T=T-rchild;return T;/BST_SearchfT设 key=48fTfT23pfTfTTTffp30201040352523根据动态查找表的定义，“插入”操作在查找不成功时才进行;3二叉排序树的插入算法二叉排序树的插入算法若二叉排

11、序树为空树空树，则新插入的结点为新的根结点新的根结点；否则，新插入的结点必为一个新的叶子结点新的叶子结点，其插入位置插入位置由查找过程得到。int BST_Insert(BiTree&T,KeyType k)/在二叉排序树T中插入一个关键字为k的结点 if(T=NULL)T=(BiTree)malloc(sizeof(BSTNode);T-key=k;T-lchild=T-rchild=NULL;return 1;/返回1，表示成功 else if(k=T-key)/树中存在相同关键字的结点 return 0;else if(kkey)/插入到T的左子树中 return BST_Insert(

12、T-lchild,k);else /插入到T的右子树中 return BST_Insert(T-rchild,k);/BST_Insert4二叉排序树的删除算法二叉排序树的删除算法 删除在查找成功查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性仍然保持二叉排序树的特性。(1)被删除的结点是叶子；被删除的结点是叶子；(2)被删除的结点只有左子树或者只有右子树；被删除的结点只有左子树或者只有右子树；(3)被删除的结点既有左子树，也有右子树被删除的结点既有左子树，也有右子树。可分三种情况讨论：可分三种情况讨论：设被删除结点为P，由指针p指向；P的双亲结点为F，由指针

13、f指向；FPPLPRfp50308020908540358832（1）被删除的结点是叶子结点叶子结点例如例如:被删关键字被删关键字=2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”50308020908540358832（2）被删除的结点只有左子树只有左子树或者只有右子树只有右子树 其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树指向被删除结点的左子树或右子树”。被删关键字被删关键字=4080503080209085403588324040以其前驱替代之，然后再删除该前驱结点被删关键字被删关键字=50某结点的前驱一某结点的

14、前驱一定在它的左子树定在它的左子树的最右下方的最右下方(3)被删除的结点既有左子树，也有右子树既有左子树，也有右子树FPSQCCLQLSLPRfp(1)设S结点是P结点的直接前驱，用S结点取代P结点，然后再从二叉树中删除S结点，并将SL作为S的双亲结点的右子树。FSQCCLQLSLPRfpCLCQLQSLSPPRFqsFPSSLPRfp(2)S结点是P结点的直接前驱，用S结点取代P结点，然后再从二叉树中删除S结点，并将SL作为S的双亲结点的左子树。FSSLPRfpSLSPPRFqsStatus DeleteBST(BiTree&T,KeyType kval)/若二叉排序树 T 中存在其关键字等

15、于 kval 的数据元素，则删除该数据元素结点，并返回 函数值 TRUE，否则返回函数值 FALSE if(!T)return FALSE;/不存在关键字等于kval的数据元素 else if(EQ(key,T-data.key)return Delete(T);/找到关键字等于key的数据元素 else if(LT(key,T-data.key)return DeleteBST(T-lchild,key);else return DeleteBST(T-rchild,key);/DeleteBST算法描述如下：算法描述如下：void Delete(BiTree&p)/从二叉排序树中删除结点

16、p并重接它的左子树或右子树 if(!p-rchild)/右子树空则只需重接它的左子树 q=p;p=p-lchild;free(q);else if(!p-lchild)/只需重接它的右子树 q=p;p=p-rchild;free(q);else /左右子树均不空 q=p;s=p-lchild;while(s-rchild)q=s;s=s-rchild/转左然后向右到尽头 p-data=s-data;/s指向被删结点的“前驱”if(q!=p)q-rchild=s-lchild;/重接*q的右子树 else q-lchild=s-lchild;/重接*q的左子树 delete s;return T

17、RUE;/Delete其中删除操作删除操作过程如下所描述：5查找性能的分析查找性能的分析 对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大。由关键字序列 3，1，2，5，4构造而得的二叉排序树由关键字序列 1，2，3，4，5构造而得的二叉排序树，例如：例如：2134535412ASL=（1+2+3+4+5）/5 =3ASL=（1+2+3+2+3）/5 =2.2 下面讨论平均情况下面讨论平均情况:不失一般性，假设长度为 n 的序列中有 k 个关键字小于小于第一个

18、关键字，则必有 n-k-1 个关键字大于大于第一个关键字,由它构造的二叉排序树n-k-1k的平均查找长度是 n 和 k 的函数P(n,k)(0 k n-1)假设 n 个关键字可能出现的 n!种排列的可能性相同，则含 n 个关键字的二叉排序树的平均查找长度在等概率查找等概率查找的情况下，二、二叉平衡树二、二叉平衡树何谓何谓“二叉平衡树二叉平衡树”？二叉平衡树的查找性能分析二叉平衡树的查找性能分析如何构造如何构造“二叉平衡树二叉平衡树”二叉平衡树二叉平衡树：对于每个结点，|左子树的深度左子树的深度-右子树的深度右子树的深度|1结点的平衡因子结点的平衡因子=左子树的深度左子树的深度-右子树的深度右子

19、树的深度AVL树中所有结点的平衡因子只有三种值：-1，0，1是平衡树是平衡树不是平衡树不是平衡树141253928635360501718730+1+1-1-1-100000000145392863536050171830+1+2-1-100000+1-1希望任何序列构成的二叉排序树都是希望任何序列构成的二叉排序树都是AVL树，因树，因为含有为含有n个节点的个节点的AVL树的深度和树的深度和logn是同数量是同数量级的，因此它的平均查找长度和级的，因此它的平均查找长度和logn同数量级。同数量级。如何检测二叉树是否失去平衡？如何检测二叉树是否失去平衡？当插入一个新结点时，重新计算从新插入的结点

20、到根结点的路径上所包含结点的平衡因子（bf），如果某一结点的 bf 的绝对值超过1，则二叉树失去平衡。0-1平衡平衡133713372401-2失去平衡失去平衡 如何使失衡的二叉树达到平衡？如何使失衡的二叉树达到平衡？在插入过程中，采用平衡旋转技术。在插入过程中，采用平衡旋转技术。例如:依次插入的关键字为5,4,2,8,6,95424258665842向右旋转一次先向右旋转再向左旋转四种调整类型：四种调整类型：设设x为插入结点，为插入结点，A结点为离插入结点结点为离插入结点x最近的最近的一个失衡结点：一个失衡结点：XA1BBLBRAR0LL型型BLBBRAARABBLBRARXBAALBLBR

21、XALABLBBRRR型型BAALBLBRXXXABCLBLCRCAR01LR型型BLBCLC CR AARABCLBLCRCAR-1XXABCLALCRCBR0-1XXRL型型BACLALCRCBR-1XXALACLC CR BBR例：按下列关键字的次序生成一棵AVL树。13，24，37，90，53，28，981313插入点插入点 插入后结果插入后结果 失衡原因失衡原因 调整调整2437RR型1324132437AB243713AB28RL型98RR型2453139037BCA28-23753249028BAC133753249028AB-213983790249828135353RL型90

22、243713902437139053ABC-22453139037CBA 在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数进行比较的关键字的个数不超过平衡 树的深度。平衡树的查找性能分析平衡树的查找性能分析：问：含 n 个关键字的二叉平衡树可能达到的最大深度最大深度是多少？n=0空树空树最大深度为最大深度为 0n=1最大深度为最大深度为 1n=2最大深度为最大深度为 2n=4最大深度为最大深度为 3n=7最大深度为最大深度为 4先看几个具体情况:反过来问，深度为深度为 h 的二叉平衡树平衡树中所含结点的最小值含结点的最小值 Nh 是多少？h=0N0=0h

23、=1h=2h=3一般情况下一般情况下，N1=1N2=2N3=4Nh=Nh-1+Nh-2+1利用归纳法可证得，利用归纳法可证得，Nh=Fh+2-1Fh=/5 ,其中其中=(1+5)/2 因此，在二叉平衡树二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字进行比较的关键字的个数和的个数和 log(n)相当。深度为深度为 h 的二叉平衡树二叉平衡树中所含结点含结点的最小值的最小值 Nh=h+2/5-1 反之，含有含有 n 个结点的二叉平衡树能个结点的二叉平衡树能达到的最大深度达到的最大深度 hn=log(5(n+1)-2 一、哈希表是什么？一、哈希表是什么？二、哈希函数的构造方法哈希函数的构

24、造方法三、处理冲突的方法处理冲突的方法 四、哈希表的查找哈希表的查找 五、哈希表的删除操作哈希表的删除操作7.4 哈哈 希希 表表 以上两节讨论的表示查找表的各种结构结构的共同特点特点：记录在表中的位置位置和它的关关键字键字之间不存在不存在一个确定的关系，一、哈希表是什么？哈希表是什么？查找的过程是把给定值查找的过程是把给定值依次与关键字集合中各个关键字关键字进行比较比较。查找的效率查找的效率取决于与给定值进行比较进行比较的关键字个数个数。用这类方法表示的查找表，其平均查找长度都不为零 不同的表示方法，其差别仅在于：差别仅在于：关键字和给定值进行比较的顺序不同。只有一个办法：预先知道所查关键字

25、在表中的位置，对于频繁使用的查找表，希望 ASL=0。即，要求：记录在表中位置和其关键字之间存在一种确定的关系。若以下标为以下标为0 999 的顺序表存储学生信息。的顺序表存储学生信息。例如：为每年招收的 1000 名新生建立一张查找表（学生信息表），其关键字为学号，其值的范围为 xx000 xx999(前两位为年份)则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较不需要经过比较便可直接从顺序表中找到待查关键字。但是，对于动态查找表动态查找表而言，因此在一般情况下，需在关键字和记录在表中的存储位置之间建立一个函数关系f，以 f(key)作为关键字为 key 的记录在表中的位置，

26、通常称这个函数 f 为哈希函数。1)表长不确定；2)在设计查找表时，只知道关键字所 属范围，而不知道确切的关键字。1)哈希(Hash)函数是一个映象映象，即：将关键字的集合映射到某个地址集合上，将关键字的集合映射到某个地址集合上，它的设置很灵活灵活，只要这个地址集地址集合的 大小不超出存储允许范围不超出存储允许范围即可;2)由于哈希函数通常是一个压缩映象压缩映象，因此，在一般情况下，很容易产生“冲冲突突”现象，即：key1 key2，而 f(key1)=f(key2)。3)很难很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地发生。因此，在构造这种特殊的“查

27、找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外;还需要找到一种“处理冲突”的方法。哈希表的定义:根据设定的哈希函数哈希函数 H(key)和所选中的处理冲突的方法处理冲突的方法，将一组关键字映象映象到到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置存储位置，如此构造所得的查找表称之为“哈希表哈希表”。二、构造哈希函数的方法构造哈希函数的方法 对数字型数字型关键字可有下列构造方法:1.直接定址法直接定址法3.平方取中法平方取中法5.除留余数法除留余数法4.折叠法折叠法2.数字分析法数字分析法构造哈希函数的目标：构造哈希函数的目标

28、：u哈希地址尽可能均匀分布哈希地址尽可能均匀分布均匀性好；均匀性好；u哈希地址计算尽量简单。哈希地址计算尽量简单。哈希函数为关键字的线性函数H(key)=a key+b，其中a,b为常数1.直接定址法直接定址法此法不会发生冲突，但是仅适合于：此法不会发生冲突，但是仅适合于：地址集合的大小地址集合的大小 等于等于 关键字集合的大小关键字集合的大小例：1949年后出生的人口调查表，关键字是年份 年份 1949 1950 1951 人数 H(key)=key+(-1948)5.除留余数法除留余数法H(key)=key MOD p 其中其中，pm(表长表长)并且并且 p 应为不大于应为不大于 m 的质

29、数的质数 或是或是 不含不含 20 以下的质因子以下的质因子当关键字当关键字key为整数时，用关键字为整数时，用关键字除以一个整除以一个整数数p 所得余数作为哈希地址。所得余数作为哈希地址。给定一组关键字为:12,39,18,24,33,21，若取 p=9,则他们对应的哈希函数值将为:3,3,0,6,6,3例如：例如：为什么要对为什么要对 p 加限制？加限制？可见，若 p 中含质因子 3,则所有含质因则所有含质因子子 3 的关键字均映射到的关键字均映射到“3 的倍数的倍数”的地的地址上址上，从而增加了“冲突”的可能。实际造表时，采用何种采用何种构造哈希函数的方法方法取决于建表的关键字集合的情况

30、(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到的原则是使产生冲突的可能性降到尽可能地小。尽可能地小。三、处理冲突的方法处理冲突的方法 “处理冲突处理冲突”的实际含义是：为产生冲突的地址寻找下一个寻找下一个哈希地址1.开放定址法开放定址法2.链地址法链地址法 为产生冲突的地址 H(key)求得一个地址序列地址序列：H0,H1,H2,Hs 1 sm-1其中：H0=H(key)Hi=(H(key)+di)MOD m i=1,2,s m为哈希表表长为哈希表表长1.开放定址法开放定址法对增量 di 有两种取法：1)线性探测再散列线性探测再散列 di=1，2，3，,2)平方探测再散列平方探测

31、再散列 di=12,-12,22,-22,0 1 2 3 4 5 6 7 8 9 100 1 2 3 4 5 6 7 8 9 10例如例如:关键字集合 19,01,23,14,55,68,11,82,36 设定哈希函数：H(key)=key%11 (表长=11)191011232141551683191011232141684若采用线性探测再散列线性探测再散列处理冲突若采用二次探测再散列二次探测再散列处理冲突116822365551113821362将所有哈希地址相同的记录都链接在同一链表中。2.链地址法链地址法0123456 11 198268 55 1436 01 23 ASL=(61+2

32、2+3)/9=13/9例如:同前例的关键字，哈希函数为 H(key)=key MOD 7 查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程查找过程为:四、哈希表的查找哈希表的查找 对于给定值 K,计算哈希地址 i=H(K)若若 ri=NULL 则查找不成功若若 ri.key=K 则查找成功否则否则“求下一地址 Hi”，直至 rHi=NULL (查找不成功)或 rHi.key=K (查找成功)为止。1)选用的哈希函数哈希函数;2)选用的处理冲突的方法处理冲突的方法;3)哈希表饱和的程度，装填因子装填因子 =n/m 值的大小（大小（n记录数，记录数，m表的长度）表的长度）决定哈希表查找

33、的决定哈希表查找的ASL的因素的因素：哈希表查找的分析:从查找过程得知，哈希表查找的平均查找长度实际上并不等于零实际上并不等于零。一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。因此，哈希表的因此，哈希表的ASL是处理冲突方法是处理冲突方法和装载因子的函数。和装载因子的函数。例如：前述例子线性探测处理冲突时，ASL=二次探测处理冲突时，ASL=链地址法处理冲突时，ASL=22/916/913/9线性探测再散列线性探测再散列链地址法链地址法二次探测再散列二次探测再散列可以证明：查找成功查找成功时有下列结果：从以上结果可见，哈希表的平均查找长度是 的函数，而不是 n 的函数。这说明，用哈希表构造查找表时，可以选择一个适当的装填因子 ，使得平均查找长度限定在某个范围内平均查找长度限定在某个范围内。这是哈希表所特有的特点。这是哈希表所特有的特点。小结小结 1.顺序表顺序表和有序表有序表的查找方法及其平均查找长度的计算方法。2.熟练掌握二叉排序树二叉排序树的构造和查找方法，会对不平衡的二叉排序中进行平衡旋转操作。3.熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的查找表的实质性差别。4.掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。