【学习笔记】数据结构（九）

查找

简述

查找表(Search Table) 是由同一类型的数据元素（或记录）构成的集合。

对查找表经常进行的操作有：

• (1)查询某个“特定的“数据元素是否在查找表中；

• (2)检索 某个“特定的“数据元素的各种属性;

• (3)在查找表中插入一个数据元素；

• (4)从查找表中删去 某个数据元素。

只作前两种统称为“查找＂的操作，则称此类查找表为静态查找表(Static Search Table) 。

在查找过程中同时插入查找表中不存在的数据元素，或者从查 找表中删除已存在的某个数据元素，则称此类表为动态查找表(Dynamic Search Table)。

关键字(Key) 是数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数 据元素（或记录）

​ ·若此关键字可以惟一地标识一个记录，则称此关键字为主关键字 (Primary Key) (对不同的记录，其主关键字均不同）

​ 称用以识别若干记录的关键 字为次关键字(Secondary Key)

​ 例如，在一个学生信息表中，主关键字可能是学生的学号，而次关键字可以是学生的姓名或班级。

查找(Searching) 根据给定的某个值，在查找表中确定一个其关键字等于给定值的 记录或数据元素。

若查找表中存在这样一个记录，则称 “查找成功”
查找结果给出整个记录的信息，或指示该记录在查找表中的位置
否则称 “ 查找不成功”
查找结果给出“空记录”或“空指针”

查找算法的评价指标：关键字的平均比较次数也称平均查找长度ASL(Average Search Length)
$$\begin{gathered} ASL=\sum _{i=1}^n{p}_i{c}_i(关键字比较次数的期望值) \\ n:记录的个数 \\ {p}_i:查找第i个记录的概率(通常认为p_i=1/n) \\ i:找到第i个记录所需的比较次数 \end{gathered}$$

9.1 静态查找表

9.1.1 顺序表的查找 - 线性查找

以顺序表或线性链表表示，且表内元素之间无序

// ------－静态查找表的顺序存储结构-------
typedef int KeyType;

typedef struct {
	KeyType key; //关键字域
	... //其他域
}ElemType;

typedef struct {
	ElemType* elem; //表基址
	int length; //表长
}SSTable;  //Sequential Search Table

顺序查找(Sequential Search) 的查找过程为：

从表中最后一个记录开始，逐个进行记 录的关键字和给定值的比较，

• 若某个记录的关键字和给定值比较相等，则查找成功，找到 所查记录；

• 反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查 记录，查找不成功。

改进：

​ 查找之前先对ST.elem[0]的关键字赋值 key, 目的在于免去查找过程中每一步都要检测 整个表是否查找完毕

#define _CRT_SECURE_NO_WARNINGS *1
#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;

typedef struct {
	KeyType key; //关键字域
}ElemType;

typedef struct {
	ElemType* elem; //表基址
	int length; //表长
}SSTable;  //Sequential Search Table

int Search_Seq_old(SSTable ST, KeyType key)
{
	int i;
	for (i = ST.length; ST.elem[i].key != key && i > 0; --i);  //做两次比较
	if (i > 0) {
		return i;
	}
	else
	{
		return 0;
	}
}

int Search_Seq(SSTable ST, KeyType key)
{
	ST.elem[0].key = key;  //哨兵
	int i;
	for (i = ST.length; ST.elem[i].key != key; --i); //做一次比较
	return i;
}

int main() {
	SSTable ST;
	int elem[12] = { 0,5,7,19,21,13,56,64,92,88,80,75 };
	ST.elem = elem;
	ST.length = 12;
	int index = Search_Seq(ST, 60);
	printf("60-index：%d\n", index);
	int index0 = Search_Seq_old(ST, 60);
	printf("60-index_old：%d\n", index);


	int index1 = Search_Seq(ST, 88);
	printf("88-index：%d\n", index1);
	int index2 = Search_Seq_old(ST, 88);
	printf("88-index_old：%d", index2);
	return 0;
}

时间效率：O(n)

​ 比较次数与key位置有关

​ 查找第i个元素，需要比较 n-i+1 次

​ 查找失败，需比较 n+1 次

​ $$ASL=\frac{1}{n}\sum _{i=1}^n(n-i+1)=\frac{n+1}{2}$$

空间复杂度：O(1)

1、查找概率不相等时如何提高查找效率?

​ 查找表存储记录原则 – 按查找概率高低存储，使表中记录按查找概率由小至大重新排列。

​ 1)查找概率越高，比较次数越少;

