前言

查找表：是一种数据集合（记录），可以理解为你要从哪里查找

查找表可以分为静态查找表和动态查找表

  • 静态查找：只需要执行查找操作
  • 动态查找：除了查找之外还需要增/删除数据元素

顺序查找

顺序查找是我们最开始，也是最熟悉的查找方式，就是一个一个查找（遍历）。

常规

顺序查找又称“线性查找”，通常用于线性表。其查找模式是线性的。代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define ElemType int
#define MaxSize 10

typedef struct sTable{
	ElemType a[MaxSize];
	int TableLen;
}STable;

//顺序查找
int Serach_Seq(STable s,ElemType data) {
	for (int i = 0; i < s.TableLen; i++)
	{
		if (data == s.a[i])
		{
			printf("下标为:%d", i);
			return i;
		}
	}
	return -1;
}

哨兵

哨兵模式查找还是顺序查找，不过它将数组的 0 号元素空出来填充为需要查找的元素，查找方向改为从后向前查找。代码示例：

1
2
3
4
5
6
//顺序查找——哨兵模式
int Serach_Seq2(STable s, ElemType data) {
	int i = 0;
	for (i = s.TableLen; data != s.a[i]; i--);
	return i;
}

折半查找

折半查找就是我们常说的二分查找，它只适用于有序的顺序表。

二分查找需要借助最高位和最低位的指针，每次根据low+high/2结果向下取整，根据和mid指针指向的值大小比较，获取区间，依次比较到最后。

image-20220901082019481

当比较到最后的时候，如下图所示，当low指针超过high指针的时候表示查找失败

image-20220901082556151

其代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>

#define ElemType int
#define Maxsize 10

typedef struct list {
	ElemType num;
	ElemType data[Maxsize];
}List;

//二分查找——递归查找
int Binary_Serach(List l,ElemType sdata,int low,int high) {
	if (low<=high)
	{
		int mid = (high + low) / 2;	//折半
		if (sdata>l.data[mid])
		{
			return Binary_Serach(l, sdata, mid + 1, high);
		}
		else if (sdata< l.data[mid])
		{
			return Binary_Serach(l, sdata, low, mid - 1);
		}
		else
		{
			return mid;
		}
	}
	return -1;
}

int main() {
	List l;
	for (int i = 0; i < 10; i++)
	{
		l.data[i] = i;
	}
	l.num = 10;
	printf("其位置为: %d", Binary_Serach(l,3,0,9)+1);
}

如上是通过递归实现的二叉查找，由于递归的效率相对较低，如下使用迭代来实现二叉查找：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//二叉查找——迭代
int Binary_Search2(List l,ElemType sdata) {
	int low = 0, high = l.num - 1, mid;
	while (low<=high)
	{
		mid = (high + low) / 2;
		if (sdata < l.data[mid])
		{
			high = mid - 1;
		}
		else if(sdata > l.data[mid])
		{
			low = mid + 1;
		}
		else
		{
			return mid;
		}
	}
	return -1;
}

分块查找

分块查找查找思想如下图所示：

image-20220903085157039

通过将数据分块划分大小，先判断数据区间，然后再到指定的数据区间进行顺序查找。

二叉排序树

二叉排序树是利用了二叉树的结构，通过根节点来区分排序数据，如下图所示：

image-20220903085942168

其结构特点：左子树结点 < 根节点值 < 右子树结点值

前排提醒：二叉排序树的代码基础是在【5.1】树与二叉树的基础上编写的

查找操作

采用迭代搜索，代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//二叉排序树——迭代搜索
TreeNode* BST_Serach(Tree t,int sdata) {
	TreeNode* tempnode = t;
	while (tempnode != NULL)
	{
		if (sdata < tempnode->data)
		{
			tempnode = tempnode->lchild;	//小于往左走
		}
		else if(sdata >tempnode->data)
		{
			tempnode = tempnode->rchild;	//大于往右走
		}
		else
		{
			return tempnode;	//找到了
		}
	}
	return NULL;	//没找到
}

采用递归搜索，代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//二叉排序树——递归搜索
TreeNode* BST_Serach2(TreeNode* t, int sdata) {
	if (t!=NULL)
	{
		if (sdata <t->data)
		{
			return BST_Serach2(t->lchild, sdata);	//小于往左走
		}
		else if(sdata >t->data)
		{
			return BST_Serach2(t->rchild, sdata);	//大于往右走
		}
		else
		{
			return t;
		}
	}
	return t;
}

插入操作

当插入的值相同时则不允许插入，反之则类似于搜索，找到对应的位置插入。代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//二叉树插入——迭代插入
int BST_Insert(Tree* t, int sdata) {
	TreeNode* tempnode = (*t);
	TreeNode* front = NULL;
	while (tempnode != NULL)
	{
		front = tempnode;
		if (sdata < tempnode->data)
		{
			tempnode = tempnode->lchild;	//小于往左走
		}
		else if (sdata > tempnode->data)
		{
			tempnode = tempnode->rchild;	//大于往右走
		}
		else
		{
			printf("插入失败：已存在结点\n");
			return tempnode;	//找到了
		}
	}
	tempnode = malloc(sizeof(TreeNode));
	tempnode->data = sdata;
	tempnode->lchild = tempnode->rchild = NULL;
	if (sdata< front->data)
	{
		front->lchild = tempnode;
	}
	else
	{
		front->rchild = tempnode;
	}
	printf("插入成功\n");
	return tempnode;	//没找到
}

