——类C描述
数据结构 DATA STRUCTURE
——类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
=
本节结束