数据结构查找

1、第九章第九章 查找查找静态查找表静态查找表9.19.1动态查找表动态查找表9.29.2哈希表哈希表9.39.3（1）掌握静态查找表的顺序表的查找、有序表的折半查找、静 态树表查找（最优查找树）、索引顺序表的查找方法。 （2）掌握动态查找表的二叉排序树、B_树和B+树的概念和构造 方法。（3）掌握哈希表方法处理思想和过程。各种查找方法的处理过程n查找表查找表(Search Table)：同一类型的数据元同一类型的数据元素的集合。素的集合。n静态查找表静态查找表(Static Search Table)：查询某个查询某个元素、检索指定元素的属性。元素、检索指定元素的属性。n动态查找表动态查找表(D

2、ynamic Search Table) ：查找查找后插入、删除。后插入、删除。n关键字关键字(Key) ：可以唯一标识一个数据元素可以唯一标识一个数据元素或记录的数据项的值。或记录的数据项的值。第九章第九章 查找查找n查找，检索查找，检索(Searching)：给出一个：给出一个key值，值，在含有若干个结点的序列中找出它。在含有若干个结点的序列中找出它。n查找成功查找成功当某个元素的当某个元素的key值等于给定值值等于给定值K，返回该元素的位置。返回该元素的位置。n查找失败查找失败所有元素的所有元素的key值均不等于给定值均不等于给定值值K，返回表示失败的标志。，返回表示失败的标志。第九章

3、第九章 查找查找n平均查找长度平均查找长度Average Search Length： n n ASL= pici 可简化为：可简化为：ASL=1/n ci i=1 i=1nn为结点个数，为结点个数，pi是查找第是查找第i个结点的概率，个结点的概率， 且且pi=1/n， ，即各结点的查找概率相等。，即各结点的查找概率相等。ci是找到第是找到第i个结点时与个结点时与key值进行的比较次数。值进行的比较次数。第九章第九章 查找查找 n pi=1 i=1典型的关键字类型说明和定义典型的关键字类型说明和定义n类型说明类型说明typedef float KeyType; /实型实型typedef int

4、 KeyType; /整型整型typedef char KeyType; /字符型字符型n类型定义类型定义typedef struct KeyType key; /关键字域关键字域 /其它域其它域SElemType;9.1 静态表查找静态表查找n静态查找表的抽象数据类型静态查找表的抽象数据类型ADT StaticsearchTable 数据对象数据对象D：具有同一特性和类型的元素的集合、具有同一特性和类型的元素的集合、可唯一标识数据元素的关键字。可唯一标识数据元素的关键字。 数据关系数据关系R：数据集合数据集合 基本操作基本操作P：create(&ST,n) /构造查找表构造查找表 destr

