数据结构--第八章 查找

《数据结构--第八章 查找》由会员分享，可在线阅读，更多相关《数据结构--第八章 查找（101页珍藏版）》请在金锄头文库上搜索。

1、第八章 查 找8.1 查找的基本概念列表：由同一类型的数据元素（或记录）构成的集 合，可利用任意数据结构实现。 关键字：数据元素的某个数据项的值，用它可以标 识列表中的一个或一组数据元素。主关键字：如果一个关键字可以唯一标识列表中的 一个数据元素，则称其为主关键字，否则为次关键 字。当数据元素仅有一个数据项时，数据元素的值 就是关键字。查找：根据给定的关键字值，在特定的列表中确定 一个其关键字与给定值相同的数据元素，并返回该 数据元素在列表中的位置。 在查找算法中要用到三类参量，即：查找对象K（找什么）查找范围L（在哪找）查找的结果（K在L中的位置）其中、 为输入参量，在函数中不可缺少。为输出

2、参量，可用函数返回值表示。平均查找长度：为确定数据元素在列表中的位置，需 和给定值进行比较的关键字个数的期望值，称为查找 算法在查找成功时的平均查找长度。 对于长度为n的列表，查找成功时的平均查找长度为 ：ASL=P1C1+ P2C2+ PnCn = i=1nPiCi其中Pi为查找列表中第i个数据元素的概率，Ci为找 到列表中第i个数据元素时，已经进行过的关键字比 较次数。 查找的基本方法 ：比较式查找法计算式查找法HASH（哈希）查找法基于线性表的查找法基于树的查找法8.2 基于线性表的查找法具有顺序查找法、折半查找法和分块查找法三种8.2.1 顺序查找法顺序查找法的特点是：用所给关键字与线

3、性表中 各元素的关键字逐个比较，直到成功或失败。 存储结构 ：顺序结构链式结构顺序结构有关数据类型的定义：#define LIST_SIZE 20typedef struct KeyType key;OtherType other_data; RecordType;typedef struct RecordType rLIST_SIZE+1; /* r0为工作单元 */int length; RecordList; 设置监视哨的顺序查找算法int SeqSearch（RecordList l, KeyType k）/*在顺序表l中顺序查找其关键字等于k的元素，若找到，则 函数值为该元素在表中的

