🔑【数据结构】之查找

查找

查找基本概念、顺序查找法、折半查找法

查找的基本概念

查找的定义：给定一个值k，在含有n个记录的表中找出关键字等于k的记录，若找到，则查找成功，返回该记录的信息或者该记录在表中的位置；若查找失败，返回相关的指示信息

平均比较次数（也称为平均查找长度） ： $ASL=\sum_{i=1}^Np_i*c_i$ （n是查找表中记录的个数， $p_i$ 是查找第i个记录的概率，在考研中一般取 $1/n$ ； $c_i$ 是找到第i个记录所需要进行比较的次数，即查找长度）

顺序查找法

基本思路：从表的一段开始，顺序扫描线性表，依次与k值比较，若相等则查找成功

int Search(int a[], int n, int k)
{
    int i;
    for(i=1;i<=n;++i)
    {
        if(a[i]==k)
        return i;
      return 0;  
    }
}

$ASL_1$ 为成功查找长度 $ASL_2$ 为失败查找长度
$ASL_1=\sum_{i=1}^n i/n=1/n*n*(n+1)/2=(n+1)/2$
$ASL_2=n$
由此可得：成功和失败的时间复杂度都是 $O(n)$

折半查找法

折半查找法要求线性表是有序的
基本思路：设R[low,……,high]，是当前查找区间，首先确定中间位置 $mid=(low+high)/2$ ，然后与R[mid]比较，成功则返回，失败则确定新的查找区间，左或右

int Bsearch(int R[], int low, int high, int k)
{
    int mid
    while(low<=high)
    {
        mid=(low+high)/2;
        if(R[mid]==k)
        return mid;
        if(R[mid>k]
        high=mid-1;
        else low=mid+1;
    }
    return 0;
}

折半查找判定树的层数为比较次数
$ASL_1$ =比较次数之和/关键字数
$ASL_2$ 计算时不把空指针的比较次数计算在内

分块查找（索引查找）

块与块之间按照关键字有序的方式排列
索引表定义：

typedef struct
{
    int key;
    int low, high;
}indexElem;
indexElem index[maxSize];

第一步采用二分查找，第二部采用顺序查找
平均查找长度等于二分查找+顺序查找平均长度

二叉排序树与平衡二叉树

二叉排序树

BST定义
二叉排序树或者是空数，或者是满足以下性质的二叉树

若它的左子树不空，则左子树所有关键字的值小于根关键字的值
若它的右子树不空，则右子树所有关键字的值大于根关键字的值

BST的存储结构

typedef struct BTNode
{
    int key;
    struct BTNode *lchild;
    struct BTNode *rchild;
}BTNode;

二叉排序树的基本算法

查找关键字

BTNode* BSTSearch(BTNode *bt,int key)
{
    if(bt=NULL)
    return NULL;
    else 
    {
        if(bt->key==key)
        return bt;
        else if(key<bt->key)
        return BSTSearch(bt->lchild,key);
        else
        return BSTSearch(bt->rchild,key);
    }
}

插入关键字
查找不成功的位置即为该关键字插入的位置

int BSTInserrt(BTNode *&bt, int key)
{
    if(bt==NULL)
    {
        bt=(BTNode*)malloc(sizeof(BTNode));
        bt->lchild=bt->rchild=NULL;
        bt->key=key;
        return 1;
    }
    else
    {
        if(key==bt->key)
        return 0;
        else if(key<bt->key)
        return BSTInsert(bt->lchild,key);
        else return BSTInsert(bt->rchild,key);
    }
}

二叉排序树的构造算法

void CreateBST(BTNode *&bt,int key[],int n)
{
    int i;
    bt=NULL;
    for(i=0;i<n;++i)
    {
        BSTInsert(bt,key[i]);
    }
}

删除关键字的操作
画图即可
叶子结点：直接删除
只有左子树或者右子树
有左右子树：顺着左子树的右指针最后一个替换（也可以是右子树的最左）

B-树的基本概念及其基本操作、B+树的基本概念

B-树（B树）的基本概念

所有结点的个数称为B-树的阶，通常用m表示，从查找效率看：m>=3；
一颗m阶的B-树或者一颗空数或满足：

  1. 每个结点**至多有m颗子树**
  2. 若根结点不是叶子结点，则**至少有2颗子树**
  3. 除根结点之外的所有非终端结点**至少有m/2颗子树**
  4. 所有非终端结点包含**n个关键字和n+1颗子树**：$(n,A_0,K_1,A_1,...,K_n,A_n)$，其中关键字满足$A_0<K_1<A_1<...<K_n<A_n$
  5. 所有叶子在同一层，不含信息，表示查找失败

B+树：

  1. 差异：**n颗子树结点中含有n个关键字**；所有叶子结点中包含了全部关键字，且按大小顺序排列；所有非终端结点都是索引
  2. 对B+树可以进行顺序查找又可以进行随机查找

散列表

散列表的概念

根据给定的关键字来计算出关键字在表中的地址（H(key)指key在表中的地址，常用的除留余数法 $H(key)=key MOD p$ ）

散列表的建立方法以及冲突的解决方法

冲突：散列函数可能会吧两个或两个以上的不同关键字映射到同一个地址
装填因子： $\alpha=\frac{n}{m}$ ,n个记录，m个地址空间，哈希表的平均查找长度与记录个数n不直接相关，而是取决于装填因子和处理冲突的方法
散列冲突的解决办法：
- 开放地址法
  - 线性探测再散列
  - 二次探测再散列
  - 伪随机探测再散列
- 再哈希法
- 链地址法
- 建立公共溢出区

Liu, Jian's Blog

【数据结构】查找

查找