【知识框架】
在这里插入图片描述

一、查找的基本概念

1、查找表

查找表是由同一类的数据元素（或记录）构成的集合。集合中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。

2、关键字

关键字是数据结构（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。
主关键字：关键字可以唯一标识一个记录；（不同的记录，主关键字不同）
次关键字：用以识别若干记录的关键字；

3、查找

查找是指根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在该数据，则查找成功；否则查找不成功；

4、动态、静态查找表

动态查找表：在查找的过程中对表进行修改（插入、删除）；
静态查找表：在查找过程中不做修改；

5、平均查找长度

可以用平均平均查找长度来衡量查找算法的性能；

二、线性表的查找

1、顺序查找

顺序表的定义

typedef struct{
 ElemType *R;  //储存空间基地址
 int length;   //表长度
}SSTable;

【算法描述】

int Search_Seq(SSTable ST,KeyType key)
{
 for(i=ST.length;i>=1;--i)
 {
  if(ST.R[i].key==key)return i;
 }
 return 0;
}

设置监视哨的顺序查找

int Search_Seq(SSTable ST,KeyType key)
{
 ST.R[0].key=key;
 for(i=ST.length;ST.R[i].key!=key;--i);
 return i;
}

【特点】
算法简单，对表结构无任何要求，但查找效率低；
【适用情况】
任何结构的线性表，不经常做插入和删除；

2、折半查找（二分查找）

要求：线性表必须采用顺序存储结构，且元素有序排列；
例如：在这里插入图片描述
【代码示例】

#include<iostream>
using namespace std;
typedef struct 
{
    int R[100];
    int length;
}SSTable;
//折半法查找元素
void Search_Bin(SSTable ST,int key)
{
    int mid;
    int low = 1;
    int hight = ST.length;
    while (low <= hight)
    {
        mid = (low + hight) / 2;
        if (key == ST.R[mid])
        {
            cout << "查找元素在第" << mid << "位置";
            break;
        }
        else if (key < ST.R[mid])hight = mid - 1;
        else if (key > ST.R[mid])low = mid + 1;
    }
    if (low > hight)cout << "不存在该查找数";
}
int main()
{
    SSTable ST;
    int len;
    cout << "请输入数组长度：";
    cin >> len;
    ST.length = len;
    cout << "请输入数组元素：";
    for (int i = 1; i <= len; i++)
    {
        cin >> ST.R[i];
    }
    int key;
    cout << "请输入要查找的数：";
    cin >> key;
    Search_Bin(ST, key);
    cout << endl;
    return 0;
}

【运行结果】
在这里插入图片描述
【特点】
对表结构要求较高，查找效率高；
【适用情况】
有序的顺序表，不经常做插入和删除；

3、分块查找（索引顺序查找）

首先需要建立一个索引表，索引表的每个块包含两部分：关键字项（该块内的最大关键字），指针项（该块第一个记录在表中的位置）。

【查找过程】
先确定待查记录所在的块，然后在块中顺序查找（或折半查找）。
【特点】
对表结构由一定要求，查找效率介于折半查找和顺序查找之间；
【适用情况】
块间有序、块内无序的顺序表，经常做插入和删除；

三、树表的查找

1、二叉排序树（二叉查找树）

【定义】
二叉排序树可以是一棵空树，或者是满足下列条件的树：
（1）若它的左子树非空，则左子树上所有节点均小于它的根结点；
（2）若它的右子树非空，则右子树上所有节点均大于它的根结点；
（3）它的左右子树也为二叉排序树；

【二叉排序树的递归查找算法描述】
（1）若树为空，则查找失败；
（2）若树非空：将查找值与树根结点比较：
a、若两值相等，则输出根结点的地址；
b、若查找值<根结点，则在左子树进行查找，重复（1）（2）步骤；
c、若查找值>根结点，则在右子树进行查找，重复（1）（2）步骤；

【二叉排序树的插入、创建、删除】

//插入
void InsertBST(BSTree &T,ElemType e)
{
 if(!T)   //如果是空树
 {
  S=new BSTNode;    //生成新结点*S
  S->data=e;        //将结点*S的数据域置为e
  S->lchild=S->rchild=NULL;   //*S为叶子结点
  T=S;              //把结点*S链接到已找到的插入位置
 }
 else if(e.key<T->data.key)  //关键字小于根结点的值
 InsertBST(T->lchild,e);     //往左子树中插入
 else if(e.key>T->data.key)  //关键字大于根结点的值
 InsertBST(T->rchild,e);     //往右子树中插入
}
//创建
void CreatBST(BSTree &T)
{
 T=NULL;
 cin>>e;
 while(e.key!=ENDFLAG)
 {
  InsertBST(T,e);
  cin>>e;
 }
}

【删除的三种类型】
在这里插入图片描述

2、平衡二叉树

【定义】
二叉排序树可以是一棵空树，或者是满足下列条件的树：
（1）左子树和右子树的深度之差的绝对值不超过1；
（2）左子树和右子树也是平衡二叉树；
平衡因子：该结点的左子树与右子树之差，（平衡因子只可能是-1，0，1）若不是这三个值，则该树不平衡。
【平衡调整方法】
（1）LL型
进行一次向右的顺时针旋转操作
（2）RR型
进行一次向左的逆时针旋转操作
（3）LR型
需进行两次旋转操作，第一次逆时针旋转变为LL型，再顺时针旋转恢复平衡
（4）RL型
需进行两次旋转操作，第一次顺时针向右旋转，第二次逆时针向左旋转

3、B-树

【定义】
一棵m阶B-树可以是一棵空树，或者是满足下列条件的m叉树：
（1）树中每个结点至多有m棵子树；
（2）若根结点不是叶子结点，则至少有两棵子树；
（3）除根之外的所有非终端结点至少有[m/2]棵子树；
（4）所有的叶子结点都出现在同一层次上，并且不带信息，通常称为失败结点；
（5）所有的非终端结点最多有m-1个关键字；
【查找】
B-树是一种平衡的多叉查找树，是一种在外存文件系统中常用的动态索引技术。查找过程与二叉排序树类似，是一个顺指针查找结点和在结点内的关键字中查找交叉进行的过程。

4、B+树

【特点】
（1）有n棵子树的结点中含有n个关键字；
（2）所有的叶子结点中包含了全部关键字信息，以及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；
（3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树中的最大关键字；
【查找】
若非终端结点上的关键字等于给定值，查找并不终止，而是继续向下直到叶子结点。
【插入和删除】
插入和删除仅发生在叶子结点上。

四、散列表的查找

1、散列表的基本概念

散列查找法：如果能在元素的存储位置和其关键字之间建立某种直接关系，按照这种关系直接由关键字找到相应的记录。
散列函数、散列地址：在记录的存储位置p和关键字key之间建立一种确定的对应关系H，使p=H（key）;对应关系H称为散列函数，p称为散列地址。
散列表：一个有限连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录。
冲突：对于不同的关键字可能得到同一散列地址；
同义词：具有相同函数值的关键字对该散列函数来说称作同义词；