(10.1)--数据结构第8章查找.pdf

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

1、第第8章章 查找查找提提 纲纲查找基本概念及查找基本概念及顺序查找顺序查找有序表的查找有序表的查找二叉排序树（二叉排序树（1）二叉排序树（二叉排序树（2）平衡二叉树平衡二叉树哈希表哈希表（1）哈希表哈希表（2）基本概念基本概念查找表查找表：是由：是由同一类型同一类型数据元素数据元素（或记录或记录）构成的构成的集合集合。四种操作四种操作：查询查询，检索检索，插入插入，删除删除静态查找表静态查找表：只有：只有查找操作查找操作动态查找表动态查找表：四种操作：四种操作查找查找：根据给定的某个：根据给定的某个值值，在查找表中在查找表中确定确定一个关键字等于一个关键字等于给定值的记录或数据元素给定值的记录

2、或数据元素。查找查找成功成功查找结果查找结果查找查找不成功不成功关键字关键字：是数据元素：是数据元素（或记录或记录）中某个中某个数据项的值数据项的值，用它可用它可以以标识标识（识别识别）一个数据元素一个数据元素（或记录或记录）。典型的关键字类型定义有：典型的关键字类型定义有：typedefint KeyType;整型整型typedef char*KeyType;字符串字符串数据元素类型数据元素类型定义为：定义为：typedef structKeyType key;.ElemType;三个三个比较函数比较函数：EQ(a,b),LT(a,b),LQ(a,b);静态查找表静态查找表顺序表的查找顺序表

3、的查找typedef struct ElemType*elem;int length;SSTable;SSTable ST;for(i=1;i ST.length)return(0);else return(i);顺序查找顺序查找监视哨监视哨：免去：免去了查找过程中了查找过程中每一步都要检每一步都要检测扫描是否越测扫描是否越界界。int Search_Seq(SSTable ST,KeyType key)ST.elem0.key=key;for(i=ST.length;!EQ(ST.elemi.key,key);-i);return(i);查找算法性能分析查找算法性能分析定义定义：为了确定记录

