第八章查找.ppt
《第八章查找.ppt》由会员分享,可在线阅读,更多相关《第八章查找.ppt(94页珍藏版)》请在三一文库上搜索。
1、第八章 查找,第八章 查找,8.1 静态查找表 8.1.1 顺序表的查找 8.1.2 有序表的查找 8.1.3 索引顺序表的查找 8.2 动态查找表 8.2.1 二叉树和平衡二叉树 8.2.2 B-树和B+树的结构 8.3 哈希表 8.3.1 什么是哈希表 8.3.2 哈希函数的构造方法 8.3.3 冲突的处理方法,第八章 查找,本章要点,掌握:静态搜索表的顺序搜索和折半搜索方法 掌握:二叉搜索树的表示、搜索、插入、删除算法及 性能分析 掌握:哈希表函数的构造方法 了解:哈希表冲突处理方法,“学生”表格,8.1 查找的基本概念,1.查找表(Search Table) 由同一类型的数据元素(或记
2、录)构成的集合。,2.关键字(Key) 数据元素(或记录)中某个数据项的值,用它可标识一 个数据元素(或记录)。 主关键字(Primary Key):可唯一标识一个记录的关键字。 次关键字(Secondary Key):用以识别若干个记录的关键字。,3.查找(Search) 根据给定的某个值或某种条件,在查找表中确定一个或多个关键字等于给定值或满足给定条件的数据元素(或记录)的操作。若表中存在这样的一个记录,则称查找成功,否则称查找失败。,8.1 查找的基本概念,4.静态查找 对查找表只查询特定数据元素是否在表中或查询特定元素的各种属性,不对查找表作任何修改。,5.动态查找 修改查找表。表结构
3、本身是在查找过程中动态生成的,通常是查找不成功则将该元素插入到查找表中;如果存在,可能需要从表中删除它。,8.1 查找的基本概念,6.平均查找长度(衡量查找算法好坏的一个重要指标) 查找过程中,和给定值进行比较的关键字个数的期望值。,其中,Pi为查找表中第i个记录的概率,且,Ci为找到表中其关键字与给定值相等的第i个记录时, 和给定值已进行过比较的关键字个数。,对于含有n个记录的表,查找成功时的平均查找长度为,关键字类型说明 typedef float KeyType;/实型 typedef int KeyType;/整型 typedef char * KeyType;/字符串型 数据元素类型
4、定义 typedef struct KeyType key;/关键字域 ;/其它域 ElemType;,两个关键字的比较约定 /对数值型关键字 #define EQ(a,b) (a)(b) #define LT(a,b) (a)(b) #define LQ(a,b) (a) (b) /对字符串型关键字 #define EQ(a,b) (!strcmp(a),(b) #define LT(a,b) (strcmp(a),(b)0) #define LQ(a,b) (strcmp(a),(b)0),8.2 静态查找表,8.2.1 无序表的查找,无序表:查找表中的结点是按关键字的任意顺序排列的。,顺
5、序查找(Sequential Search):从表中最后一个(或第一个)记录开始,逐个进行记录的关键字与给定值的比较,若某个记录的关键字和给定值比较相等,则查找成功,找到所查记录;反之,若直到第一个(或最后一个)记录,其关键字和给定值比较都不相等,则表明表中没有所查记录,查找失败。,顺序查找算法(P217 算法9.1),int Search_Seq(SSTable ST,KeyType key) ST.elem0.keykey;/哨兵 for(iST.length;!EQ(ST.elemi.key,key); i); return i; /Search_Seq,8.2.1 无序表的查找,特点:
6、1)算法简单,适用面广 2)平均查找长度较大 3)在等概率情况下,ASL(n1)/2 4)若各结点被查找的概率不相同,应先查找概 率高的结点,8.2.2 有序表的查找,有序表:查找表按关键字有序。,1.折半查找(二分法查找),设用low和high表示当前查找区间的下界和上界,mid为区间的中间位置。,折半查找步骤: 1)查找范围中间位置的数据元素的关键字ST.elemmid与给定值key相比较 2)若ST.elemmidkey,则查找成功。 若ST.elemmidkey,则在查找范围low,mid-1内继续查找 查找区间不存在时(即lowhigh),查找失败。,8.2.2 有序表的查找,例:在
7、11个数据元素5 13 19 21 37 56 64 75 80 88 92中查找关键字为21和85的数据元素。,5 13 19 21 37 56 64 75 80 88 92 l m h,5 13 19 21 37 56 64 75 80 88 92 l m h,5 13 19 21 37 56 64 75 80 88 92 l,m h,5 13 19 21 37 56 64 75 80 88 92 l m h,5 13 19 21 37 56 64 75 80 88 92 l m h,5 13 19 21 37 56 64 75 80 88 92 l,m h,5 13 19 21 37 5
8、6 64 75 80 88 92 h l,8.2.2 有序表的查找,特点:1)只适用于关键字有序的顺序存储结构 2)平均查找长度为log2n(满二叉树P221) 3)最大比较次数为: log2n +1或 log2(n+1),判定树:描述查找过程的二叉树。,折半查找算法( P220 算法9.2 ),int Search_Bin(SSTable ST,KeyType key) low1; highST.length; while(lowhigh) mid(low+high)/2; if EQ(key,ST.elemmid.key) return mid; else if LT(key,ST.ele
9、mmid.key)highmid1; else lowmid+1; return 0; /Search_Bin,8.2.2 有序表的查找,2.斐波那契查找,根据斐波那契序列的特点来对表进行划分: F0=0,F1=1,Fi=Fi-1+F i-2,斐波那契查找步骤: 假设开始时,表中结点数目比某个斐波那契数小1,即n=Fu1。 1)将ST.elemFu-1 与 key相比较 2)若ST.elemFu-1 =key,则查找成功。 若ST.elemFu-1 key,则在 Fu-11, Fu1 内继续查找。 若ST.elemFu-1 key,则在 1, Fu-1 1 内继续查找。 若查找区间不存在,则查
10、找失败。,特点:1)平均性能较好,但最坏情况比折半查找差 2)算法中只有加、减运算,8.2.2 有序表的查找,3.插值查找 用插值的方法计算出一个与给定值比较的元素下标,i=,其中, ST.eleml 、 ST.elemh 分别为有序表中具有最 小关键字和最大关键字的记录。,8.2.2 有序表的查找,插值查找步骤: 根据key与ST.elemi.key的比较结果,修改查找区间的上界、下界,重复进行,直到查找成功,或查找区间不存在,则查找失败。,特点:1)只适用于关键字均匀分布的表 2)对表长较大的顺序表,其平均性能比折半查找好,8.2.3 索引顺序表的查找,索引顺序表查找(也称分块查找):,索
11、引顺序表查找步骤: 1.确定要查找的数据元素在表中的哪一块 2.在确定的块中查找数据元素,1)表中的数据元素被分为若干块,每块中的数据元素可 以任意存放,但块与块之间的数据元素的关键字值是 有序的。,2)建立一个索引表,该索引表的数据元素个数等于查找 表被分割的块数,即查找表中的每一块对应索引表中 的一个索引项。在索引项中存放对应块的最大关键字 值和该块的起始位置。,8.2.3 索引顺序表的查找,例:在查找表中查找key65和key111的数据元素。,8.2.3 索引顺序表的查找,索引表按关键字有序,可以利用顺序查找,也可用折半查找。 块中数据元素是任意存放的,则在块中只能是顺序查找。,其中,
12、n为查找表的长度,s为查找表分成的每一块中的数据元素个数。,当用顺序查找确定记录的所在块,则分块查找的平均查找长度(参考P226):,当用折半查找确定记录的所在块(即索引表用折半查找),则:,8.3 动态查找表,8.3.1 二叉排序树 ( 查找树或搜索树),1.二叉排序树(Binary Sort Tree),对二叉排序树进行中序遍历,可以按从小 到大的顺序,将各结点关键字排列起来。,二叉排序树是一棵空树或是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于 它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于 它的根结点的值; 它的左、右子树分别为二叉排序树。,
13、8.3.1 二叉排序树,二叉排序树的查找步骤: 当二叉排序树T不空时, 1)将给定值key与根结点的关键字T-data比较 2)若key=T-data,则查找成功 若keyT-data,则继续在左子树中查找 若keyT-data,则继续在右子树中查找,二叉排序的查找(P228 算法9.5(a),BiTree SearchBST(BiTree T,KeyType key) if(!T)|(EQ(key,Tdata.key) return(T); else if LT(key,Tdata.key) return(SearchBST(Tlchild,key); else return(SearchB
14、ST(Trchild,key); /SearchBST,如何将该算法转换成非递归?,8.3.1 二叉排序树,例:在图示的二叉排序树中查找关键字等于100的记录。,45,53,100,8.3.1 二叉排序树,2.二叉排序树的插入,向二叉排序树中插入一个新元素,必须先检查这个元素是否在树中已经存在。,新插入的结点一定是一个新添加的叶子结点,并且是查 找不成功时查找路径上访问的最后一个结点的左孩子或 右孩子结点。,先使用查找算法在树中检查要插入元素是否存在。 查找成功: 树中已有这个元素,不再插入。 查找不成功: 树中原来没有关键字等于给定值的结点,把新元素加到查找操作停止的地方。,8.3.1 二叉
15、排序树,在二叉排序树中插入关键字为23和88的结点,二叉排序的查找(P228 算法9.5(b),Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p) /查找成功,p指向该数据元素结点,返回TRUE,否则p指向查找路径上访问 /的最后一个结点,返回FALSE,f指向T的双亲 if(!T) pf;return FALSE; else if EQ(key,Tdata.key) pT;return TRUE; else if LT(key,Tdata.key) return SearchBST(Tlchild,key,T,p); else
16、return SearchBST(Trchild,key,T,p); /SearchBST,二叉排序的插入(P228 算法9.6),Status InsertBST(BiTree &T,ElemType e) if(!SearchBST(T,e.key,NULL,p) s(BiTree)malloc(sizeof(BiTNode); sdatae; slchildsrchildNULL; if(!p) Ts; else if LT(e.key,pdata.key)/p指向查找路径上的最后一个结点。 plchilds; else prchilds; return TRUE; else retur
17、n FALSE; /InsertBST,输入数据,建立二叉排序树的过程,输入数据序列(8 5 10 1 6 9 11 3 7 2 4),8.3.1 二叉排序树,同样的数据,输入顺序不同,建立起来的二叉搜索树的形态也不同。这直接影响到二叉搜索树的搜索性能。 如果输入序列选得不好,会建立起一棵单支树,使得二叉搜索树的高度达到最大,这样必然会降低搜索性能。,例:,2, 1, 3 1, 2, 3 1, 3, 2 2, 3, 1 3, 1, 2 3, 2, 1,8.3.1 二叉排序树,3.二叉排序树的删除,必须将因删除结点而断开的二叉链表重新链接起来,并确保仍是一棵二叉排序树。 防止重新链接后树的高度增
18、加。,假设被删结点为*p,其双亲结点为*f,设*p是*f的右孩子。,8.3.1 二叉排序树,(1)若*p结点为叶结点,只需修改其双亲结点的指针。,(2)若*p结点只有左子树(或右子树)H,只需令H直接成为其双亲结点*f的右子树。,删除单链结点,8.3.1 二叉排序树,(3)若*p结点的左子树和右子树均不空,2)令*p的右子树为*f的右子树, *p的左子树为H的左子树。,1)令*p的中序直接后继H(或直接前驱)替代*p,然后再从二叉排序树中删除*p的中序直接后继H(或直接前驱)。,删除结点80,令*p的中序直接后继H(或直接前驱) 的值替代*p的值,然后再从二叉排序树中删除*p的中序直接后继H
19、。,P,H,寻找左子树的最大结点或右子树中的最小结点。,删除结点80,令*p的右子树为*f的右子树, *p的左子树为H的左子树。,P,H,f,二叉排序树删除算法(P230 算法9.7),Status DeleteBST(BiTree &T,KeyType key) if(!T) return FALSE; else if EQ(key,Tdata.key) return delete(T); else if LT(key,Tdata.key) return DeleteBST(Tlchild,key); else return DeleteBST(Trchild,key); return TR
20、UE; /DeleteBST,二叉排序树删除算法(P230 算法9.8),void Delete(BiTree &p) if(!prchild)qp;pplchild;free(q); else if(!plchild) qp;pprchild;free(q); else /左右子树均不为空 qp;splchild; while(srchild)qs;ssrchild; /找p的直接前驱 pdatasdata;/s指向p的直接前驱 if(q!p)qrchildslchild;/重接*q的右子树 else qlchildslchild; /当p的左孩子是其直接前驱时, 重接*q的左子树 free
21、(s);/教材上漏了,补上! /Delete,8.3.1 二叉排序树,4.二叉排序树的查找分析,两棵不同形态的二叉排序树 ASL(a)=(1+2*2+3*4)/7=17/7 ASL(b)=(1+2+3+4+5+6+7)/7=28/7,8.3.1 二叉排序树,设二叉排序树的深度为n, 最差情况下,平均查找长度(n1)/2(顺序查找) 最好情况下,平均查找长度与log2n成正比(折半情况) 一般情况下,平均查找长度与logn等数量级,8.3.2 平衡二叉树,一、平衡二叉树(Balanced Binary Tree,也称AVL树),平衡因子BF:结点的左子树的深度减去它的右子树的 深度。,平衡二叉树
22、上所有结点的平衡因子只可能是1、0、1。 若有一个结点的平衡因子的绝对值大于1,则该二叉树是不平衡的。,平衡二叉树:一棵空树,或者它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差绝对值不超过1。,8.3.2 平衡二叉树,8.3.2 平衡二叉树,非平衡二叉树,平衡二叉树,平衡树的生成过程,0 13,关键字序列:13 24 37 90 53,左旋转,右旋转,左旋转,8.3.2 平衡二叉树,设在二叉排序树上插入新结点而失去平衡的最小子树根结点的指针为a,则二叉排序树调整的规律如下: 1.单向右旋平衡处理(左倾斜) 在*a的左子树根结点的左子树上插入结点,使*a的平衡因子由1增到2,则需进
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第八 查找
链接地址:https://www.31doc.com/p-2565173.html