第8章 查 找,8.1 基本概念 8.2 静态查找 8.3 动态查找 8.4 哈希查找,一、 何谓查找表 ？,查找表是由同一类型的数据元素（或记录）构成的集合。,由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。,8.1 基 本 概 念,二、 对查找表经常进行的操作,1. 查询某个“特定的”数据元素是否在查找表中； 2. 检索某个“特定的”数据元素的各种属性； 3. 在查找表中插入一个数据元素； 4. 从查找表中删去某个数据元素。,仅作查询和检索操作的查找表。,1. 静态查找表,有时在查询之后，还需要将不在查找表中的数据元素插入到查找表中； 或者，从查找表中删除指定的数据元素。,2. 动态查找表,三、查找表的分类,是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。,四、关键字,若此关键字可以识别惟一的一个记录，则称之谓“主关键字”。,若此关键字能识别若干记录，则称 之谓“次关键字”。,例如：学生管理系统中，可将姓名作为关 键字，也可将学号作为关键字。,学号 姓名 专业 年龄 01 王洪 计算机 17 02 孙文 计算机 18 03 谢军 计算机 18 04 李辉 计算机 20 05 沈福 计算机 25 06 余斌 计算机 19 07 巩力 数学 17 08 王辉 数学 18,根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）的过程。,五、查找,若查找表中存在这样一个记录，则称查找成功，返回整个记录的信息，或返回该记录在查找表中的位置；否则称查找不成功，返回空记录或空指针。,由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表的元素之间人为地 附加某种确定的关系，即： 用另外一种结构来表示查找表。,六、如何进行查找,查找的方法取决于查找表的结构。,8.2 静 态 查 找,数据元素类型的定义为:,typedef struct keyType key; / 关键字域 / 其它属性域 ElemType ;,以顺序表或线性链表表示静态查找表的查找。,8.2.1 顺序查找顺序表,se_list,查找成功！,查找失败！,分析顺序查找的时间性能。,定义： 查找算法的平均查找长度ASL 为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值,其中: n 为表长，Pi 为查找表中第 i 个记录的概率 且 Ci为找到该记录时，曾和给定值 比较过的关键字的个数,顺序表查找的平均查找长度为：,对顺序表而言，Ci = n-i+1,ASL = nP1 +(n-1)P2 + +2Pn-1+Pn,在等概率查找的情况下，,上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。,8.2.2 折半查找顺序表,若以有序表表示静态查找表，则查找过程可以折半进行。,bi_list,长度n,例如， key = 64 的查找过程如下：,low,high,mid,low,mid,high,mid,low 指示查找区间的下界; high 指示查找区间的上界; mid = (low+high)/2。,int binarysearch(elemtype bi_list,keytype key,int n) /在有序表bi_list1bi_listn中查找关键字为key的记录 int low,high,mid; low=1; high=n; while(low=high) mid=(low+high)/2; if(bi_listmid.key=key) break;/找到记录 else if(bi_listmid.keykey) low=mid+1;/在右半继续查找 else high=mid-1;/在左半继续查找 if(low=high) return mid; else return FALSE;/查找成功时返回该记录的下标序号， 失败时返回FALSE ,设查找每一个记录的概率相同，即均为1/10， 平均查找长度 ASL= PiCi=（1+22+43+34）/10,二分查找法查找过程的判定树描述: 1 2 3 4 5 6 7 8 9 10 例 L2=( 3, 12, 24, 37, 45, 53, 61, 78, 90, 100 ) 查找过程可用如下判定树描述:,Key=24的查找路径为5,2,3,所需的比较次数为3,查找第5个记录需的比较次数为1,查找第2、8个记录需的比较次数均为2,查找 n 个元素的判定树是唯一的,假设 n=2h-1 并且查找概率相等 则,一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。,在 n50 时，可得近似结果,8.2.3 分块查找（索引顺序查找）,在建立顺序表的同时，建立一个索引。,例如：,索引顺序表 = 索引表 + 顺序表,顺序表,索引,索引顺序表的查找过程：,1. 由索引确定记录所在区间；,2. 在顺序表的某个区间内进行查找。,可见，索引顺序查找的过程也是一个“缩小区间”的查找过程。,索引表,最大关键字,起始地址,第1块,第2块,第3块,22,48,86,例：,特点：块间有序 块内无序,顺序表,8.3 动 态 查 找,8.3.1 二叉排序树（二叉查找树）,1定义,2查找算法,3插入算法,4删除算法,5查找性能的分析,（1）若它的左子树不空，则左子树上所有结点 的值均小于根结点的值；,1定义：,二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：,（3）它的左、右子树也都分别是二叉排序树。,（2）若它的右子树不空，则右子树上所有结点 的值均大于根结点的值；,例如:,是二叉排序树。,不,通常，取二叉链表作为二叉排序树的存储结构。,typedef struct bsnode /定义二叉排序树中的结点类型 keytype key; struct bsnode *lchild; struct bsnode *rchild; bsnodetype;,2二叉排序树的查找算法,1. 若给定值等于根结点的关键字, 则查找成功； 2. 若给定值小于根结点的关键字，则继续在左子树上进行查找； 3. 若给定值大于根结点的关键字，则继续在右子树上进行查找。,否则:,若二叉排序树为空，则查找不成功；,例如:,二叉排序树,查找关键字,= 50 ,50,50,35 ,50,30,40,35,50,90 ,50,80,90,95 ,从上述查找过程可见，,在查找过程中，生成了一条查找路径:,从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;,或者,从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。,查找成功,查找不成功,算法8.5 用非递归算法描述二叉排序树的查找 ：,bsnodetype *bs_search(bsnodetype *bt,keytype key) bsnodetype *p=bt; /指针p指向根结点，搜索从根结点开始 while (p!=NULL ,3二叉排序树的插入算法,若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点。 其插入位置由查找过程得到。,二叉排序树的插入算法（算法8.6）如下： void bs_insert (bsnodetype *bt , bsnodetype *pn) if(*bt=NULL) *bt=pn; /如果根结点为空，就把待插结点作为根结点 else if(*bt)-keypn-key) bs_insert( /如果待插结点的值大于根结点，就插入到右子树中 ,（1）被删除的结点是叶子； （2）被删除的结点只有左子树或者只有右子树 （3）被删除的结点既有左子树，也有右子树。,4二叉排序树的删除算法,可分 3 种情况讨论：,和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。,（1）被删除的结点是叶子结点,其双亲结点中相应指针域的值改为“空”,（2）被删除的结点只有左子树或者 只有右子树,其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。,（3）被删除的结点既有左子树，也有右子树,以其前驱替代之，然后再删除该前驱结点,void bs_delete ( bsnodetype *bt, keytype key) bsnodetype *p,*q,*r,*s; p=NULL; q=*bt; while(q /在二叉树中查找关键字等于key的结点,删除算法描述如下：, ,if(q=NULL) return; /如果二叉树中没有该结点，则不进行删除，直接返回 if(q-lchild=NULL) s=q-rchild; else s=q-lchild; r=s; while(r-rchild) r=r-rchild; r-rchild=q-rchild; /若被删结点有左子树，则在其左子树中找到中序遍历下的最后一个结点r, , ,if(p=NULL) *bt=s; /如果要删除的结点是根结点，就令s为根结点 else if(q=p-lchild) p-lchild=s; else p-rchild=s; free(q); , , ,若被删结点没有左子树，则用其右孩子代替它（注意，右孩子可以为空） 若被删结点有左子树，则在其左子树中找到中序遍历的最后一个结点r，把被删结点的右子树作为结点r的右子树，并用被删结点的左孩子代替被删结点。,注意：如果被删结点是根结点，同样适用上述方法，只不过要对根结点做调整，因为原根结点要被删除，所以把取代根结点的结点作为新的根结点。,5二叉排序树的查找性能分析,对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大。,由关键字序列 3，1，2，5，4构造而得的二叉排序树,由关键字序列 1，2，3，4，5构造而得的二叉排序树，,例如：,2,1,3,4,5,3,5,4,1,2,ASL =（1+2+3+4+5）/ 5 = 3,ASL =（1+2+3+2+3）/ 5= 2.2,含n个结点的平均查找长度为：,8.3.2 平衡二叉树,什么是平衡二叉树(Balanced Binary Tree) ? 平衡二叉树是空树,或者是具有以下性质的二叉树: 它的左子树和右子树也都是平衡二叉树并且 左子树和右子树的深度之差的绝对值不超过1 结点的平衡因子BF(Balance Factor)是 左子树的深度减去右子树的深度,它只可能是-1,0,1 平衡二叉树(也称AVL树)的深度为O(log N)(其中N为结点个数) 它的平均查找长度也是O(log N),平衡二叉树及平衡因子举例,平衡的二叉树,不平衡的二叉树,不平衡二叉树及平衡因子举例,二叉排序树转成平衡树示例 设关键字序列为(13,24,37,90,53),0 13,-1 13,0 24,0 37,0 13,-2 13,-1 24,0 24,0 37,0 53,0 13,0 13,0 37,0 90,0 53,-1