七、查找
7.1 查找的概念
1、查找的定义
查找表：是由一组记录组成的表或文件，而每个记录由若干个 数据项组成，并假设每个记录都有一个能唯一标识该记录的关键字。
2、内查找和外查找
若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。
3、查找的数据组织
采用何种存储结构？(1）顺序表 （2）链表 （3）其他
若在查找的同时对表做修改操作（如插入和删除）， 则相应的表称之为动态查找表；否则称之为静态查找表。
7.2 线性表的查找
线性表查找的主要方法有：顺序查找、二分查找、分块查找
7.2.1 顺序查找
思路：
从表的一端开始，顺序扫描线性表，依次将扫描到的关 键字和给定值k相比。若当前扫描到的关键字与k相等，则查找成功；若扫描结束后， 仍未找到关键字等于k的记录，则查找失败。
代码：
int SeqSearch(SeqList R,int n,KeyType k){
int i=0;
while(i<n && R[i].key!=k) //从表头往后找
i++;
if(i>=n) //未找到返回0
return 0;
else return i+1; //找到返回逻辑序号i+1
}
①成功情况下的平均查找长度ASL=(n+1)/2
②不成功情况下的平均查找长度ASL=n
7.2.2 折半查找
折半查找也称为二分查找，要求线性表中的记录必须己按关键 字值有序（递增或递减）排列。
代码：
//迭代版本
int BinSearch(SeqList R,int n,KeyType k){
int low=0,hight=n-1,mid;
while(low<=high){
mid=(low+high)/2;
if(R[mid].key==k) //查找成后返回其逻辑序号mid+1
return mid+1;
if(k<R[mid].key) //继续在R[low..mid-1]中查找
high=mid-1;
else low =mid+1; //继续在R[mid+1..hight]中查找
}
return 0;
}
//递归版本
int BinSearch(SeqList R,KeyType k,int l,int r){
int mid;
if(l<=r){
mid=(l+r)/2;
if(R[mid].key==k)
return mid+1;
else if(k<R[mid].key)
return BinSearch(R,k,l,mid-1);
else return BinSearch(R,k,mid+1,r);
}
return 0;
}
①成功情况下的平均查找长度ASL=log2 n
7.2.3 索引存储结构和分块查找
1、索引存储结构
索引存储结构 = 数据表 + 索引表
索引表中的每一项称为索引项，索引项的一般形式是： （关键字，地址）
关键字唯一标识一个节点，地址作为指向该关键字对应节点的指针， 也可以是相对地址。
2、分块查找
分块查找方法：
索引表(有序)：可以顺序查找块，也可以二分查找块。
数据块(无序)：只能顺序查找块中的元素。
分块查找的效率介于顺序查找和二分查找之间。
7.3 树表的查找
以二叉树或树作为表的组织形式，称为树表，它是一类动 态查找表，不仅适合于数据查找，也适合于表插入和删除操作。
常见的树表：
(1) 二叉排序树 (2) 平衡二叉树
(3) B-树 (4) B+树
二叉树→(满足节点值约束)→二叉排序树→(所有节点的平衡因子的绝对值<=1,结构约束)→平衡二叉树
7.3.1 二叉排序树(BST)
二叉排序树（简称BST）又称二叉查找（搜索）树，其定义为：二叉 排序树或者是空树，或者是满足如下性质（BST性质）的二叉树：
①若它的左子树非空，则左子树上所有节点值（指关键字值）均小于根 节点值；
②若它的右子树非空，则右子树上所有节点值均大于根节点值；
③左、右子树本身又各是一棵二叉排序树。
注意：二叉排序树中没有相同关键字的节点。
1、二叉排序树上的查找
二叉排序树可看做是一个有序表，所以在二叉排序树上进行查 找，和二分查找类似，也是一个逐步缩小查找范围的过程。
代码：
BSTNode *SearchBST(BSTNode *bt,KeyType k){
if(bt==NULL||bt->key==k) //递归出口
return bt;
if(k< bt->key)
return SearchBST(bt->left,k); //在左子树中递归查找
else
return SearchBST(bt->right,k); //在右子树中递归查找
}
2、二叉排序树的插入和生成
在二叉排序树中插入一个关键字为k的新节点，要保证插入后 仍满足BST性质。
插入过程：
(1) 若二叉排序树T为空，则创建一个key域为k的节点，将它作为根节点；
(2) 否则将k和根节点的关键字比较，若两者相等，则说明树中已有此关键字k，无须插入，直接返回0；
(3) 若k< T->key，则将k插入根节点的左子树中；
(4) 否则将它插入右子树中。
代码：
int InsertBST(BSTNode *&p,KeyType k) {
if(p==NULL){ //原树为空，新插入的记录为根节点
p=(BSTNode *)malloc(sizeof(BSTNode));
p->key=k; p->left=p->right=NULL;
return 1;
}else if(k==p->key) //存在相同关键字的节点，返回0
return 0;
else if(k< p->key)
return InsertBST(p->left,k); //插入到左子树中
else
return InsertBST(p->right,k); //插入到有右子树中
}
//利用数组创建二叉排序树
BSTNode *CreatBST(KeyTypeA[],int n){ //返回树根指针
BSTNode *bt=NULL; //初始时bt为空树
int i=0;
while(i<n){
InsertBST(bt,A[i]); //将A[i]插入二叉排序树T中
i++;
}
return bt; //返回建立的二叉排序树的根节点
}
注意：任何节点插入到二叉排序树时，都是以叶节点插入的。
二叉排序树的特点：
(1) 二叉排序树的中序序列是一个递增有序序列
(2) 根节点的最左下节点时关键字最小的节点
(3) 根节点的最右下节点时关键字最大的节点
3、 二叉排序树的节点删除
（1）被删除的节点是叶子节点：直接删去该节点。
（2） 被删除的节点只有左子树或者只有右子树，用其左子树或者 右子树替换它（节点替换）。
（3）被删除的节点既有左子树，也有右子树
以其中序前趋值替换之（值替换） ，然后再删除该前趋节点。 前趋是左子树中最大的节点。
也可以用其后继替换之，然后再删除该后继节点。后继是右子树 中最小的节点。
算法实现：如何删除仅仅有右子树的节点*p:
//1.查找被删节点
int deletdk(BSTNode *&bt,KeyType k){
if(bt!=NULL){
if(k==bt->key){
deletep(bt);
return 1;
}
else if(k< bt->key)
deletek(bt->left,k);
else
deletek*bt->right,k);
}
else return 0;
}
//2.删除节点*p
void deletep(BSTNode *&p){
BSTNode *q;
q=p;
p=p->right; //用其右孩子节点替换它
free(q);
}
在二叉排序树bt中删除节点的算法：
int DeleteBST(BSTNode *&bt,KeyType k){
if(bt==NULL) return 0; //空树删除失败
else{
if(k< bt->key) return DeleteBST(bt->left,k); //递归在左子树中删除为k的节点
else if(k> bt->key) return DeleteBST(bt->right,k); //递归在右子树中删除为k的节点
else{
Delete(bt); //调用Delete(bt)函数删除*bt节点
return 1;
}
}
}
void Delete(BSTNode *&p){ //从二叉排序树中删除*p节点
BSTNode *q;
if(p->right==NULL){ //*p节点没有右子树的情况
p=q;p=p->left; //用其左孩子节点替换它
free(q);
}else if(p->left==NULL){ //*p节点没有左子树的情况
p=q;p=p->right; //用其右孩子节点替换它
free(q);
}else Delete1(p,p->left); //*p节点既没有左子树右没有右子树的情况
}
void Delete1(BSTNode *p, BSTNode *&r) {
//p指向待删除的节点，r指向其左孩子节点
//当被删*p节点有左右子树时的删除过程
BSTNode *q;
if(r->right!=NULL)
Delete1(p,r->right); //递归找*r的最右下节点
else{ //r指向最右下节点
p->key=r->key; p->data=r->data; //值替换
q=r; r=r->left; //删除原*r节点
free(q); //释放原*r的空间
}
}
7.3.2 平衡二叉树(AVL)
1、 什么是平衡二叉树
若一棵二叉树中每个节点的左、右子树的高度至多相差1,则称 此二叉树为平衡二叉树（AVL）。
平衡因子：该节点左子树的高度减去右子树的高度。
若一棵二叉树中所有节点的平衡因子的绝对值小于或等于1， 该二叉树称为平衡二叉树。
2、平衡二叉树的插入调整
平衡二叉树中插入新节点方式与二叉排序树相似，只是插入后 可能破坏了平衡二叉树的平衡性，解决方法是调整。
调整操作可归纳为4种情况：
(1) LL型调整 (2) RR型调整 (3) LR型调整 (4) RL型调整
3、平衡二叉树的查找
含有n个节点的平衡二叉树的平均查找长度为O(log2 n)。
7.3.3 B-树
B-树又称为多路平衡查找树，是一种组织和维护外存文件系统非常有效的数据结构。
B-树的定义：
一棵m阶B-树或者是一棵空树，或者是满足要求的m叉树：
(1) 树中每个节点至多有m个孩子节点(即至多有m-1个关键字)，最多关键字个数Max=m-1
(2) 除根节点外，其他非叶子节点至少有 m/2↑ 个孩子节点，最少关键字个数Min=m/2↑ -1
(3) 若根节点不是叶子节点，则根节点至少有两个孩子节点；
(4) 每个节点的结构 指针和关键字交叉排列，节点中按关键字大小顺序排列；
(5) 所有外部节点都在同一层上。B-树是所有节点的平衡因子均等于0的多路查找树。
在计算B-树的高度时，需要计入最底层的外部节点
说明：外部节点就是失败节点，指向它的指针为空，不含有任何信 息，是虚设的。一棵B-树中总有n个关键字，则外部节点个数为n+1。
在B-树的存储结构中，节点的类型定义如下：
typedef struct node{
int keynum; //节点当前拥有的关键字的个数
KeyType key[MAXM]; //[1..keynum]存放关键字
struct node *parent; //双亲节点指针
struct node *ptr[MAXM]; //孩子节点指针数组[0..keynum]
}BTNode;
7.3.4 B+树
B+树的定义：
一棵m阶B+数满足下列要求：
(1) 每个分支节点至多有m棵子树。
(2) 根节点或者没有子树，或者至少有两棵子树。
(3) 除根节点外，其他每个分支节点至少有m/2↑棵子树。（↑表示向上取整）
(4) 有n棵子树的节点恰好有n个关键字。
(5) 所有叶子节点包含全部关键字及指向相应记录的指针，而且叶子节 点按关键字大小顺序链接。并将所有叶子节点链接起来。
(6) 所有分支节点（可看成是索引的索引）中仅包含它的各个子节点（即下级索引的索引块）中最大关键字及指向子节点的指针。
7.4 哈希表的查找
7.4.1 哈希表的基本概念
哈希函数：把关键字为ki的对象存放在相应的哈希地址中
哈希冲突：对于两个关键字分别为ki和kj（i≠j）的记录，有ki≠kj，但h(ki)=h(kj)。 把这种现象叫做哈希冲突（同义词冲突）。
1、哈希表设计
哈希表设计主要需要解决哈希冲突。实际中哈希冲突是难以避 免的，主要与3个因素有关：
(1) 与装填因子有关。装填因子α=存储的记录个数/哈希表的大小 =n/m α越小，冲突的可能性就越小； α越大（最大可取1）， 冲突的可能性就越大。通常使最终的控制在0.6～0.9的范围内。
(2) 与所采用的哈希函数有关。好的哈希函数会减少冲突的发生；不好的哈希函数会增加冲突的发生。
(3) 与解决冲突方法有关。好的哈希冲突解决方法会减少冲突的发生。
7.4.2 哈希函数构造方法
(1) 直接定址法 (2) 除留余数法 (3) 数字分析法
7.4.3 哈希冲突解决方法
1、开放地址法：冲突时找一个新的空闲的哈希地址。
（1）线性探查法 （2）平方探查法
2、拉链法：拉链法是把所有的同义词用单链表链接起来的方法。