数据结构之查找
查找概论
查找表
定义
查找表（Search Table）是同一类型的数据元素（或记录）的集合。
查找表分类
静态查找表
静态查找表（Static Search Table）：只做查找操作的查找表。
它的主要操作有：
- 查找某个“特定的”数据元素是否存在于查找表中。
- 检索某个“特定的”数据元素和各种属性。
动态查找表
动态查找表（Dynamic Search Table）：在查找过程中同时插入不存在的数据元素，
或在查找过程中删除已经存在的数据元素。
它的主要操作有：
- 查找时插入数据元素。
- 查找时删除数据元素。
关键字
关键字（Key）是数据元素中某个数据项的值，又称为键值。（难理解）
若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（Primary key）。
可以识别多个数据元素（或记录）的关键字，是次关键字（Secondary Key）。
意思是根据次关键字可以查询到多条数据元素吗？
查找定义
查找（Searching）是根据给定的某个值，在查找表中确定一个其关键字等于给定
值的数据元素（或记录）。
若查找到了数据元素，则查找成功；否则，查找失败。
查找结构
面向查找操作的数据结构叫做查找结构。
顺序表查找
概念
顺序表查找（Sequential Search）又叫线性查找，是最基本的查找技术。它的查找过程是：
-
从表中第一个（或最后一个）记录开始，逐个比较记录的关键字和给定值。
-
若某个记录的关键字和给定值相等，则查找成功。
-
若一直查找到最后一个（或第一个）记录，其关键字都不等于给定值，则查找失败。
代码
int Sequential_search(int *a, int n, int key)
{
int i;
for(i = 1; i < n; i++){
if(a[i] == key){
return i;
}
}
return 0;
}
顺序表查找代码优化
int Sequential_search(int *a, int n, int key)
{
int i;
a[0] = key;
i = 1;
while(a[i] != key){
i--;
}
return i; // 当i等于0时查找失败
}
或
int Sequential_search(int *a, int n, int key)
{
int i;
a[n-1] = key;
while(a[i] != key){
i++;
}
return i; // 当i等于n-1时查找失败
}
时间复杂度
$O(n)$
有序表查找
折半查找
摘抄
一看就懂的知识点，一般不再打字记录笔记，直接摘抄书本。
数据结构_查找_折半查找
代码
int Binary_search(int *a, int n, int key)
{
int low, high, mid;
low = 1;
high = n;
while(low <= high){
/*1*/ mid = (low + high) / 2;
if(key > a[mid]){
low = mid + 1;
}else if(key < a[mid]){
high = mid - 1;
}else{
return mid;
}
}
/*2*/ return 0;
}
第1行，取值相当于PHP中的 floor 函数。
第2行，查找结果不是 mid 就是查找失败。这说明，若查找表中存在要
查找的关键字，那么该关键字的位置一定是某个中间位置。不能理解这点。
差值查找
差值计算公式
$key-a[low]\over a[high]-a[low]$
这个公式是如何得到的？
代码
int Binary_search(int *a, int n, int key)
{
int low, high, mid;
low = 1;
high = n;
while(low <= high){
mid = (key - a[low]) / (a[high] - a[low]);
if(key > a[mid]){
low = mid + 1;
}else if(key < a[mid]){
high = mid - 1;
}else{
return mid;
}
}
/*2*/ return 0;
}
时间复杂度
$O(logn)$
斐波那契查找
代码
int Fibonacci_Search(int *a, int n, int key)
{
int low, high, mid, i, k;
low = 1;
high = n;
k = 0;
/*1*/ while(n>F[k]-1){ // 计算n位于斐波那契数列的位置
k++;
}
for(i = n; i < F[k]-1; i++){ // 将不满的数值补全
a[i] = a[n];
}
while(low <= high){
mid = low + F[k-1] - 1; // 计算当前分隔的下标
if(key < a[mid]){
high = mid - 1;
/*2*/ k = k -1; // 斐波那契数列下标减一位
}else if(key > a[mid]){
low = mid + 1;
/*3*/ k = k - 2; // 斐波那契数列下标减二位
}else{
if(mid <= n){
return mid; // 若相等则说明mid即为查找到的位置
}else{
return n; // 若mid>n说明是补全数值，返回n
}
}
}
return 0;
}
理解不了第1行、第2行、第3行。
摘抄
数据结构_查找_斐波那契查找_核心
不理解上图中的范围个数是怎么得到的。
数据结构_查找_斐波那契查找_范围个数示意图
这个图好像有助于理解某些东西。
线性索引查找
摘抄
概念
数据结构_查找_线性索引查找_概念
稠密索引
概念
数据结构_查找_线性索引查找_稠密索引_概念
对于稠密索引的的索引表，索引项一定是按照关键码有序的排列。
分块索引
概念
数据结构_查找_线性索引查找_分块索引_概念
数据结构_查找_线性索引查找_分块索引_例子
时间复杂度（不懂）
数据结构_查找_线性索引查找_分块索引_时间复杂度
倒排索引
概念
数据结构_查找_线性索引查找_倒排索引_概念
存储技巧
数据结构_查找_线性索引查找_倒排索引_存储技巧
二叉排序树
二叉排序树查找操作代码
typedef struct BiTNode
{
int data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
if(!T){
*p = f;
return FALSE;
}else if(key == T->data){
*p = T;
return TRUE;
}else if(key > T->data){
return SearchBST(T->rchild, key, T, p);
}else{
return SearchBST(T->lchild, key, T, p);
}
}
二叉排序树插入操作代码
二叉排序树插入操作代码
Status InsertBST(BiTree *T, int key)
{
BiTree p, s;
if(!SearchBST(*T, key, NULL, &p)){
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild = NULL;
if(!p){
*T = s;
}else if(key > p->data){
p->rchild = s;
}else{
p->lchild = s;
}
return TRUE;
}else{
return FALSE;
}
}
如果查找到的是叶子结点，插入新的结点很容易。
如果查找到的不是叶子结点，假如此结点刚好有左右孩子结点，如何插入新的结点？
查找停止的情况有两种：找到了和关键字匹配的记录；查找失败。第二种情况，必然
是遍历到了叶子结点。好不能透彻地理解这点，只能大概不确定地得出这样的结论。
创建二叉排序树代码
int CreateBST(void)
{
int i;
int a[10] = {62, 88, 58, 47, 35, 73, 51, 99, 37, 93};
BiTree T = NULL;
for(i = 0; i < 10; i++){
InsertBST(T, a[i]);
}
return 0;
}
二叉排序树删除操作代码
代码
Status Delete(BiTree *p)
{
BiTree q, s;
if((*p)->rchild == NULL){
q = *p;
*p = (*p)->lchild;
free(q);
}else if((*p)->lchild == NULL){
q = *p;
*p = (*p)->rchild;
free(q);
}else{
q = *p;
s = (*p)->lchild;
while(s->rchild){
q = s;
s = s->rchild;
}
(*p)->data = s->data;
if(q != *p){
q->rchild = s->lchild;
}else{
q->lchild = s->lchild;
}
free(s);
}
}
二叉排序树删除结点代码
Status DeleteBST(BiTree *T, int key)
{
if(!*T){
return FALSE;
}else{
if(key == (*T)->data){
return Delete(T);
}else if(key < (*T)->data){
return DeleteBST(&(*T)->lchild, key);
}else{
return DeleteBST(&(*T)->rchild, key);
}
}
}
删除操作有四种情况：
- 要删除的结点是叶子结点。
- 要删除的结点有左孩子。
- 要删除的结点有右孩子。
- 要删除的结点有左右孩子。理解不了这种情况的代码。
代码解读
数据结构_查找_二叉排序树_二叉排序树删除操作代码_代码解读_7
数据结构_查找_二叉排序树_二叉排序树删除操作代码_代码解读_1
数据结构_查找_二叉排序树_二叉排序树删除操作代码_代码解读_2
数据结构_查找_二叉排序树_二叉排序树删除操作代码_代码解读_3
数据结构_查找_二叉排序树_二叉排序树删除操作代码_代码解读_4
数据结构_查找_二叉排序树_二叉排序树删除操作代码_代码解读_5
数据结构_查找_二叉排序树_二叉排序树删除操作代码_代码解读_6
摘抄
概念
数据结构_查找_二叉排序树_概念
平衡二叉树（AVL树）
概念
平衡二叉树
平衡二叉树（Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree），
是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1。
平衡因子
平衡二叉树上的结点的左子树减去右子树的得到的差值，叫做平衡因子（Balance Factor）。
平衡因子可能的值是 -1，0 和 1。
数据结构_查找_平衡二叉树（AVL树）_平衡因子
书中认为图3中，结点58的左子树的高度是2，我认为是3。
最小不平衡子树
距离插入结点最近的、平衡因子的绝对值大于 1 的结点为根的子树，叫做最小不平衡子树。
什么叫插入结点？是指插入新结点的那个位置吗？
数据结构_查找_平衡二叉树（AVL树）_最小不平衡子树
结点58的左子树的高度，我认为是3。
平衡二叉树实现算法代码
旋转操作
树的结点结构
typedef struct BiTNode
{
int data;
int bf; // 结点的平衡因子
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
右旋转操作代码
void R_Rotate(BiTree *p)
{
BiTree L;
L = (*p)->lchild; // L指向p的左子树根结点
(*p)->lchild = L->rchild; // L的右子树挂结为p的左子树
L->rchild = (*p);
*p = L; // P指向新的根结点
}
左旋操作代码
void L_Rotate(BiTree *p)
{
BiTree R;
R = (*p)->rchild; // R指向p的右子树根结点
(*p)->rchild = R->lchild; // R的左子树挂接为p的右子树
R->lchild = (*p);
*p = R; // p指向新的根结点
}
理解不了。按照我的思路，p 是 R->lchild 的左子树，可是这和左旋转
后的结果不吻合。
重新画了几次，根据代码，可以得到预期效果图了。可是，L 的右子树为何
会变成 p 的左子树？
旋转操作的关键在于：第一步的时候，原树拆成了两棵树。旋转过程见纸质笔记。
左平衡旋转处理函数代码
代码
#define LH +1; // 左高
#define EH 0; // 等高
#define RH -1; // 右高
void LeftBalance(BiTree *T)
{
BiTree L, Lr;
L = (*T)->lchild; // L指向T的左子树根结点
switch(L->bf){
case LH:
/*1*/ (*T)->bf = L->bf = EH;
R_Rotate(T);
break;
case RH:
Lr = L->rchild; // Lr指向T的左孩子的右子树的根
switch(Lr->bf){ // 修改T及其左孩子的平衡因子
case LH:
(*T)->bf = RH;
L->bf = EH;
break;
case EH:
(*T)->bf = L->bf = EH;
break;
case RH:
(*T)->bf = EH;
L->bf = LH;
break;
}
Lr->bf = EH;
L_Rotate(&(*T)->lchild); // 对T的左子树作左旋平衡处理
R_Rotate(T); // 对T做右旋平衡处理
}
}
代码解读
数据结构_查找_平衡二叉树（AVL树）_最小不平衡子树_左平衡旋转处理函数代码_代码解读_1
数据结构_查找_平衡二叉树（AVL树）_最小不平衡子树_左平衡旋转处理函数代码_代码解读_2
数据结构_查找_平衡二叉树（AVL树）_最小不平衡子树_左平衡旋转处理函数代码_代码解读_3
数据结构_查找_平衡二叉树（AVL树）_最小不平衡子树_左平衡旋转处理函数代码_代码解读_4
主函数代码
代码
Status InsertAVL(BiTree *T, int e, Status *taller)
{
if(!T){
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = e;
(*T)->lchild = (*T)->rchild = NULL;
(*T)->bf = EH;
*taller = TRUE;
}else{
if(e = (*T)->data){
*taller = FALSE;
return FALSE;
}
if(e <(*T)->data){
if(!InsertAVL(&(*T)->lchild, e, taller)){
return FALSE;
}
if(taller){
switch((*T)->bf){
case LH:
LeftBalance(T);
*taller = FALSE;
break;
case EH:
(*T)->bf = LH;
*taller = TRUE;
break;
case RH:
(*T)->bf = EH;
*taller = FALSE;
break;
}
}
}else{
if(!InsertAVL(&(*T)->rchild, e, taller)){
return FALSE;
}
if(*taller){
switch((*T)->bf){
case LH:
(*T)->bf = EH;
*taller = FALSE;
break;
case EH:
(*T)->bf = RH;
*taller = TRUE;
break;
case RH:
RightBalance(T);
*taller = FALSE;
break;
}
}
}
}
return TRUE;
}
代码解读
《大话数据结构》中的代码，好像有很多错误，只可以当作逼真的伪代码去看待。
数据结构_查找_平衡二叉树（AVL树）_平衡二叉树实现算法代码_代码解读_1
数据结构_查找_平衡二叉树（AVL树）_平衡二叉树实现算法代码_代码解读_2
数据结构_查找_平衡二叉树（AVL树）_平衡二叉树实现算法代码_代码解读_3
数据结构_查找_平衡二叉树（AVL树）_平衡二叉树实现算法代码_代码解读_4
多路查找树（B树）
摘抄
必要性
要操作的数据非常大，大到无法在内存中处理。
定义
多路查找树（multi-way search tree）的每一个结点的孩子数可以多于两个，且每一个结点
处可以存储多个元素。元素之间存在某种特定的排序关系。
2-3树
概念
数据结构_查找_多路查找树_23树_概念_1
数据结构_查找_多路查找树_23树_概念_2
2-3树的插入实现
数据结构_查找_多路查找树_23树_插入_1
数据结构_查找_多路查找树_23树_插入_2
数据结构_查找_多路查找树_23树_插入_3
数据结构_查找_多路查找树_23树_插入_4
2-3树的删除实现
数据结构_查找_多路查找树_23树_删除_1
数据结构_查找_多路查找树_23树_删除_2
数据结构_查找_多路查找树_23树_删除_3
数据结构_查找_多路查找树_23树_删除_4
数据结构_查找_多路查找树_23树_删除_5
数据结构_查找_多路查找树_23树_删除_6
数据结构_查找_多路查找树_23树_删除_7
数据结构_查找_多路查找树_23树_删除_8
可以理解这些方法能够保证删除的元素在被删除后，新树仍然是2-3树，但不明白这么做的规律性，
更无能力用代码实现删除操作。
2-3-4树
概念
数据结构_查找_多路查找树_234树_概念
2-3-4树的插入和删除
数据结构_查找_多路查找树_234树_插入删除_1
数据结构_查找_多路查找树_234树_插入删除_2
B树
概念与性质
数据结构_查找_多路查找树_B树_概念与性质_1
数据结构_查找_多路查找树_B树_概念与性质_2
减少内存与外存交换数据的频率的原因
数据结构_查找_多路查找树_B树_减少内存与外存交换数据的频率的原因_1
数据结构_查找_多路查找树_B树_减少内存与外存交换数据的频率的原因_2
B+树
产生原因--优化B树
数据结构_查找_多路查找树_B加树_概念_1
数据结构_查找_多路查找树_B加树_概念_2
与B树的对比
数据结构_查找_多路查找树_B加树_与B树的对比
散列查找表概述
摘抄
定义
数据结构_查找_散列查找表概述_摘抄_定义_1
散列表查找步骤
1.存储时，通过散列函数计算记录的散列地址，并按该存储地址存储这条记录。
2.查找时，通过相同的散列函数计算记录的散列地址，并按该散列地址读取记录。
散列表适用场景
1.最适合的求解问题是查找与给定关键字等值的记录。
2.同样的关键字对应很多记录的问题，不适合用散列表查找。
3.范围查找，不适合用散列表查找。
冲突
数据结构_查找_散列查找表概述_摘抄_冲突
散列函数的构造方法
设计好的散列函数的原则
1.计算简单。
2.散列地址分布均匀。这和“使用连续的存储空间存储记录”有关吗？
直接定址法
概念
数据结构_查找_散列查找表概述_摘抄_数字分析法
只强调了抽取，对散列函数并无固定要求。
平方取中法
数据结构_查找_散列查找表概述_摘抄_平方取中法
折叠法
数据结构_查找_散列查找表概述_摘抄_折叠法
存储标签id时，我常用的方法是，存储“1,2,3,4”这样的字段。有人提出，
计算这4个标签ID的“位运算”，存储“位运算”的结果。具体应用方法已经
忘记。这也是折叠法。它们都减少了占用的存储空间。
除留余数法
数据结构_查找_散列查找表概述_摘抄_除留余数法_1
数据结构_查找_散列查找表概述_摘抄_除留余数法_2
随机数法
数据结构_查找_散列查找表概述_摘抄_随机数法
处理散列冲突的方法
摘抄
开放定址法
数据结构_查找_处理散列冲突的方法_摘抄_开放定址法_1
数据结构_查找_处理散列冲突的方法_摘抄_开放定址法_2
数据结构_查找_处理散列冲突的方法_摘抄_开放定址法_3
再散列函数法
数据结构_查找_处理散列冲突的方法_摘抄_再散列函数法
存储的时候，是否应该记录解决冲突使用的散列函数？若不记录，读取
数据的时候，如何计算存储时候的地址？
链接地址法
数据结构_查找_处理散列冲突的方法_摘抄_链接地址法_1
数据结构_查找_处理散列冲突的方法_摘抄_链接地址法_1
公共溢出法
数据结构_查找_处理散列冲突的方法_摘抄_公共溢出法_1
数据结构_查找_处理散列冲突的方法_摘抄_公共溢出法_2
散列表查找实现
代码
散列表结构
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12
#define NULLKEY -32768
typedef struct
{
int *elem; // 数据元素存储基址
int count; // 当前数据元素个数
}HashTable;
int m = 0; // 散列表表长，全局变量
散列表初始化
Status InitHashTable(HashTable *H)
{
int i;
m = HASHSIZE;
H->count = m;
H->elem = (int *)malloc(m*sizeof(int));
for(i = 0; i < m; i++){
H->elem[i] = NULLKEY;
}
return OK;
}
散列函数
int Hash(int key)
{
return key % m;
}
插入操作
void InsertHash(HashTable *H, int key)
{
int addr = Hash(key); // 求散列地址
while(H->elem[addr] != NULLKEY)
addr = (addr + 1) % m;
H->elem[addr] = key;
}
查询操作
void SearchHash(HashTable *H, int key)
{
int addr = Hash(key);
while(H->elem[addr] != key){
addr = (addr + 1) % m;
if(H->elem[addr] != key || addr == Hash(key))
{
return UNSUCCESS;
}
}
return SUCCESS;
}
if(H->elem[addr] != key || addr == Hash(key)) 中的 addr == Hash(key) 说明
循环回到原点，我不理解这点。
if(H->elem[addr] != key || addr == Hash(key))
{
return UNSUCCESS;
}
这块代码是否有问题？
当 H->elem[addr] != key 成立时，应该继续计算哈希地址。
散列表查找性能分析
数据结构_查找_散列表查找实现_摘抄_散列表查找性能分析_1
数据结构_查找_散列表查找实现_摘抄_散列表查找性能分析_2
喜欢我的文章请关注公众号
ganggangwudao或扫描个人主页的微信二维码，谢谢！
我笃信“写作可以促进思考”，会以自己面临的问题为思考素材，写成文字，坚持每天推文。
如果可以和大家共同探讨，就更开心了。
网友评论