查找的对象是由一组记录组成的表或文件,而每个记录则由若干个数据项组成,并假设每个记录都有一个能唯一标识该记录的关键字

在这种条件下,查找的定义是:给定一个值$k$,在含有$n$个记录的表中找出关键字等于$k$的记录。

有两种查找结果:

  • 查找成功,返回该结点的信息或该结点在表中的位置
  • 查找失败,返回相关的提示信息

线性表的查找

线性表上常见的查找方法有:

  • 顺序查找

  • 二分查找

  • 分块查找

查找与数据的存储结构有关,线性表有顺序链式两种存储结构

被查找的顺序表元素类型定义如下:

typedef int KeyType;	// 关键字的数据类型
typedef struct 
{	
    KeyType key; 	
 	InfoType data; 		// 其他数据, 可选
} RecType;

顺序查找

顺序查找是一种最简单的查找方法。它的基本思路是:从表的一端开始,顺序扫描线性表,依次将扫描到的关键字和给定值$k$相比较,若当前扫描到的关键字与$k$相等,则查找成功;若扫描结束后,仍未找到关键字等于$k$的记录,则查找失败。

image-20210110162824169
// 顺序查找
int seqSearch(RecType R[], int n, KeyType k)
{
    int i = 0;
    // 从表头往后找
    while (i < n && R[i].key != k) i++;
    if (i >= n) return 0;
    else return i + 1;
}

顺序查找的优点为算法简单且适用面广,缺点为查找效率相对较低。

二分查找

二分查找(或折半查找)的查找过程中每次将待查记录所在区间缩小一半

  • 适用条件:采用顺序存储的有序表
  • 算法实现
    1. 设表长为nlowhighmid分别指向待查元素所在区间的起点、终点和中间点,k为给定值
    2. 初始时,令low=1high=nmid=(low+high)/2向下取整
    3. kmid指向的记录比较
      • k == R[mid].key,已查到
      • k < R[mid].key,则high = mid-1,在表的前半部分继续查找
      • k > R[mid].key,则low = mid+1,在表的后半部分继续查找
    4. 重复上述操作,直至low > high时,查找失败
image-20210110164111971 image-20210110164130886 image-20210110164233274
// 二分查找
int binSearch(RecType R[], int n, KeyType k)
{
    int low = 0, high = n - 1, mid;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (R[mid].key == k) return mid + 1;  // 查找成功返回
        if (R[mid].key > k) high = mid - 1;   // 继续在R[low..mid-1]中查找
        else low = mid + 1;                   // 继续在R[mid+1..high]中查找
    }
    return 0;
}

二分查找的优点为速度较快,缺点为只能适用于有序表,且仅限于顺序存储结构。

树表的查找

以二叉树或树作为表的组织形式, 称为树表

二叉排序树

二叉排序树(BST)又称二叉查找(搜索)树,其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树:

  • 若它的左子树非空,则左子树上所有记录的值均小于根记录的值
  • 若它的右子树非空,则右子树上所有记录的值均大于根记录的值
  • 左、右子树本身又各是一棵二叉排序树

二叉排序树中没有相同关键字的节点

image-20210110164726752

如果按中序遍历(左根右)二叉排序树,便可得到所有关键码从小到大排成的序列。

被查找的二叉排序树类型定义如下:

// 记录类型
typedef struct node
{
    KeyType key;                    // 关键字项
    InfoType data;                  // 其他数据域, 可选
    struct node *lchild, *rchild;   // 左右孩子指针
} BSTNode;

二叉排序树的插入

若二叉排序树为空,则插入结点应为新的根结点;否则,继续在其左、右子树上查找,直至某个叶子结点的左子树或右子树为空为止,则插入结点应为该叶子结点的左孩子或右孩子

