数据结构——查找算法 一. 概念 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据素（或记录）。 ASL平均查找长度：ASL= ∑P*C ( ∑范围是n，即表长；Pi是查找第i个素的概率；Ci是找到第i个素比较次数） 二. 线性结构 (1) 顺序查找： i. 无序顺序查找：ASL= (n+1)/2 ii. 有序顺序查找：ASL= n/2+n/(n+1) (2) 折半查找： i. 查找成功：ASL=∑n*h (累加n为查找成功结点与深度的乘积/查找成功结点数量) ii. 查找失败：ASL=∑l*(h-1) (累加n为查找失败结点与深度的乘积/查找失败结点数量) iii. 查找判定树： 类型：平衡二叉树 条件：中序为有序序列 建立：模拟查找过一遍 树高：h = ⌈log(2,n+1)⌉ 三. 树形结构 (1) B树： B 树就是常说的“B 减树（B- 树）”，又名平衡多路（即不止两个子树）查找树。 在计算机科学中，B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。 注：也有材料将B树称为二叉搜索树，B减树作为多路查找树。 i. 定义： 阶数：m阶意味所有结点的孩子结点最大值为m m叉树： 树中所有叶子结点均不带信息，且在树中同一层次上 仅有根结点或者根结点至少有两棵子树 所有非叶子（不包括根）结点至少含有⌈m/2⌉棵子树（[⌈m/2⌉-1，m-1]个关键字） 根结点可以仅有一个关键字 非叶子结点：
[ P是子树结点指针K是关键字（有序）] ii. 操作： 查找、插入、删除 iv. 性质： h>=⌈log(m, n+1)⌉ h<=log(⌈m/2⌉, (n+1)/2)) + 1 叶结点数=关键字数+1 n>=2⌈m/2⌉^(h-1) – 1 (2) B+树： 与b树区别：每个关键字对应一子树；叶点包含了全部关键字；支持顺序查找 四. 散列结构 (1) 概念： 散列是一种思想。与已经学过的其他数据结构相比较，向量是采用循秩访问(call by rank)的访问方式，列表是采用循位置访问(call by position)的访问方式，二叉搜索树是采用循关键码访问(call by key)的访问方式，散列与他们都不一样，是采用循值访问(call by value)的访问方式 散列函数： 关键字与地址的映射:address=f(key) key的定义域应包括关键字所有的可能 值域应该在存储接受范围内 由于不可能精确到所有的关键字，所以肯定存在冲突 (2) 散列函数构造法： i. 直接定址法：线性变换法，f(x)=kx+b ii. 除留余数法：f(x)=x%p iii. 数字分析法：根据关键字频率构造 iv. 折叠法：划分关键字，取每部分叠加和作为散列地址 (3) 冲突处理方法： i. 开放地址法： 线性探测法： 目标地址已经被合法关键字占据——顺序循环查找下一个空位置放 目标地址已经被非法关键字占据——顺循环序查找下一个空位置放 再散列法： 遇到冲突的时候，再使用新散列函数计算 ii. 拉链法：发生冲突的关键字放到该位置的链表里 (4) 性能分析： 查找效率取决因素：散列函数、处理冲突的方法、装填因子(a=已使用空间/总空间) 常见散列函数查找成功ASL：线性探测、随机探测、链地址
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/84050.html
