考研笔记-计算机之数据结构:集合结构-查找表(基础概览)
- 2026-11-10 00:30:59
考研笔记-计算机之数据结构:集合结构-查找表(基础概览)
——如阅读体验不佳，可转为横屏阅读；如微信无法横屏，可尝试文末方法。
查找
查找表：由同一类型的数据元素构成的集合，数据元素之间是完全松散的关系。
静态查找表：只对查找表进行查找操作。
动态查找表：可对查找表进行查找、插入和删除操作。
定义 | 实现 | 表示 | 查找方法 | 平均查找性能 |
静态查找表 | 顺序表 （有序或无序） | 顺序/链式存储 | 顺序查找 |
|
有序表 （有序、等概率） | 顺序存储 | 折半查找 |
| |
次优查找树 （有序、不等概率） | 链式存储 | 随机查找 |
| |
索引顺序表 （索引表有序，查找表块间有序） | 顺序/链式存储 | 分块查找 |
| |
动态查找表 | 二叉查找树 （有序） | 链式存储 | 随机查找 |
|
平衡二叉查找树 （有序） | 链式存储 | 随机查找 |
| |
B-树 （有序） | 链式存储 | 随机查找 |
| |
B+树 （有序） | 链式存储 | 随机查找或顺序查找 |  | |
键树 | 链式存储 | 随机查找 | (1+d)h/2 | |
哈希表 | 线性探测再散列冲突处理 | 顺序存储 | 哈希函数+冲突处理 |
|
二次探测再散列冲突处理 | 顺序存储 | 哈希函数+冲突处理 |
| |
随机探测再散列冲突处理 | 顺序存储 | 哈希函数+冲突处理 |
| |
再哈希冲突处理 | 顺序存储 | 哈希函数+冲突处理 |
| |
链地址冲突处理 | 顺序+链式存储 | 哈希函数+冲突处理 |
| |
说明： 类似顺序查找的查找算法的时间复杂度为 |
——可选择“【右上角···】→【在浏览器中打开】”进行横屏阅读。
本文来自网友投稿或网络内容，如有侵犯您的权益请联系我们删除，联系邮箱：wyl860211@qq.com 。