4、在查找表中的位置：为了确定记录在查找表中的位置，需和给定值进行比较的关需和给定值进行比较的关键字个数的期望值键字个数的期望值称为查找算法在称为查找算法在查找成功时查找成功时的的平均查找长度平均查找长度。niiiCPASL1其中：其中：Pi为在查找表中为在查找表中查找第查找第i个记录的概率个记录的概率；Ci为找到第为找到第i个记录个记录的的比较次数比较次数；ai查找成功要和关键字比较查找成功要和关键字比较n-i+1次，设每个数据元素查找次，设每个数据元素查找概率相等，查找成功的概率相等，查找成功的平均查找长度平均查找长度：nininnASL121)1(1查找不成功：查找不成功：n+1顺序查找性能

5、分析顺序查找性能分析提提 纲纲查找基本概念及查找基本概念及顺序查找顺序查找有序表的查找有序表的查找二叉排序树（二叉排序树（1）二叉排序树（二叉排序树（2）平衡二叉树平衡二叉树哈希表哈希表（1）哈希表哈希表（2）有序表的查找有序表的查找折半查找折半查找：先确定待查记录所在的：先确定待查记录所在的范围范围（区间区间），然后逐步然后逐步缩小范缩小范围围直到找到或找不到和给定值相等的记录为止直到找到或找不到和给定值相等的记录为止。int Search_Bin(SSTable ST,KeyType key)low=1;high=ST.length;*0号单元未用号单元未用while(low50)时时，A

6、SL成功成功=log2(n+1)-1ASL失败失败=h=log2(n+1)hjjnnnjnASL1211)1(log12*1提提 纲纲查找基本概念及查找基本概念及顺序查找顺序查找有序表的查找有序表的查找二叉排序树（二叉排序树（1）二叉排序树（二叉排序树（2）平衡二叉树平衡二叉树哈希表哈希表（1）哈希表哈希表（2）动态查找表动态查找表特点特点查找表本身是在查找过程中查找表本身是在查找过程中动态生成的动态生成的（插入或删除插入或删除），即对于给定值即对于给定值key，若表中存在其关键字等于若表中存在其关键字等于key的记录的记录，则则查找成功查找成功返回；返回；否则插入关键字等于否则插入关键字等于

7、key的记录的记录。二叉排序树二叉排序树二叉排序树二叉排序树(Binary Sort Tree)：或者是一棵：或者是一棵空树空树；或者是具有；或者是具有下列性质的二叉树：下列性质的二叉树：（1）若它的左子树不空若它的左子树不空，则则左子树左子树上所有结点的上所有结点的值均小于值均小于根结根结点的值；点的值；（2）若它的右子树不空若它的右子树不空，则则右子树右子树上所有结点的上所有结点的值均大于值均大于根结根结点的值；点的值；（3）它的它的左左、右子树也分别是二叉排序树右子树也分别是二叉排序树；二叉排序树示例二叉排序树示例二叉排序的查找二叉排序的查找if(!T)|EQ(key,T-data.ke

8、y)return(T);else if LT(key,T-data.key)return(SearchBST(T-lchild,key);else return(SearchBST(T-rchild,key);typedef struct BiTNodeElemTypedata;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;查找过程查找过程BiTree SearchBST(BiTree T,KeyType key)*若查找成功返回指向该记录结点的指针若查找成功返回指向该记录结点的指针，否则返回否则返回NULL思考题思考题：用递推的方式实：用递推的方

9、式实现以上算法现以上算法二叉排序树的插入二叉排序树的插入插入插入：新插入的结点一定：新插入的结点一定是一个是一个新添加的叶子新添加的叶子，并且是并且是查找不成功查找不成功时时，查找路径上访查找路径上访问的问的最后一个结点的左孩子或最后一个结点的左孩子或右孩子右孩子。实现细节实现细节：需要修改查找：需要修改查找过程过程，使使查找不成功查找不成功时时，返回返回查找路径上查找路径上最后一个访问的结最后一个访问的结点点。Status SearchBST(BiTree T,KeyType key,BiTree f,Bitree&p)*若查找成功若查找成功p指向该记录结点指向该记录结点，否则否则p指向查找

10、路径上访问的最后一个结点指向查找路径上访问的最后一个结点*指针指针f始终指向当前始终指向当前T(根结点根结点）的双亲的双亲，查找失败时查找失败时，f指向查找路径上访问的指向查找路径上访问的最后一个结点最后一个结点if(!T)p=f;return False*p可能为可能为NULL？else if EQ(key,T-data.key)p=T;return True;else if LT(key,T-data.key)return(SearchBST(T-lchild,key,T,p);else return(SearchBST(T-rchild,key,T,p);Status InsertBST

11、(BiTree&T,ElemType e)if(!SearchBST(T,e.key,NULL,p)s=(BiTree)malloc(sizeof(BiTNode);s-data=e;s-lchild=s-rchild=NULL;if(!p)T=s;else if LT(e.key,p-data.key)p-lchild=s;else p-rchild=s;return True;ifelse return FALSE;中序遍历二叉中序遍历二叉排序树排序树可得到一个可得到一个关键字的有序序列关键字的有序序列，可以说可以说，一个无序一个无序序列通过构造一棵序列通过构造一棵二叉排序树而变成二叉排序

12、树而变成一个一个“有序序列有序序列”，构造过程即为排序构造过程即为排序过程过程。提提 纲纲查找基本概念及查找基本概念及顺序查找顺序查找有序表的查找有序表的查找二叉排序树（二叉排序树（1）二叉排序树（二叉排序树（2）平衡二叉树平衡二叉树哈希表哈希表（1）哈希表哈希表（2）二叉排序树的删除二叉排序树的删除二叉排序树的删除二叉排序树的删除假设假设：p指向被删除的的结点指向被删除的的结点，f指向其双亲结点指向其双亲结点，且不失一且不失一般性般性，设设p是是f的左孩子的左孩子。分分三种情况来讨论三种情况来讨论：若若*p结点为结点为叶子结点叶子结点，直接删除直接删除。f-lchild=NULL;若若*p结

13、点结点只有只有左子树左子树PL或者只有右子树或者只有右子树PR，f-lchild=p-lchild;或或 f-lchild=p-rchild;若若*p结点结点左右子树均不空左右子树均不空中序遍历该二叉排序树得到序列为中序遍历该二叉排序树得到序列为.CLC.QLQSLSPPRF.（有序序列有序序列），删除后应保持序列中其它元素之间的相删除后应保持序列中其它元素之间的相对位置对位置不变不变，有有两种两种做法：做法：其一其一，令令*p的左子树为的左子树为*f的左子树的左子树，*p的右子树为的右子树为*s的右子树；的右子树；（可能可能导致二叉排序树变深导致二叉排序树变深）其二其二，令令*p的的直接前驱

14、直接前驱（或直接后继或直接后继）替代替代*p，然后再从二叉然后再从二叉排序树中排序树中删去它的直接前驱删去它的直接前驱（直接后继直接后继），算法算法9.8采取第二种采取第二种方法；方法；二叉排序树的查找性能分析二叉排序树的查找性能分析因为二叉排序树的形态和构造时的关键字序列有关因为二叉排序树的形态和构造时的关键字序列有关，不同的不同的构造序列生成不同形态的二叉树构造序列生成不同形态的二叉树。例例：（45，24，53，12，37，93）和和（12，24，37，45，53，93）所构成的二叉排序树如图所构成的二叉排序树如图1和和2所示所示。提提 纲纲查找基本概念及查找基本概念及顺序查找顺序查找有序

15、表的查找有序表的查找二叉排序树（二叉排序树（1）二叉排序树（二叉排序树（2）平衡二叉树平衡二叉树哈希表哈希表（1）哈希表哈希表（2）平衡二叉树平衡二叉树又称为又称为AVL树树。它或者是一棵空树它或者是一棵空树，或者是具有下列性质的或者是具有下列性质的二叉树二叉树:它的左子树和右子树它的左子树和右子树都是平衡二叉树都是平衡二叉树，且它的左子树和右且它的左子树和右子树的子树的深度之差的绝对值不超过深度之差的绝对值不超过1。平衡因子平衡因子：二叉树：二叉树的左子树深度与右的左子树深度与右子树深度差子树深度差。若是若是平衡二叉树平衡二叉树，其其所所有结点有结点的平衡因子的平衡因子只能是只能是（-1,0

16、,1）二叉排序树失衡的调整二叉排序树失衡的调整初始时初始时，空树空树，空树是一棵平衡二叉排序树空树是一棵平衡二叉排序树，伴随插入伴随插入（每每次作为一个叶子次作为一个叶子），出现失衡出现失衡，需要进行调整需要进行调整。例例：四种情况下的调整方法四种情况下的调整方法设设a为指向因插入结点而为指向因插入结点而失去平衡的最小子树的根结点失去平衡的最小子树的根结点。单向右旋平衡处理单向右旋平衡处理（LLLL型型）原因原因：在：在*a a的左子树根结点的左子树插入结点的左子树根结点的左子树插入结点，即即左子树的左子树左子树的左子树LLLL型型一般的情况一般的情况单向左旋平衡处理单向左旋平衡处理（RRRR

17、型型）原因原因：在：在*a a的右子树根结点的右子树插入结点的右子树根结点的右子树插入结点，即即右子树的右右子树的右子树子树双向旋转双向旋转（先左后右先左后右）平衡处理平衡处理（LRLR型型）原因原因：在：在*a a的左子树根结点的右子树插入结点的左子树根结点的右子树插入结点，即即左子树的左子树的右子树右子树.LRLR型型一般的情况一般的情况双向旋转双向旋转（先右后左先右后左）平衡处理平衡处理（RLRL型型）原因原因：在：在*a a的右子树根结点的左子树插入结点的右子树根结点的左子树插入结点，即即右子树的左右子树的左子树子树.平衡二叉排序树查找性能分析：平衡二叉排序树查找性能分析：O(log2

18、n)提提 纲纲查找基本概念及查找基本概念及顺序查找顺序查找有序表的查找有序表的查找二叉排序树（二叉排序树（1）二叉排序树（二叉排序树（2）平衡二叉树平衡二叉树哈希表哈希表（1）哈希表哈希表（2）哈希表哈希表什么是哈希表什么是哈希表哈希函数哈希函数：在记录的：在记录的关键字和它的存储位置之间建立一个确定关键字和它的存储位置之间建立一个确定的对应关系的对应关系f，使每个关键字和结构中一个使每个关键字和结构中一个唯一的存储位置唯一的存储位置相对相对应应，称对应关系称对应关系f为哈希为哈希(Hash)函数函数。哈希表哈希表：按：按哈哈希函数建立希函数建立的的查找表称为哈查找表称为哈希表。希表。例例：3

19、0个地区人口统计表个地区人口统计表（为查找方便为查找方便，以地区名做关键字以地区名做关键字）keyBEIJING（北京）（北京）TIANJIN（天津）（天津）HEBEI（河北）（河北）SHANXI（山西）（山西）SHANGHAI（上海）（上海）SHANDONG（山东）（山东）HENAN（河南）（河南）SICHUAN（四川）（四川）f1(key)0220081919190819f2(key)0904172828262203f3(key)0426021323271616f1(key)：关键字：关键字首字母在字母表中的序号作为首字母在字母表中的序号作为哈希地址；哈希地址；f2(key)：先求关键字的

20、第一个和最后一个字母在字母表中的序号：先求关键字的第一个和最后一个字母在字母表中的序号之和之和，若大于表长若大于表长（30），则减去则减去30；f3(key)：先 求 关 键 字 的 每 个 汉 字 的 第 一 个 拼 音 字 母 的 的：先 求 关 键 字 的 每 个 汉 字 的 第 一 个 拼 音 字 母 的 的 ASCII 码码之和的八进制形式之和的八进制形式，然后将这个八进制看成是十进制再除以然后将这个八进制看成是十进制再除以30取余数：取余数：注：注：本质是对本质是对关键字特征关键字特征的抽取的抽取。哈希函数值的范围和冲突哈希函数值的范围和冲突通过上述例子通过上述例子，注意到哈希表设

21、计中的两个问题注意到哈希表设计中的两个问题 哈希哈希函数值函数值应落在应落在表长的范围内表长的范围内 不同的不同的关键字有关键字有相同的相同的哈希函数值哈希函数值针对第针对第2个问题个问题，要求要求：一个一个好的好的哈希函数哈希函数（尽量避免冲突尽量避免冲突！）一种一种处理冲突处理冲突的方法的方法哈希函数的构造方法哈希函数的构造方法均匀的哈希函数均匀的哈希函数：若对于关键字集合中的：若对于关键字集合中的任一个关键字任一个关键字，经哈经哈希函数映射到地址集合中希函数映射到地址集合中任一个地址任一个地址的的概率是相等概率是相等的的。（使一组关使一组关键字的哈希地址均匀分布在整个地址空间中键字的哈希

22、地址均匀分布在整个地址空间中，从而减少冲突从而减少冲突）直接定址法直接定址法取关键字或关键字的某个取关键字或关键字的某个线性函数值线性函数值为哈希地址：为哈希地址：H(key)=key 或或 H(key)=a*key+b注：注：要求关键字为要求关键字为整数值整数值；地址集合和关键字集合的大小相同地址集合和关键字集合的大小相同，不会不会发生冲突；发生冲突；数字分析法数字分析法假设关键字是假设关键字是以以r为基的数为基的数（如十进制如十进制），并且哈希表中可能出现并且哈希表中可能出现的关键字都是的关键字都是事先知道事先知道的的，则可则可取关键字的若干位组成哈希地址取关键字的若干位组成哈希地址。81

23、3465328137224281387422813013678132281781338967813541578136853781419355平方取中法平方取中法取关键字平方后的取关键字平方后的中间几位中间几位为哈希地址为哈希地址。注：注：关键字平方后的关键字平方后的中间几位和数的每一位都相关中间几位和数的每一位都相关，由此使随机分由此使随机分布的关键字得到的哈希地址也是随机的布的关键字得到的哈希地址也是随机的，取的位数由表长决定取的位数由表长决定。例：例：1234123449363702246812341522756折叠法折叠法将关键字将关键字分割成位数相同的几部分分割成位数相同的几部分（最后

24、一部分的位数可以最后一部分的位数可以不同不同），然后取这几部分的然后取这几部分的叠加和叠加和（舍弃进位舍弃进位）作为哈希地址作为哈希地址。（使每一位都在哈希地址中使每一位都在哈希地址中产生影响产生影响）0-442-20586-45864586442200224+04+04-100886092H(key)=0088H(key)=6092除留余数法除留余数法取关键字被某个不大于取关键字被某个不大于哈希表长哈希表长m的数的数p除后所得余数除后所得余数为哈希地为哈希地址址。H(key)=key mod p,pm关键字关键字284*7355*7639*77711*710515*7哈希地址哈希地址7140

25、140注：注：一般情况下一般情况下，可以选可以选p为为质数或不包含小于质数或不包含小于20的质因数的和数的质因数的和数例例：p选不好选不好，容易产生同义词容易产生同义词（哈希地址相同哈希地址相同）p=21=3*7（含质因子含质因子7），则含有因子则含有因子7的关键字对的关键字对21取模的哈希取模的哈希地址均为地址均为7的倍数的倍数随机数法随机数法选择一个选择一个随机函数随机函数，取关键字的随机函数值为它的哈希地址取关键字的随机函数值为它的哈希地址H(key)=random(key);提提 纲纲查找基本概念及查找基本概念及顺序查找顺序查找有序表的查找有序表的查找二叉排序树（二叉排序树（1）二叉排

26、序树（二叉排序树（2）平衡二叉树平衡二叉树哈希表哈希表（1）哈希表哈希表（2）处理冲突的方法处理冲突的方法为发生为发生冲突冲突的关键字记录的关键字记录找到另一个空的哈希地址找到另一个空的哈希地址，可能得可能得到一个地址序列：到一个地址序列：Hi,i=1,2,3,.,k(Hi0,n-1)，若若H(key)发生冲突发生冲突，求求H1，H1仍然冲突仍然冲突，求求H2，依次类推依次类推，直到直到Hk不发生冲突为止不发生冲突为止。开放定址法开放定址法Hi=(H(key)+di)mod m,i=1,2,.,k(km-1)其中：其中：H(key)为哈希函数为哈希函数；m为哈希表长；为哈希表长；di为增量序列

27、为增量序列，可有可有下列三种取法：下列三种取法：(1)di=1,2,3,.,m-1，称为称为线性探测线性探测再散列；再散列；(2)di=12,-12,22,-22,32,.,k2,(km/m/2 2),),称为称为二次探测二次探测再散列；再散列；(3)di=伪伪随机数序列随机数序列，如如 9,30，.，称为称为伪随机探测伪随机探测再散列；再散列；例：例：长度为长度为11的哈希表中已填有关键字的哈希表中已填有关键字17，60，29，哈希函数为哈希函数为H(key)=key mod 11，现在插入关键字现在插入关键字38二次聚集：二次聚集：在处理冲突的过程中在处理冲突的过程中，发生的两个发生的两个

28、哈希地址不同的哈希地址不同的记录争夺同一个后继记录争夺同一个后继的哈希地址的现象称作的哈希地址的现象称作“二次聚集二次聚集”。再哈希法再哈希法Hi=RHi(key),i=1,2,.,k其中：其中：RHi均是不同的哈希函数（增加计算时间）均是不同的哈希函数（增加计算时间）链地址法链地址法将所有关键字为将所有关键字为（哈希哈希）同义词同义词的记录的记录存储在同一线性链表中存储在同一线性链表中。例：例：(19,14,23,01,68,20,84,27,55,11,10,79)H(key)=key mod 13建立一个公共溢出区建立一个公共溢出区除了哈希基本表除了哈希基本表，另外建立另外建立OverT

29、able0.v 溢出表溢出表，一旦发生一旦发生冲突冲突，则把发生冲突的记录填入溢出表则把发生冲突的记录填入溢出表。HashTable0.m-1OverTable0.v这样处理冲突怎样查找？这样处理冲突怎样查找？ASL?哈希表的查找及其分析哈希表的查找及其分析在哈希表上进行查找的过程和哈希造表的过程基本一致在哈希表上进行查找的过程和哈希造表的过程基本一致。给定给定K值值，根据造表时设定的根据造表时设定的哈希函数计算哈希地址哈希函数计算哈希地址若表中此位置上若表中此位置上没有记录没有记录，则查找不成功；则查找不成功；若表中此位置上若表中此位置上有记录有记录，则比较关键字则比较关键字，若和给定值相等

30、若和给定值相等，则查找成功；则查找成功；若和给定值不相等若和给定值不相等，则根据造表时设定的则根据造表时设定的处理冲突的方法处理冲突的方法找找“下一个地址下一个地址”，直至哈希表中某个位置为直至哈希表中某个位置为“空空”（不成功不成功），或或者表中所填记录的关键字者表中所填记录的关键字等于给定值等于给定值（成功成功）为止为止哈希表的查找性能哈希表的查找性能用哈希表表示动态查找表用哈希表表示动态查找表，原希望其平均查找长度为原希望其平均查找长度为1 1（成功成功）或或0 0（失败失败）。但由于构建哈希表时可能会产生冲突但由于构建哈希表时可能会产生冲突，因此在哈希因此在哈希表上进行查找表上进行查找

31、还是需要通过还是需要通过“比较比较”来确定查找是否成功来确定查找是否成功，因此因此仍然存在仍然存在平均查找长度平均查找长度的问题的问题。一般情况下一般情况下，在哈希函数为在哈希函数为 均匀均匀 的前提下的前提下，哈希表的平哈希表的平均查找均查找长度长度仅取决于仅取决于处理冲突的方法处理冲突的方法和和哈希表的装填因子哈希表的装填因子。哈希表的装填因子定义为哈希表的装填因子定义为：=表中记录数表中记录数/哈希表长度哈希表长度即即装满的程度装满的程度例：例：哈希函数为哈希函数为H(key)=key mod 13,利用利用线性探测线性探测再散列处理冲突：再散列处理冲突：Hi=(H(key)+di)mo

32、d m，m=14如：如：key=84H(84)=6H1=(6+1)mod 14=7H2=(6+2)mod 14=8成功成功：比较了：比较了3次次key=36H(36)=10H1=(10+1)mod 14=11H2=(10+2)mod 14=12H3=(10+3)mod 14=13失败失败：比较了：比较了3次次ASL？在等概率查找的情况下在等概率查找的情况下，可以证明：可以证明：线性探测再散列线性探测再散列的哈希表查找成功的平均查找长度为的哈希表查找成功的平均查找长度为：(1 1+1 1/(/(1 1-)/)/2 2随机随机(或平方或平方)探测再散列探测再散列的哈希表查找成功的平均查找长度为的哈

33、希表查找成功的平均查找长度为：(ln(ln(1 1-)/)/链地址链地址处理冲突的哈希表查找成功的平均查找长度为：处理冲突的哈希表查找成功的平均查找长度为：1 1+/2 2哈希表的平均查找长度哈希表的平均查找长度不是不是 n 的函数的函数，而而是是的函数的函数，因此虽然因此虽然不能做到平均查找长度为不能做到平均查找长度为1，但可以但可以设计一个哈希表设计一个哈希表，使它的平均使它的平均查找长度查找长度控制在一个期望值控制在一个期望值之内之内。最后要说明的一点是最后要说明的一点是，对开放定址的哈希表对开放定址的哈希表不能随意删除表中记不能随意删除表中记录录，而必须在该记录所在位置作一而必须在该记录所在位置作一特殊标记特殊标记，同时需修改查找算法同时需修改查找算法添加添加识识别已被删除记录别已被删除记录。