删除操作

二叉树的删除还要保证其二叉排序树的特性，则有三种情况：

  • 删除的是叶子结点：直接删除即可
  • 删除的结点只有左子树或者右子树：删除结点，然后让其子树替代它的位置即可
  • 删除的结点存在左右子树
    • 选择将右子树的最小值（即删除节点右子结点的左结点）作为删除结点的新结点。
    • 也可以选择将左子树的最大值（即删除节点左子树的左结点）作为删除结点的新结点

代码示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//二叉树删除
bool DeleteNode(Tree* t,int ddata) {
	TreeNode* delnode = (*t);	//要删除的结点
	TreeNode* delnodeF = NULL;	//要删除的结点的父结点
	TreeNode* newnode = NULL;	//要替换删除的结点
	TreeNode* newnodeF = NULL;	//要替换删除的结点的父结点
	while (delnode !=NULL && delnode->data!=ddata)
	{
		if (ddata < delnode->data)
		{
			delnodeF = delnode;	//获取其父结点
			delnode = delnode->lchild;	//小于往左走
		}
		else if(ddata > delnode->data)
		{
			delnodeF = delnode;	//获取其父结点
			delnode = delnode->rchild;	//大于往右走
		}
	}
	//如果要删除的结点没找到
	if (delnode ==NULL)
	{
		printf("未查找到要删除的结点\n");
		return false;
	}
	//如果要删除的结点存在左右子树
	if (delnode->lchild!=NULL && delnode->rchild !=NULL)
	{
		newnodeF = delnode->rchild;	//让要替换删除结点的结点的父结点是删除结点的右孩子，因为我要用右子树的最小值替换删除结点
		newnode = newnodeF->lchild;	//暂时设定要替换删除的结点
		while (newnode->lchild!=NULL)
		{
			newnodeF = newnode;	//获取其父结点
			newnode = newnode->lchild;	//一直往左走，直到最后一个
		}
		delnode->data = newnode->data;	//新结点替换要删除的结点
		newnodeF->lchild = newnode->rchild;	//要替换结点的父结点的左指针指向替换结点的右指针
		free(newnode);	//释放结点
	}
	//反之则要删除的结点要么是叶子结点要么存在一个子树
	else
	{
		//如果要删除的结点左子树为空
		if (delnode->lchild!=NULL)
		{
			if (delnodeF->lchild==delnode)
			{
				delnodeF->lchild = delnode->lchild;	//左子树成为替换的结点
			}
			else
			{
				delnodeF->rchild = delnode->lchild;	//左子树成为替换的结点
			}
		}
		else
		{
			if (delnodeF->lchild == delnode)
			{
				delnodeF->lchild = delnode->rchild;	//左子树成为替换的结点
			}
			else
			{
				delnodeF->rchild = delnode->rchild;	//左子树成为替换的结点
			}
		}
		free(delnode);	//释放结点
	}
	printf("删除结点成功\n");
	return true;
}

二叉平衡树

二叉平衡树是在二叉排序树的基础上做了一些改动，这些改动确保了二叉平衡树是“平衡”的，类似于最优哈夫曼树，其规定了：树上任一结点的左子树和右子树的高度之差不超过1如下图所示：

image-20220904081205438

结点的平衡因子 = 左子树高 - 右子树高

插入操作

当我们对二叉平衡树做插入操作时，有概率将破坏平衡二叉树的平衡性，例如下图：

image-20220904083034248

我们通过对最小二叉不平衡树进行调整就可以达到二叉平衡树的结果。

根据插入位置的不同而引起的“不平衡”，可以分为：

  • LL：新元素插在了某节点左孩子的左子树中
  • RR：新元素插在了某节点右孩子的右子树中
  • LR：新元素插在了某节点左孩子的右子树中
  • RL：新元素插在了某节点右孩子的左子树中

其上各种情况的调整方法如下：

image-20220904083519069

图片来源：王道《数据结构》

我个人认为可以通过将二叉树的数据进行排序，再组织二叉平衡树的方法会更加简单，或者说有规律。

红黑树

408 难民课程（🤣）

红黑树也是一种二叉排序树的优化，它的诞生是由于对平衡二叉树的插入和删除很容易被破坏其平衡性，以至于不得不计算其平衡因子，来使其达到平衡，这样就导致了在插入和删除操作就需要耗费大量的时间开销。而对于红黑树来收，插入和删除很多时候不会破坏“红黑”特性，无需频繁调整；即使需要调整，也可以在常数级时间内完成。

