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

发表于 分类于 阅读次数： 本文字数： 3.8k 阅读时长 ≈ 3 分钟

  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. ```c
    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!

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    11.  $ASL_{成功}=\frac{n+1}{2}\quad ASL_{失败}=n+1$
    12.  优点：思路简单、适用面广（对查找表无特殊要求）
           缺点：n较大时，平均查找长度大，效率低；
    	   对线性链表只能顺序查找。
    13.  有序表的顺序查找，当查找到一定范围时，可提前返回失败信息，$ASL_{不成功}=\frac{n}{2}+\frac{n}{n+1}$
    14.  折半查找：又称二分查找，适用有序顺序表。从中间开始，每次抛弃一半范围。
    15.  ```c
    		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;
    		}

  11. ```c
    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);
    }

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    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}$

    |  1   | 2   | 3   | 4   | 5   | 6   | 7   | 8   | 9   | 10 |
    | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |

    ![示例][7.1]

    20.  分块查找，又称索引顺序查找。把查找表分为若干子块，块内元素可无序，但块间有序。再建立一个索引表，索引表中每个元素含各块的最大关键字和各块第一个元素的地址。索引表按关键字有序排列。
    21.  $ASL=L_1+L_s$设将长度为$n$的查找表均分为$b$块，每块有$S$个记录。$ASL=\frac{b+1}{2}+\frac{S+1}{2}=\frac{S^2+2S+n}{2S}$
    22.  B树，又称多路平衡查找树。B树中所有结点的孩子结点的最大值称为B树的阶，用$m$表示
    23. 一棵$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$ |
    | ----- | ----- | ----- | ----- | ----- | ----- | ------- | ----- | ----- |

    24. $B^+$树与B树的差异
    	1. $n$棵子树的结点中含有$n$个关键字；
    	2. 所有叶子节点中包含全部关键字，目标大小排列；
    	3. 所有非终端结点都是索引。
    25. 散列(Hash)表：根据关键字直接访问的数据结构。其建立了关键字与存储地址中的一种直接映射关系。
    26. 哈希函数：$Hash(Key)=Addr$，常用$H(Key)=key\quad MOD \quad p$
    27. 冲突：把两个或两个以上关键字映射到同一地址。$H(Key_1)=H(Key_2)$，且$Key_1 \neq Key_2$
    28. 散列函数构造：
    	1. 直接定址法：$H(Key)=a\times key+b$，适用于关键字分布基本连续；
    	2. 除余留数法：$H(Key)=key\quad \% \quad p$，关键是选好$p$；
    	3. 数字分析法：对关键字若$r$进制，而$r$个数码在各位上出现频率不同，应选取数码分布较均匀的若干位作地址，适用于已知关键字。
    29. 处理冲突
    	- 开放定址法：$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=伪随机序列数$。

    30. 拉链法：对冲突存储于一链表中，散列表存储地址。
    31. 查找效率：与散列函数、冲突树立、装填因子有关。$因子=\frac{表中记录数n（越大越容易冲突）}{散列表长度m}$
    32. 字符串模式匹配算法
    	```c
    	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;
    	}

  12. 改进算法 ——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];
    	}
    }