image-20210110165212220
// 插入二叉排序树, 在以*p为根节点的BST中插入一个关键字为k的节点, 插入成功返回1, 否则返回0
int insertBST(BSTNode *&bt, KeyType k)
{
    if (bt == NULL)     // 原树为空, 新插入的记录为根节点
    {
        bt = (BSTNode *) malloc(sizeof(BSTNode));
        bt->key = k;
        bt->lchild = bt->rchild = NULL;
        return 1;
    }
    else if (k == bt->key) // 存在相同关键字的节点, 返回0
        return 0;
    else if (k < bt->key)
        return insertBST(bt->lchild, k); // 插入到左子树中
    else
        return insertBST(bt->rchild, k); // 插入到右子树中
}

二叉排序树的生成

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

image-20210110165357476
// 生成二叉排序树, 返回树根指针
BSTNode *creatBST(KeyType A[], int n)
{
    BSTNode *bt = NULL;          // 初始时bt为空树
    int i = 0;
    while (i < n)
    {
        insertBST(bt, A[i]);  // 将A[i]插入二叉排序树T中
        i++;
    }
    return bt;                   // 返回建立的二叉排序树的根指针
}

二叉排序树的查找

二叉排序树上进行查找,和二分查找类似,也是一个逐步缩小查找范围的过程。

image-20210110165915737
// 查找二叉排序树
BSTNode *searchBST(BSTNode *bt, KeyType k)
{
    if (bt == NULL || bt->key == k)        // 递归终结条件
        return bt;
    if (k < bt->key)
        return searchBST(bt->lchild, k); // 在左子树中递归查找
    else
        return searchBST(bt->rchild, k); // 在右子树中递归查找
}

哈希表的查找

哈希表概述

哈希表(Hash Table)又称散列表,是除顺序表存储结构链接表存储结构索引表存储结构之外的又一种存储线性表的存储结构

哈希表存储的基本思路是:设要存储的元素个数为$n$,设置一个长度为$m(m≥n)$的连续内存单元,以线性表中每个元素的关键字$k_i(0≤i≤n-1)$为自变量,通过一个称为哈希函数的函数$h(k_i)$,计算出$h$函数的值,并把该元素存储在这个地址对应的内存单元中。$h$函数的值称为哈希地址(又称散列地址)。把如此构造的线性表存储结构称为哈希表

image-20210110191303744 image-20210110170602602

对于两个关键字$k_i$和$k_j(i≠j)$,有$k_i≠k_j(i≠j)$,但$h(k_i)=h(k_j)$。我们把这种现象称为哈希冲突

通常把这种具有不同关键字具有相同哈希地址的对象称做「同义词」,由同义词引起的冲突称作同义词冲突

在哈希表存储结构的存储中,同义词冲突很难避免

哈希函数的构造

除留余数法

除留余数法是用关键字$k$除以某个不大于哈希表长度m的数$p$所得的余数作为哈希地址的方法。除留余数法的哈希函数$h(k)$为:
$$
h(k)=k \bmod p(mod为求余运算,p \leq m)
$$
$p$最好取不大于$m$的最大质数(素数)

哈希冲突的解决方法

线性探测法

线性探测法是一种开放定址法,开放定址法就是在出现哈希冲突时在哈希表中找一个新的空闲位置存放元素。

线性探测法是从发生冲突的地址(设为$d_0$)开始,依次探查$d_0$的下一个地址(当到达下标为$m-1$的哈希表表尾时,下一个探查的地址是表首地址$0$),直到找到一个空闲单元为止(当$m≥n$时一定能找到一个空闲单元)。

线性探测法的数学递推描述公式为:
$$
\begin


d_i=\left(d_d_{0}=h(k) \
+1\right) \bmod m(1 \leq i \leq m-1)
\end

$$
探测序列:$d_0+1,d_0+2,d_0+3,…,m-1,0,1,2,…,d_0-1$

image-20210110190854626

拉链法

拉链法是把所有的同义词用单链表链接起来的方法。在这种方法中,哈希表每个单元中存放的不再是记录本身,而是相应同义词单链表的头指针

image-20210110194542061