8.1 查找基本概念及顺序查找在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这节课开始，我们讨论第8章查找

第1节课，介绍查找的基本概念以及顺序查找

先介绍查找的基本概念

查找的对象我们称为查找表

查找表是由同一类型数据元素构成的集合

请同学注意集合两个字

第1章介绍过集合这种数据结构

集合强调的是数据元素之间没有关系

这章查找和下一章排序的对象都是集合

我们不会再讨论关系的表达了

查找表中的数据元素也被称为记录

记录和数据元素是一回事

在查找表上的操作可以分为4种

一是查询，查询的含义是依照一个条件

在查找表中查找满足条件的记录

二是检索，检索也是按照条件找到记录

并且获取记录的内容

三是插入，查找表中可能有新的记录的加入

这就需要在查找表上执行插入操作

四是删除，可能有的记录需要从查找表中删除

这就需要在查找表上执行删除操作

依据操作的差异，可以把查找表分为两种类型

一种称为静态查找表

针对静态查找表的操作只有查询和检索

这两类操作不会改变查找表本身

一种称为动态查找表

是指在查找表上4种操作都可能发生

那么，在动态查找表的实现上就要考虑

怎样适应频繁的插入和删除操作

那么在查找表中进行查找依据是什么呢

一般是一个关键字

关键字是数据元素或者记录中的某个数据项的值

关键字最大的特点是，只要用这样一个数据项

就可以标识，或者识别一个数据元素

例如学校信息系统中关于同学的记录

这样的记录包括很多数据项

如学号，姓名，年龄等，学号就是一个很好的关键字

同一个学校，每个同学的学号都是唯一

用学号作为关键字就可以标识或是识别一个同学

所谓的查找操作，就是根据给定的某个值

一般是关键字类型的一个值

在查找表中确定一个关键字等于给定值的记录

这样的操作，我们称为查找

查找的结果，可能有两种

一个是某个记录的关键字和给定值相等，称为查找成功

如果，查找表中所有记录的关键字和给定值都不相等

称为查找不成功

下面说一下本章数据元素类型的定义

本章关键字的类型名字是KeyType

主要是两种数据类型，一种是整型

一种是字符串类型，都起类型名为KeyType

为了讨论方便，大多时候我们讨论的关键字类型都是以整型为例

当然，不是说关键字只能是整型

其它类型也可以，只要定义了比较方式就可以

数据元素的类型被定义为一个结构体

结构体中可能包含多个成员

这里只关注作为关键字的成员key

其它成员和查找关系不大，在此忽略

key的类型是刚才说到的KeyType

结构体的类型名是ElemType

如果关键字的类型是整型

比较时可以直接用关系运算符进行比较

如果是字符串或是其它不能直接使用关系运算符比较的类型

我们需要自己定义比较函数

为了后面讨论的方便，这里定义了三个比较函数

EQ(a, b) 的含义是说如果a和b两个关键字类型的值相等

则返回真，否则返回假

LT(a, b) 的含义是,

如果a小于b，则返回真，否则返回假

LQ(a, b) 的含义是, 如果a小于等于b

则返回真，否则返回假

因为关键字类型多样，三个比较函数只是形式上的定义

程序中，应该结合关键字具体的类型来实现

静态查找表中，先考虑顺序表达查找

顺序表是一种查找表

表中有n个记录，存储在一个一维数组当中

顺序表的存储类型定义为一个结构体

结构体中有两个成员

elem是一个指向数据元素的指针

顺序表的存储空间仍然是通过malloc函数申请获得的

申请成功后，用指针elem指向其分配空间的起始地址

经常把这个指针作为一个数组名使用

另一个整型成员length是给出顺序表中记录的个数

给这个结构体起类型名SSTable

那随后定义顺序表的变量ST

为ST分配空间

如图所示，假设顺序表中有a1到an，n个记录

它们存在数组1到n号单元

0号单元不存数据元素

本章中，0号单元一般都不存数据元素

有的方法中做监视哨

有的方法中作为暂存单元

有的方法中直接就闲置了

如果给定一个关键字类型的值key

我们要在顺序表中进行查找

一般想到的方法是从1号单元开始

自前向后进行扫描，扫描过程当中

把正在考察的记录i的关键字和给定值key进行比较

