——类C描述

数据结构 DATA STRUCTURE

点击添加相关标题文字 《数据结构》

A D D R E L A T E D T I T L E W O R D S

顺序查找

查找表是由同一类型的数据元素(或记录)构成的集合。

何谓查找表 ？

由于“集合”中的数据元素之间存在着松散的关系，因此查找表是

一种应用灵便的结构。

点击添加相关标题文字 《数据结构》

A D D R E L A T E D T I T L E W O R D S

顺序查找

1)查询某个“特定的”数据元素是否在查找表中；

对查找表经常进行的操作:

2)检索某个“特定的”数据元素的各种属性；

3)在查找表中插入一个数据元素；

4)从查找表中删去某个数据元素。

点击添加相关标题文字 《数据结构》

A D D R E L A T E D T I T L E W O R D S

顺序查找

◆ 静态查找表

查找表可分为两类:

◆ 动态查找表

仅作查询和检索操作的查找表为静态查找表。

有时在查询之后，还需要将“查询”结果为“不在查找表中”

的数据元素插入到查找表中；或者，从查找表中删除其“查询”

结果为“在查找表中”的数据元素,此类表为动态查找表。

点击添加相关标题文字 《数据结构》

A D D R E L A T E D T I T L E W O R D S

顺序查找

◆ 关键字

查找表可分为两类:

◆ 主关键字

用来标识一个数据元素（或记录）的某个数据项的值，称为关键

字。

若此关键字可唯一地标识一个记录，则称此关键字是主关键字；

◆ 次关键字

反之，用以识别若干记录的关键字是次关键字。

点击添加相关标题文字 《数据结构》

A D D R E L A T E D T I T L E W O R D S

顺序查找

◆ 查找

查找表可分为两类:

根据给定的某个值，在查找表中确定一个其关键字等于给定

值的数据元素或(记录)

若查找表中存在这样一个记录，则称“查找成功”。查找结果给

出整个记录的信息，或指示该记录在查找表中的位置；

否则称“查找不成功”。查找结果给出“空记录”或“空指针”。

点击添加相关标题文字 《数据结构》

A D D R E L A T E D T I T L E W O R D S

顺序查找

假设静态查找表的顺序存储结构为

typedef struct {

ElemType *elem;

// 数据元素存储空间基址，建表时

// 按实际长度分配，0号单元留空

int length; // 表的长度

} SSTable;

点击添加相关标题文字 《数据结构》

A D D R E L A T E D T I T L E W O R D S

顺序查找

数据元素类型的定义为:

typedef struct {

keyType key; // 关键字域

… … // 其它属性域

} ElemType ; TElemType ;

点击添加相关标题文字 《数据结构》

A D D R E L A T E D T I T L E W O R D S

顺序查找

一、顺序查找表

以顺序表或线性链表表示静态查找表

点击添加相关标题文字 《数据结构》

A D D R E L A T E D T I T L E W O R D S

顺序查找

21 37 88 19 92 05 64 56 80 75 13

0 1 2 3 4 5 6 7 8 9 10 11

ST.Length

ST.elem i

21 37 88 19 92 05 64 56 80 75 13

0 1 2 3 4 5 6 7 8 9 10 11

ST.Length

ST.elemi

60

i

key=64

key=60

i

64

点击添加相关标题文字 《数据结构》

A D D R E L A T E D T I T L E W O R D S

顺序查找

int Search_Seq(SSTable ST,

KeyType key) {

// 在顺序表ST中顺序查找其关键字等于

// key的数据元素。若找到，则函数值为

// 该元素在表中的位置，否则为0。

ST.elem[0].key = key; // “哨兵”

for (i=ST.length; ST.elem[i].key!=key; --i);

// 从后往前找

return i; // 找不到时，i为0

} // Search_Seq

点击添加相关标题文字 《数据结构》

A D D R E L A T E D T I T L E W O R D S

顺序查找

分析顺序查找的时间性能

查找算法的平均查找长度 (Average Search Length)

为确定记录在表中的位置，需和给定值进行比较的关键字次数的

期望值称为查找算法在查找成功时的平均查找长度。

点击添加相关标题文字 《数据结构》

A D D R E L A T E D T I T L E W O R D S

顺序查找

对于含有n个数据元素的表,查找成功时的平均查找长度为:

n

ASL=ΣPiCi

i=1

其中:Pi为查找第i个数据元素的概率,且

1

1

 =

=

n

i

Pi

Ci为查到第i个数据元素时,需要进行的比较次数.

点击添加相关标题文字 《数据结构》

A D D R E L A T E D T I T L E W O R D S

顺序查找

对顺序表而言， Ci取决于所查元素所处的位置：

-查找记录是A[n]时,仅需比较一次;

-查找记录是A[1]时,要比较n次;

-查找记录是A[i]时,要比较n-i+1次.

ASL = nP1 +(n-1)P2 + … +2Pn-1+Pn

2

1

1

1

1

+

=  − + =

=

n

(n i )

n

ASL

n

i

s s

在等概率查找的情况下，

顺序表查找的平均查找长度为：

n

Pi

1

=

本节结束