5、oy(&ST) /销毁查找表销毁查找表 search(ST,ch) /查找表中指定元查找表中指定元素素 Traverse(ST,visit() /遍历表遍历表 ADT StaticsearchTable9.1.1 顺序表的查找顺序表的查找n顺序表顺序表(Sequential List)：线性表的顺序存储结构：线性表的顺序存储结构 用数组用数组AMaxSize表示表示n元素类型为元素类型为ElemType，关键字，关键字key域的类型为域的类型为KeyType9.1.1 顺序表查找顺序表查找n顺序查找，线性查找顺序查找，线性查找Sequential Search：一种：一种最基本和最简单的查找方

6、法。从表中的第一个最基本和最简单的查找方法。从表中的第一个元素开始，顺序扫描。元素开始，顺序扫描。n将给定的值与表中逐个元素的关键字进行比较，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。直到两者相符，查到所要找的元素为止。n对于表中记录的关键字是无序的表，只能采用对于表中记录的关键字是无序的表，只能采用这种方法。这种方法。n静态查找表的顺序存储结构typedef struct ElemType *elem; int length;SSTable;顺序查找顺序查找int Search_Seq(SSTable ST, KeyType key) ST.elem0.k

7、ey=key; for(i=ST.length; ST.elemi.key!=key;i-) return i; 顺序查找顺序查找int Seqsch1(ElemType A,int n,KeyType K) An.key=K; 设置岗哨设置岗哨 for(int i=0; ;i+) if(Ai.key=K) break; if(in) return i; else return -1; n省略了对下标越界省略了对下标越界的检查，提高算法的检查，提高算法的执行速度的执行速度n时间复杂度为时间复杂度为O(n)n速度慢速度慢顺序查找表的平均查找长度顺序查找表的平均查找长度n在等概率且查找成功的情况下

8、：在等概率且查找成功的情况下： n n ASLss=PiCi=(1/n)(n-i+1) i=1 i=1 =(n+1)/2顺序查找表的平均查找长度顺序查找表的平均查找长度n顺序查找成功时最多查找顺序查找成功时最多查找n次，不成功时的次，不成功时的查找次数为查找次数为n+1。n此时的查找概率为此时的查找概率为Pi=1/(2n) n ASLss=1/(2n)(n-i+1)+1/2(n+1) i=1 =3/4(n+1)9.1.2 有序表的查找有序表的查找n有序表有序表：关键字有序，即表中的各元素按关关键字有序，即表中的各元素按关键字的值有序键字的值有序(升序或降序升序或降序)存放。存放。n二分查找，折

9、半查找二分查找，折半查找(Binary Search)：在有：在有序表中进行，先确定表的中点位置，再通过序表中进行，先确定表的中点位置，再通过比较确定下一步在哪一个半区查找。比较确定下一步在哪一个半区查找。n假设指针low和high分别指示待查元素所在区间的下界和上界，指针mid指示区间的中间位置，mid= (low+high)/2 n(1)若若key=rmid.key，成功，否则：成功，否则：n(2)若krmid.key, 则则low=mid+1，重复重复(1)；n直到查找成功直到查找成功n查找不成功时查找不成功时: lowhigh。基本思想基本思想n查找2112345678910 1105

10、 13 19 21 37 56 64 75 80 88 92lowhighmidhighmid lowmidn例如：已知11个数据元素的有序表：05,13,19,21,37,56,64,75,80,88,92现要查找关键字为21和85的数据元素。n查找8512345678910 1105 13 19 21 37 56 64 75 80 88 92lowhighmid lowmid lowmidhighint BinSearch(SeqList R,KeyType K) int low=1,high=n,mid; mid为二分点为二分点while(lowK) 继续继续 high=mid-1; R

11、low.mid-1 else low=mid+1; Rmid+1.high return 0; 查找失败查找失败查找成功查找成功二分查找二分查找二分查找的判定树二分查找的判定树n二分查找的判定树二分查找的判定树：以：以Rmid为根结点，左、为根结点，左、右两个区间对应左、右子树，子树的根是各右两个区间对应左、右子树，子树的根是各自区间的中点，自区间的中点，n二分查找的判定树是一棵理想平衡树，除最二分查找的判定树是一棵理想平衡树，除最后一层外，其余层是满的。后一层外，其余层是满的。n查找路线：在二叉树上用虚线标出访问结点查找路线：在二叉树上用虚线标出访问结点的顺序。的顺序。二分查找的判定树二分查

12、找的判定树 1 2 3 4 5 6 7 8 9 1012 23 26 37 54 60 68 75 82 96n(a) (b) (c)分别为分别为23、96、58的查找路线的查找路线54237526688260371296null4789653201(a)(b),(c)(c)(b)(b)二分查找二分查找n平均查找次数：利用二分查找的判定树，当平均查找次数：利用二分查找的判定树，当n足够大时，有：足够大时，有： ASLbn2(n+1)-1= log2n +1=hn最大查找次数为判定树的高度最大查找次数为判定树的高度h6319471025811具有具有11个元素的有序表进行二分查找时，查找成个元素

13、的有序表进行二分查找时，查找成功时的时间复杂度是什么？功时的时间复杂度是什么？1133)4*44*32*21 (1111niiibsCPASL9.1.4 索引顺序表查找索引顺序表查找索引的概念索引的概念n索引查找，分块查找索引查找，分块查找Index Search：在线性：在线性表的表的索引存储结构的基础上进行查找。索引存储结构的基础上进行查找。n把主表按照一定的函数关系或条件划分成若把主表按照一定的函数关系或条件划分成若干个逻辑上的子表，为每个子表建立一个索干个逻辑上的子表，为每个子表建立一个索引项，由这些索引项构成主表的一个索引表。引项，由这些索引项构成主表的一个索引表。索引的概念索引的概

14、念n索引项通常包括三个域：索引项通常包括三个域：n索引值域索引值域index：存储对应子表的索引值，：存储对应子表的索引值，相当于关键字，唯一标识索引项。相当于关键字，唯一标识索引项。n子表的开始位置域子表的开始位置域start：子表第一个元：子表第一个元素的存储位置。素的存储位置。n子表长度域子表长度域length：存储对应子表的元素：存储对应子表的元素个数。个数。索引顺序表的查找索引顺序表的查找 n分块查找分块查找、索引顺序查找索引顺序查找Blocking Search，将主表分成若干个子表将主表分成若干个子表( (块块) )，分块有序，分块有序，即，即块间按大小排序，块内不排序。块间按大

15、小排序，块内不排序。n建立一个块的最大建立一个块的最大(或最小或最小)关键字表，称之关键字表，称之为为“索引表索引表” 。索引顺序表的查找索引顺序表的查找 n在处理线性表时，希望能够快速查找，又要在处理线性表时，希望能够快速查找，又要经常动态变化，则可以采用分块查找方法。经常动态变化，则可以采用分块查找方法。n分块：分块：按结点元素关键字升序方式组织表中按结点元素关键字升序方式组织表中各块，则要求第一块中任一结点的关键字值各块，则要求第一块中任一结点的关键字值都小于第二块中所有结点的关键字值；第二都小于第二块中所有结点的关键字值；第二块中任一结点的关键字值都小于第三块中所块中任一结点的关键字值

16、都小于第三块中所有结点的关键字值；如此类推。有结点的关键字值；如此类推。n选择每块中的最大选择每块中的最大(或最小或最小)关键字值组成索关键字值组成索引表。引表。n索引表中的结点个数等于被分割的块数。索引表中的结点个数等于被分割的块数。 索引表 22 48 86 1 7 13最大关键字起始地址22 12 13 8920 33 42 44 38 24 48 60 58 74 49 86 53索引顺序表的查找算法索引顺序表的查找算法n查找关键字为查找关键字为k的元素，分两步进行：的元素，分两步进行：1.根据给定的索引值，在索引表上查找出索引根据给定的索引值，在索引表上查找出索引项，确定对应子表在主

17、表中的开始位置和长项，确定对应子表在主表中的开始位置和长度。度。2.再根据给定的关键字，在对应子表中查找出再根据给定的关键字，在对应子表中查找出元素结点。元素结点。n先用折半查找法由索引表查出先用折半查找法由索引表查出k所在的块，所在的块，再用顺序查找法在对应的块中找出再用顺序查找法在对应的块中找出k。分块查找分析分块查找分析n分块查找的平均查找长度为：分块查找的平均查找长度为： ASLbs=Lb+Lwn其中：其中：Lb是折半查找的平均查找长度，是折半查找的平均查找长度，Lw是是用顺序查找法查块内元素的平均查找长度。用顺序查找法查块内元素的平均查找长度。n分块查找的平均查找长度位于顺序查找和折

18、分块查找的平均查找长度位于顺序查找和折半查找之间。半查找之间。分块查找分析分块查找分析n以二分查找确定块：以二分查找确定块： ASLblk2(n/s+1)+s/2 以顺序查找确定块：以顺序查找确定块： ASLblk=(s2+2s+n)/2s=1/2(n/s+s)+1n时间复杂度：时间复杂度：O(n)(1) 平均查找长度：平均查找长度：折半查找最小，分块查找折半查找最小，分块查找次之，顺序查找最大；次之，顺序查找最大；(2) 表的结构：表的结构：顺序查找对有序表、无序表均顺序查找对有序表、无序表均适用；折半查找仅适用于有序表；分块查找适用；折半查找仅适用于有序表；分块查找要求表中元素是块与块之间

19、的记录按关键字要求表中元素是块与块之间的记录按关键字有序；有序；(3) 存储结构：存储结构：顺序查找和分块查找对向量和顺序查找和分块查找对向量和线性链表结构均适用；折半查找只适用于向线性链表结构均适用；折半查找只适用于向量存储结构的表。量存储结构的表。 小结小结9.2 动态查找表动态查找表n表结构在查找过程中动态生成。表结构在查找过程中动态生成。n即对于给定值即对于给定值key，若表中存在其关键字等，若表中存在其关键字等于于key的记录，则查找成功；否则插入关键的记录，则查找成功；否则插入关键字等于字等于key的记录。的记录。动态查找表的抽象数据类型动态查找表的抽象数据类型ADT Dynami

20、csearchTable 数据对象数据对象D：具有同一特性和类型的元素的集合、具有同一特性和类型的元素的集合、可唯一标识数据元素的关键字。可唯一标识数据元素的关键字。 数据关系数据关系R：数据集合数据集合 基本操作基本操作P：InitDSTable(&DT,n) /构造查找表构造查找表 destroyDSTable(&DT) /销毁查找表销毁查找表 searchDSTable(DT,ch) /查找表中指定元素查找表中指定元素 TraverseDSTable(DT,visit() /遍历表遍历表 ADT DynamicsearchTable9.2.1 二叉排序树和平衡二叉树二叉排序树和平衡二叉树

21、二叉排序树的定义二叉排序树的定义n二叉排序树二叉排序树 Binary Sort Treen二叉查找树、二叉搜索树二叉查找树、二叉搜索树Binary Search Treen结点的关键字：结点的关键字：n简单类型简单类型结点的值结点的值n记录类型记录类型结点的某一个域的值结点的某一个域的值n以结点值域以结点值域data中关键字域中关键字域key作为结点作为结点的关键字。的关键字。二叉排序树的定义二叉排序树的定义n二叉排序树或是一棵空树，或是具有如下特二叉排序树或是一棵空树，或是具有如下特性的非空二叉树：性的非空二叉树：1.若它的左子树非空，则左子树上所有结点的若它的左子树非空，则左子树上所有结点

22、的关键字均小于根结点的关键字；关键字均小于根结点的关键字；2.若它的右子树非空，则右子树上所有结点的若它的右子树非空，则右子树上所有结点的关键字均大于根结点的关键字关键字均大于根结点的关键字3.左、右子树本身又各是一棵二叉排序树。左、右子树本身又各是一棵二叉排序树。二叉排序树的抽象数据类型二叉排序树的抽象数据类型n结点类型结点类型BTreeNode，根结点指针，根结点指针BSTint Find(BTreeNode * BST, ElemType& item);查找查找int Update(BTreeNode *BST, const ElemType& item);更新更新void Insert

23、(BTreeNode * BST, const ElemType& item); 插入插入int Delete(BTreeNode * BST, const ElemType& item);删除删除29925603913523118例如中序遍历序列：中序遍历序列： 9 13 18 25 29 31 39 52 60 n二叉排序树的特点：中序遍历二叉排序树得到的关键字序列是一个递增的有序序列。n在二叉排序树中查找关键字值为29和30的过程。29925603913523118n查找3029925603913523118n基本思路：n若二叉排序树为空，则查找失败；n若key等于当前根结点的值，则查找

24、成功；n若key小于当前根结点的值，在继续在根的左子树中查找；n若key大于当前根结点的值，在继续在根的右子树中查找；n如何在二叉排序树中查找给定关键字值为key的结点？二叉排序树的查找二叉排序树的查找int Find(BTreeNode * BST, ElemType& item); if(BST=NULL) return; else if(item.key=BST-data.key) item=BST-data; return 1; else if(item.keydata.key) return Find(BST-left,item); 递归算法递归算法 else return Find

25、(BST-right,item); 二叉排序树的查找二叉排序树的查找int Find(BTreeNode * BST, ElemType& item); while(BST!=NULL) 非递归算法非递归算法 if(item.key=BST-data.key) item=BST-data; 查找成功，值由查找成功，值由item带回带回 return 1; else if(item.keydata.key) BST=BST-left; 查找左子树查找左子树 else BST=BST-right; 查找右子树查找右子树 return 0; 二叉排序树的查找二叉排序树的查找n二叉排序树的查找：与二分

26、查找类似，逐步二叉排序树的查找：与二分查找类似，逐步缩小查找范围。缩小查找范围。n在二叉排序树上的平均查找长度与二叉树的在二叉排序树上的平均查找长度与二叉树的形态有关。树的形态比较均衡时，树的高度形态有关。树的形态比较均衡时，树的高度较小，平均查找长度也较小。较小，平均查找长度也较小。二叉排序树的更新二叉排序树的更新n与二叉排序树的算法基本相同与二叉排序树的算法基本相同n在更新算法中，在查找到待更新元素后，将在更新算法中，在查找到待更新元素后，将item值赋给该元素。值赋给该元素。nitem可为变参，也可为实参。可为变参，也可为实参。二、二叉排序树的插入和删除1、二叉排序树的插入基本思想：n若

27、二叉排序树为空，则待插结点作为根结点插入到空树中；n若待插结点的关键字值和根结点的关键字值相等，则说明树中已有此结点，无需插入；n若待插结点的关键字值小于根结点的关键字值，则将待插结点插入到根的左子树中；n若待插结点的关键字值大于根结点的关键字值，则将待插结点插入到根的右子树中；n如此进行下去，直到把待插结点作为一个叶结点插入到二叉排序树中，或直到发现树中已存在该结点为止 在二叉排序树中插入58和3929925603913523118 插入5858 插入392992560391352311858n对给定的关键字序列7,16,4,8,20,9,6,18,5，构造一棵二叉排序树。n二叉排序树的生成

28、是从空的二叉排序树开始，每输入一个数据，建立一个新结点，插入到当前已经生成的二叉排序树中。输入数据：输入数据：7164208918656208416759187二叉排序树的插入二叉排序树的插入n例：待建立二叉排序树的一组元素为例：待建立二叉排序树的一组元素为n(38,26,62,94,35,50,28,55)3826623555945028n练习：n输入一个序列45,24,53,45,12,30,90，构造一棵二叉排序树。123090245345二叉排序树的插入二叉排序树的插入n向二叉排序树插入元素的递归过程：向二叉排序树插入元素的递归过程：n若树为空：由若树为空：由item生成的结点为根结点

29、生成的结点为根结点n若若item.key小于根结点的小于根结点的key，则，则item插入到插入到左子树。左子树。n若若item.key大于根结点的大于根结点的key，则，则item插入到插入到右子树。右子树。二叉排序树的插入二叉排序树的插入int Insert(BTreeNode *& BST, ElemType& item); if(BST=NULL) 递归算法递归算法 BTreeNode * p=new BTreeNode; p-data=item; p-left=p-right=NULL; BST=p; else if(item.keydata.key) Insert(BST-left

30、,item); 向左子树插入向左子树插入 else Insert(BST-right,item); 向右子树插入向右子树插入 二叉排序树的删除二叉排序树的删除1.删除叶子结点：直接删除，双亲中指向该结删除叶子结点：直接删除，双亲中指向该结点的指针域置为点的指针域置为NULL。2.删除单分支结点：将双亲与孩子直接连接删除单分支结点：将双亲与孩子直接连接3.删除双分支结点：用它的中序后继替换它，删除双分支结点：用它的中序后继替换它，并使整棵树保持并使整棵树保持BST性质。性质。29925603913523118删除删除3129ps29925603913523118删除删除60删除删除3939删除删

31、除13pf9291825291825s29925603913523118删除删除3129psn练习n依次删除二叉排序树中的关键字为13，12，4，8的各结点后，该二叉排序树的结构。76141041285111513答案答案176141051115答案答案214106117515n练习n依次删除二叉排序树中的关键字为13，12，4，8的各结点后，该二叉排序树的结构。76141041285111513三、二叉排序树的查找分析 下面两棵二叉排序树分别由序列12,24,37,45,53,93和序列45,24,53,12,37,93构成，计算其平均查找长度。12243745539345245312379

32、3122437455393621)654321 (61ASL452453123793614)333221 (61ASLn由此可见，在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关。在最坏情况下二叉排序树是通过把一个有序表的n个结点依次插入而生成的，此时所得的二叉排序树退化为深度为n的单支树，它的平均查找长度和顺序查找相同，亦是(n+1)/2；在最好的情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与判定树相似的二叉排序树，此时它的平均查找长度大约是log2n。n如果所建二叉排序树的形态和折半查找的判定树相似，平均查找长度和log2n是等数量级的，尚需在构造二叉排

33、序树的过程中进行平衡化处理，成为平衡二叉树。n如何构造平衡二叉树？调用二叉排序树算法的程序举例调用二叉排序树算法的程序举例n假定二叉排序树中元素类型假定二叉排序树中元素类型ElemType定义定义为为student记录类型：记录类型： struct student int key; int rest; void main() 定义数组，指针等；定义数组，指针等； 调用对二叉排序树操作的各种算法；调用对二叉排序树操作的各种算法；n树表查找是对树型结构所做的查找树表查找是对树型结构所做的查找n树型存储结构树型存储结构树表树表n树型逻辑结构树型逻辑结构树树n平衡二叉树平衡二叉树balanced bi

34、nary tree平衡树平衡树n由于二叉排序树的结构可能不平衡，导致对由于二叉排序树的结构可能不平衡，导致对树的运算的时间复杂度增加。树的运算的时间复杂度增加。n调整二叉排序树的结构，使其始终成为平衡调整二叉排序树的结构，使其始终成为平衡的状态的状态平衡二叉树。平衡二叉树。平衡二叉树平衡二叉树n平衡树平衡树 Adelson-Velskii and LandisAVL树树n定义：若一棵二叉树中每个结点的左、右子定义：若一棵二叉树中每个结点的左、右子树的高度至多相差树的高度至多相差1，则称此树为平衡树。，则称此树为平衡树。n平衡因子平衡因子balance factor：二叉树中的每个：二叉树中的每

35、个结点的左子树高度减去右子树高度。结点的左子树高度减去右子树高度。n平衡树中的每个结点的平衡因子只能是：平衡树中的每个结点的平衡因子只能是：1，0，-1平衡二叉树平衡二叉树299256039135231181-10000000平衡二叉树平衡二叉树76141041285111513000000000-1-2非平衡二叉树非平衡二叉树n如何构造平衡二叉树呢？n在构造平衡二叉树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，若是，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，以达到新的平衡。n如果在平衡树上插入一个结点，可能影响到如果

36、在平衡树上插入一个结点，可能影响到某一结点的平衡因子，如果导致破坏了平衡某一结点的平衡因子，如果导致破坏了平衡树的限制条件，就需要进行调整。树的限制条件，就需要进行调整。n最小不平衡子树最小不平衡子树以离插入结点最近，且平以离插入结点最近，且平衡因子绝对值大于衡因子绝对值大于1的结点作为根的子树。的结点作为根的子树。n对最小不平衡子树进行调整对最小不平衡子树进行调整平衡树平衡树n归纳为四种情况：归纳为四种情况：(1) LL型调整操作型调整操作在在A结点的左孩子的左子结点的左孩子的左子树上插入结点，导致平衡因子变化而引起的树上插入结点，导致平衡因子变化而引起的不平衡所进行的调整操作。不平衡所进行

37、的调整操作。(2) RR型调整操作型调整操作(3) LR型调整操作型调整操作(4) RL型调整操作型调整操作平衡树平衡树1321183529918139352921LL型3492260131822346013918RR型359291318837241628189138352937162428RL型n输入序列为13,24,37,90,53构造平衡二叉排序树的过程。9037532413133724379053n练习：对给定的数列R=7,16,4,8,20,9,6,18,5构造一棵平衡二叉树。4720961685189.2.2 B-树树nB-树是由树是由R.bayer和和E.Maccreight于于

38、1970 年年提出的，一种特殊的多元树，一种在外存文提出的，一种特殊的多元树，一种在外存文件系统中常用的动态索引技术。件系统中常用的动态索引技术。nB-树或是一棵空树，或是一棵具有如下结点树或是一棵空树，或是一棵具有如下结点结构的树：结构的树：nB-树中的每个结点的大小相同，树中的每个结点的大小相同，m3为为B-树树的阶，的阶，par为指向父结点的指针域。为指向父结点的指针域。nparp0k1p1k2p2 knpn kmpmB-树树1.B-树的定义树的定义(1) 每个结点至少包含下列数据域：每个结点至少包含下列数据域： (j,p0,k1, p1, k2, kj, pj)nJ为关键字总数，为关键

39、字总数， ki(1ij)是关键字，是关键字， pi(0ij)是指向孩子的指针，叶子结点是指向孩子的指针，叶子结点pi为为空。空。n用用keys(pi)表示子树表示子树pi中的所有关键字有：中的所有关键字有：keys(p0)k1keys(p1)k2 kjkeys(pj)B-树树(2) 所有的叶子都在同一层上，叶子的所在层所有的叶子都在同一层上，叶子的所在层数为树的高度数为树的高度h。(3) 每个非根结点中包含的关键字个数每个非根结点中包含的关键字个数j满足：满足： m/2 j m-1 (4) 若树非空，则根至少有一个关键字，若根若树非空，则根至少有一个关键字，若根不是叶子，则它至少有两棵子树，根

40、至多不是叶子，则它至少有两棵子树，根至多有有m-1个关键字，故至多有个关键字，故至多有m棵子树。棵子树。B-树树2. B-树的查找：多路平衡查找树，可用顺序树的查找：多路平衡查找树，可用顺序查找或二叉查找。查找或二叉查找。3. B-树的插入：先插入到某个叶子，再根据树的插入：先插入到某个叶子，再根据B-树的性质进行调整。树的性质进行调整。4. B-树的删除：先删除指定的叶子，再根据树的删除：先删除指定的叶子，再根据B-树的性质进行调整。树的性质进行调整。B-树树nB-树的阶树的阶n一棵度为一棵度为m的的B-树称为树称为m阶阶B_树。树。n根据定义，在一棵根据定义，在一棵5阶阶B-树里，根的关键

41、字树里，根的关键字数目可以是数目可以是14，子树数可以是，子树数可以是25，其它，其它结点中关键字数目可以是结点中关键字数目可以是24，若该结点不，若该结点不是叶子，可以有是叶子，可以有35棵子树。棵子树。9.3 哈希表一、基本概念 哈希、哈希查找和哈希表 哈希（Hash）又称散列，是一种重要的存储方法。它的基本思想是：以结点的关键字k为自变量，通过一个确定的函数H，计算出对应的函数值H(k)，作为结点的存储位置，将结点存入H(k)所指的存储位置上。 哈希查找是一种常见的查找方法，查找时根据要查找的关键字用同样的函数H计算地址，然后到相应的单元去取要找的结点。顺序查找、折半查找、树表的查找都是

42、建立在比较基础上的查找，而哈希查找是直接查找。 用哈希法存储的线性表叫做哈希表。上述的H函数称为哈希函数。H(k)称为哈希地址。通常哈希表的存储空间是一个一维数组，哈希地址是数组的下标。 冲突和同义词 若某个哈希函数H对于不同的关键字key1和key2得到相同的哈希地址，这种现象称为冲突。而发生冲突的这两个关键字则称为该哈希函数的同义词。9.3.2 哈希函数的构造方法哈希函数的构造方法n构造哈希函数的目标：使哈希地址尽可能构造哈希函数的目标：使哈希地址尽可能地均匀分布在散列空间上，计算要简单。地均匀分布在散列空间上，计算要简单。n根据关键字的结构和分布情况，构造出相根据关键字的结构和分布情况，

43、构造出相适应的哈希函数。适应的哈希函数。n假定关键字为整型数假定关键字为整型数哈希函数哈希函数1.直接定址法直接定址法以关键字以关键字K本身或本身或K加上一个常加上一个常数数C，生成散列地址。，生成散列地址。n对应的哈希函数为：对应的哈希函数为：h(K)=K+Cn当当C=0时，为关键字本身。时，为关键字本身。n计算最简单，一般情况下无冲突。计算最简单，一般情况下无冲突。n如发生冲突，则可能是关键字错误。如发生冲突，则可能是关键字错误。哈希函数哈希函数2.数字分析法数字分析法取关键字中某些取值较分散的取关键字中某些取值较分散的数字位作为散列地址。数字位作为散列地址。n适合于所有关键字已知，并对关

44、键字中的每适合于所有关键字已知，并对关键字中的每一位的取值分布情况作出了分析。一位的取值分布情况作出了分析。n例如：例如：2004*哈希函数哈希函数3.平方取中法平方取中法取关键字平方的中间某些位取关键字平方的中间某些位作为散列地址。作为散列地址。n具体位数依实际需要而定具体位数依实际需要而定n一个数的平方的中间某些位和数的每一位一个数的平方的中间某些位和数的每一位都有关。都有关。即：得到散列地址与关键字的每即：得到散列地址与关键字的每一位都有关，这样就比较分散。一位都有关，这样就比较分散。n适合于每一位都不够分散或较分散的位数适合于每一位都不够分散或较分散的位数不满足实际需要的情况。不满足实

45、际需要的情况。哈希函数哈希函数4.折叠法折叠法将关键字分割成位数相同的若干段，将关键字分割成位数相同的若干段，然后将各段的叠加和作为散列地址。然后将各段的叠加和作为散列地址。n段的位数取决于散列地址的位数，最后一段段的位数取决于散列地址的位数，最后一段位数可少一些。叠加和舍去最高位进位。位数可少一些。叠加和舍去最高位进位。n例如：例如：K=68242324，散列地址为，散列地址为3位，分成位，分成3段：段：682、423、24，叠加和为，叠加和为129。以此。以此作为该关键字的散列地址。作为该关键字的散列地址。n适合于关键字位数较多而所需要的散列地址适合于关键字位数较多而所需要的散列地址的位数

46、又较少，各个位取值较集中的情况。的位数又较少，各个位取值较集中的情况。哈希函数哈希函数5.除留余数法除留余数法关键字关键字K除以哈希表长度除以哈希表长度m所所得的余数作为散列地址。得的余数作为散列地址。n哈希函数为：哈希函数为：h(K)=k%mn最重要的是选择模数最重要的是选择模数m，使得：每一个关键，使得：每一个关键字经函数转换后，映射到散列空间上任一地字经函数转换后，映射到散列空间上任一地址的概率都相等。址的概率都相等。n通常选择通常选择m为小于或等于线性表长度的最大为小于或等于线性表长度的最大素数。素数。哈希函数哈希函数6.随机数法随机数法选择一个随机函数，取关键字的选择一个随机函数，取

47、关键字的随机函数为散列地址。随机函数为散列地址。n哈希函数为：哈希函数为：H(key)=random(key)n适合于关键字长度不等的情况适合于关键字长度不等的情况9.3.3 处理冲突的方法处理冲突的方法1.开放定址法开放定址法n开放定址法开放定址法从发生冲突的单元开始，按照从发生冲突的单元开始，按照一定的次序，在哈希表中确定可以存储待插一定的次序，在哈希表中确定可以存储待插入元素的位置。入元素的位置。n空闲单元即向同义词元素开放，也向非同义空闲单元即向同义词元素开放，也向非同义词元素开放。词元素开放。n开放定址法确定位置有多种方法开放定址法确定位置有多种方法处理冲突的方法处理冲突的方法(1)

48、线性探查法线性探查法线性探测再散列线性探测再散列n线性探查法线性探查法最简单的方法。最简单的方法。将哈希表作为将哈希表作为循环表，从发生冲突的循环表，从发生冲突的d单元开始，依次探单元开始，依次探察下一个单元，直到找出一个空闲单元为止察下一个单元，直到找出一个空闲单元为止n递推公式：递推公式： d0=h(K) di=(di-1+1)%m (1im-1)n步长为步长为1处理冲突的方法处理冲突的方法n因为最先找到的空闲单元都是被占用单元的因为最先找到的空闲单元都是被占用单元的下一个单元，因此利用线性探查法处理冲突下一个单元，因此利用线性探查法处理冲突容易造成元素的堆积，增加了查找长度。容易造成元素

49、的堆积，增加了查找长度。n例：在哈希表例：在哈希表H中再插入中再插入31和和58两个元素。两个元素。H(K)=k%13 0 1 2 3 4 5 6 7 8 9 10 11 1275604618435490756046184354905831HH处理冲突的方法处理冲突的方法(2)再哈希法再哈希法(双哈希函数探查法双哈希函数探查法)n使用两个哈希函数使用两个哈希函数h1和和h2，均以关键字为，均以关键字为自变量，产生一个自变量，产生一个0m-1之间的数。之间的数。nh1同前面的同前面的h(K)，产生的数作为散列地址，产生的数作为散列地址h2产生的数不能整除产生的数不能整除m，作为步长。，作为步长。n递推公式：递推公式： d0=h1(K) di=(di-1+h2(K)%m (1im-1)处理冲突的方法处理冲突的方法2.链地址法链地址法n把发生冲突的同义词元素用单链表链接把发生冲突的同义词元素用单链表链接n哈希表的每个单元作为各个单链表的表头指哈希表的每个单元作为各个单链表的表头指针，单链表的结点动态产生。针，单链表的结点动态产生。n首先根据待插入元素的关键字首先根据待插入元素的关键字K计算出散列计算出散列地址地址d，并由该元素动态生成结点，然后将，并由该元素动态生成结点，然后将该结点插入到地址该结点插入到地址d单元为表头的单链表中。单元为表头的单链表中。01