数据结构——查找

查找基本概念

查找表：由同一类型的数据元素构成的集合
关键字：数据元素中某个数据项的值，用它可以标识一个数据元素。若这个标识唯一，则此关键字为主关键字；否则为次关键字
查找：根据给定记录，若记录存在则查找成功，否则查找失败
动态查找表和静态查找表：在查找同时做插入删除等操作则为动态，否则为静态
平均查找长度(ASL)：

注：P为每个数据元素的查找概率，C为查找到该数据元素时的查找次数

线性表查找

顺序查找

从1开始，0是不使用的。

第一个算法每次循环都要判断是否i>=1，而第二个设置监视哨来解决这个问题，如果没有找到key，i就会直接返回0，简化程序。

//顺序表
typedef struct
{KeyType key;//关键字InfoType otherinfo;//其他数据
}ElemType;//每个节点的数据域类型typedef struct
{ElemType* R;//存储空间基地址int length;//当前长度
}SSTable;//顺序查找
int Search_Seq(SSTable ST, KeyType key)
{for(int i = ST.length; i >= 1; --i)if(ST.R[i].key = key) return i;//从后往前找return 0;//找不到返回0
}//设置监视哨的顺序查找
int Search_Seq(SSTable ST, KeyType key)
{ST.R[0].key = key;//监视哨int i;for (i = ST.length; ST.R[i].key != key; --i);//从后往前找return i;
}

折半查找/二分查找

它是一种效率较高的查找方法，但是有两个要求：

1.必须为顺序存储（顺序表、链表就不行）

2.必须为有序的（从小到大/从大到小）
查找过程：从表中间开始，如果给定值与中间记录关键字相等，则查找成功；如果给定值大于中间记录关键字，往右重复前面步骤（表中间变为右半部分中间）；如果给定值小于中间记录关键字，往左重复前面步骤（表中间变为左半部分中间），以此重复直至查找完成
low（left）标志查找区间下界，high（right）标志查找区间上界，mid标志查找区间中间位置

/*算法步骤：1. 置查找区间初值，low为1，high为表长2. 当low <= high（此处不可以为low<high，因为当两个等于时，查找还有最后一个节点需要比较）时，循环以下操作：·mid取low和high的中间值（如果(low+high)/2为小数，则向下取整）·将给定值key与中间位置记录的关键字进行比较，若相等则查找成功，返回mid·若不相等则利用中间位置记录将表对半分为前后两个子表。若key比中间位置记录的关键字小，则high取mid-1，否则low取mid+13. 循环结束，若查找区间为空，则查找失败，返回0
*/int Search_Bin(SSTable ST, KeyType key)
{int low = 1, high = ST.length;//置查找区间初值while(low <= high){int mid = (low + high) / 2;if(ST.R[mid].key == key) return mid;//找到给定值else if(ST.R[mid].key < key) low = mid + 1;//给定值比mid大else high = mid - 1;//给定值比mid小}return 0;
}

分块查找/索引顺序查找

介于前面两种查找方法之间
需要建立一个索引表，下面的表有18个记录，故分为六个子表，每个子表都有对应的索引表，包括关键字项（子表内最大的值）和指针项（子表的起始位置）

树表的查找

二叉排序树

如果用顺序表存储，不利于动态查找，有一种更合适的数据搜索方案，即二叉排序树，利用它可以减少时间复杂度，提高程序效率

定义

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

若左子树不空，则左子树上所有节点的值都小于它根节点的值
若右子树不空，则右子树上所有节点的值都大于它根节点的值
它的左右子树也是二叉排序树

二叉排序树的定义是递归的
性质：中序遍历一颗二叉排序树可以得到一个节点值递增的有序序列

代码表示

typedef struct
{KeyType key;//关键字InfoType otherinfo;//其他数据
}ElemType;//每个节点的数据域类型typedef struct BSTNode
{ElemType data//每个节点的数据域包括以上两项struct BSTNode *lchild, *rchild;//左右孩子
}BTSNode, *BSTree;

查找

