数据结构考研查找部分学习笔记

数据结构考研查找部分学习笔记

一、查找的基本概念

（一）查找的定义

查找是在数据集合中寻找满足特定条件数据元素的过程。这里的 “特定条件” 多为数据元素的关键字等于给定值，偶尔也可能是关键字满足大于、小于等比较关系。比如在学生信息数组中，按学号查找对应学生信息，学号就是关键字，目标是找到学号与给定值相等的学生信息。

（二）关键字的分类

1. 主关键字：能唯一标识一个数据元素的关键字。像学生的学号，在学校范围内通常唯一，可作为主关键字，通过它查找最多能找到一个匹配元素。

2. 次关键字：不能唯一标识数据元素的关键字。例如学生姓名，可能有重名情况，通过它查找可能得到多个结果。

（三）查找表的定义及分类

查找表是由同一类型数据元素（或记录）构成的集合，可分为：

1. 静态查找表：仅支持查找，不允许修改（插入、删除元素）。如存储历史成绩的表格，查询时不会改动。

2. 动态查找表：既支持查找，又允许插入、删除等修改操作。像实时更新的商品库存表，查询时可能因进货或卖出而修改。

（四）查找成功与失败

1. 查找成功：在查找表中找到满足条件的元素，结果可能是元素信息或其位置。

2. 查找失败：未找到满足条件的元素，需返回标识信息表明失败。

（五）平均查找长度

平均查找长度（ASL）是衡量查找算法性能的关键指标，指查找过程中关键字比较次数的平均值。

• 查找成功时（含 n 个元素的表），等概率下公式为：ASL 成功 =∑（第 i 个元素的查找次数）/n。

• 查找失败时，是查找不到元素时比较次数的平均值，计算方式因算法而异。ASL 越小，算法性能越好。

二、线性查找

（一）基本思想

从查找表一端开始，逐个将元素关键字与给定关键字比较，直到找到（成功）或遍历完（失败）。比如在数组 [5,3,8,1,2] 中找 8，依次比较 5、3 后，找到 8 即成功。

（二）算法实现

int linearSearch(int arr\[], int n, int key) {

&#x20;   for (int i = 0; i < n; i++) {

&#x20;       if (arr\[i] == key) {

&#x20;           return i; // 成功返回下标

&#x20;       }

&#x20;   }

&#x20;   return -1; // 失败返回-1

}

（三）哨兵模式

在数组末尾设值为 key 的哨兵，减少循环中对遍历结束的判断，提高效率。

int linearSearchWithSentinel(int arr\[], int n, int key) {

    int i = 0;

    arr\[n] = key; // 设哨兵

    while (arr\[i] != key) {

        i++;

    }

&#x20;   return (i < n) ? i : -1;

}

（四）性能分析

• 时间复杂度：成功时最坏 O (n)、最好 O (1)，平均 O (n)；失败时 O (n)。

• 空间复杂度：O (1)，仅需临时变量。

• 平均查找长度：成功（等概率）(n+1)/2；失败 n+1（哨兵模式）。

（五）优缺点及适用场景

• 优点：简单易懂，对表结构无要求，支持顺序和链式存储，元素可无序。

• 缺点：效率低，数据量大时速度慢。

• 适用场景：数据量小、表结构不规则或元素无序的情况。

三、折半查找

（一）基本思想

要求表有序（通常升序）且为顺序存储。先将关键字与中间元素关键字比较，相等则成功；小于中间则查左半部分；大于则查右半部分，重复至成功或失败。如在 [1,3,5,7,9,11,13] 中找 7，中间元素即 7，成功；找 4，先左查 [1,3,5]，再右查 [5]，最后失败。

（二）算法实现

int binarySearch(int arr\[], int n, int key) {

    int low = 0, high = n - 1;

&#x20;   while (low <= high) {

&#x20;       int mid = (low + high) / 2;

&#x20;       if (arr\[mid] == key) return mid;

&#x20;       else if (arr\[mid] > key) high = mid - 1;

&#x20;       else low = mid + 1;

&#x20;   }

&#x20;   return -1;

}