如果相等，则查找成功，返回该记录的位置i

如果不等，则继续考察下一个记录

如果扫描了整个顺序表

仍然没有找到和给定值相等的记录关键字

那么就说查找失败

看一下实现上述扫描的for循环语句

i=1，从第1个单元开始扫描

循环条件是i小于等于ST.length

判断第i个单元是否在表长范围内

如果i在表长范围内

并且第i的单元记录的关键字ST.elem[i].key

不等于给定值key，则继续循环

循环结束后判断，如果i大于ST.length

说明扫描完整个顺序表都没有找到和给定值相等的记录关键字

说明查找失败，返回0

否则，说明循环结束是因为某个记录i的关键字和给定值相等

这是查找成功，返回1。

教材中顺其查找的方法和这个方法不一样

不同点有2个，看图

第一，设置了一个监视哨

就是把给定值key赋值给0号单元的关键字成员

我们把它称为监视哨

第二个不同是，扫描不是从前向后

而是从后向前，从第n个元素开始向前扫描

如果在顺序表中查找不成功，i最后会等于0

因为0号单元的关键字中存有给定值

此时给定值必然和关键字相等，扫描结束

设置了监视哨后，查找失败时

扫描必会在0号单元结束

这就避免了查找过程当中

每一步都要检测扫描是否越界

提高了算法执行的效率

看一下顺序查找的代码

查找函数Search_Seq的返回值是一个整型数

如果查找成功，返回查找成功的记录在表中的位置

如果查找失败，则返回0

涉及到的参数有两个

一个是SSTable类型的顺序表ST

一个是关键字类型的给定值key，这是查找的依据

首先设置监视哨

把给定值key赋值给ST中0号单元的关键字ST.elem[0].key

随后，for循环进行扫描，i被赋值ST.length

这是表中最后一个元素的位置

如果考察的记录i的关键字和给定值不等

则--i，循环考察前一个位置的记录

循环结束以后

如果查找成功，那么返回成功记录的位置i

如果失败，那么i会在监视哨的位置0

返回i，就是返回0

如何度量查找算法的效率呢

下面介绍对查找算法的性能分析

回顾顺序表的查找过程，我们注意到

查找主要操作是给定值和关键字的比较

通过和关键字比较的次数度量查找算法的性能是合理

当然，在顺序表中不同位置i查找成功

需要的比较次数是不一样的

如果查找的是后半部的记录

比较次数会少一点，查找的是前半部的记录

比较次数会多一点

根据查找的特点

我们以平均查找长度来度量查找算法的效率

平均查找长度是指

为了确定记录在查找表中的位置

需要和给定值进行比较的关键字的个数的期望值

称为查找算法在查找成功时的平均查找长度

提到期望值肯定就涉及到概率

设查找表中查找第i个元素的概率为pi

Ci为找到第i个记录和关键字比较的次数

那么n个记录Pi*Ci的累加和就是查找成功的平均查找长度ASL

我们用ASL来度量查找算法的效率

具体看一下顺序表查找的性能分析

从顺序表的查找过程来看，从后向前比较的话

第i的元素ai查找成功需要和关键字比较n-i+1次

不失一般性，设每个数据元素查找概率相等

每个记录的查找概率都是n分之一

那么查找成功的平均查找长度ASL等于1/n乘以1到n

n-i+1的连加，连加的内容是1到n的等差数列

计算结果是(n+1)/2

也就是说等概率的情况下查找成功的平均查找长度

相当于表长的一半，这和我们直观的认识是一致的

查找成功，如果是后半部分的记录

那么比较次数少一些，如果是前半部分的记录

比较次数呢多一些

度量查找算法的效率

不仅要考虑查找成功时的平均查找长度

也需要考虑查找失败的平均查找长度

毕竟查找可能成功，也可能失败

一个好的查找算法应该是查找成功快

查找失败也快，才能说是一个好的查找算法

对顺序查找来说，查找失败需要和n个记录各比较一次

另外，还要和监视哨比较一次

所以查找失败需要和关键字比较的次数是n+1

这个可以称为顺序表查找失败的平均查找长度

对顺序表的查找来说

不管是成功还是失败

ASL都是线性的，效率不高

后续我们会讨论效率更好的算法

好，同学们，这节课我们就介绍到这儿

下次课再见