第七章-查找

7.1 查找的基本概念

• 1.查找
  • 在数据集合中寻找满足某种条件的数据元素的过程称为查找
• 2.查找表（查找结构）
  • 用于查找的数据集合称为查找表
  • 由同一类型的数据元素组成
• 3.静态查找表
  • 无须动态地修改查找表称为静态查找表
    • 适合静态：顺序查找、折半查找、散列查找
    • 适合动态：二叉排序树的查找、散列查找
• 4.关键字
  • 数据元素中唯一标识该元素的某个数据项的值
• 5.平均查找长度
  • $ASL = \sum^n_{i=1}P_iC_i$

7.2 顺序查找和折半查找

1.顺序查找

• 顺序查找：又称线性查找，适用于顺序表和链表
• 1.一般线性表的顺序查找

  • 从线性表的一端开始，逐个检查关键字是否满足给定的条件

  • 代码

      typedef struct{
        ElemType *elem;
        int TableLen;
      }SSTable;
      int Search_Seq(SSTable ST,ElemType key){
        ST.elem[0] = key;   //哨兵
        for(i = ST.TableLen;ST.elem[i] != key;--i);   //从后向前遍历
        return i;
      }
    

  • $ASL_{成功}= (n+1)/2$

  • $ASL_{不成功}= n+1$

  时间复杂度为$O(n)$

• 2.有序表的顺序查找
  • 

  • $$ASL_{不成功}= {(1+2+3+...+n+n)\over(n+1)}={n\over2}+{n\over n+1}$$

2.折半查找

• 适合于顺序存储，不适合于链式

• 首先将给定值key与表中中间位置的元素（mid的指向元素）比较。mid=low+high/2（向下取整）

  • 若key与中间元素相等，则查找成功，返回该元素的存储位置，即mid；
  • 若key与中间元素不相等，则所需查找的元素只能在中间元素以外的前半部分或后半部分
    • 在查找表升序排列的情况下，若给定值key大于中间元素则所查找的元素只可能在后半部分。此时让low=mid+1
    • 若给定值key小于中间元素则所查找的元素只可能在前半部分。此时让high=mid-1

  //折半查找
  int Binary_Search(SSTable 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
  }
  

• 

• $ASL=log_2(n+1)–1$

时间复杂度$O(log_2 n)$

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

• 内和索引表中均采用顺序查找时，平均查找长度为

  • $$ASL = L_I+L_S=\frac {s^2+2s+n}{2s}$$

  当$s=\sqrt{n}$ 时，平均查找长度取最小值$\sqrt{n}+1$

• 若对索引表采用折半查找时，平均查找长度为

  • $$ASL = L_I+L_S=\lceil\log_2(b+1)\rceil+\frac {s+1}2$$

7.3树形查找

7.3 B 树和 B+树

1.B 树的概念（又称多路平衡查找树）

• 1.又称为多路平衡查找树

• 2.B树的阶：所有结点的孩子个数的最大值

• 3.一棵 m 阶B树特性

  • 每个结点至多有m棵子树，至多含有 m-1 个关键字
  • 若根结点不是终端结点，至少有两棵子树
  • 除根结点外的所有非叶节点至少有$\lceil m/2 \rceil$棵子树，即至少有$\lceil m/2 -1\rceil$个关键字
  • 所有叶节点都出现在同一层次上

• 4.B树操作

  • B 树的高度（磁盘存取次数）
  • B 树的查找
  • B 树的插入
  • B 树的删除

• B+树的基本概念

7.4 散列表

1.散列表的基本概念

• 散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数

  $$Hash(key) = Addr$$

• 散列表：根据关键字而直接进行访问的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系

2.散列函数的构造方法

• 1.直接定址法
  • 直接取关键字的某个线性函数值为散列地址
  • $H(key)=key$或$H(key)=a*key+b$

  适合分布基本连续的情况

• 2.除余留数法
  • 假定散列表长为m，取一个不大于m但接近等于m的质数p
  • $H(key)=key\% p$

  关键是p的选择

• 3.数字分析法
  • 选取数码分布均匀的若干位作为散列地址

  适合已知的关键字集合，更换关键字需重新构造散列函数

• 4.平方取中法
  • 取关键字的平方值中间几位作为散列地址

3.处理冲突的方法

• 开放定址法
  • 线性探测法
  • 平方探测法
  • 再散列法
  • 伪随机序列法
• 拉链法

4.散列查找及性能分析

装填因子

$$\alpha={ 表中记录n \over 散列表长度m}$$