--- title: "《数据结构》查找" date: 2023-08-02T13:19:44+08:00 --- ## 查找基本概念 * 查找 * 在数据集合中寻找满足某种条件的数据元素的过程 * 查找表 * 用于查找的数据集合 * 关键字 * 数据元素中唯一标识该元素的某个数据项的值 * 平均查找长度 * 所有查找过程中进行关键字比较次数的平均值 ## 查找分类 * 静态查找表 * 只作查找操作的查找表 * 顺序查找 * 二分查找 * 插值查找 * 斐波那契查找 * 线性索引查找 * 动态查找表 * 表结构本身是在查找过程中动态生成的 * 查找时插入数据元素 * 查找时删除数据元素 * 二分排序树 * 平衡二叉树 * B树 * 散列表 ## 顺序查找 ### 一般线性表的顺序查找 |66|33| 10 |13|29| 16| 19| 32| 7| 43| 41| 37| |---|---|---|---|---|---|---|---|---|---|---|---| |0|1|2|3|4|5|6|7|8|9|10|11| * $ASL_{成功}$ = $\frac{1+2+3+\cdots+n}{n} = \frac{n+1}{2}$ * $ASL_{失败} = n+1$ * 时间复杂度均为O(n) 代码 ```c typedef Struct{ ElemType *elem; int TableLen; }SSTable // int Search.Seq(SSTable ST,ElemType key){ ST.elem[0] = key; int i; for(i =ST.TableLen;ST.elem[i]! = key;--i); return i; } ``` ### 顺序查找的优化（对有序表） 查找目标 ：21 查找表： |7|13|19|29|37|43| |---|---|---|---|---|---| 查找判定树 ![](../../images/408/《数据结构》查找/顺序查找的优化.jpg) 性质： $ASL_{失败} = \frac{1+2+3+\cdots + n + n}{n+1} = \frac{n}{2} + \frac{n}{n+1}$ 成功结点的查找长度 = 自身层数[length(13) = 2] 失败结点的查找长度 = 父节点层数 [length(16) = 3] ## 折半查找 ### 查找目标 查找：33 顺序表; |T|10|13|16|19|29|32|33|37|41|43| |---|---|---|---|---|---|---|---|---|---|---| |0|1|2|3|4|5|6|7|8|9|10| ### 代码 ```c typedef Struct{ ElemType *elme; int TableLen; }SSTable; // int Binary_Search(SSTable L,ElemType ket){ int low = 0,haigh = L.TableLen-1,mid = 0; while(low<=high){ mid = (low+high)/2; //取中间位置 if(L.elem[mid] == key) return mid;//查找成功则返回所在位置 else if(L.elem[mid] > key) high = mid -1;//左边查找 else low = mid + 1;//右边查找 } return -1;//查找失败 } ``` ### 查找效率分析 ![](../../images/408/《数据结构》查找/查找效率分析.jpg) $ASL_{成功} = (1 \cdot 1 + 2\cdot 2+3\cdot 4+4\cdot 4)/11 = 3$（有分支结点） $ASL_{失败} = (4\cdot 3+8\cdot 4)/12 = \frac{11}{3}$（叶子结点） ### 折半查找判定树 * 折半查找树是平衡二叉树（左右子树高度之差不大于1） * 折半查找判定树可以用二叉排序树来判别，其中序序列是一个有序序列 * 还有可能要判断取整方向是否一致 * ![](../../images/408/《数据结构》查找/折半查找判定树.jpeg) ### 常考结论 * 树的高度 h = 向下取整(log2n) + 1 = 向上取整(log2n+1) * 时间复杂度O(log2 n) * 查找不成功时比较次数最多即为高度h，注意最后一个数叶要比较 * 折半查找和二叉排序树最好的情况时平均查找长度都是O(log2 n) * 二叉排序树最坏的情况形成单支树，查找长度为O(n) ## 分块查找 ### 定义 ![](../../images/408/《数据结构》查找/分块查找.jpg) ```c //索引表 typedef Struct{ ElemType maxValue; int low,high; }Index; //顺序表存储实际元素 ElemType List[100]; ``` ### 效率分析 ![](../../images/408/《数据结构》查找/效率分析.jpg) 设长度为n的查找表被均匀低分为6块，每个块包含s个元素 则：ASL(分块查找的平均查找长度) = $L_1（索引查找的平均查找长度）+L_s（块内查找的平均查找长度）$ #### 顺序查找查找索引表 $L_1 = \frac{(1+2+\cdots)}{b} = \frac{b+1}{2}$ $L_s = \frac{(1+2+\cdots)}{s} = \frac{s+1}{2}$ 则ASL=$\frac{b+1}{2} + \frac{s+1}{2} = \frac{s^2+2s+n}{2s}$，当$s = \sqrt{n}时，ALS_{min} = \sqrt{n} + 1$ #### 折半查找查找索引表 $L_1 = [\log_2(b+1)],L_2 = \frac{(1+2+\cdots+s)}{s} = \frac{s+1}{2}$ $ASL = [\log_2(b+1)]+\frac{s+1}{2}$ ### 常考结论 * 顺序查找效率最快时，块数 = $\sqrt{n}$ * 数据分成若干块，每块内数据不必有序，但块间必须有序，但块内最大/最小的数据组成索引块 ## 树型查找 ### 常考结论 * 二叉排序树 * 当二叉树的叶子节点全部都在相邻的两层时，深度最小。理想情况是从第一层到第二层为满二叉树，$h = 向上取整(\log_2n+1)$ * 当输入序列是有序序列时，构造的二叉排序树是一支单支树，查找一个关键词最多需要比较n次 * 按中序遍历二叉排序树得到的序列是一个有序序列 * 二叉排序树中，关键字值最大的节点右指针一定为空 * 平衡二叉树 * 平衡二叉树任意节点的做优子树高度差不超过1 * 平衡二叉树节点递推公式：$n_0=0,n_1=1,n_2=2,n_h=n_{h-2}+n_{h-1}+1\cdots(斐波那契数列，n_1为第一层)$ * ALV是高度平衡的二叉树，查找效率最高 * ALV和红黑树查找，删除，插入的平均时间复杂度都相同 * 红黑树 * 一颗含有n个节点的红黑树的高度至多为$2\log_2(n+1)$ * 如果一个节点是红色的，则它的父节点和子节点都是黑色的 * 从一个节点到其子孙节点的所有路径上包含相同数量的黑节点 * 红黑树是适度平衡的二叉树，查找效率低于平衡二叉树 * 红黑树可能会出现超出2次旋转的操作 * 红黑树的任意节点的左右子树高度之差不超过2倍 * 如果红黑树的所有节点都是黑色的，则它一定是满二叉树 ### 二叉排序树BST #### 查找 ![](../../images/408/《数据结构》查找/BST查找.png) ```c typedef Struct BSTNode{ int key; Struct BSTNode *lchild,*rchild; }BTNode,*BSTTree; //在二叉排序树中查找值为key的结点 //最坏空间复杂度O(1) BSTNode *BST_Search(BSTTree T,int key){ while(T! = Null&&key! = T->key){ if(keykey) //小于，查询左子树 { T = T->lchild; } else //大于，查询右子树 { T = T->rchild; } return T; } } //在二叉排序树中查找值为key的结点（递归方式） //最坏空间复杂度O(h) BSTNode *BSTSearch(BSTTree T,int key){ if(T = Null) return Null; if(key = T->key) return T; else if (key < T->key) return BSTSearch(T->lchild,key); else return BSTSearch(T->rchild,key); } ``` #### 插入 ![](../../images/408/《数据结构》查找/BST插入.jpg.png) ```c //在二叉排序树中插入关键字为key的新结点（递归） int BST_Insert(BSTTree &T,int k){ if(T==Null){ //原树为空，新插入的结点为根结点 T = (BSTTree)malloc(sizeof(BSTNode)); T->key = k; T->lchild = T->right = Null; return 1; } else if (k==T->key) //树中存在相同关键字的结点，插入失败 return 0; else if(k< T->key) return BST_Insert(T->lchild,k); else return BST_Insert(T->rhchild,k); } ``` #### 构造 按{50,66,60,26,21,30,70,68}建立BST ![](../../images/408/《数据结构》查找/BST构造.png) ```c //按照str[]中的关键字序列建立二叉排序树 void Create_BST(BSTTree &T,int str[],int n){ T = Null; int i = 0; while(im叉查找树|分块查找的进化->分级分块查找| |关键字与分叉|n个关键字对应n+1个分叉（子树）|n个关键字对应n个分叉| |结点包含的信息|所有结点中都包含记录的信息|只有最下层叶子结点才包含记录的信息（可使树更矮）| |查找方式|不支持顺序查找，查找成功时，可能停在任何一层结点，查找速度不稳定|支持顺序查找，查找成功或失败都会到达最下一层结点，查找速度稳定| |相同点|除根节点外，最少[m/2]个分叉（确保结点不要太空）任何一个结点的子树都要一样高（确保绝对平衡）| |---|---| ## 散列表 * 概念 * 散列查找一般适用于关键字集合与地址集合之间存在对应关系的情况下的查找 * 散列查找的思想是计算出散列地址来查找，然后比较关键字以确定是否比较成功 * 散列查找的平均查找长度与装填因子有关，与表长无关 * 装填因子 = $\frac{表中记录数}{散列表长度}$ * 冲突是不可避免的，与装填因子无关 * 提高查找效率方法 * 设计冲突少的散列函数 * 处理冲突时避免产生堆积现象【装填因子是固有属性，不可变】 * 产生了堆积即产生了冲突，他对存储效率，散列函数和装填因子没有什么影响，但ASL会随堆积现象而增大 * 两项基本工作 * 计算位置 * 构造散列函数确定关键词存储位置 * 解决冲突 * 应用某种策略解决多个关键词位置相同的问题 * 计算位置 * 除留余数法 * h(key) = key%p * 直接定址法 * h(key) = a$\times$ key + b 【线性函数】 * 平方取中法 * key取平方再取中间几位 * 数字分析法 * 分析数字关键字在各位上的变化情况 * 取比较随机的位作为散列地址 * 如电话号码、身份证号码某几位会比较随机 * 解决冲突 * 开放地址法 * 一旦产生了冲突，就按某种规则去寻找另一空地址 * 发生聚集的原因主要是解决冲突的方法选择不当 * 线性探测 * ![](../../images/408/《数据结构》查找/线性探测.png) * ![](../../images/408/《数据结构》查找/散列表查找性能分析.png) * 平方探测 * ![](../../images/408/《数据结构》查找/平方探测.png) * 有定理显示，如果散列表长度TableSize是某个4k+3(k是正整数)形式的素数时，平方探测就可以探查到整个散列表空间 * 链地址法 * 将相应位置上冲突的所有关键词存储在同一单链表中 * ![](../../images/408/《数据结构》查找/链地址法.png)