数据结构之查找

发表于 更新于 分类于 阅读次数： Valine： 本文字数： 4.3k 阅读时长 ≈ 4 分钟

第十章查找

第一节查找的概念

在数据集合中寻找满足某种条件的数据元素的过程

第二节静态查找

1.顺序（线性）查找

（1）一般线性表的查找

1
2
3
4
5
6
7
8
9
typedef struct{					//查找表的数据结构
    ElemType *elem;				//元素存储空间基址，建表时按实际长度分配，0号单元留空
    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;					//若表中不存在关键字为key的元素，将查找到i=0时退出for循环
}

对于有n个元素的表，给定值key与表中第i个元素相等，即定位第i个元素时，需进行n-i+1次关键词的比较。

\begin{flalign}
&1.查找成功时:\
&顺序查找的平均长度为：ASL_{成功} = \sum_{i=1}^nP_i(n-i+1)\
&当每个元素的查找概率相等，即P_i=1/n时，有：ASL_{成功} = \sum_{i=1}^nP_i(n-i+1)=(n+1)/2\
&2.查找失败时：\
&与表中各关键词的比较次数时n+1次，从而顺序查找不成功的平均查找长度为：ASL_{不成功} = n+1
\end{flalign}

（2）有序表的查找

\begin{flalign}
&1.查找成功时:\
&顺序查找的平均长度为：ASL_{成功} = \sum_{i=1}^nP_i(n-i+1)\
&当每个元素的查找概率相等，即P_i=1/n时，有：ASL_{成功} = \sum_{i=1}^nP_i(n-i+1)=(n+1)/2\
&2.查找失败时：\
&查找不成功的平均查找长度为：ASL_{不成功} = \sum_{j=1}^nq_i(l_j-1)=(1+2…+n+n)/(n+1)=n/2+n/(n+1)
\end{flalign}

2.二分（折半）查找

时间复杂度：O(logn)

1
2
3
4
5
6
7
8
9
10
int Binary_Search(SeqList L,ElemType key){
    int low = 0,high = L.TableLen-1,mid;
    while(low<=high){
        min = (low+high)/2;							//取中间位置
        if(L.elem[mid] = key)	return min;			//查找成功则返回所在位置
        else if(L.elem[mid]>key)	high = mid-1;	//从前半部分继续查找
        else	low = mid+1;						//从后半部分继续查找
    }
    return -1;										//查找失败，返回-1
}

\begin{flalign}
&ASL_{成功} = 1/n\sum_{i=1}^nl_i=1/n(11+22+…+h2^{h-1})=(n+1)/nlog_2(n+1)≈log_2(n+1)-1\
\end{flalign}

3.索引（分块）查找

基本思想：将查找表氛围若干子块。块内元素可以无序，但块之间时有序的，即第一个块中的最大关键字小于第二块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。
$$
\begin{flalign}
&1.分块查找的平均查找长度为索引查找和块内查找的平均长度之和，设索引查找和块内查找的平均查找长度分别为L_l和L_s\
&~~~则分块查找的平均查找长度为：ASL = L_l+L_s\
&2.将长度为n的查找表均匀的分成b块，每块有s各记录，在等概率情况下，若块内和索引表中均采用顺序查找\
&~~~则平均查找长度为：ASL = L_l+L_s = (b+1)/2+(s+1)/2 = (s^2+2s+n)/(2s)\
&3.若s = \sqrt n，则平均查找长度取最小值\sqrt n+1；\
&4.若对索引表采用折半查找时，\
&~~~则平均查找长度为ASL= L_l+L_s = \lceil log_2(b+1)\rceil+(s+1)/2
\end{flalign}
$$

第三节动态查找

二叉排序树（BST）

二叉排序树（二叉查找树）或者是一棵空树，或者时具有下列特性的二叉树：

1）若左子树非空，则左子树上所有结点的值均小于根结点的值；

2）若右子树非空，则右子树上所有结点的值均大于根结点的值；

3）左、右子数也分别是一棵二叉排序树。

（1）查找

1
2
3
4
5
6
7
BSTNode *BST_Search(BiTree T,ElemType key){
    while(T&&key!=T->data){				//若树空或等于根结点值，则结束循环
        if(key<T->data)	T = T->lchild;	//小于，则在左子树上查找
        else	T = T->rchild;			//大于，则在右子树上查找
    }
    return T;
}

（2）插入