​ 2)查找概率越低，比较次数较多。

2、查找概率无法测定时如何提高查找效率?

​ 方法 – 按查找概率动态调整记录顺序:

​ 1)在每个记录中设一个访问频度域,

​ 2)始终保持记录按访问频度非递减有序的次序排列;

​ （使得查找概率大的记录在查找过程中不断往后移，以便在以后的逐次查找中减少比较次数）

​ 3)每次查找后均将刚查到的记最直接移至表尾

优缺点：

​ 优点: 算法简单，逻辑次序无要求，且不同存储结构均适用。

​ 缺点: ASL太长，时间效率太低。

9.1.2 有序表的查找 - 折半查找/二分查找

(非递归)算法步骤：

• 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点，key为给定的要查找的值；
• 初始时，令low=1，high=n，mid=⌊(low+high)/2⌋
• 让k与mid指向的记录比较:
  • 若key==R[mid].key，查找成功
  • 若key<R[mid].key，则 high=mid-1
  • 若key>R[mid].key，则low=mid+1
• 重复上述操作，直至low>high时，查找失败

#define _CRT_SECURE_NO_WARNINGS *1
#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;

typedef struct {
	KeyType key; //关键字域
}ElemType;

typedef struct {
	ElemType* elem; //表基址
	int length; //表长
}SSTable;  //Sequential Search Table

int Search_Bin(SSTable ST, KeyType key)
{
	// 初始化 - 坐标从0开始
	int low = 0;
	int high = ST.length - 1;
	//判断
	while (low <= high) {
		int mid = (low + high) / 2;
		if (ST.elem[mid].key == key) return mid;
		else  //缩小查找范围
		{
			if (key < ST.elem[mid].key) {
				high = mid - 1; //前半区查找
			}
			else
			{
				low = mid + 1; //后半区查找
			}
		}
	}
	return -1; //不存在
}
int main() {
	SSTable ST;
	int elem[11] = { 5,13,19,21,37,56,64,75,80,88,92 };
	ST.elem = elem;
	ST.length = 11;
	int index = Search_Bin(ST, 21);
	printf("21-index：%d\n", index);


	int index1 = Search_Bin(ST, 63);
	printf("63-index：%d\n", index1);
	return 0;
}

递归算法：

#define _CRT_SECURE_NO_WARNINGS *1
#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;

typedef struct {
	KeyType key; //关键字域
}ElemType;

typedef struct {
	ElemType* elem; //表基址
	int length; //表长
}SSTable;  //Sequential Search Table

int Search_Bin(SSTable ST, KeyType key, int low, int high)
{
	if (low > high) return -1;
	int mid = (low + high) / 2;
	if (key == ST.elem[mid].key) return mid;
	else
	{
		if (key < ST.elem[mid].key) {
			high = mid - 1; //前半区查找
			Search_Bin(ST, key, low, high);
		}
		else
		{
			low = mid + 1; //后半区查找
			Search_Bin(ST, key, low, high);
		}
	}
}
int main() {
	SSTable ST;
	int elem[11] = { 5,13,19,21,37,56,64,75,80,88,92 };
	ST.elem = elem;
	ST.length = 11;
	int low = 0;
	int high = ST.length - 1;
	int index = Search_Bin(ST, 21, low, high);
	printf("21-index：%d\n", index);


	int index1 = Search_Bin(ST, 63, low, high);
	printf("63-index：%d\n", index1);
	return 0;
}

优缺点：

​ 折半查找优点:效率比顺序查找高。

​ 折半查找缺点:只适用于有序表，且限于顺序存储结构(对线性链表无效)

9.1.3 静态树表的查找

针对有序表中各记录的查找概率不等

使查找性能达最佳的判定树是其带权内路径长度 之和PH值 $$PH=\sum _{i=1}^n(w_i{h}_i)$$取最小值的二叉树为静态最优查找树(Static Optimal Search Tree)

• n为二叉树上结点的个数（即有序表的长度）；
• h_i为第i 个结点 在二叉树上的层次数；
• 结点的权w_i=cp_i(i=1, 2, …, n), 其中 p_i为结点的查找概率，c 为 某个常量。

使这棵二叉树的带权内路径长度PH值在所有具有同样权值的二叉树中近似为最小，称这类二叉树为次优查找树(Nearly Optimal Search Tree)

