

首页  思维导图  详情



查找_计算机数据结构考研

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自增至满足条件

删除操作不能置空做法是标记已删除

易产生堆积问题效率低

平方探测法

不易产生堆积问题

H=(H(key)+d)%m 其中d从0,1,-1,4,-4,9,-9至满足条件

散列表长度必须是4i+3的素数

伪随机序列法

H=(H(key)+d)%m 其中d是随机递增序列

章节技巧

B树 VS B+树

 Collect

Get Started

计算机数据结构算法

 Collect

Get Started

串_计算机数据结构考研

 Collect

Get Started

排序_计算机数据结构考研

 Collect

Get Started

计算机科学 AP课程





0 条评论

下一页