【数据结构】课堂复习笔记5——查找

Kendal2024-12-112024-12-11

学习的网课是青岛大学-王卓的数据结构与算法基础系列课程，可在bilibili上观看。并配合zjut课堂笔记整理，仅用于学习和复习

六、查找

6.1 查找的基本概念

是一种数据结构

查找表：由同一类型的数据元素（或记录）构成的集合
静态查找表：查找的同时对查找表不做修改操作（如插入和删除）
动态查找表：查找的同时对查找表具有修改操作
关键字：记录中某个数据项的值，可用来识别一个记录
主关键字：唯一标识数据元素
次关键字：可以标识若干个数据元素
关键字的平均比较次数，也称平均搜索长度ASL(Average Search Length)：

6.2 线性表的查找

6.2.1 顺序查找

应用范围：

顺序表或线性链表表示的静态查找表；
表内元素之间无序。

顺序表的表示:

typedef struct 
{
     ElemType   *R; //表基址
     int          length;     //表长
}SSTable;

在顺序表L中查找值为e的数据元素:监视哨

int Search_Seq(SSTable  ST , KeyType  key)
{
   //若成功返回其位置信息，否则返回0
    ST.R[0].key =key;   
    for( i=ST.length; ST.R[ i ].key!=key;  - - i  );
 //不用for(i=n; i>0; - -i) 或 for(i=1; i<=n; i++)，直接将查找条件作为循环判别条件。  
    return i; 
}

性能分析：

时间复杂度：
- 查找成功时的平均查找长度设表中各记录查找概率相等
- 查找不成功时的平均查找长度
空间复杂度：一个辅助空间
非等概率查找时，可按照查找概率进行排序。

6.2.2 折半查找

int Search_Bin(SSTable ST, KeyType key)
{
    //若找到，则函数值为该元素在表中的位置，否则为0
    low=1; high=ST.length;						 
    while(low<=high){
        mid=(low+high)/2;
        if(key==ST.R[mid].key) return mid; 
        else if(key<ST.R[mid].key) high=mid-1;    //前一子表查找
        else low=mid+1;                       		    //后一子表查找
    }									    
    return 0;		//表中不存在待查元素
}

递归算法：

int Search_Bin (SSTable ST, keyType key, int low, int high) 
{ 
  if(low>high) return 0;   //查找不到时返回0，递归结束条件
  mid=(low+high)/2; 
  if(key等于ST.elem[mid].key)  return mid; 
  else if(key小于ST.elem[mid].key)  
    Search_Bin (SSTable ST, keyType key, int low, int mid-1)//递归
  else Search_Bin (SSTable ST, keyType key, int mid+1, int high)  //递归
}

性能分析：判定树

查找成功时比较次数：为该结点在判定树上的层次数，不超过树的深度
查找不成功的过程就是走了一条从根结点到外部结点的路径或
每次将待查记录所在区间缩小一半，比顺序查找效率高,时间复杂度
适用条件：采用顺序存储结构的有序表，不宜用于链式结构

6.2.3 分块查找

分块有序，即分成若干子表，要求每个子表中的数值都比后一块中数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。

查找效率：
优点：插入和删除比较容易，无需进行大量移动。
缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算。
适用情况：如果线性表既要快速查找又经常动态变化，则可采用分块查找。

6.3 树表的查找

6.3.1 二叉排序树

二叉排序树或是空树，或是满足如下性质的二叉树：

若其左子树非空，则左子树上所有结点的值均小于根结点的值；
若其右子树非空，则右子树上所有结点的值均大于等于根结点的值；
其左右子树本身又各是一棵二叉排序树

中序遍历后：得到一个关键字的递增有序序列

二叉排序树操作：查找

BSTree SearchBST(BSTree T,KeyType key) 
{
   if((!T) || key==T->data.key) return T;       	 
   else if (key<T->data.key)  return SearchBST(T->lchild,key);	//在左子树中继续查找
   else return SearchBST(T->rchild,key);    		   		//在右子树中继续查找
} // SearchBST

