查找
2021-04-14 19:42:34 7 举报AI智能生成
数据结构 查找 笔记
作者其他创作
大纲/内容
动态查找
插入删除
顺序查找
要查的关键字存在下标为0的位置作为监视哨
作用：省去判断循环中下标越界的条件
不用判断查找表是否检测完
不用判断查找表是否检测完
折半查找
条件：按关键字大小有序排列
平均时间复杂度：O(log2 n）
只适用于顺序存储结构 插入删除必须移动大量节点
分块查找、索引顺序查找
块中元素任意 块按元素大小存储 索引表存储块内最大关键字及相应指针指向该块第一个和最后一个元素
ASL根号n+1
哈希表查找法
时间复杂度为O（1）
时间复杂度为O（1）
直接定址法
简单，不会冲突；元素不连续，空间浪费
除留余数法
平方取中法
数字分析法
分段叠加法
伪随机数法
关键字长度不等
哈希表冲突处理
开放定址法-再散列法
p=H(key）出现冲突时，以p为基础产生另一个哈希地址p1
1线性探测法
冲突发生时顺序查看表中下一单元，直到找出单元或查遍全表
2二次探测法
m为表长 k为关键字 要求m为某个4k+3的质数
冲突发生时，在表的左右跳跃式探测，灵活
3伪随机法
用伪随机数发生器给定的随机数作为起点
链地址法
将所有哈希值为i的元素构成一个同义词链的单链表，单链表头指针放在哈希表的第i个单元
再哈希法
同时构造多个不同的哈希函数
建立公共溢出区
哈希表分为基础表和溢出表，凡是和基本表发生冲突的元素，填入溢出表
哈希表查找及性能分析
装填因子阿尔法a=哈希表中元素个数n/哈希表长度m
0 条评论
下一页
为你推荐
查看更多