4、位置，否则为0*/l.r0.key=k; i=l.length;while (l.ri.key!=k) i-;return（i）; 其中l.r0为监视哨，可以起到防止越界的作用。不设置监视哨的顺序查找算法int SeqSearch（RecordList l, KeyType k）/*不用监视哨法，在顺序表中查找关键字等于k的元素*/l.r0.key=k; i=l.length;while (i=1if (i=1) return（i）else return (0); 循环条件i=1判断查找是否越界。用平均查找长度分析顺序查找算法的性能。假设列表长度为n，那么查找第i个数据元素时需 进行n-i+1

5、次比较，即Ci=n-i+1。又假设查找每个数据 元素的概率相等，即Pi=1/n，则顺序查找算法的平均 查找长度为： ASL= i=1nPiCin1 i=1nCin1 i=1n(n-i+1)=21(n+1)8.2.2 折半查找法（二分法查找法）条件：要求待查找的列表必须是按关键字大小有序 排列的顺序表。 基本过程：将表中间位置记录的关键字与查找关键 字比较，如果两者相等，则查找成功；否则利用中 间位置记录将表分成前、后两个子表，如果中间位 置记录的关键字大于查找关键字，则进一步查找前 一子表，否则进一步查找后一子表。重复以上过程 ，直到找到满足条件的记录，使查找成功，或直到 子表不存在为止，此时

6、查找不成功。 例如用折半查找法查找10、50的具体过程，其中 mid=(low+high)/2，当high key=key; s-lchild=NULL; s-rchild=NULL; *bst=s; else if (key key)InsertBST(/*将s插入左子树*/else if (key (*bst)-key) InsertBST( /*将s插入右子树*/ 二叉排序树的生成方法： 假若给定一个元素序列，可以利用上述算法创建一棵 二叉排序树。将二叉排序树初始化为一棵空树，然后逐个读入元素 ，每读入一个元素，就建立一个新的结点插入到当前 已生成的二叉排序树中，即调用上述二叉排序树的插

7、 入算法将新结点插入。 生成二叉排序树的算法：void CreateBST(BSTree *bst)/*从键盘输入元素的值，创建相应的二叉排序树*/ KeyType key;*bst=NULL;scanf(“%d“, while (key!=ENDKEY) /*ENDKEY为自定义常数*/InsertBST(bst, key);scanf(“%d“, 设关键字的输入顺序为：45，24，53，12，28，90， 按上述算法生成的二叉排序树的过程：空树45插入454524插入24452453插入5345245312插入124524531228插入28452453122890插入90对同样一些元素值

8、，如果输入的顺序不同，则所建 的二叉树形态也不同。如果将上述例子中的关键字 顺序变为：24，53,90,12,28,45,则生成的二叉排序树 为：2412285390452. 二叉排序树的删除删除操作： 首先确定被删除的结点是否在二叉排序树中。若不 在 ，则不做任何操作；否则，假设要删除的结点为 p，结点p的双亲结点为f，并假设结点p是结点f的左 孩子（右孩子的情况类似）。 从二叉排序树中删除一个结点，必须保证删除 后所得的二叉树仍然满足二叉排序树的性质不变。下面分三种情况讨论：（2）若p结点只有左子树，或只有右子树，则可将p 的左子树或右子树直接改为其双亲结点f的左子树。 即：f-lchil

9、d=p-lchild（或f-lchild=p-rchild） ；free(p)； （1） 若p为叶结点，则可直接将其删除：f-lchild=NULL；free(p)； （3）若p既有左子树，又有右子树， 如下图(a)，则处理的方法有两种：FPPLPRfp(a) P的左右子树均不空方法一：首先找到p结点在中序序列中的直接前驱s 结点，如图 (b) 所示，然后将p的左子树改为f的左子 树，而将p的右子树改为s的右子树：f-lchild=p- lchild；s-rchild= p-rchild；free(p)；结果如图 (c) 所示。 FPCPRfpcSQQLSLqsCL(b) S为P的直接前驱CL

10、FCSSLPRfc(c) 将P的左子树改为F的左子树 ，将P的右子树改为S的右子树 。方法二：首先找到p结点在中序序列中的直接前驱s 结点，如图 (b) 所示，然后用s结点的值，替代p结点 的值，再将s结点删除，原s结点的左子树改为s的双 亲结点q的右子树：p-data=s-data；q-rchild= s -lchild；free(s)；结果如图 (d) 所示。 F P CPRf p cSQ QLSLq sCL(b) S为P的直接前驱(d) 将原P结点的值改为S结点的值，删除 原S结点并将原S的左子树改为Q的右子树F S CPRf p cQ QLSLqCL在二叉排序树中删除结点的算法BSTN

11、ode * DelBST(BSTree t, KeyType k)/*在二叉排序树t中删去关键字为k的节点*/ BSTNode *p, *f,*s ,*q;p=t;f=NULL;while(p)/*查找关键字为k的待删结点p*/ if(p-key=k ) break;/*找到，则跳出查找循环*/f=p;/*f指向p结点的双亲结点*/if（p-keyk） p=p-lchild;else p=p-rchild; if(p=NULL) return t;/*若找不到，返回原来的二叉排序树*/if(p-lchild=NULL)/*p无左子树*/if(f=NULL) t=p-rchild;/*p是原二叉

12、排序树的根*/else if(f-lchild=p)/*p是f的左孩子*/f-lchild=p-rchild ； /*将p的右子树链到f的左链上*/else /*p是f的右孩子*/f-rchild=p-rchild ;/*将p的右子树链到f的右链上*/free(p);/*释放被删除的节点p*/else /*p有左子树*/ q=p;s=p-lchild;while(s-rchild)/*在p的左子树中查找最右下结点*/q=s;s=s-rchild;if(q=p) q-lchild=s-lchild ;/*将s的左子树链到q上*/else q-rchild=s-lchild;p-key=s-key

13、;/*将s的值赋给p*/free(s);return t; /*DelBST*/ 3. 二叉排序树的查找根据二叉排序树的特点，首先将待查关键字k与根结 点关键字t进行比较，如果：（1）k= t：则返回根结点地址； （2）kt：则进一步查右子树。 显然，这是一个递归过程。可用如下递归算法实现 ： 二叉排序树查找的递归算法为：BSTree SearchBST(BSTree bst, KeyType key)/*在根指针bst所指二叉排序树中，递归查找某关键字等于key的元素， 若查找成功，返回指向该元素结点指针，否则返回空指针。*/ if (!bst) return NULL;else if (b

14、st- key=key) return bst;/*查找成功*/elseif (key key)return SearchBST(bst-lchild, key);/*在左子树继续查找*/else return SearchBST(bst-rchild, key);/*在右子树继续查找*/ 二叉排序树查找的非递归算法：BSTree SearchBST(BSTree bst, KeyType key)/*在根指针bst所指二叉排序树bst上，查找关键字等于key的结点，若查 找成功，返回指向该元素结点指针，否则返回空指针。*/ BSTree q; q=bst;while(q)if (q-key=

15、k) return q;/*查找成功*/if (key data.key) q=q-lchild;/*在左子树中查找*/else q=q-rchild; /*在右子树中查找*/return NULL;/*查找失败*/*SearchBST*/ 4. 二叉排序树的查找性能对于含有同样关键字序列的一组结点，结点插入 的先后次序不同，所构成的二叉排序树的形态和深度 不同。而二叉排序树的平均查找长度ASL与二叉排序 树的形态有关，二叉排序树的各分支越均衡，树的深 度浅，其平均查找长度ASL越小。 例如：452412375393(a) 输入关键字序列为 45,24,53,12,37,93时的二叉排序树12

16、12 24 37 45 53 93 (b)输入关键字序列为 12,24,37,45,53,93时的二叉排序树假设每个元素的查找概率相等，则它们的平均 查找长度分别是： ASL=(1+2+2+3+3+3)/6=14/6ASL=(1+2+3+4+5+6)/6=21/6由此可见，在二叉排序树上进行查找时的平均查找 长度和二叉排序树的形态有关。 若考虑把n个结点，按各种可能的次序插入到二叉 排序树中，则有n！棵二叉排序树（其中有的形态 相同），可以证明，对这些二叉排序树进行平均， 得到的平均查找长度仍然是O(log2n)。 8.3.2 平衡二叉排序树平衡二叉排序树又称为AV树。一棵平衡二叉排序树或者是空树，或者是具有下列性质的二叉排序树： （1）左子树与右子树高度之差的绝对值小于等于1；