第9章 查找.ppt

1、第九章 查找,何谓查找表 ？,查找表是由同一类型的数据元素(或记录)构成的集合。,由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。,对查找表经常进行的操作:,1）查询某个“特定的”数据元素是否在查找表中； 2）检索某个“特定的”数据元素的各种属性； 3）在查找表中插入一个数据元素； 4）从查找表中删去某个数据元素。,仅作查询和检索操作的查找表。,静态查找表,若在查找过程中同时插入查找表中不存在的数据元素；或者从查找表中删除已存在的某个数据元素。,动态查找表,查找表可分为两类:,是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。,关键字,

2、若此关键字可以识别唯一的一个记录，则称之为“主关键字”。,若此关键字能识别若干记录，则称 之为“次关键字”。,根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）,查找,若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置； 否则称“查找不成功”，查找结果：给出 “空记录”或“空指针”。,由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说， 用另外一种结构来表示查找表。,如何进行查找？,查找的方法取决于查找表的结构。,9.1

3、 静态查找表,9.2 动态查找树表,9.3 哈希表,静态查找表:可以有不同的表示方法，在不同的表示方法中，实现查找操作的方法也不同,9.1 静 态 查 找 表,顺序查找表,有序查找表,索引顺序表,以顺序表或线性链表表示静态查找表,查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。找到：返回元素在线性表中的存储位置；未找到：返回0。,顺序查找表,算法描述,找64,64,监视哨,比较次数=5,比较次数： 查找第n个元素： 1 查找第n-1个元素：2 . 查找第1个元素： n 查找第i个元素： n -i +1 查找失败： n+1,查找算法的平均查找长度: 为确定记录在查找表中的位置，需和给

4、定值 进行比较的关键字个数的期望值 其中: n 为表长，Pi 为查找表中第i个记录的概率， 且 Ci为找到该记录时，曾和给定值 比较过的关键字的个数,分析顺序查找的时间性能。,在等概率查找的情况下， 顺序表查找的平均查找长度为：,对顺序表而言，Ci = n-i+1,ASL = nP1 +(n-1)P2 + +2Pn-1+Pn,typedef struct / 数据元素存储空间基址，建表时 / 按实际长度分配，0号单元留空 int length; / 表的长度 SSTable;,静态查找表的顺序存储结构,ElemType *elem;,int Search_Seq(SSTable ST, Key

5、Type key) / 在顺序表ST中顺序查找其关键字等于 / key的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为0。 ST.elem0.key = key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); return i; / 找不到时，i为0 / Search_Seq,若以有序表表示静态查找表，则查找过程可以基于“折半”进行。,有序查找表,思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。 前提：必须在具有顺序存储结构的有序表中进行,算法实现 设表长为n，low、high和mid分别指向

6、待查元素所在区间的上界、下界和中点,key为给定值 初始时，令low=1,high=n,mid=(low+high)/2 让key与mid指向的记录比较 若key=rmid.key，查找成功 若krmid.key，则low=mid+1 重复上述操作，直至lowhigh时，查找失败,ST.elem,ST.length,例如: key=64 的查找过程如下,low,high,mid,low,mid,high,mid,low 指示查找区间的下界; high 指示查找区间的上界; mid = (low+high)/2。,int Search_Bin ( SSTable ST, KeyType key

7、) low = 1; high = ST.length; / 置区间初值 while (low = high) mid = (low + high) / 2; if （EQ (key , ST.elemmid.key) ) return mid; / 找到待查元素 else if ( LT (key , ST.elemmid.key) ) high = mid - 1; / 继续在前半区间进行查找 else low = mid + 1; / 继续在后半区间进行查找 return 0; / 顺序表中不存在待查元素 / Search_Bin,分块查找又称索引顺序查找,是顺序查找的一种改进方法。 适

8、用条件：分块有序表,索引顺序表,块间有序 块内无序,在此查找法中，除表本身以外，尚需建立一个索引表。如图所示：,索引表,块中的最大关键字,块内第一个记录位置的指针,索引顺序表的查找过程：,1）由索引确定记录所在区间；,2）在顺序表的某个区间内进行查找。,可见， 索引顺序查找的过程也是一个 “缩小区间”的查找过程。,9.2 动态查找表,特点：表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功，否则，插入关键字等于key的记录,动态查找表亦可有不同的表示方法：,二叉排序树（二叉查找树） 平衡二叉树 B - 树,二叉排序树（二叉查找树）,（1）若它

9、的左子树不空，则左子树上所有结 点的值均小于根结点的值；,定义：二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：,（3）它的左、右子树也都分别是二叉排序树。,（2）若它的右子树不空，则右子树上所有结 点的值均大于根结点的值；,是二叉排序树。,66,不,2二叉排序树的查找：,1）若给定值等于根结点的关键字，则查找成功； 2）若给定值小于根结点的关键字，则继续在左子树上进行查找； 3）若给定值大于根结点的关键字，则继续在右子树上进行查找。,否则,若二叉排序树为空，则查找不成功；,50,30,80,20,90,85,40,35,88,32,例如:,二叉排序树,查找关键字,key= 50,50,