次优查找树和最优查找树的查找性能之差仅为1%~2%,很少超过3%,而且构造次优查找树的算法的时间复杂度为O(nlogn)

方法：

• 取第i个记录构造根节点 r_i （l ≤ i ≤h）
• $$\Delta P_i=|\sum _{j=i+1}^h{w}_j-\sum _{j=l}^{i-1}{w}_j|$$ (左子树和右子树的权值之差) ； 取最小值 —— $$\Delta P_i=min\Delta P_j,l\le i\le h$$
• 分别对子序列{r_l,r_l+1•…, r_i-1} 和{r_i+1 , ···, r_h} 构造两棵次优查找树，并分别设为根结点r_i的左子树和右子树
• 

例子：

#define _CRT_SECURE_NO_WARNINGS *1
#include <stdio.h>
#include <stdlib.h>

typedef char KeyType;

typedef struct {
	KeyType key; //关键字域
	int weight;
}ElemType;

typedef struct {
	ElemType* elem; //表基址
	int length; //表长
}SSTable;  //Sequential Search Table

typedef struct BiTNode {
	ElemType data;
	struct BiTNode* lchild, * rchild; //左孩子、右孩子指针
}BiTNode, * BiTree;

typedef BiTree SOSTree; // 次优查找树采用二叉链表的存储结构

void FindSW(int sw[], SSTable ST) {
	int i;
	int sum = 0;
	for (i = 0; i < ST.length; i++)
	{
		sum += ST.elem[i].weight;
		sw[i] = sum;
	}
}

void SecondOptimal(SOSTree* T, ElemType R[], int sw[], int low, int high)
{
	int i = low;
	int min = abs(sw[high] - sw[low]);
	int dw = sw[high] + sw[low - 1];
	int j;
	//选择最小的ΔPi - 根
	for (j = 0; j <= high; ++j)
	{
		if (abs(dw - sw[j] - sw[j - 1]) < min)
		{
			i = j;
			min = abs(dw - sw[j] - sw[j - 1]);
		}
	}
	*T = (SOSTree)malloc(sizeof(BiTNode));
	if (*T != NULL)
	{
		(*T)->data = R[i]; // 生成结点
		if (i == low) {
			(*T)->lchild = NULL; //左子树结点
		}
		else {
			SecondOptimal(&((*T)->lchild), R, sw, low, i - 1); //构造左子树
		}
		if (i == high) {
			(*T)->rchild = NULL; //右子树结点
		}
		else {
			SecondOptimal(&((*T)->rchild), R, sw, i + 1, high);//构造右子树
		}
	}	
}

//中序
void Print_Tree(SOSTree T)
{
	if (T)
	{
		Print_Tree(T->lchild);
		printf("%c  ", T->data.key);
		Print_Tree(T->rchild);
	}
}

void CreateSOSTree(SOSTree* T, SSTable ST)
{
	if (ST.length == 0) T = NULL;
	else
	{
		int sw[10];
		FindSW(sw, ST); // 按照由有序表 ST 中各数据元素的 weig址域求累计权值表 sw
		SecondOptimal(T, ST.elem, sw, 1, ST.length - 1);
		/*for (int i = 0; i < 10; i++)
		{
			printf("%d ", sw[i]);
		}*/
	}
}


