数据结构之查找
查找概论
查找表
定义
查找表（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);
}
}
}
删除操作有四种情况：
- 要删除的结点是叶子结点。
- 要删除的结点有左孩子。
- 要删除的结点有右孩子。
- 要删除的结点有左右孩子。理解不了这种情况的代码。
代码解读
摘抄
概念
平衡二叉树（AVL树）
概念
平衡二叉树
平衡二叉树（Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree），
是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1。
平衡因子
平衡二叉树上的结点的左子树减去右子树的得到的差值，叫做平衡因子（Balance Factor）。
平衡因子可能的值是 -1，0 和 1。
书中认为图3中，结点58的左子树的高度是2，我认为是3。
最小不平衡子树
距离插入结点最近的、平衡因子的绝对值大于 1 的结点为根的子树，叫做最小不平衡子树。
什么叫插入结点？是指插入新结点的那个位置吗？
结点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做右旋平衡处理
}
}
代码解读
主函数代码
代码
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;
}
代码解读
《大话数据结构》中的代码，好像有很多错误，只可以当作逼真的伪代码去看待。
多路查找树（B树）
摘抄
必要性
要操作的数据非常大，大到无法在内存中处理。
定义
多路查找树（multi-way search tree）的每一个结点的孩子数可以多于两个，且每一个结点
处可以存储多个元素。元素之间存在某种特定的排序关系。
2-3树
概念
2-3树的插入实现
2-3树的删除实现
可以理解这些方法能够保证删除的元素在被删除后，新树仍然是2-3树，但不明白这么做的规律性，
更无能力用代码实现删除操作。
2-3-4树
概念
2-3-4树的插入和删除
B树
概念与性质
减少内存与外存交换数据的频率的原因
B+树
产生原因--优化B树
概念
与B树的对比
散列查找表概述
摘抄
定义
散列表查找步骤
1.存储时，通过散列函数计算记录的散列地址，并按该存储地址存储这条记录。
2.查找时，通过相同的散列函数计算记录的散列地址，并按该散列地址读取记录。
散列表适用场景
1.最适合的求解问题是查找与给定关键字等值的记录。
2.同样的关键字对应很多记录的问题，不适合用散列表查找。
3.范围查找，不适合用散列表查找。
冲突
散列函数的构造方法
设计好的散列函数的原则
1.计算简单。
2.散列地址分布均匀。这和“使用连续的存储空间存储记录”有关吗？
直接定址法
概念
优缺点
数字分析法
只强调了抽取，对散列函数并无固定要求。
平方取中法
折叠法
存储标签id时，我常用的方法是，存储“1,2,3,4”这样的字段。有人提出，
计算这4个标签ID的“位运算”，存储“位运算”的结果。具体应用方法已经
忘记。这也是折叠法。它们都减少了占用的存储空间。
除留余数法
随机数法
处理散列冲突的方法
摘抄
开放定址法
再散列函数法
存储的时候，是否应该记录解决冲突使用的散列函数？若不记录，读取
数据的时候，如何计算存储时候的地址？
链接地址法
公共溢出法
散列表查找实现
代码
散列表结构
#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 成立时，应该继续计算哈希地址。
散列表查找性能分析
喜欢我的文章请关注公众号
ganggangwudao或扫描个人主页的微信二维码，谢谢！
我笃信“写作可以促进思考”，会以自己面临的问题为思考素材，写成文字，坚持每天推文。
如果可以和大家共同探讨，就更开心了。