10、50,35,50,30,40,35,50,90,50,80,90,95,3二叉排序树的建立,二叉排序树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点。并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。,若从一棵空树出发，经过一系列的查找插入操作之后，可生成一棵二叉树。且对其进行中序遍历可得到一个关键字的有序序列。这说明一个无序序列可通过构造一棵二叉排序树而变成一棵有序序列。,中序序列为： 10 20 23 25 30 35 40 50 80 85 88 90,二叉排序树查找分析,树型查找最坏情

11、况时，需要的查找时间取决于树的高度，当二叉排序树接近满二叉树时，其高度为log2n，最坏情况下查找时间为O(log n)，与二分查找是同样数量级的；当二叉排序树为只有一个端结点的所谓“退化树”时，其高度等于n，最坏情况下查找时间为O(n)，与顺序查找属于同一数量级。 为了保证树型查找有较高的查找速度，我们希望该二叉树接近满二叉树，也就是希望二叉树的每一个结点的左、右子树高度尽量接近平衡，即使按任意次序不断地插入结点，也不要使此树成为退化树。,树中每个结点的左、右子树深度之差（平衡因子）的绝对值不大于1 。,例如:,5,4,8,2,5,4,8,2,1,是平衡树,不是平衡树,平衡二叉树,一般地，假

12、设由于在二叉树上插入结点而失去平衡的最小子树的根结点指针为a（即a是离插入结点最近，且平衡因子绝对值超过1的祖先结点），则失去平衡后进行调整的规律可归纳为下列四种情况：,（1）单向右旋平衡处理：由于在*a的左子树的左子树上插入结点，使*a的平衡因子由1增至2而失去平衡，需进行一次顺时针旋转操作；,（2）单向左旋平衡处理：由于在*a的右子树的右子树上插入结点，使*a的平衡因子由-1减至-2而失去平衡，需进行一次逆时针旋转操作；,7,9,8,7,9,8,（3）双向旋转（先左后右）平衡处理：由于在*a的左子树的右子树上插入结点，使*a的平衡因子由1增至2而失去平衡，需进行两次旋转操作（先逆时针，后顺

13、时针）；,（4）双向旋转（先右后左）平衡处理:由于在*a的右子树的左子树上插入结点，使*a的平衡因子由-1减至-2而失去平衡，需进行两次旋转操作（先顺时针，后逆时针）；,构造平衡二叉（查找）树的方法是： 在插入过程中，采用平衡旋转技术。,例如:依次插入的关键字为5, 4, 2, 8, 6, 9,5,4,2,4,2,5,8,6,6,5,8,4,2,向右旋转 一次,先向右旋转 再向左旋转,4,2,6,5,8,9,6,4,2,8,9,5,向左旋转一次,继续插入关键字 9,9.3 哈 希 表,什么是哈希表？ 哈希函数的构造方法 处理冲突的方法 哈希表的查找,什么是哈希表？,对于频繁使用的查找表，理想的

14、情况是依据关键字直接得到其对应的数据元素位置，这就需要在关键字和数据元素存储位置之间建立一个确定的对应关系f，使每个关键字和结构中唯一的存储位置相对应。称这个对应关系f为哈希函数。按这个思想建立的表为哈希表。,若以下标为000 999 的顺序表表示之。,例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 xx999 (前两位为年份)。,则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。,对于表长不确定的动态查找表需在关键字与记录在表中的存储位置之间建立一个函数关系，即以 f(key) 作为关键字为 key

15、 的记录在表中的位置，通常称这个函数 f(key) 为哈希函数。,Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei,例如：对于如下 9 个关键字,设 哈希函数 f(key) = (Ord(第一个字母) -Ord(A)+1)/2,Chen,Zhao,Qian,Sun,Li,Wu,Han,Ye,Dei,问题: 若添加关键字 Zhou , 怎么办？,1) 哈希函数是一个映象，即： 将关键字的集合映射到某个地址集合上， 它的设置很灵活，只要这个地址集合的 大小不超出允许范围即可;,从这个例子可见，,2) 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“

16、冲突”现象，即： key1 key2，而 f(key1) = f(key2),哈希表的定义:,根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。,构造哈希函数的方法,1. 直接定址法,3. 平方取中法,5. 除留余数法,4. 折叠法,6. 随机数法,2. 数字分析法,哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a key + b,地址集合的大小 = = 关键字集合的大小 不会产生冲突。但实际使用

17、很少。,1. 直接定址法,5. 除留余数法,设定哈希函数为: H(key) = key MOD p 其中， pm (表长) 并且 p 应为不大于 m 的素数 以减少冲突的发生。,处理冲突的方法,“处理冲突” 的实际含义是： 为产生冲突的地址寻找下一个哈希地址,2. 链地址法,1. 开放定址法,为产生冲突的地址 H(key) 求得一个地址序列： H0, H1, H2, , Hs 1 sm-1 其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, , s,1. 开放定址法,对增量 di 有三种取法：,1) 线性探测再散列 di = 1,2,3, 2) 二次探测再散列 di = 12, -12, 22, -22, , 3) 随机探测再散列 di 是一组伪随机数序列, di = hi-1,