/*算法步骤：1. 若二叉排序树为空，则查找失败，返回空指针2. 若二叉排序树非空，将给定值key与根节点的关键字T->data.key进行比较：·若key等于T->data.key则查找成功，返回根节点地址·若key小于T->data.key，则递归查找左子树·若key大于T->data.key，则递归查找右子树
*/BSTree SearchBST(BSTree T, KeyType key)
{if((!T) || key == T->data.key) return T;else if(key < T->data.key) SearchBST(T->lchild, key);else SearchBST(T->rchild, key);
}

插入

/*算法步骤：1. 若二叉排序树为空，则待插入节点*S作为根节点插入空树2. 若二叉排序树非空，将给定值key与根节点的关键字T->data.key进行比较：·若key小于T->data.key，则将*S插入左子树·若key大于T->data.key，则将*S插入右子树
*/
void InsertBST(BSTree &T, ElemType e)
{if(!T){BSTNode S = new BSTNode;S->data.key = e;S->lchild = S->rchild = NULL;T = S;}else if(e < T->data.key) InsertBST(T->lchild, e);else if(e > T->data.key) InsertBST(T->rchild, e);
}

创建

/*算法步骤：1. 将二叉排序树初始化为空2. 读入一个关键字为Key的节点3. 若读入Key不是输入结束操作，则循环执行以下操作：·将此节点插入二叉排序树T中·读取下一个关键字为Key的节点
*/
void CreateBST(BSTNode &T)
{T = NULL;cin >> e;while(e.key != ENDFLAG){InsertBST(T, e);cin >> e;}
}

删除

/*算法步骤：首先查找二叉树是否有要删除的节点，若没有则不做任何操作；若有，则假设被删节点为*p（指向节点的指针），其双亲节点为*f（指向节点双亲的指针），PL、PR分别表示其左子树、右子树不失一般性，可设*p是*f的左孩子（右孩子类似）。下面分3种情况进行讨论：1. 若*p为叶子，即PL与PR为空，直接删去即可，即只需修改其双亲节点的指针为空：f->lchild = NULL2. 若*p只有左子树PL或者只有右子树PR，此时只要让PL或PR代替删除节点即可，即只需修改其双亲节点的指针指向PL或PR：f->lchild = p->lchild (或f->lchild = p->rchild)3. 若*p左右子树均不为空，则找左子树最大节点替代他或者找右子树最小节点替换他,然后再接入被删节点的左子树即可，因为在中序遍历二叉排序树中，左子树最大节点与右子树最小节点分别为被删节点的直接前驱和直接后继，挪动这两个的位置不会影响其它节点的相对次序
*/
void DeleteBST(BSTNode &T, KeyType key)
{BSTNode* p = T,* f = NULL;/*--------------------------------------------寻找是否有被删节点----------------------------------------------*/while(p){if(p->data.key == key)break;f = p;if(p->data.key > key)p = p->lchild;else p = p->rchild;}if(!p) return;/*-----------------------------------------分三种情况执行相对应的删除操作--------------------------------------*/BSTNode* q = p;//后面用来指示被删节点的直接前驱的双亲节点if(p->lchild && p->rchild){BSTNode* 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;//如果直接前驱的双亲节点是被删节点，则直接把直接前驱的左子树接到被删节点处即可delete S;//删除直接前驱return;}//如果是左右子树非空情况则完成删除直接退出，不会执行下面这些，下面这些是只有左子树或右子树非空时才会进行else if(!p->rchild) p = p->lchild;//无右子树，只有左子树else if(!p->lchild) p = p->rchild;//无左子树，只有右子树//这里把为叶子的删除和左子树或右子树非空的删除后挂接*f结合在一起if(!f) T = p;//被删节点父节点为空，即为根节点，直接把根节点替换为p，因为左右子树有一个为空，所以不需要考虑移接左右子树else if(q == f->lchild) f->lchild = p;//挂接到*f的左子树位置else f->rchild = p;//挂接到*f的右子树位置delete q;
}

平衡二叉树

定义

当构造二叉排序树的输入数组本身就已经排序好，创建后的二叉排序树就会变成链表，这样子又会使复杂度增高。故此引入平衡二叉树来解决这一问题。

平衡二叉树又称AVL树，它也是一种二叉排序树，具有以下特征：

