考研笔记 | 数据结构 §7.查找

  • 英语:

  1. 查找:在数据集合中寻找满足某种条件的数据元素,结果有两种:查找成功与查找失败。
  2. 查找表(查找结构):用于查找的数据集合。它由同一类型的数据元素(或记录)组成,可以为一个数组或链表等数据类型。
  3. 对查找表的操作:
    1. 查找某一特定元素是否在查找表中
    2. 检索满足条件的某个特定元素的各种属性
    3. 在查找表中插入一个数据元素
    4. 从查找表中删除某个数据元素
  4. 静态查找表:仅涉及3.1,3.2操作(查找)
  5. 动态查找表:设计3.1,3.2,3.3,3.4操作(查,插,删)
  6. 平均查找长度:$ASL=\sum^n_{i=1}{P_i,C_i}\qquad(P_i)为第i个关键字概率$
  7. 关键字:数据元素中唯一标识该元素的某个数据项的值。
  8. 静态查找表适用:顺序查找、折半查找、静态树、次优先查找树、索引顺序。
    动态查找表适用:二叉排序树、平衡二叉树(AVL树)、B-树、B+树、键树、哈希表。
  9. 顺序查找:又称线性查找,一般的无序线性表适用。
  10. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    typedef struct{
    ElemType *elem;
    int Tablelen.
    }SStable

    int Search(int a[],int n,int x){
    for(i=n-1;i<=1,i--){
    if(a[i]==x) return true;
    return flase;//找不到
    }

    int Search_Seq(SStable ST,ElemType key){
    ST.elem[0]=key;
    for(i=ST.TableLen;St.elem[i]=key;--i)//逆序找
    return i;//若不存在关键字为key的元素,i=0退出循环
    }//所有程序需要有return!
  11. $ASL_{成功}=\frac{n+1}{2}\quad ASL_{失败}=n+1$

  12. 优点:思路简单、适用面广(对查找表无特殊要求)
    缺点:n较大时,平均查找长度大,效率低;
    对线性链表只能顺序查找。
  13. 有序表的顺序查找,当查找到一定范围时,可提前返回失败信息,$ASL_{不成功}=\frac{n}{2}+\frac{n}{n+1}$
  14. 折半查找:又称二分查找,适用有序顺序表。从中间开始,每次抛弃一半范围。
  15. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int BinarySearch(DataType a[],int t,DataType x){//无递归版本
    low=0,high=n-1;
    while(low<=high){
    mid=(low+high)/2;
    if(a[mid]=x return mid;
    else
    if(x<a[mid] high=mid-1; //低半区
    else low=mid+1;
    }
    return flase;
    }
  16. 1
    2
    3
    4
    5
    6
    7
    8
    int BinarySearch(DataType a[],int low,int high,DataType x){//递归版本
    if(low>high) return false;
    mid=(low+high)/2;
    if(a[mid]==x) return mid;
    else
    if(x<a[mid]) return BinarySearch(a,low,mid-1,x);
    else return BinarySearch(a,mid+1,high,x);
    }
  17. 特点:速度快,要求查找表有序,且随机访问(便于计算下标)。因此,此法不支持链表,但可转为二叉排序树等形式。

  18. 判定树:$ASL \approx \log_2{n+1}-1$,时间复杂度$O(\log_2{n})$
  19. 平均查找长度$ASL=\frac{4\times3+3\times4+2\times2+1}{10}=\frac{29}{10}$
12345678910

示例

  1. 分块查找,又称索引顺序查找。把查找表分为若干子块,块内元素可无序,但块间有序。再建立一个索引表,索引表中每个元素含各块的最大关键字和各块第一个元素的地址。索引表按关键字有序排列。
  2. $ASL=L_1+L_s$设将长度为$n$的查找表均分为$b$块,每块有$S$个记录。$ASL=\frac{b+1}{2}+\frac{S+1}{2}=\frac{S^2+2S+n}{2S}$
  3. B树,又称多路平衡查找树。B树中所有结点的孩子结点的最大值称为B树的阶,用$m$表示
  4. 一棵$m$阶的B树或为空树,或
    1. 树中每个结点至多有$m$棵子树,至多含$m-1$个关键字;
    2. 若根结点不是终端点,则至少有两棵子树;
    3. 除根结点外,所有非叶子结点至少有$\left \lceil m/2 \right \rceil$棵子树
    4. 所有叶子在同一层,不含信息。(访问到意味着查找失败)
    5. 所有非叶结点结构如下:
      其中,$k$为结点关键字,满足$k_1<k_2<\dots<k_n$;$P_i$为指向根子树结点指针,且指针$P_{i-1}$所指的根结点的子树中所有结点关键字满足小于$k_i,P_i$所指的子树,所有结点关键字大于$K_i$,$n(\left \lceil m/2 \right \rceil-1\leq n\leq m-1)$为结点中关键字个数。
$n_0$$P_0$$k_1$$P_1$$k_2$$P_2$$\dots$$k_n$$P_n$
  1. $B^+$树与B树的差异
    1. $n$棵子树的结点中含有$n$个关键字;
    2. 所有叶子节点中包含全部关键字,目标大小排列;
    3. 所有非终端结点都是索引。
  2. 散列(Hash)表:根据关键字直接访问的数据结构。其建立了关键字与存储地址中的一种直接映射关系。
  3. 哈希函数:$Hash(Key)=Addr$,常用$H(Key)=key\quad MOD \quad p$
  4. 冲突:把两个或两个以上关键字映射到同一地址。$H(Key_1)=H(Key_2)$,且$Key_1 \neq Key_2$
  5. 散列函数构造:
    1. 直接定址法:$H(Key)=a\times key+b$,适用于关键字分布基本连续;
    2. 除余留数法:$H(Key)=key\quad \% \quad p$,关键是选好$p$;
    3. 数字分析法:对关键字若$r$进制,而$r$个数码在各位上出现频率不同,应选取数码分布较均匀的若干位作地址,适用于已知关键字。
  6. 处理冲突

    • 开放定址法:$H_i=(H(key)+d_i)%m$,可有放新项的空闲空间,向它的同义词开放,又向它的非同义词开放。
    • 线性探测法:当$H(key)$满,尝试$H(key)+1,H(key)+2,\dots$直到成功。会造成大量元素在相邻的散列地址上“聚集”,降低效率;
    • 平方探测法:当冲突时,测试$H(key)+1^2,H(key)-1^2,H(key)+2^2,H(key)-2^2$,可避免“堆积”问题,缺点是不能探测所有单元,但至少有一半;
    • 再散列法:当$d_1=Hash_2(key)$,及准备两个哈希函数,当$H(key)$冲突,既用$H_2(key)$计算。最多经过$m-1$次探测会遍历完所有位置;
    • 伪随机序列法:设$d_1=伪随机序列数$。
  7. 拉链法:对冲突存储于一链表中,散列表存储地址。

  8. 查找效率:与散列函数、冲突树立、装填因子有关。$因子=\frac{表中记录数n(越大越容易冲突)}{散列表长度m}$
  9. 字符串模式匹配算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int Index(SString S,SString T){
    int i=1,j=1;
    while(i<=S[0]&&j<=T[0]){
    if(S[i]==T[j]){
    ++i;++j;//继续比较后继字符
    }
    else{
    i=j-j+2;j=1;//指针后退重新匹配
    }
    }
    if(j>T[0]) return i-T[0];
    else return 0;
    }
  10. 改进算法——KMP算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    int KMP(char S[],char T[],int next[],int pos){
    //求串T在主串S中第pos个字符后的位置,其中1<=pos<=strlen[s]
    i=pos;j=1;
    while(i<=S[0]&&j<=T[0]){
    if(j==0||S[i]==T[j]){
    ++i;++j;
    }
    else j=next[j];
    }
    if(j>T[0]) return i-T[0];
    else return 0;
    }
    void get_next(char T[],int next[]){
    i=1;next[1]=0;j=0;
    while(i<=T[0]){
    if(j==0||T[i]==T[j]){
    ++i;++j;next[i]=j;
    }else j=next[j];
    }
    }
-------文章到此结束  感谢您的阅读-------