数据结构(c语言版)第8章 查找(5.26)

1、第9章 查 找 第第8章章 查找查找 8.1 静态查找表静态查找表8.2 动态查找表动态查找表 8.3 哈希表哈希表 第9章 查 找 查找表查找表：由同一类型的数据元素（或记录）构成的集合， 可利用任意数据结构实现。松散的关系。 关键字关键字：数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。如果一个关键字可以唯一标识列表中的一个数据元素，则称其为主关键字，否则为次关键字。第9章 查 找 查找：查找：根据给定的关键字值，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。查找可能成功或失败。 查找算法中涉及到三类参量： 查找对象K（找什么）；

2、查找范围L（在哪找）； K在L中的位置（查找的结果）。第9章 查 找 查找的操作：查找的操作：1、查某个数据元素是否存在。、查某个数据元素是否存在。2、检索某、检索某个特定数据元素的属性。个特定数据元素的属性。3、在查找表中插入一个数据元素。、在查找表中插入一个数据元素。4、从查找表中删除某个数据元素。、从查找表中删除某个数据元素。 查找的基本方法查找的基本方法可以分为两大类，即比较式查找法比较式查找法和计计算式查找法算式查找法。其中比较式查找法比较式查找法又可以分为静态查找表静态查找表和动动态查找表态查找表，而计算式查找法计算式查找法也称为HASH（哈希）查找法（哈希）查找法。 静态查找表静

3、态查找表：只作前两种操作。：只作前两种操作。 动态查找表动态查找表：查找过程中同时插入不存在或删除已存在：查找过程中同时插入不存在或删除已存在的某个元素。的某个元素。第9章 查 找 平均查找长度：平均查找长度：为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。对于长度为n的列表，查找成功时的平均查找长度为： niiinnCPCPCPCPASL12211其中Pi为查找列表中第i个数据元素的概率，Ci为找到列表中第i个数据元素时，已经进行过的关键字比较次数。由于查找算法的基本运算是关键字之间的比较操作，所以可用平均查找长度来衡量查找算法的

4、性能。 第9章 查 找 8.1.1 顺序表的查找顺序表的查找 顺序查找法的特点是，用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。存储结构通常为顺序结构，也可为链式结构。 下面给出顺序结构有关数据类型的定义： typedef struct ElemType *elem; int length;SSTable;8.1 静态查找表静态查找表 第9章 查 找 查找过程：从最后一个记录开始逐个比较。 int Search_Seq(SSTable ST,KeyType key)/*在顺序表ST中顺序查找其关键字等于key的元素，若找到，则函数值为该元素在表中的位置，否则为0*/ ST.el

