数据结构（本科）辅导第八章

### 数据结构（本科）辅导第八章：查找技术详解 #### 一、查找的基本概念 查找是一种常见的数据处理方法，主要用于从一系列数据项中找到特定的数据。查找的目标对象通常由一个包含多个结点的表或文件构成，每个结点又由若干个数据项组成。每个结点拥有一个唯一标识该结点的关键字，通过这个关键字可以实现查找。 **1. 查找的定义：** - 给定一个值K，在含有n个结点的表中找出关键字等于给定值K的结点。 - 若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。 **2. 查找表的数据结构表示：** - **动态查找表和静态查找表：** - 动态查找表是指在查找的同时对表进行修改操作(如插入和删除)的查找表。 - 静态查找表则是指在查找过程中不对表进行修改的查找表。 - **内查找和外查找：** - 内查找指的是整个查找过程都在内存中完成。 - 外查找则是指查找过程中需要访问外存的查找方式。 **3. 平均查找长度ASL：** - ASL(Average Search Length)定义为查找过程中对关键字需要执行的平均比较次数。 - 公式为：\[ASL = \sum_{i=1}^{n} p_i \cdot c_i\]，其中n为结点的个数；\(p_i\)是查找第i个结点的概率；\(c_i\)是找到第i个结点所需进行的比较次数。 #### 二、顺序查找 **1. 基本思想：** - 从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较。 - 若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。 **2. 存储结构要求：** - 顺序查找既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。 **3. 基于顺序结构的顺序查找算法分析：** - **监视哨R[0]的作用：** - 在for循环中省去判定防止下标越界的条件i≥1，从而节省比较的时间。 - **成功时的顺序查找的平均查找长度：** - 在等概率情况下，成功的平均查找长度为\((n+1)/2\)。 - 若K值不在表中，则须进行n+1次比较之后才能确定查找失败。 - **表中各结点的查找概率不相等时的ASL：** - 如果事先知道表中各结点的查找概率不相等和它们的分布情况，则应将表中结点按查找概率由小到大地存放，以提高顺序查找的效率。 - **优点与缺点：** - **优点：**算法简单，适用于各种存储结构。 - **缺点：**查找效率低，不适合大规模数据查找。 #### 三、二分查找 **1. 二分查找(Binary Search)：** - 一种效率较高的查找方法，要求线性表是有序表，并且使用向量作为表的存储结构。 **2. 基本思想及算法：** - 参见教材。 **3. 二分查找的平均查找长度：** - 设内部结点的总数为n=2^h-1，则判定树是深度为h=lg(n+1)的满二叉树。 - 在等概率假设下，二分查找成功时的平均查找长度为\[ASL_{bn} ≈ lg(n+1) - 1\]。 **4. 优点和缺点：** - **优点：**效率高。 - **缺点：**需要对表进行排序，排序本身就是一项耗时的操作；只适用于顺序存储结构，对于频繁改动的线性表不适用。 #### 四、分块查找的算法分析 **1. 分块查找简介：** - 分块查找是一种结合了顺序查找和二分查找优点的方法，通过将数据分成多个块，先对块进行二分查找，再在找到的块中进行顺序查找。 **2. 平均查找长度ASL：** - 分块查找是两次查找的组合，一次是在块间进行的二分查找，另一次是在块内进行的顺序查找。 - ASL的具体计算公式依赖于具体的分块策略和数据分布情况。 通过以上内容的学习，我们可以了解到不同的查找方法在不同场景下的适用性和效率问题。选择合适的查找算法能够显著提升数据处理的速度和效率。