查找_计算机数据结构考研
2020-07-07 13:38:57 2 举报AI智能生成
登录查看完整内容
查找_计算机数据结构考研
作者其他创作
大纲/内容
版权∈ 本人所有 严禁擅自转载和商用 受法律保护
更新记录
2020.6.4 开坑
查找_计算机数据结构考研
查找
基本概念
关键字 —— 唯一标识数据元素的数据项
查找表
静态查找表
只需要查找
动态查找表
查找+增/删
评价指标
平均查找长度 ASLEEP
算法
顺序查找/线性查找
适用线性表【包括顺序表和链表】
哨兵版本顺序表实现 O(N)无需判断i值是否越界效率更高
有序元素 查找判定树ASL
折半查找/二分查找
适用于有序顺序表【不能链表】
升序排列的顺序表实现时间复杂度O（log2n)
折半查找判定树的构造一定是平衡二叉树（左右子树深度之差不超过1）只有最下面一层是元素不满的，n个元素树高为log2(n+1)【不包含失败结点】若查找树有n个关键字 则失败结点有n+1
分块查找/索引顺序查找
特点 —— 块内无序 块间有序
查找效率分析ASL=索引查找ASL + 块内查找ASL
B树/多路平衡查找树
n个关键字的m阶B树 最小高度 h≥logm(n+1) 最大高度 h≤log[m/2][(n+1)/2+1]
B树核心特性 1）使之尽可能\"满\" 2)使之尽可能\"平衡\"n个关键字的B树必有n+1个叶子结点(划分n+1分区)
插入
删除
B+树
散列查找/哈希表
一种数据结构 空间换时间的算法
数据元素的关键字与其存储地址直接相关 Addr=H(key)
查找长度
需要对比关键字的次数
装填因子α=表中记录数/散列表长度
反映散列表的查找效率
常见散列函数
处理冲突
拉链表
再散列法
设置多个散列函数
开放地址法
线性探测法
冲突时每次往后探测相邻的下一个单元是否为空 H=(H(key)+d)%m 其中d从0自增至满足条件
删除操作 不能置空 做法是标记已删除
易产生堆积问题 效率低
平方探测法
不易产生堆积问题
散列表长度必须是4i+3的素数
伪随机序列法
H=(H(key)+d)%m 其中d是随机递增序列
章节技巧
B树 VS B+树
0 条评论
回复 删除
下一页