int main() {
	SSTable ST;
	char e[10] = { ' ', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'};
	int w[10] = { 0,1,1,2,5,3,4,4,3,5 };
	ElemType elem[10];
	int i;
	for (i = 0; i < 10; i++)
	{
		elem[i].key = e[i];
		elem[i].weight = w[i];
	}
	ST.elem = elem;
	ST.length = 10;
	SOSTree* T = NULL;
	CreateSOSTree(&T, ST);
	Print_Tree(T);
	return 0;
}

9.1.4 索引顺序表的查找 - 分块查找

条件：

​ 1、将表分成几块，且表或者有序，或者分块有序(块间有序，块内无序)

​ 若i < j， 则第 j 块中所有记录的关键字均大于第 i 块中的最大关键字。

​ 2、建立“索引表”(每个结点含有最大关键字域和指向本块第一个结点的指针，且按关键字有序)。

​

优缺点：

优点: 插入和删除比较容易，无需进行大量移动。

缺点: 要增加一索引表的存储空间并对初始索引表进行排序运算。

适用情况: 如果线性表既要快速查找又经常动态变化，则可采用分块查找。

9.2 动态查找表

9.2.1 二叉排序树和平衡二叉树

参考： 树和二叉树（一）

二叉排序树(Binary Sort Tree) 或者是一棵空树；或者是具有下列性质的二叉树：

​ (1) 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

​ (2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

​ (3)它的左、右子树也分别为二叉排序树。

**性质：**中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。

查找 - 递归算法：

​ (1)若二叉排序树为空，则查找失败，返回空指针。
​ (2)若二叉排序树非空，将给定值key与根结点的data比较：
​ ① 若key等于T->data，则查找成功，返回根结点地址
​ ② 若key小于T->data，则进一步查找左子树;
​ ③ 若key大于T->data，则进一步査找右子树。

插入节点 - 算法:

• 若二叉排序树为空，则插入结点作为根结点插入到空树中

• 否则，继续在其左、右子树上查找

  • 树中已有，不再插入

  • 树中没有，查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子

• 插入元素一定在叶结点上，不同插入次序的序列生成不同形态的二叉排序树

删除节点 - 算法：

• 被删除的结点是叶子结点：直接删去该结点；

• 被删除的结点只有左子树或者只有右子树：用其左子树或者右子树替换它(结点替换)；

• 被删除的结点既有左子树，也有右子树

  • 以其中序前驱值替换之(值替换)，然后再删除该前驱结点。前驱是左子树中最大的结点。

    

  • 以其中序后继替换之，然后再删除该后继结点。后继是右子树中最小的结点。

    

平衡二叉树(balanced binary tree)：又称AVL树(Adelson-Velskii and Landis)。
一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：
① 左子树与右子树的高度之差的绝对值小于等于1;
② 左子树和右子树也是平衡二叉排序树。

平衡因子(BF) = 结点左子树的高度-结点右子树的高度

LL型调整算法：

• B结点带左子树一起上升
• A结点成为B的右孩子
• 原来B结点的右子树作为A的左子树

RR型调整算法：

• B结点带右子树一起上升
• A结点成为B的左孩子
• 原来B结点的左子树作为A的右子树

LR型调整算法：

• C结点穿过A、B结点上升
• B结点成为C的左孩子
• A结点成为C的右孩子
• 原来C结点的左子树作为B的右子树
• 原来C结点的右子树作为A的左子树

RL型调整算法：

• C结点穿过A、B结点上升
• A结点成为C的左孩子
• B结点成为C的右孩子
• 原来C结点的左子树作为A的右子树
• 原来C结点的右子树作为B的左子树

9.2.2 B树和B+树

B树 是一种平衡的多路查找树;

特点：

• 平衡：所有的叶结点都在同一层

• 有序：结点内有序，任一元素的左子树都小于它，右子树都大于它

• 多路：（元素比分支小1个）

  ​ 最多：m个分支，m-1个元素

  ​ 最少：根节点：2个分支， 1个元素

  ​ 其他节点：⌈m/2⌉个分支，⌈m/2⌉-1个元素

  例如：5阶B树 - 最多5个分支，4个元素 / 最少3个分支，2个元素

查找： 和二叉搜索树类似

访问结点是在硬盘上进行的; 结点内的查找是在内存中进行的

• 判断B树是否为空
  • 空 - 查找失败
  • 非空
    • 从根节点开始，比较查询的关键字与节点中的关键字，
    • 如果相等则查找成功；
    • 如果关键字小于当前节点的关键字，则进入左子树；
    • 如果关键字大于当前节点的关键字，则进入右子树；
    • 直到叶子节点没有找到，则查找失败

结点内有多个元素，要依次对每个元素进行比较，元素比查找值小就继续往后比，直到比到第一个比查找值大的元素并进入这个元素的左子树，要不比到该节点最后元素并进入到这个元素的右子树

插入：

• 先查找到插入的位置进行插入
  • 插入关键字后该结点的关键字数小于等于 m - 1，没有上溢出,无需调整。
  • 插入关键字后该结点的关键字数等于m，则应该进行分裂操作，分裂操作如下：【中间元素上移，两边分裂，分裂时连带子树】
    • 生成一个新结点，找到中间元素（⌈m/2⌉）分为两部分。
    • 前半部分留在旧结点中，后半部分复制到新结点中。
    • 中间元素连同新结点的存储位置插入到父结点中，如果插入后父结点的关键字个数也超过了m-1，则继续分裂，直到没有上溢出为止。

删除：

• 删除非叶节点元素最终都转换成删除叶节点元素
• 删除叶节点元素
  • 没有下溢出 - 无需调整
  • 下溢出
    • 左右兄弟够借 ： 借 - 父下来，兄上去
    • 左右兄弟不够借 ：合并 - 父下移到左再合并 （可能导致父结点下溢出，继续判断其左右兄弟够不够借，直到不下溢出为止）

B+树

• B+树是一套多级索引结构
• 叶结点层包含所有元素,从小到大链接起来，所有关键字只出现在叶子节点的链表中
• m个分支的结点有m个元素
• 非叶结点上的每个元素都是它子结点的最大值，非叶子节点只存储索引，不存储数据

B+树常被用做数据库中的索引结构：

叶结点每个元素都包含指向对应记录存储地址的指针，此时结点内的元素又被称作关键字（key）, 通过关键字包含的指针，可以索引到数据库中的某一条记录

顺序查找关键字：遍历链表一样

随机查找关键字：通过非叶节点可以快速定位到叶节点，最后一定落在叶节点上，因为只有叶结点层的关键字能索引到对应的记录，如果在非叶节点上遇到相同关键字还需要继续往下查找，直到叶节点层

范围查找关键字 A~B：结合顺序和随机——先通过随机查找大于等于A值的叶节点，然后顺序查找在A~B范围的所有叶节点

B树和B+树对比

• B树所有结点的关键字都有直接指向对应记录的指针
• B树中m个分支有m-1个关键字
• 没有链表结构
• B树顺序查找或范围查找只能中序遍历,效率低

• B+树叶结点包含全部关键字及指向相应记录的指针，非叶结点只作索引
• B+树中m个分支有m个关键字
• 叶子节点之间通过链表连接，便于范围查找
• B+树兼顾顺序查找和随机查找，还可方便地进行范围查找

9.2.3 键树

键树又称数字查找树(Digital Search Trees) 。它是一棵度≥2 的树，树中的每个结点 中不是包含一个或几个关键字，而是只含有组成关键字的符号。例如，若关键字是数值， 则结点中只包含一个数位；若关键字是单词，则结点中只包含一个字母字符。

从根到叶子结点路径中结点的字符组成的字符串表示一个关键字，叶子结点中的特殊符号＄表示字符串的结束。在叶子结点还含 有指向该关键字记录的指针。为了查找和插入方便，约定键树是有序树，即同一层中兄弟结点之间依所含符号 自左至右有序．并约定结束符＄小于任何字符。

键树有两种存储结构

1、双链树

以树的孩子兄弟链表来表示键树，则每个分支结点包括三个域：

• symbol 域：存储关键字的一个字符；

• first 域：存储指向第一棵子树根的指针；

• next 域：存储指向右兄弟的指针

  同时，叶子结点不含first域，它的infoptr成存储指向该关键字记录的指针。

​

#define MAXKEYLEN 16 // 关键字的最大长度
typedef struct {
	char ch[MAXKEYLEN]; // 关键字
	int num; // 关键字长度
}KeysType; // 关键字类型
typedef struct Record // 记录类型
{
	KeysType key; // 关键字
}Record;
typedef enum { LEAF, BRANCH } NodeKind; // 结点种类：{叶子，分支}
typedef struct DLTNode {
	char symbol;
	struct DLTNode* next;	// 指向兄弟结点的指针
	NodeKind kind;
	union {
		Record* infoptr;	// 叶子结点内的记录指针
		struct DLTNode* first;	// 分支节点内的孩子链指针
	};
}DLTNode, * DLTree;	// 双链树的类型

查找

• 关键字长度为num，待查关键字中 num-1 个字符，$为1 个字符；那么 K. ch(0… num-1), 其中 K. ch[0]至 K. ch [num-2]表示待查关键字中 num-1 个字符，K. ch[num-1]为结束符＄

• 算法思路：从双链树的根指针出发，顺 first 指针找到第一棵子树的根结点，以 K. ch[0]和此结点的 symbol 域比较，若相等，则顺 first 域再比较下一字符，否则沿 next 域顺序查找。若直至“空”仍比较不等，则查找不成功。

  Record* SearchDLTree(DLTree T, KeysType K) {
  	// 在非空双链树T中查找关键字等于k的记录，若存在，则返回指向该记录的指针，否则返回空/指针
  	//-----初始化-----
  	DLTNode* p = T->first; //从双链树的根指针出发，顺 first 指针找到第一棵子树的根结点
  	int i = 0;
      //-----kai's比较----
  	while (p && i < K.num) {
  		//以 K.ch[i]和此结点的 symbol 域比较，不等，沿 next 域顺序查找
  		while (p && p->symbol != K.ch[i]) p = p->next;
  		//相等，则顺 first 域再比较下一字符
  		if (p && i < K.num - 1) p = p->first;
  		++i;
  	}
  	//查找结束
  	if (!p) return NULL;  //直至“空”仍比较不等，则查找不成功
  	else return p->infoptr; //p不为空，查找成功
  }
  

2、Trie 树

树的每个结点中应含有d个指针域, 在 Trie树 中有两种结点：

• 分支结点 - 含有 d个指针域和一个指示该结点中非空指针域的个数的整数域

• 叶子结点 - 含有关键字域和指向记录的指针域

#define MAXKEYLEN 16 // 关键字的最大长度
typedef struct {
	char ch[MAXKEYLEN]; // 关键字
	int num; // 关键字长度
}KeysType; // 关键字类型
typedef struct Record // 记录类型
{
	KeysType key; // 关键字
}Record;
typedef enum { LEAF, BRANCH } NodeKind; // 结点种类：{叶子，分支}
typedef struct TrieNode
{
    NodeKind kind;
    union
    {
        struct { KeysType K; Record* infoptr; }lf; //Leaf Node - 叶子结点 
        struct { struct TrieNode* ptr[27]; int num; }bh; //Branch Node - 分支结点
    };
}TrieNode, * TrieTree;

查找：

• 从根结点出发，沿和给定值相应的指针逐层向下，直 至叶子结点，若叶子结点中的关键字和给定值相等，则查找成功，若分支结点中和给定值相应的指针为空，或叶结点中的关键字和给定值不相等，则查找不成功。

int KeysTypeCompare(KeysType k1, KeysType k2) {
    if (k1.num != k2.num) return 0;
    for (int i = 0; i < k1.num; i++) {
        if (k1.ch[i] != k2.ch[i]) return 0;
    }
    return 1;
}

Record* SearchTrie(TrieTree T, KeysType K)
{
    TrieNode* p = T; // 从 Trie 树的根节点开始
    int i = 0;      // 初始化关键字索引
    // 循环条件：当前节点不为空，节点类型为分支，且索引小于关键字长度
    while (p != NULL && p->kind == BRANCH && i < K.num) {
        // 计算当前字符对应的索引，假设字符是小写字母
        int index = (K.ch[i] == '$') ? 0 : (K.ch[i] - 'a' + 1);

        // 移动到分支节点的下一个子节点
        p = p->bh.ptr[index];

        // 移动到关键字的下一个字符
        i++;
    }
    if (p && p->kind == LEAF && KeysTypeCompare(p->lf.K, K))
    {
        return p->lf.infoptr;
    }
    else
    {
        return NULL;
    }
}

若键树中结点的度较大，则采用 Trie树结构较双链树更为合适。

9.3 哈希表

9.3.1 什么是哈希表

• 哈希/散列：在记录的 存储位置和它的关键字之间建立一个确定的对应关系 f,使每个关键字和结构中一个惟 一的存储位置相对应，称这个对应关系 f为哈希(Hash)函数。

• 对不同的关键字可能得到同一哈希地址，即 key₁ ≠ key₂ , 而 f(key₁) = f(key₂), 这种现象称冲突(collision) 。

• 同义词: 具有相同函数值的多个关键字

• 哈希表：根据设定的「哈希函数（散列函数） Hash(key) 」和处理冲突的方法将「键 key 」计算出对应的「关键码值 Key Value」，把关键码值映射到表中一个位置来访问记录。存放记录的数组叫做**「哈希表（散列表）」，这一映像过程称为「哈希造表或散列」，所得 存储位置称「哈希地址或散列地址」**。

• 优点： 查找效率高——查找的时间复杂度为O(1)。
  缺点： 空间效率低

• 使用哈希表要解决好两个问题:

  • 构造好的哈希函数
    (a) 所选函数尽可能简单，以便提高转换速度;
    (b) 所选函数对关键码计算出的地址，应在散列地址集中致均匀分布，以减少空间浪费。
  • 制定一个好的解决冲突的方案
    查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。

9.3.2 哈希函数的构造方法

常用的构造哈希函数的方法有：

1. 直接定址法

   取 关键字或关键字的某个线性函数值 为哈希地址。即：H(key) =key 或 H(key)=a• key+b 其中a 和b为常数

   直接定址所得地址集合和关键字集合的大小相同。因此，对于不同的关键字不 会发生冲突。要占用连续地址空间，空间效率低。

   例如：H(key) =key - 年龄作为关键字

   关键字 - 年龄	哈希值	信息
   ……	……	…….
   1	01	…….
   2	02	…….
   ……	……	…….
   10	10	…….
   ……	…….	……

   例如：H(key) =key + (-1948) - 年份作为关键字

   关键字 - 年份	哈希值	信息
   ……	……	…….
   1949	01	…….
   1950	02	…….
   ……	……	…….
   1958	10	…….
   ……	…….	……

2. 数字分析法

   选择 关键字的某些位数作为映射 的位置。常见的选择包括关键字的最高位、最低位、中间位或者特定的位数组合

   例如：

   关键字	哈希值	员工信息
   ……	……	…….
   010020093	0093	…….
   010020094	0094	…….
   010130095	0095	…….
   010250096	0096	…….
   ……	…….	……

3. 平方取中法

   一种比较常用的哈希函数构造方法，这个方法是 先取关键字的平方，然后再根据可使用空间的大小，选取平方数的中间几位 作为哈希地址。取的位数由表长决定。一般适用于不了解关键字分布而关键字位数又不是很多的情况。

   关键字	关键字的平方	哈希函数值
   1234	1522756	227
   2143	4592449	924
   4132	17073424	734
   3214	10329796	297

4. 折叠法

   将 关键字分割成位数相同的几部分 （最后一部分的位数可以不同），然后取这几位的叠加和（舍去进位）作为哈希地址。这种方法适用于关键字位数较多，而且关键字中每一位上数字分布大致均匀的情况。

   • 移位叠加是将分割后每一部分的最低位对齐，然后相加；
   • 边界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。

   如国际标准图书编号0-442-20586-4,它是一个10位的十进制 数字，当馆藏书种类不到10000时，可采用折叠法构 造一个四位数的哈希函数。

   

5. 除留余数法（常用）

   取 关键字被某个不大于哈希表表长m的数p除后所得余数 为哈希地址。H(key) = key MOD p, p ≤ m

   由众人的经验得知：一般情况下，可以选p为质数或不包含小于20 的质因数的合数。

   质数

   质数是只有两个正因数（1和它本身）的自然数，例如2、3、5、7、11等。

   不包含小于20的质因数的合数

   合数是指除了1和它本身之外还有其他正因数的自然数。不包含小于20的质因数意味着这个合数不能被2、3、5、7、11、13、17、19这些质数整除。

   举个例子

   1. 选择质数 p：
      • 比如 p=23，它是一个质数，因为它只有1和23两个正因数。
   2. 选择不包含小于20的质因数的合数 p：
      • 假设 p=529，它是一个合数，因为它可以被23整除（23×23=529），它不包含小于20的质因数

6. 随机数法

   选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 H(key) = random (key), 其中 random 为随机函数。通常，当关键字长度不等时采用此法构造哈希函数较恰当。

采用不同的哈希函数主要考虑的因素有：

​ (1) 计算哈希函数所需时间（包括硬件指令的因素）；

​ (2) 关键字的长度；

​ (3) 哈希表的大小；

​ (4) 关键字的分布情况；

​ (5) 记录的查找频率。

9.3.3 处理冲突的方法

一旦冲突，就找下一个地址，直到找到空地址存入

1. 开放定址法

   基本函数是：
   $$\begin{gathered} H_i(key)=(Hash(key)+d_i)MODm, \\ i=1,2,\dots ,k(k\le m-1)， \end{gathered}$$
   其中： Hash(key) 为哈希函数； m 为哈希表表长； d_i为增量序列

   在开放寻址法中，有几种常见的探测方式，用于确定下一个位置：

   • 线性探测再散列（Linear Probing）

     d_i = 1,2,3, …, m-1 线性序列

   • 二次探测再散列（Quadratic Probing）

     d_i = 1², -1², 2², -2², 3³,……, ±k² ( k ≤ m/2) 二次序列

   • 伪随机探测再散列

     d_i = 伪随机数序列

2. 再哈希法

   同时构造多个不同的哈希函数，发生哈希冲突时就使用第二个、第三个……等其他的哈希函数计算地址，直到不发生冲突为止。虽然不易发生聚集，但是增加了计算时间。

3. 链地址法

   将所有关键字为同义词的记录存储在同一线性链表中。

   m个散列地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。

   ​

   链地址法的优点:

   • 非同义词不会冲突，无“聚集”现象

   • 链表上结点空间动态申请，更适合于表长不确定的情况

4. 建立一个公共溢出区

   将哈希表分为基本表和溢出表，将发生冲突的都存放在溢出表中。

9.3.4 哈希表的查找及其分析

哈希表的查找效率分析

使用平均查找长度ASL来衡量查找算法，ASL取决于：

• 哈希函数

• 处理冲突的方法

• 哈希表的装填因子α： α 越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比较次数就越多。
  $$\alpha =\frac{表中填入的记录数}{哈希表的长度}$$

$$\begin{gathered} 链地址法：ASL\approx 1+\frac{\alpha }{2} \\ 线性探测法：ASL\approx \frac{1}{2}(1+\frac{1}{1-\alpha }) \\ 随机探测法：ASL\approx -\frac{1}{\alpha }ln(1-\alpha ) \end{gathered}$$

// ------------ 线性探测法 ------------
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#define NIL 0
typedef struct {
	int* Table;//储存哈希节点的数组基地址
	int size;//哈希表长度
}HashTable;
//初始化哈希表
HashTable* InitHashTabel(int size) {
	HashTable* H = malloc(sizeof(HashTable));
	H->size = size;
	H->Table = (int*)malloc(sizeof(int) * size);
	//将所以槽位初始化为空闲状态
	while (size > 0) H->Table[--size] = NIL;
	return H;
}
//哈希函数
int Hash(int data, int size) {
	return data % size;//除留余数法
}
//线性探测法解决哈希冲突
int LinearProbe(HashTable* H, int data, int* count) {
	int Pos = Hash(data, H->size);//通过哈希函数计算得到其哈希地址
	(*count) += 1;
	//若当前位置被占用
	while (H->Table[Pos] != NIL) {
		(*count) += 1;
		//若已存在当前键
		if (H->Table[Pos] == data) {
			return Pos;//返回其位置
		}
		Pos = (Pos + 1) % H->size;//线性探测下一个槽位
	}
	return Pos;//返回空闲位置
}
//插入哈希节点
int Insert(HashTable* H, int key, int* count) {
	int Pos = LinearProbe(H, key, count);//获取该关键字应所在位置
	//判断该关键字是否在哈希表中
	if (H->Table[Pos] != key) {
		H->Table[Pos] = key;
		return 1;//插入成功
	}
	return 0;//插入失败
}
//查询哈希节点
int Search(HashTable* H, int key) {
	//线性探测查找key是否在哈希表中
	int count = 0;
	int Pos = LinearProbe(H, key, &count);
	if (H->Table[Pos] != NIL)
		return Pos;
	return -1;//所查元素不存在
}
//删除哈希节点
int Delete(HashTable* H, int key) {
	int Pos = Search(H, key);//查找该关键字
	if (Pos != -1) {
		H->Table[Pos] = NIL;//直接将槽位置空
		return 1;//删除成功，返回1
	}
	return 0;//删除失败，返回0
}
//打印哈希表节点
void print(HashTable* H) {
	for (int i = 0; i < H->size; i++) {
		if (H->Table[i] == NIL)
			printf("NIL  ");
		else  printf("%d  ", H->Table[i]);
	}
}
int main() {
	HashTable* H = InitHashTabel(13);
	int value[12] = { 19, 14, 23, 1,68, 20, 84, 27, 55, 11, 10, 79 };
	printf("插入元素19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79:\n");
	int i;
	for (i = 0; i < 12; i++)
	{
		int count = 0;
		Insert(H, value[i], &count);
		printf("%2d 比较次数： %d\n", value[i], count);
	}
	print(H);
	printf("\n-----删除23-----\n");
	Delete(H, 23);
	print(H);
	printf("\n------查询------\n");
	int pos = Search(H, 23);
	printf("23的位置：%d", pos);
	int pos1 = Search(H, 14);
	printf("\n14的位置：%d\n", pos1);
}

参考：

教材：严蔚敏《数据结构》（C语言版）.pdf

视频：

数据结构与算法基础（青岛大学-王卓）

B树(B-树)

代码：

哈希查找详解

博客：

键树