5、em0.key=key; for(i=ST.length; !EQ(ST.elemi.key,key); -i); return i; ST.elem0起监视哨。当ST.length=1000时，平均时间减少一半。 第9章 查 找 下面用平均查找长度来分析一下顺序查找算法的性能。假设列表长度为n，那么查找第i个数据元素时需进行n-i+1次比较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即Pi=1/n， 则顺序查找算法的平均查找长度为： niniiniiininnCnCPASL111) 1(21) 1(11 考虑到查找不成功的情况，不成功比较n+1次，设查找成功和不成功概率相同，则P

6、i = 1/2n;ASLss= (1/2n)* (n-i+1)+ (1/2n)* (n+1) = 3/4(n+1) 若查找概率不等时，将概率高的放在最后，即按概率递增的顺序存放，可提高查找效率。但实际上记录的查找概率无法预测，可通过设一个访问频度域来解决该问题。第9章 查 找 8.1.2 有序表的查找有序表的查找 折半查找法又称为二分法查找法，这种方法要求待查找的列表必须是按关键字大小有序排列的顺序表。其基本过程是：p 将表中间位置记录的关键字与查找关键字比较，p如果两者相等，则查找成功；p否则利用中间位置记录将表分成前、后两个子表，p如果中间位置记录的关键字大于查找关键字，则进一步查找前一子

7、表，p否则进一步查找后一子表。p重复以上过程，直到找到满足条件的记录，查找成功，或直到子表不存在，查找不成功。第9章 查 找 图8.1 折半查找示意图 第9章 查 找 折半查找的算法如下： int Search_Bin(SSTable ST, KeyType key）/*在有序表ST中折半查找其关键字等于key的元素，若找到，则函数值为该元素在表中的位置*/ low = 1 ; high = ST.length; /*置区间初值*/ while ( low BST-data ) return Find( X, BST-rchild ); /*在右子树继续查找*/ else if( X data

8、 ) return Find( X, BST-lchild); /*在左子树中继续查找*/ else /* X = BST-data */ return BST; /*查找成功，返回找到结点的地址*/ 第9章 查 找 由于非递归函数的执行效率高，可将“尾递归”函数改为迭代函数 。BiTree Find(TElemType X, BiTree BST ) while( BST ) if( X BST-data ) BST = BST-rchild; /*向右子树中移动，继续查找*/ else if( X data ) BST = BST-lchild; /*向左子树中移动，继续查找*/ else

9、 /* X = BST-data */ return BST; /*查找成功，返回结点的找到结点的地址*/ return NULL; /*查找失败*/ 查找的效率决定于树的高度 第9章 查 找 2. 二叉排序树的插入和生成二叉排序树的插入和生成 关键是要找到元素应该插入的关键是要找到元素应该插入的位置位置，可以采用与可以采用与Find类似的方法类似的方法p若二叉排序树是空树，则key成为二叉排序树的根；p若二叉排序树非空，则将key与二叉排序树的根进行比较， 如果key的值等于根结点的值，则停止插入； 如果key的值小于根结点的值，则将key插入左子树； 如果key的值大于根结点的值，则将ke

10、y插入右子树。第9章 查 找 例：在二叉排序树中插入333333新插入的结点一定是新插入的结点一定是叶子结点叶子结点，且其位置一定是查找不，且其位置一定是查找不成功时指向最后一个结点的左孩子或右孩子。成功时指向最后一个结点的左孩子或右孩子。第9章 查 找 算法如下：算法如下：BiTree Insert( TElemType X, BiTree BST ) if( !BST ) /*若原树为空，生成并返回一个结点的二叉搜索树*/ BST = (BiTree) malloc(sizeof(BiTNode); BST-data = X; BST-lchild = BST-rchild = NULL;

11、 else /*开始找要插入元素的位置*/ if( X data ) BST-lchild = Insert( X, BST- lchild); /*递归插入左子树*/ else if( X BST-data ) BST-rchild = Insert( X, BST- rchild); /*递归插入右子树*/ else /* X已经存在，什么都不做 */ return BST; 第9章 查 找 若从空树出发经过一系列的查找插入操作之后，可生成一棵二叉树。 中序遍历二叉排序树可得到一个关键字的有序序列。一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列。又因为每次插入在叶子，无需移动其它

12、结点。所以二叉排序树既具有类似于折半查找的性能，又可以使用链式结构，避免元素位置的移动。 第9章 查 找 例：根据输入序列45，24，53，45，12，24，28，90生成二叉排序树452412532890第9章 查 找 p考虑三种情况： 要删除的是叶结点：直接删除，并再修改其父结点相应指针-置为置为NULL3. 二叉排序树的删除二叉排序树的删除452412532890例：要删除28fpppf第9章 查 找 p要删除的结点只有一个孩子结点要删除的结点只有一个孩子结点: 将其将其父结点父结点的指针的指针指向指向要删除结点的要删除结点的孩子结点孩子结点 。3. 二叉排序树的删除二叉排序树的删除45

13、2412532890例：要删除53fpp第9章 查 找 p 要删除的结点有左、右两棵子树： 用另一结点替代被删除结点：右子树的最小元素 或者 左子树的最大元素。3. 二叉排序树的删除二叉排序树的删除452412532890例：要删除536080704524125328906080702、取、取左子树中的最大元素左子树中的最大元素替代替代 1、取、取右子树中的最小元素右子树中的最小元素替代替代 908070第9章 查 找 BiTree Delete ( TElemType X, BiTree BST ) BiTree p; if( !BST ) printf(要删除的元素未找到); else i

14、f( X data ) BST-lchild = Delete( X, BST- lchild); /* 左子树递归删除 */ else if( X BST-data ) BST-rchild = Delete( X, BST- rchild); /* 右子树递归删除 */ else /*找到要删除的结点 */ 第9章 查 找 if( BST- lchild & BST- rchild ) /*被删除结点有左右两个子结点 */ p = FindMin( BST- rchild ); /*在右子树中找最小的元素填充删除结点*/ BST-data = p-data; BST- rchild = D

15、elete( BST-data, BST- rchild); /*在删除结点的右子树中删除最小元素*/ else /*被删除结点有一个或无子结点*/ p = BST; if( !BST- lchild ) /* 有右孩子或无子结点*/ BST = BST- rchild; else if( !BST- rchild ) /*有左孩子或无子结点*/ BST = BST- lchild; free( p ); return BST; 第9章 查 找 4. 二叉排序树的查找性能分析二叉排序树的查找性能分析 图图8.4 二叉排序树的不同形态二叉排序树的不同形态 93371224534512243745

16、5393(a) 输入关键字序列为45,24,53,12,37,93时的二叉排序树(b) 输入关键字序列为12,24,37,45,53,93时的单支二叉排序树ASLa=1/61+2+2+3+3+3=14/6ASLb =1/61+2+3+4+5+6=21/6含有含有n n个结点的二叉排序树的平均查找长度和树的形态有关个结点的二叉排序树的平均查找长度和树的形态有关第9章 查 找 由上节可知，二叉排序树结点的不同插入次序，将导致不同的深度和平均查找长度ASL 平衡二叉排序树平衡二叉排序树 933712245345122437455393(a) 输入关键字序列为45,24,53,12,37,93时的二叉

17、排序树(b) 输入关键字序列为12,24,37,45,53,93时的单支二叉排序树第9章 查 找 平衡二叉树又称为AVL树。p 或者是空树，p 或者任一结点左、右子树高度差的绝对值不超过1。 结点的平衡因子（结点的平衡因子（balance factor）BF：BF = HL-HR 引入平衡二叉树的目的是为了提高查找效率，其平均查找长度为O（log2n）。平衡二叉排序树平衡二叉排序树 第9章 查 找 图8.5 平衡与不平衡的二叉排序树 208070302560405011110006030255040120058100(a) 一棵平衡二叉排序树(b) 一棵失去平衡的二叉排序树第9章 查 找 不平

18、衡点是A，插入结点15 在A的左子树左子树的左边左边，因而叫 LL 插入，需要LL 旋转旋转。 6015302025604010000AB(a) 一棵平衡二叉排序树(b) 插入15后 失去平衡302025604020110AB030152040250000BA01(c) 调整后的二叉排序树平衡二叉排序树的调整（平衡二叉排序树的调整（1） (a) 插入新结点S后 失去平衡(b) 调整后恢复平衡ABBLBRARS21BABLARBRS00第9章 查 找 不平衡结点是A，插入结点70 在A的右子树的右边，因而叫 RR 插入，需要RR 旋转旋转。30607060302040251000AB(a) 一棵

19、平衡二叉排序树(b) 插入70后失去平衡204025200AB0202560400000BA0(c) 调整后的二叉排序树70111300（2）(a) 插入新结点S后失去平衡(b) 调整后恢复平衡ABBRBLALS21BABRALBLS00第9章 查 找 (a) 一棵平衡二叉排序树507000103095204090801000B06085AC0000(b) 插入45后失去平衡507010103095204090802101B06085AC00000458595(c) 调整后的二叉排序树45103090204080600001B05070C00001A00 不平衡结点是A，插入结点45 在A的左

20、子树的右边，因而叫 LR 插入，需要LR 旋转旋转。（3）第9章 查 找 (a) 插入新结点S后失去平衡(b) 调整后恢复平衡ABCLARS21CCR1BLCACLARCRS01B0BL第9章 查 找 (c) 调整后的二叉排序树(a) 一棵平衡二叉排序树(b) 插入55后失去平衡859550709010208040100003060A00B0000C859550709010208040200003060A11B000C15508595551030902040806000A05070C0001B00100（4） 不平衡结点是A，插入结点55在A的右子树的左边，因而叫 RL 插入，需要RL 旋转旋

21、转。第9章 查 找 (b) 调整后恢复平衡(a) 插入新结点S后失去平衡ABBRCRS21CCL1ALCACRALCLS01B0BR第9章 查 找 综上所述，在一个平衡二叉排序树上插入一个新结点S时，主要包括以下三步： （1） 查找应插位置，同时记录离插入位置最近的可能失衡结点A（A的平衡因子不等于0）。 （2） 插入新结点S，并修改从A到S路径上各结点的平衡因子。 （3） 根据A、B的平衡因子，判断是否失衡以及失衡类型， 并做相应处理。 第9章 查 找 8.2.2 B-树和树和B+树树 1. m路查找树路查找树 与二叉排序树类似，可以定义一种“m叉排序树”，通常称为m路查找树。 一棵m路查找

22、树，或者是一棵空树，或者是满足如下性质的树： (1) 每个结点最多有m棵子树、 m-1个关键字，其结构如下： nP0K1P1K2P2KnPn第9章 查 找 其中n为关键字个数，Pi(0in)为指向子树根结点的指针， Ki(1in)为关键字。 (2） Ki37，所以找到结点C，又因为405885，所以找到结点G，最后在结点G中找到58。如果要查找32，首先由根指针mbt找到根结点A，因为3225，所以找到结点E，又因为303235，所以最后找到失败结点f，表示32不存在，查找失败。 在具体实现时， 采用如下结点结构： parentnK1K2KnP0P1Pn第9章 查 找 3. B-树的插入树的插

23、入已知一棵3阶B-树如图8.8(a)所示，要求插入52、20、49。插入52：首先查找应插位置，即结点f中50的后面，如图8.8(b)所示。插入20：直接插入后如图8.8(c)所示，由于结点c的分支数变为4，超出了3阶B-树的最大分支数3，需将结点c分裂为两个较小的结点。以中间关键字14为界，将c中关键字分为左、右两部分，左边部分仍在原结点c中，右边部分放到新结点c中，中间关键字14插到其父结点的合适位置，并令其右指针指向新结点c，如图8.8(d)所示。 插入插入49：直接插入后如图8.8(e)所示。f结点应分裂，分裂后的结果如图8.8(f)所示。50插到其父结点e的key1处，新结点f的地址

24、插到e的ptr1处，e中ptr0不变，仍指向原结点f。此时，e仍需要分裂，继续分裂后的结果如图8.8(g)所示。53存到其父结点a的key2处，ptr2指向新结点e，ptr1仍指向原结点e 。 第9章 查 找 (a) 一棵3阶B树(b) 插入52 后(c) 插入20,结点c需要分裂(d) 结点c分裂后(e) 插入49, 结点f需要分裂(g) 结点e分裂后(f) 结点f分裂后,结点 e 仍需要分裂48256 1437cdbabt53 8650 5258 7098efgh48256 1437cdbabt53 865058 7098efgh48256 14 203753 8650 5258 7098

25、cdbabtefghbt4814 2563753 8650 5258 7098cdbaefgh20c4814 2563753 8649 50 5258 7098cdbabtefgh20cbt4814 2563750 53 8658 7098cdbaefgh20c52f4948 5314 2563758 7098cdbabtfgh20c52f495086ee图图8.8B-树的插入实例树的插入实例 第9章 查 找 我们可以利用B-树的插入方法，从空树开始，逐个插入关键字，从而创建一棵B-树。例如，已知关键字集为37， 70， 12， 45， 90， 3， 24， 61， 53， 要求从空树开始，逐

26、个插入关键字，创建一棵3阶B-树。创建过程如图8.9所示。 第9章 查 找 (a) 空树37(b) 插入3737 70(c) 插入70(d) 插入12(e) 插入45(g) 插入3(h) 插入24(i) 插入61(j) 插入53(分裂前)37 703 12 24904512 37 70902434590243451270379024345 611270379024345 53 61127037(f) 插入9037 701290371245 70 904537 703 12904512 37 70371270371245 70分裂分裂分裂分裂图8.9 从空树开始，逐个插入关键字，创建一棵3阶B-

27、树 第9章 查 找 从上述B-树的构造过程可得出以下结论： （1） 由于B树是“从叶往根”长，而根对每个分支是公用的， 所以不论根长到多“深”，各分支的长度同步增长，因而各分支是“平衡”的。 （2） 生长的几种情况： 最底层某个结点增大，分支数不变且各分支深度也不变。 从最下层开始，发生单次或连续分裂，但根结点未分裂，此时分支数增1（最下层结点增1），但原分支深度不变，新分支深度与原分支相同。 从最下层开始，连续分裂，根结点也发生分裂，产生一个新的根结点，此时分支数仍增1（最下层结点增1），但新、旧分支均为原分支长度加1。 第9章 查 找 （3） 根的形成过程： 初始未分裂的根：关键字个数为0

28、m-1，分支数为0(空树)。2m(失败结点数)。 由分裂形成的根：关键字个数为1m-1，分支数为 2m。 显然，对非空的B-树而言，根结点至少有两棵子树（包括由失败结点构成的子树），这就是B-树定义中提到的第2条性质。 第9章 查 找 （4） 除根以外的非终端结点的形成过程：除根以外的非终端结点的形成过程： 由“满结点”分裂而得。假设m阶B-树中p结点中已有m-1个关键字，当再插入一个关键字后，结点中信息为：m, A0, (k1, A1), (k2, A2), , （km, Am），有m+1个分支，为保持m阶（m个分支），应将p结点分裂为关键字个数尽量相等的p结点和新结点p1（或者说从p中分出

29、一部分信息构成p1）。分裂后p中剩余信息为：m/2-1, A0, (k1, A1), (k2, A2), , （km/2-1, Am/2-1），共有m/2-1个关键字，及这些关键字的m/2个左、右相邻分支指针。 第9章 查 找 分裂出去的信息为：（k m / 2 , A m / 2 ）, （k m / 2 + 1, Am/2+1）, , （km, Am）， 共计m-(m/2-1) = m-m/2+1个关键字及其右指针，其中km/2上移到p的父结点中，其余信息存入新结点p1中，所以p1中信息为：m-m/2，Am/2, （km/2+1, Am/2+1）, , （km, Am）。显然，分裂后的非终端

30、结点（除根结点）所含关键字最少，分支也最少，其中p的分支数为B1=m/2，p1的分支数为B2=m-m/2+1。容易证明，B1B2，所以，除根之外的所有非终端结点至少有m/2棵子树，这就是B-树定义中提到的第3条性质。 第9章 查 找 4. 在在B-树中删除一个关键字树中删除一个关键字 1） 在最下层结点中删除一个关键字 图8.10(a)所示为一棵4阶B-树(m = 4)，要求删除11、53、39、64、27。 第9章 查 找 (1) 删除11时，13与其右的指针左移即可，如图8.10(b)所示。 (2) 删除53后，如图8.10(c)所示。 结论：被删关键字所在结点中关键字数目不小于被删关键字

31、所在结点中关键字数目不小于m/2m/2，则只需从该结点中删去关键字则只需从该结点中删去关键字KiKi和相应指针和相应指针AiAi，树的其他部，树的其他部分不变。分不变。 第9章 查 找 (3) 删除39时，为保持其“中序有序”，可将父结点中43下移至39处，而将右兄弟中最左边的47上移至原43处，如图8.10(d)所示。 结论：被删关键字所在结点中关键字数目等于被删关键字所在结点中关键字数目等于m/2-1m/2-1，而，而与该结点相邻的右兄弟（左兄弟）结点的关键字数目大于与该结点相邻的右兄弟（左兄弟）结点的关键字数目大于m/2-1m/2-1，则需将，则需将右兄弟的最小（左兄弟的最大）关键字右兄

32、弟的最小（左兄弟的最大）关键字移至双移至双亲结点中，而将亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键双亲结点中小于（或大于）且紧靠该上移关键字的关键字字的关键字移至被删关键字所在结点中。移至被删关键字所在结点中。第9章 查 找 (4) 删除64后，为保持各分支等长（平衡），将删除64后的剩余信息(在此为空指针)及78合并入右兄弟，如图8.10(e)所示。也可将删除64后的剩余信息及47与左兄弟合并。 结论：被删关键字所在结点和其相邻的兄弟结点中的被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于关键字数目均等于m/2-1m/2-1，设该结点有右兄弟且所在结点设该结点有右兄弟且所

33、在结点中剩余的关键字和指针，加上双亲中的中剩余的关键字和指针，加上双亲中的K Ki i一起，合并到一起，合并到A Ai i所所指兄弟结点中。指兄弟结点中。 第9章 查 找 (5) 删除27时，首先将剩余信息(在此为空指针)与父结点中的18并入左兄弟，并释放空结点，结果如图8.10(f)所示。再将父结点中的剩余信息与祖父结点中的35并入47左端，释放空结点后的结果如图8.10(g)所示。至此，祖父结点仍需要合并，但由于待合并结点的父指针为NULL，故停止合并，直接将根指针bt置为指针p2的值，释放空结点后的结果如图8.10(h)所示。 第9章 查 找 (a) 一棵4 阶B树(b )删除11 后(c) 删除53 后(d) 删除39 后(e) 删除64 后(f) 删除27 后,将剩余信息与父结点中的18并入左兄弟(g) 将父结点剩余信息与祖父结点中的35并入47左端(h) 删除27 后的最终结果992711 1347 53 641843 783539