数据结构C语言版查找.pptVIP

1

1065

865

A

B

D

C

E

G

F

第章查找2

学习提要9

本章中介绍下列主要内容：

静态查找表及查找算法：顺序查找、折半查找

动态查找表及查找算法：二叉排序树

哈希表及查找算法

3

学习提要（具体来讲）

１.熟练掌握顺序表和有序表的查找方法。

２.熟练掌握二叉排序树的构造和查找方法。

３.掌握二叉平衡树的维护平衡方法。

４.理解树的特点以及它们的建树过程。

５.熟练掌握哈希表的构造方法，深刻理解哈

希表与其它结构的表的实质性的差别。

６.掌握描述查找过程的判定树的构造方法，

以及按定义计算各种查找方法在等概率情况下

查找成功时的平均查找长度。

4

基本概念

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

表。查找表由同一类型的数据元素（或记录）

构成。

静态查找表若只对查找表进行如下两种操

作：（1）在查找表中查看某个特定的数据元素

是否在查找表中，（2）检索某个特定元素的各

种属性，则称这类查找表为静态查找表。静态

查找表在查找过程中查找表本身不发生变化。

对静态查找表进行的查找操作称为静态查找。

5

动态查找表：若在查找过程中可以将查找

表中不存在的数据元素插入，或者从查找表中

删除某个数据元素，则称这类查找表为动态查

找表。动态查找表在查找过程中查找表可能会

发生变化。对动态查找表进行的查找操作称为

动态查找。

关键字：是数据元素中的某个数据项。唯

一能标识数据元素（或记录）的关键字，即每

个元素的关键字值互不相同，我们称这种关键

字为主关键字；若查找表中某些元素的关键字

值相同，称这种关键字为次关键字。例如，银

行帐户中的帐号是主关键字，而姓名是次关键

字。

6

查找：在数据元素集合中查找满足某种条

件的数据元素的过程称为查找。最简单且最常

用的查找条件是“关键字值等于某个给定值”

，在查找表有哪些信誉好的足球投注网站关键字等于给定值的数据元素

（或记录）。若表中存在这样的记录，则称查

找成功，此时的查找结果应给出找到记录的全

部信息或指示找到记录的存储位置；若表中不

存在关键字等于给定值的记录，则称查找不成

功，此时查找的结果可以给出一个空记录或空

指针。若按主关键字查找，查找结果是唯一的

；若按次关键字查找，结果可能是多个记录，

即结果可能不唯一。

7

8

查找表的存储结构：查找表是一种非常灵活的

数据结构，对于不同的存储结构，其查找方法

不同。为了提高查找速度，有时会采用一些特

殊的存储结构。本章将介绍以线性结构、树型

结构及哈希表结构为存储结构的各种查找算法

。

查找算法的时间效率：查找过程的主要操作

是关键字的比较，所以通常以“平均比较次数

”来衡量查找算法的时间效率。

9

9.1静态查找表

9.1.1.顺序查找（线性查找）

静态查找是指在静态查找表上进行的查找

操作，在查找表中查找满足条件的数据元素的

存储位置或各种属性。本节将讨论以线性结构

表示的静态查找表及相应的查找算法。

10

顺序查找的基本思想：

顺序查找是一种最简单的查找方法。其基本

思想是将查找表作为一个线性表，可以是顺序

表，也可以是链表，依次用查找条件中给定的

值与查找表中数据元素的关键字值进行比较，

若某个记录的关键字值与给定值相等，则查找

成功，返回该记录的存储位置，反之，若直到

最后一个记录，其关键字值与给定值均不相等

，则查找失败，返回查找失败标志。

11

查找过程：

对给定的一关键字K，从线性表的一端开始，逐个进

行记