1
2
3
4
5
6
7
8
9
10
11
int BST_Insert(BiTree &T,KetType k){
    if(T){									//原树为空，新插入的记录为新结点
        T = (BiTree)malloc(sizeof(BSTNode));
        T->data = k;
        T->lchild = T->rchild = NULL;
        return 1;							//返回1，表示插入成功
    }
    else if(k == T->data)	return 0;		//树中存在相同关键字的结点，插入失败
    else if(k < T-data)		return BST_Insert(T->lchild,k);		//插入到T的左子树
    else	return BST_Insert(T->rchild,k);		//插入到T的右子树
}

（3）构造

1
2
3
4
5
6
7
8
void Creat_BST(BiTree &T,KetType str[],int n){
    T = NULL;					//初始时T为空树
    int i = 0;
    while(i < n){				//依次将每个关键字插入到二叉排序树中
        BST_Insert(T,str[i]);	
        i++;
    }
}

（4）删除

①若被删除结点z时叶结点，则直接删除，不会破坏二叉排序树的性质；

②若结点z只有一棵左子树或右子树，则让z的子数称为z父节点的子数，代替z的位置；

③若结点z有左、右两棵子数，则令z的直接后继（或直接前驱）替代z，然后二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一种或第二种情况。

graph TB;
A((53))
B((17))
C((78))
D((09))
E((45))
F((65))
G((94))
H((81))
I((88))
J((23))
A-->B
A-->C
B-->D
B-->E
C-->F
C-->G
E-->J
G-->H
H-->I

删除78结点后

graph TB;
A((53))
B((17))
D((09))
E((45))
F((65))
G((94))
H((81))
I((88))
J((23))
A-->B
A-->H
B-->D
B-->E
E-->J
H-->F
H-->G
G-->I

\begin{flalign}
平衡二叉树的递推公式：n_0=0,n_1=1,n_2=2,n_h=1+n_{h-1}+n_{h-2}
\end{flalign}

第四节哈希查找（散列表）

1.哈希查找的概念

散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr（这里的地址可以实数组下标、索引或内存地址等）

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

2.哈希函数

（1）直接定址法

\begin{flalign}
H(key)=key或H(key)=a×key+b
\end{flalign}

（2）除留余数法

假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，则散列函数如下：

\begin{flalign}
H(key)=key%p
\end{flalign}

（3）数字分析法

（4）平方取中法

取关键字的平方值的中间几位作为散列地址。适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

3.哈希冲突的解决方法

（1）开放地址法

\begin{flalign}
H_i = (H(key)+d_i)%m\
H(key)为散列函数：i = 0,1,2,…,k(k ≤ m-1)；m表示散列表表长；d_i为增量序列
\end{flalign}

–a.线性探测法

特点：冲突发生时，顺序查看表中下一个单元（探测到表尾地址m-1时，下一个探测地址时表首地址0），知道招初一个空闲单元（当表为填满时一定要找到一个空闲单元）或查遍全表。

缺点：容易造成大量元素在相邻的散列地址上“聚集”（或堆积）起来，大大降低查找效率。

–b.平方探测法

特点：当d~i~ = 0²，1²，-1²，2²，-2²，…，k²，-k²时，称为平方探测法，其中k ≤ m/2，散列表长度m必须是一个可以表示成4k+3的素数，又称二次探测法。

优点：可以避免出现“堆积”问题。

缺点：不能探测散列表上的所有单元，但至少可以探测到一半单元。

–c.双散列法

​ 当d~i~=Hash~2~(key)时，称为双散列法。当通过第一个散列函数H(key)得到的地址发生冲突时，利用第二个散列函数Hash~2~(key)计算该关键字的地址增量。具体散列函数形式如下：

\begin{flalign}
H_i=(H(key)+i×Hash_2(key))%m
\end{flalign}

初始探测位置H~0~=H(key)%m。i是冲突的次数，初始为0。最多经过m-1次探测就会遍历表中所有位置，回到H~0~位置。

–d.伪随机序列法

d~i~ = 伪随机序列时，称为伪随机序列法。

（2）拉链法（链接法）

同线性探测法，但改为链表形式。

4.散列查找及性能分析

散列表的查找效率取决三个因素：散列函数、处理冲突的方法和装填因子。

\begin{flalign}
\alpha = 表中记录数n/散列表长度m
\end{flalign}

散列表的平均查找长度依赖于散列表的装填因子α，而不直接依赖于n或m。直观地看，α越大，表示装填的记录越“满”，发生冲突的可能性越大，反之发生冲突的可能性越小。