🔥基本概念

• 关键字：唯一能标识区分表内元素的某个数据项值（如学号）
• 只进行查找的表叫做静态查找表，进行删改的表叫做动态查找表
• 查找长度：操作过程中需要比较关键字的次数
• 平均查找长度ASL：过往章节提到过，就是所有查找长度的平均值。分为查找成功和失败的两种情况

🔥顺序查找

• 也叫线性查找，常用于线性表，思路就是从头查到尾

//顺序表顺序查找
int Search_Seq(SSTable ST,ElemType key){
  int i;
  for(i=0;i<ST.TableLen && ST.elem[i]!=key; ++i);
  return i==ST.TableLen ? -1 : i;     //查找成功就返回索引，否则返回-1
}
//反向查找
int Search_Seq()(SSTable ST,ElemType key){
  ST.elem[0]=key;         //哨兵，如果查到头依然没有查到，到它才结束，返回的索引自然就是0
  int i;
  for(i=ST.TableLen; ST.elem[i]!=key; --i);
  return i;
}

• 有一些简单的优化方法，比如对于有序表可以查到大小超过范围即可停止；可以将查找多的放到前面。

🔥折半查找

• 即二分查找，仅适用有序的顺序表，思路就是每次都比较中间的那个值，每次判断完成后都能缩小一半的区间，效率比较高。

//顺序表
typedef struct{
  ElemType *elem;   //动态数组基地址
  int TableLen;
}SSTable;
//升序顺序表折半查找
int Binary_Search(SSTabel L,ElemType key){
  int low=0,high=L.TableLen-1,mid;    //左中右“指针”
  while(low<=high){
    mid=(low+high)/2;       //中间值
    if(L.elem[mid]==key)
      return mid;         //查找成功
    else if(L.elem[mid]>key)
      high=mid-1;     //取前半部分继续查找
    else
      low=mid+1;      //取后半部分查找
  }
  return -1;
}

🔥分块查找

• 按大小区间将表分块，每个块存储区间最大关键字
  
• 步骤如下：

1. 索引表中确定待查记录所属的分块（可顺序、折半，顺序常用点）
2. 在块内顺序查找

• 经推算得到，把n个元素的列表分为根号n个块，每块含有根号n个元素时，ASL最小为 (根号n)+1
  

🔥B树

✍概念

• m叉查找树高效的策略：

1. m叉查找树中，规定除了根节点外，任何结点至少有[m/2]（向上取整）个分叉，即至少含有[m/2]- 1个关键字
2. 对于任何一个结点，其子树高度都相同（绝对平衡）

• 满足以上条件的查找树即为B树

  B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树:

  1. 树中每个结点至多有m棵子树，即至多含有m-1个关键字。
  2. 若根结点不是终端结点，则至少有两棵子树。
  3. 除根结点外的所有非叶结点至少有[m/2]棵子树，即至少含有[m/2]-1个关键字。
  4. 如下
     
  5. 所有的叶结点都出现在同一层次上，并且不带信息(可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空)。

✍B树的插入

• 在插入key后，若导致原结点关键字数超过上限，则从中间位置([m/2])将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置（[m/2]）的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致B树高度增1。

✍B树的删除

🔥B+树

🔥散列表

✍概念

• 又称哈希表，是一种数据结构，数据元素关键字与其存储地址通过散列函数（哈希函数）直接相关

• 如上，若不同关键字通过函数映射到同一个值，称它们为同义词
• 通过散列函数确定的位置已经存放其他元素，称这种情况为冲突，通过拉链法可以解决冲突问题

✍处理冲突

拉链法

• 拉链法就是将同义词存在同一个链表中
• 查找目标只需要通过散列函数进行查找即可，如果没有查找到，查找长度是0，查找长度与链表中位置一致
• 冲突越多ASL（平均查找长度）越大，最理想就是没有冲突，这与哈希函数的设计有关
• 散列表相当于用空间换时间，用很多散列地址加快了查找速度
• 每一个链表中关键字的顺序可以随意，但是如果是有大小顺序的将更利于查找。

开放定址法

• 这个方法允许空闲地址向其非同义词表项开放，公式如下：
  

增量d的设定方法：

1. 线性探测法：d_i=0,1,2,…,m-1。发生冲突时会向后面的地址逐个检测是否为空，为空就存入。
   查找也按照递推公式逐个查找比较。但是如果最后没有空缺，容易使得查找失败需要遍历大量地址。
   删除不能直接清空，需要设置一个标记（标志位）让指针查到这里的时候继续查
2. 平方探测法：d_i=0²,±1²,±2²,…,±k²。又称二次探测法，k≤m/2。发生冲突时会交替往前往后检测空闲地址。
   由于增量是不连续的，这会使得空缺更多，不容易像线性探测法产生聚集
3. 伪随机序列法：d_i是一个伪随机序列

再散列法

• 又名再哈希法：除了原始散列函数外，可以有多几个散列函数，查找的时候可以一次使用这些散列函数查找

✍散列函数

• 残留余数法：H(key)=k%p，对于m长的散列表，取一个不大于m但最接近或者等于m的质数p。这会使得存储分布更均匀（虽然这意味着舍弃p到m之间的位置），这在《数论》中有证明

• 数字分析法：选取数码分布较为均匀的若干位作为散列地址
  设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。（如手机号码末尾4位分布很散，可以作为关键字）

• 平方取中法：取关键字的平方值的中间几位作为散列地址。因为求平方后的数中间几位总是和关键字整体相关，而首末的位总是只和关键字头尾相关。
  具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。（如身份证）