（三）性能分析

• 时间复杂度：最坏和失败时均为 O (log₂n)，因判定树深度为⌊log₂n⌋+1。

• 空间复杂度：O (1)，需几个临时变量。

• 平均查找长度：n 较大时，≈log₂(n+1)-1。

（四）优缺点及适用场景

• 优点：效率高，时间复杂度 O (log₂n)。

• 缺点：要求表有序且为顺序存储，修改表时调整成本高，仅适用于关键字可比较的有序表。

• 适用场景：表建立后少修改、多查找的有序顺序表。

四、分块查找

（一）基本思想

将表分若干块，块内无序但块间有序，建索引表（含块最大关键字和起始位置）。查找分两步：先在索引表（有序）找所在块（用折半或线性查找），再在块内线性查找。例如表分三块，索引表 [(5,0),(10,3),(15,6)]，表为 [3,5,2,7,9,10,12,15,13]，找 9 时，先确定在第二块，再在块内找到。

（二）算法实现

typedef struct {

    int maxKey;

    int startIndex;

} Index;

int blockSearch(int arr\[], Index index\[], int blockNum, int n, int key) {

    int low = 0, high = blockNum - 1, blockIndex = -1;

    // 索引表折半查找

&#x20;   while (low <= high) {

&#x20;       int mid = (low + high) / 2;

&#x20;       if (index\[mid].maxKey >= key) {

&#x20;           blockIndex = mid;

&#x20;           high = mid - 1;

&#x20;       } else low = mid + 1;

&#x20;   }

&#x20;   if (blockIndex == -1) return -1;

&#x20;   // 块内线性查找

&#x20;   int start = index\[blockIndex].startIndex;

&#x20;   int end = (blockIndex == blockNum - 1) ? n - 1 : index\[blockIndex + 1].startIndex - 1;

&#x20;   for (int i = start; i <= end; i++)

&#x20;       if (arr\[i] == key) return i;

&#x20;   return -1;

}

（三）性能分析

平均查找长度是索引表和块内平均查找长度之和。n 个元素分 b 块，每块 s 个元素（n=b×s），等概率下：

• 索引表折半查找，ASL 索引 = log₂(b+1)-1。

• 块内线性查找，ASL 块内 =(s+1)/2。

• ASL=log₂(b+1)-1+(s+1)/2，s=√n 时达最小值≈√n + log₂√n，时间复杂度 O (√n)。

（四）优缺点及适用场景

• 优点：结合线性和折半查找优点，兼顾查找效率和表的动态性。

• 缺点：需额外存储空间建索引表，块的划分影响性能。

• 适用场景：数据量较大，且需要一定查找效率，同时有一定动态修改需求的情况。

五、B 树及其查找

（一）B 树的定义

B 树是一种多路平衡查找树，适用于外存存储系统。一棵 m 阶 B 树满足：

1. 每个节点最多有 m 个子树，即最多 m-1 个关键字。

2. 根节点至少有 2 个子树（除非为叶子节点），非根节点至少有⌈m/2⌉个子树。

3. 所有叶子节点在同一层，不带信息。

4. 节点结构：（n，P0，K1，P1，K2，P2，…，Kn，Pn），其中 n 为关键字数，Ki 为关键字且有序，Pi 为子树指针。

（二）B 树的查找过程

1. 从根节点开始，比较待查关键字与节点中关键字。

2. 若相等则查找成功。

3. 若小于某个关键字，进入其左侧子树继续查找。

4. 若大于最后一个关键字，进入右侧子树继续查找。

5. 若到达叶子节点仍未找到，则查找失败。

（三）性能分析