红黑树的特性：

  • 左子树结点值 $\leqslant$ 根节点的值 $\leqslant$ 右子树结点值
  • 每个结点或是红色，或是黑色
  • 根节点是黑色的
  • 叶结点（外部结点，NULL结点，失败结点）均是黑色的
  • 不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色）
  • 对于每个结点，从该结点到任一叶结点的简单路径上，所含黑结点数目相同
image-20220904094302945

图片来源：王道《数据结构》

其结构体实现如下所示：

1
2
3
4
5
6
7
8
9
#define ElemType int

typedef struct RBnode {
	ElemType key;	//数据
	struct RBnode* parent;	//父结点指针
	struct RBnode* lchild;	//左孩子指针
	struct RBnode* rchild;	//右孩子指针
	int color;	//结点颜色，可用0/1标识
};
  • 结点的黑高：从某结点出发（不含）到达任一空叶结点的路径上黑结点总数

其性质：

  • 从根结点到叶结点的最长路径不大于最短路径的 2 倍
  • 有 n 个内部结点的红黑树高度 $h \leq 2 log_2{(n+1)}$

红黑树还有最要么的插入和删除操作，十分繁琐，自行百度，谷歌查询，或者参考【数据结构】红 黑 树 。

B树

B 树原理上和二叉排序树类似，例如如下图的 5 叉查找树所示：

image-20220905080219195

图片来源：王道《数据结构》

B 树，又称多路平衡查找树，与二叉平衡树不同的是，对于一棵 m 阶 B 树或者为空树，或者满足如下条件：

  • 树种每个结点最多有 m 棵子树，即至多含有 m-1 个关键字。
  • 若根结点不是终端结点，则至少有两颗子树（平衡）。
  • 除根结点外所有非叶子结点至少有 $\frac{m}{2}$ 棵子树，即至少含有 $\frac{m}{2} -1$ 个关键字（向上取整）
  • 所有叶子结点都出现在同一层上，且不携带信息（空结点，或者说失败结点）。

B+树

B+ 树类似于分块查找和 B 树的结合体，如下图所示：

image-20220905080803627

图片来源：王道《数据结构》

一颗 m 阶的 B+ 树需要满足如下条件：

  • 每个分支结点最多有 m 棵子树
  • 非叶根结点至少有两颗子树，其他分支结点至少有 $\frac{m}{2}$ 棵子树（向上取整）
  • 结点子树的个数与关键字相等
  • 所有叶结点包含全部关键字以及指向相应记录的指针，叶结点中将关键字按大小顺序排序，并且相邻叶结点按大小顺序相互连接起来

散列查找

散列表（Hash Table），又称哈希表。其特点是：数据元素关键字与其存储地址直接相关。即通过一个散列函数，将关键字输入，输出其存储地址。

如果不同关键字，通过散列函数映射到了同一个存储地址，则将这些关键字称为“同义词”。

其存储地址已经有其他“同义词”存储了，这个情况称为“冲突”。

处理冲突的方法

拉链法

解决冲突的方法之一——拉链法。如下图所示，通过取余将数据映射在一个数组范围，而数组通过指针来存储数据，这样发生冲突后，将其链接下去即可。

image-20220905082508256

图片来源：王道《数据结构》

开放定址法

开放定址法是指可存放新关键字的空闲地址向它的同义词表项开放，也向非同义词表项开放。

需要注意的是：使用开放定址法做删除操作的时候，需要进行逻辑上的删除，而不是物理上的删除

线性探测法

即发生冲突时，每次往后探测相邻的下一个单元是否为空。

如下图所示，如果散列映射出现冲突了，则向下寻找空位存放

image-20220905084659096

线性探测法很容易造成同义词，非同义词“聚集（堆积）”现象，严重影响查找效率。

平方探测法

即当发生冲突的时候，每次寻址存放的时候按照：$d_i = 0^2,1^2,-1^2,2^2,-2^2…$ 方式寻址存放。

image-20220905085308600

伪随机序列法

即发生冲突的时候，使用伪随机序列进行寻址存放。

再散列法

即如果发生冲突，则对散列值进行二次散列计算，直到不冲突为止。

常用散列函数

除留余数法

即对关键字做取模运算，例如：$H(key) = key , % ,p$ 。要求是：

  • 散列表长度为 m ，则取一个不大于 m 但是最接近或者等于 m 的质数 p。

直接定址法

即直接使用关键字定位存储地址，或者对关键字做线性函数处理再定位存储地址。例如：**$H(key) = key$ 或者 $H(key) = a \times key + b$** 。

它适合关键字分布基本连续的情况。

数字分析法

即在关键字中选取数码分布比较均匀的若干位作为散列地址。例如，在记录手机号的散列映射的时候，大部分的手机号的开头都是不尽相似的，178，176等，这个时候如果选取开头的数码作为散列映射，则会出现大量的映射在同一个存储地址内，这个时候我们可以选择手机号的后四位来映射，会相对映射的均匀一些。

平方取中法

取关键字的平方值的中间几位作为散列地址。

这种方法得到的散列地址与关键字每位都有关系，因此其分布比较均匀，适用于关键字每位取值不够均匀或者小于散列地址所需的位数。

End

快要结束啦，就剩下排序啦！

image-20220905085637169