顺序查找:静态查找表（一）顺序表的查找

教学目:

查找表:

是由同类型数据元素(或记录)构成集合

查找表操作:

1、查询某个“特定”数据元素是否在查找表中
2、检索某个“特定”数据元素各种属性
3、在查找表中插入个数据元素；
4、从查找表中刪去某个数据元素

静态查找表

对查找表只作前两种操作

动态查找表

在查找过程中查找表元素集合动态改变

关键字

是数据元素(或记录)中某个数据项值

主关键字

可以唯地标识个记录

次关键字

用以识别若干记录

查找

根据给定某个值在查找表中确定个其关键字等于给定记录或数据元素若表中存在这样个记录则称查找是成功此时查找结果为给出整个记录信息或指示该记录在查找表中位置；若表中不存在关键字等于给定值记录则称查找不成功

些约定:

典型关键字类型介绍说明:

typedef float KeyType;//实型
typedef KeyType;//整型
typedef char *KeyType;//串型

数据元素类型定义为:

typedef struct{
KeyType key; // 关键字域
...
}ElemType;

对两个关键字比较约定为如下宏定义:

对数值型关键字
# EQ(a,b) ((a)(b))
# LT(a,b) ((a)<(b))
# LQ(a,b) ((a)<=(b))

对串型关键字
# EQ(a,b) (!strcmp((a),(b)))
# LT(a,b) (strcmp((a),(b))<0)
# LQ(a,b) (strcmp((a),(b))<=0)

静态查找表类型定义:

ADT StaticSearchTable{

数据对象D:D是具有相同特性数据元素集合各个数据元素均含有类型相同可唯标识数据元素关键字

数据关系R:数据元素同属个集合

基本操作P:

Create(&ST,n);

操作结果:构造个含n个数据元素静态查找表ST

Destroy(&ST);

条件:静态查找表ST存在

操作结果:销毁表ST

Search(ST,key);

条件:静态查找表ST存在key为和关键字类型相同给定值

操作结果:若ST中在在其关键字等于key数据元素则值为该元素值或在表中位置否则为“空”

Traverse(ST,Visit);

条件:静态查找表ST存在Visit是对元素操作应用

操作结果:按某种次序对ST每个元素visit次且仅次旦visit失败则操作失败

}ADT StaticSearchTable

静态查找表顺序存储结构

typedef struct {

ElemType *elem;

length;

}SSTable;

顺序查找:从表中最后个记录开始逐个进行记录关键字和给定值比较若某个记录关键字和给定值比较相等则查找成功找到所查记录；反的查找不成功

Search_Seq(SSTable ST,KeyType key){

ST.elme[0].key=key;

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

i;



}

查找操作性能分析:

查找算法中基本操作是将记录关键字和给定值进行比较通常以“其关键字和给定值进行过比较记录个数平均值”作为衡量依据

平均查找长度:

为确定记录在查找表中位置需用和给定值进行比较关键字个数期望值称为查找算法在查找成功时平均查找长度

其中:Pi为查找表中第i个记录概率且；

Ci为找到表中其关键字和给定值相等第i个记录时和给定值已进行过比较关键字个数



等概率条件下有:



假设查找成功和不成功概率相同:

什么是查找表

顺序表查找过程

延伸阅读