B 树的查找效率取决于树的高度。m 阶 B 树含 N 个关键字时，高度 h 满足 h≤log⌈m/2⌉((N+1)/2)+1。查找过程中，每访问一个节点需一次外存读写，关键字比较次数不超过树高，时间复杂度为 O (h×logm)，h 为树高。

（四）适用场景

适用于外存文件系统，如数据库索引，能有效减少外存访问次数，提高查找效率。

六、B + 树及其查找

（一）B + 树的定义

B + 树是 B 树的变种，m 阶 B + 树特点：

1. 节点关键字数与子树数相等，每个关键字对应一个子树。

2. 所有叶子节点包含全部关键字及指向记录的指针，且按关键字有序链接。

3. 非叶子节点是叶子节点的索引，关键字为其对应子树中最大关键字。

4. 根节点可为叶子节点或有至少 2 个子树。

（二）B + 树的查找过程

1. 从根节点出发，类似 B 树查找，找到关键字所在的叶子节点。

2. 在叶子节点中顺序查找（因叶子节点有序链接，也可范围查找），找到则成功，否则失败。

（三）与 B 树的区别

1. B + 树叶子节点含全部关键字，B 树非叶子节点也含部分关键字。

2. B + 树叶子节点有序链接，支持范围查找，B 树不支持。

3. B + 树查找必须到叶子节点，B 树可在非叶子节点结束。

（四）适用场景

比 B 树更适合数据库索引，尤其适合范围查询，如查询某一区间内的数据。

七、哈希表查找

（一）哈希表的基本概念

哈希表（散列表）是通过哈希函数将关键字映射到表中位置进行存储的结构。哈希函数是关键字到存储位置的映射函数，记为 H (key)。

（二）哈希函数的构造方法

1. 直接定址法：H (key)=a×key+b（a、b 为常数），适合关键字分布连续的情况。

2. 数字分析法：取关键字中分布均匀的数字作为哈希地址，适用于已知关键字集合。

3. 平方取中法：对关键字平方后，取中间几位作为哈希地址，适合关键字位数少或分布不均的情况。

4. 折叠法：将关键字分割成位数相同的几部分，叠加求和取后几位作为哈希地址，适用于关键字位数多的情况。

5. 除留余数法：H (key)=key mod p（p 为小于等于表长的质数），应用广泛。

（三）处理冲突的方法

1. 开放定址法：当冲突发生时，按一定规则在哈希表中寻找空位置。

• 线性探测法：H_i=(H (key)+i) mod m（i=0,1,…,m-1），易产生聚集。

• 二次探测法：H_i=(H (key)+i²) mod m 或 H_i=(H (key)-i²) mod m（i=1,2,…,），减少聚集。

• 伪随机探测法：H_i=(H (key)+ 随机数) mod m，随机性好。

1. 链地址法：将哈希地址相同的元素链接成单链表，冲突元素放在链表中，处理简单，不易聚集。

2. 再哈希法：用多个哈希函数，冲突时换函数计算地址。

3. 建立公共溢出区：将冲突元素放入溢出表，基本表存放不冲突元素。

（四）哈希表的查找过程

1. 计算待查关键字的哈希地址。

2. 若该地址为空，则查找失败。

3. 若该地址元素关键字与待查关键字相等，则查找成功。

4. 若不等，按处理冲突的方法寻找下一个地址，重复 2、3 步，直到找到或确定失败。

（五）性能分析

哈希表的查找性能受装载因子 α（表中元素数 / 表长）影响，α 越小，冲突概率越低。成功和失败的平均查找长度都随 α 增大而增大。链地址法在 α 较大时仍有较好性能。平均查找长度接近 O (1)，是一种高效的查找方法。

（六）优缺点及适用场景

• 优点：查找效率高，平均查找长度小。

• 缺点：哈希函数和处理冲突方法选择影响性能，不支持顺序查找和范围查找。

• 适用场景：需要快速查找，且关键字分布较均匀的情况，如字典、缓存等。

八、各种查找方法的比较与总结