静态查找操作 - 迅博思语资讯移动站

静态查找操作

2024-10-31 20:09

在日常生活中，几乎每天都要进行一些查找的工作，在电话簿中查阅某个人的电话号码；在电脑的文件夹中查找某个具体的文件等等。

静态查找操作

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

查找表：用于查找的数据集合称为查找表

在查找表中只做查找操作，而不改动表中数据元素，称此类查找表为静态查找表；

反之，在查找表中做查找操作的同时进行插入数据或者删除数据的操作，称此类表为动态查找表。

记忆一个专属名词—— 关键字

在查找表查找某个特定元素时，前提是需要知道这个元素的一些属性。例如，每个人上学的时候都会有自己唯一的学号，因为你的姓名、年龄都有可能和其他人是重复的，唯独学号不会重复。而学生具有的这些属性（学号、姓名、年龄等）都可以称为关键字。

关键字又细分为主关键字和次关键字。若某个关键字可以唯一地识别一个数据元素时，称这个关键字为主关键字，例如学生的学号就具有唯一性；反之，像学生姓名、年龄这类的关键字，由于不具有唯一性，称为次关键字。

顺序查找(又称线性查找)，主要用于在线性表中进行查找。从查找表的一端开始，顺序扫描查找表，依次将扫描到的关键字和待查找的值key进行比较。如果相等，则查找成功。如果扫描结束仍然没有发现相等的数据元素，则查找失败。

查找操作的性能分析主要考虑其时间复杂度，而整个查找过程其实大部分时间花费在关键字和查找表中的数据进行比较上。

所以查找算法衡量好坏的依据为：查找成功时，查找的关键字和查找表中的数据元素中进行过比较的个数的平均值，称为平均查找长度（Average Search Length，用ASL 表示）。

例如，对于具有 n 个数据元素的查找表，查找成功的平均查找长度的计算公式为：

Pi 为第 i 个数据元素被查找的概率，所有元素被查找的概率的和为 1；Ci 表示在查找到第 i 个数据元素之前已进行过比较的次数。若表中有 n 个数据元素，查找第一个元素时需要比较 n 次；查找最后一个元素时需要比较 1 次，所以有。

一般情况，表中各数据元素被查找的概率是未知的。假设含有 n 个数据元素的查找表中，各数据被查找的概率是相同的，则：

换算后，得：

如果对于查找表中各个数据元素有可能被查找的概率提前已知，就应该根据其查找概率的大小对查找表中的数据元素进行适当的调整：被查找概率越大，离查找出发点 i 越近；反之，越远。这样可以适当的减少查找操作中的比较次数。

上边的平均查找长度是在假设查找算法每次都成功的前提下得出的。而对于查找算法来说，查找成功和查找失败的概率是相同的。所以，查找算法的平均查找长度应该为查找成功时的平均查找长度加上查找失败时的平均查找长度。

对于含有 n 个数据的表来说，每次查找失败，比较的次数都是 n+1。所以查找算法的平均查找长度的计算公式为：

优点：算法简单，且对顺序结构或链表结构均适用。

缺点：ASL太大，时间效率太低 O(n)。

折半查找由称二分查找仅适用于有序的顺序表，最形象的一个例子猜数字游戏，取1-100，认定一个数字来猜，大了则往小猜，小了则往大猜，为了效率，我们一般第一个数字就会取中猜50，并以此类推下去。

时间复杂度为O(logn)

仅适用于有序的顺序表

求下图中该树等概率查找的情况下查找成功和失败的ASL

关键字 25 10 30 2 15 28 35 3 20 29 40 1

此处：-l 表示左孩子 -r表示右孩子

失败位置 2-l 15-l 28-l 35-l 3-l-r 20-l-r 29-l-r 40-l-r

又称索引顺序查找

流程：

分块查找性能介于顺序查找和折半查找之间

特点：块间有序，块内无序

查找：块间折半，块内线性

代码学习于王道数据结构，仅供参考。