二叉排序树操作：插入

若二叉排序树为空，则插入结点应为根结点，否则，继续在其左、右子树上查找
- 树中已有，不再插入
- 树中没有，查找直至某个结点的左子树或右子树为空为止，则插入结点应为该结点的左孩子或右孩子
插入的元素一定在叶结点上

二叉排序树的操作：生成

从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树
不同插入次序的序列生成不同形态的二叉排序树

二叉排序树的操作－删除：将因删除结点而断开的二叉链表重新链接起来，防止重新链接后树的高度增加

删除叶结点，只需将其双亲结点指向它的指针清零，再释放它即可。
被删结点缺右子树，可以拿它的左子女结点顶替它的位置，再释放它。
被删结点缺左子树，可以拿它的右子女结点顶替它的位置，再释放它。
被删结点左、右子树都存在，可以在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删结点中，再来处理这个结点的删除问题（形成递归删除操作）。

6.3.2 平衡二叉树

左、右子树是平衡二叉树；
所有结点的左、右子树深度之差的绝对值≤ 1
平衡因子：该结点左子树与右子树的高度差

对于一棵有n个结点的AVL树，其高度保持在O(log_2n)数量级，ASL也保持在O(log_2n)量级。

平衡调整：
- LL平衡旋转：若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。（以B为旋转轴）
- RR平衡旋转：若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。（以B为旋转轴）
- LR平衡旋转：若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。（以插入的结点C为轴）
- RL平衡旋转：若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。（以插入的结点C为轴）

6.4 散列（哈希）表的查找

6.4.1 散列表的基本概念

基本思想：记录的存储位置与关键字之间存在对应关系，
优点：查找速度极快 , 查找效率与元素个数n无关
缺点：空间效率低

若干术语：

哈希方法(散列法)选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比，确定查找是否成功。
哈希函数(散列函数)：哈希方法中使用的转换函数
冲突：不同的关键码映射到同一个哈希地址
同义词：具有相同函数值的两个关键字

6.4.2 散列函数的构造方法

直接定址法：

优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突。
缺点：要占用连续地址空间，空间效率低。

除留余数法：

Hash(key)=key mod p (p是一个整数)

6.4.3 处理冲突

开放地址法：

有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入
- 线性探测法：一旦冲突，就找下一个空地址存入
  - 优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素
  - 缺点：可能使第i个哈希地址的同义词存入第i+1个地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，产生“聚集”现象，降低查找效率。
- 二次探测法：
  - m为哈希表长度，m要求是某个4k+3的质数
  - di为增量序列 12，-12，22，-22，…，q2
- 伪随机探测法
  - m为哈希表长度
  - di 为随机数

链地址法： 基本思想：相同哈希地址的记录链成一单链表，m个哈希地址就设m个单链表，然后用用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构

step1 取数据元素的关键字key，计算其哈希函数值（地址）。若该地址对应的链表为空，则将该元素插入此链表；否则执行step2解决冲突。
step2 根据选择的冲突处理方法，计算关键字key的下一个存储地址。若该地址对应的链表为不为空，则利用链表的前插法或后插法将该元素插入此链表。
优点：
- 非同义词不会冲突，无“聚集”现象
- 链表上结点空间动态申请，更适合于表长不确定的情况

6.4.4 哈希表的查找

哈希表的查找效率分析：

使用平均查找长度ASL来衡量查找算法，ASL取决于：
- 哈希函数
- 处理冲突的方法
- 哈希表的装填因子
越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比较次数就越多。 $表中填入的记录数哈希表的长度$
ASL与装填因子有关！既不是严格的O(1)，也不是O(n)
- $拉链法$
- $线性探测法$
- $随机探测法$
总结：
- 对哈希表技术具有很好的平均性能，优于一些传统的技术
- 处理冲突时，链地址法优于开地址法
- 除留余数法作哈希函数优于其它类型函数