左右子树的深度之差的绝对值一定小于等于1
左右子树也是平衡二叉树

其节点的左右子树深度差叫做平衡因子

平衡调节方法

视频： https://www.bilibili.com/video/BV1tZ421q72h/?share_source=copy_web&vd_source=e873369df9d4ed0537d52369f51b2add

判断插入节点后的四种失衡情况，采取对应措施。

表格下面的左旋右旋即为措施，LL型右旋失衡节点；LR型先左旋失衡节点左孩子，后右旋失衡节点。

插入节点若有多个节点失衡了则选择离插入节点最近的进行选择操作

在这里插入图片描述

插入

#define LH +1
#define EH 0
#define RH -1typedef struct BSTNode
{int data;int bf;struct BSTNode* lchild, * rchild;
}BSTNode, * BSTree;void R_Rotate(BSTree& p)
{BSTree lc;lc = p->lchild;p->lchild = lc->rchild;lc->rchild = p;p = lc;return;
}void L_Rotate(BSTree& p)
{BSTree rc;rc = p->rchild;p->rchild = rc->lchild;rc->lchild = p;p = rc;return;
}
void LeftBalance(BSTree& T)
{//对指针T所致节点为根的二叉树作平衡旋转处理BSTree lc;lc = T->lchild;//检查T节点的左孩子，根据其平衡因子判断是右旋还是左右双旋switch (lc->bf){//左孩子的平衡因子为1，平衡因子是直线，右旋case LH:T->bf = EH;lc->bf = EH;R_Rotate(T);break;//左孩子平衡因子为-1，平衡因子为折线，先左旋左孩子，再右旋根节点case RH:BSTree rd;rd = lc->rchild;//修改T节点和其左孩子的平衡因子switch (rd->bf){case LH://左高则根改为-1，左孩子为0T->bf = RH;lc->bf = EH;break;case EH://相等则根与左孩子都为0T->bf = lc->bf = EH;break;case RH://右高则根改为0，左孩子为1T->bf = EH;lc->bf = LH;break;}rd->bf = EH;L_Rotate(T->lchild);R_Rotate(T);}
}
void RightBalance(BSTree& T)
{//对指针T所致节点为根的二叉树作平衡旋转处理BSTree rc;rc = T->rchild;//检查T节点的右孩子，根据其平衡因子判断是左旋还是右左双旋switch (rc->bf){//右孩子的平衡因子为-1，平衡因子是直线，左旋case RH:T->bf = EH;rc->bf = EH;L_Rotate(T);break;//右孩子平衡因子为-1，平衡因子为折线，，先右旋右孩子，再左旋根节点case LH:BSTree ld;ld = rc->lchild;//修改T节点和其右孩子的平衡因子switch (ld->bf){case LH://左高则根改为0，右孩子为-1T->bf = EH;rc->bf = RH;break;case EH://相等则根与左孩子都为0T->bf = rc->bf = EH;break;case RH://左高则根改为1，右孩子为0T->bf = LH;rc->bf = EH;break;}ld->bf = EH;R_Rotate(T->rchild);L_Rotate(T);}
}/*taller 的值含义true：表示插入节点后，子树的高度增加。false：表示插入节点后，子树的高度未发生变化。
*/
int InsertAVL(BSTree& T, int e, bool& taller)
{if (!T){T = (BSTree)malloc(sizeof(BSTNode));T->data = e;T->lchild = NULL;T->rchild = NULL;T->bf = EH;taller = true;}else{//树中已存在和e相同的节点，返回0if (T->data == e){taller = false;return 0;}//继续在左子树中搜索if (T->data > e){//说明递归插入失败了if (!InsertAVL(T->lchild, e, taller)){taller = false;return 0;}//到这里说明插入成功，判断平衡因子if (taller){switch (T->bf){//原本左子树比右子树高，再插入以后，平衡因子变为2，此时需要做左平衡处理case LH:LeftBalance(T);taller = false;break;//原本左右子树,等高，现因左子树增高而使树增高case EH:taller = true;T->bf = LH;break;//原本右子树比左子树高，现在左右子树登高case RH:taller = false;T->bf = EH;break;}}}//继续在右子树中搜索else{if (!InsertAVL(T->rchild, e, taller)){taller = false;return 0;}//到这里说明插入成功，判断平衡因子if (taller){switch (T->bf){//原本左子树比右子树高，插入以后，左右等高case LH:T->bf = EH;taller = false;break;//原本等高，插入以后，右子树等高case EH:T->bf = RH;taller = true;break;//原本右子树高，插入以后，平衡因子变为-2，需要做右平衡处理case RH:RightBalance(T);taller = false;break;}}}}return 1;
}//中序遍历
int temp1[1000],temp2[1000];
int i = 0;
void InorderTraversal(BSTree node)
{if (!node){return;}else{InorderTraversal(node->lchild);temp1[i] = node->data;temp2[i] = node->bf;i++;InorderTraversal(node->rchild);}return;
}

注

B-树&B+树：也是一种二叉平衡树，可从课本了解

散列表的查找

基本概念

又称杂凑法、散列法
散列表即哈希表
散列函数和散列地址：在记录存储位置p和其关键字key之间建立一个确定的对应关系H，是p=H(key)，称这个对应关系为H为散列函数，p为散列地址
散列表：一个有限连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录。通常散列表的存储空间是一个一维数组，散列地址为下标
冲突和同义词：对不同的关键字可能得到同一散列地址，这种现象叫做冲突。而这些关键字叫做同义词。

散列函数的构造方法

数字分析法

事先知道所有关键字集合，且关键字位数比散列表地址地址码位数多，去掉相同的位数，用剩下的当散列地址

平方取中法

将关键字平方后选中间几位（较为常用）。适用于不能事先了解关键字的所有情况或者男于直接从关键字找到取值较分散的几位

折叠法

将关键字分割成位数相同的几部分（最后一部分位数可不同），然后取这几部分相加**（舍去进位）**作为散列地址。适用于散列地址位数较少，关键字较多或者难以直接从关键字找到取值较分散的几位

除留余数法

假设散列表长为m，选一个不大于m的数p，用p去除关键字，除后余数为散列地址。适用范围广，但是要选择合适的p（最常用）

处理冲突的方法

开放地址法

数学递推公式解释步骤为把记录都存储在散列表数组中，当某一项记录关键字的初始散列地址 $H_0$ 发生冲突时，以 $H_0$ 为基础，采取合适方法（加上一个增量 $d_i$ 后对表长取余）来求出新的地址 $H_1$ ，如果还冲突则重复上述方法直至不冲突
三种方法是用来设计 $d_i$ 的取值的
1. 线性探测法： $d_i$ =0,1,2,3, …. ,m-1，即发生冲突时，每次往后探测相邻的下一个单元是否为空**(刚刚从关键字集合取出准备放到散列表里i由题目的散列函数决定)**
2. 平方探测法：当 $d_i$ = $0^2$ , $1^2$ , $1^2$ , $2^2$ , $2^2$ , … , $k^2$ , $k^2$ 时，称为平方探测法，又称二次探测法其中k≤m/2(使用这种方法的散列表长度必须为一个可以表示为4j+3的素数，才能探测到)
3. 伪随机序列法： $d_i$ 为某个随机数列

在这里插入图片描述

查找(线性探测法)

/*算法步骤：1. 给定查找的关键字key根据创建表时设定的散列函数计算散列地址H02. 若H0为空，则元素不存在3. 否则重复下列解决冲突过程：·按冲突处理方法，计算下一个散列地址Hi·若单元Hi为空，则所查元素不存在·若单元Hi中元素关键字为key则查找成功
*/#define m 20
typedef struct
{KeyType key;InfoType otherinfo;
}HashTable[m];#define NULLKEY 0
int SearchHash(HashTable HT, KeyType key)
{H0 = H(Key);if(HT[H0].key == NULLKEY) retrun -1;else if(HT[H0].key == key) return H0;else{for(int i =0; i < m; i++){Hi = (H0 + i) % m;if(HT[Hi].key == NULLKEY) return -1;else if(HT[Hi].key == key) return Hi;}return -1;}
}