第9章查找表.ppt

第九章查找表
静态查找表
动态查找表
哈希表
本章小结
习题九
基本术语:
查找表:由同一类型的数据元素(或记录)构成的集合。
对查找表经常进行的操作:
1)查询某个“特定的”数据元素是否在查找表中;
2)检索某个“特定的”数据元素的各种属性;
3)在查找表中插入一个数据元素;
4)从查找表中删除某个数据元素。
静态查找表、动态查找表、关键字、主关键字、次关键字、查找、查找成功、查找不成功、查找不成功
仅作查询和检索操作的查找表。
静态查找表
有时在查询之后,还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中;或者,从查找表中删除其“查询”结果为“在查找表中”的数据元素。
动态查找表
是数据元素(或记录)中某个数据项的值,用以标识(识别)一个数据元素(或记录)。
关键字:
若此关键字可以识别唯一的一个记录,则称之谓“主关键字”。
若此关键字能识别若干记录,则称
之谓“次关键字”。
根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素或(记录)
查找:
若查找表中存在这样一个记录,则称“查找成功”,查找结果:给出整个记录的信息,或指示该记录在查找表中的位置;
否则称“查找不成功”,查找结果:给出“空记录”或“空指针”。
由于查找表中的数据元素之间不存在明显的组织规律,因此不便于查找。
为了提高查找的效率, 需要在查找表中的元素之间人为地附加某种确定的关系,换句话说, 用另外一种结构来表示查找表。
如何进行查找?
查找的方法取决于查找表的组织形式。
静态查找表
动态查找树表
哈希表
本章一些约定:
典型的关键字类型说明可以是:
typedef float KeyType ; // 实型
typedef int KeyType ; // 整型
typedef char* KeyType ; // 字符串型
数据元素类型的定义:
Typedef struct {
KeyType key ;//关键字
…//其它域
} ElemType ;
对两个关键字的比较:
//对数值型关键字
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))
//对字符串型关键字
#define EQ(a,b) (!strcmp((a),(b)))
#define LT(a,b) (strcmp((a),(b))<0)
#define LQ(a,b) (strcmp((a),(b))<=0)
数据对象D:
数据关系R:
D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字,可唯一标识数据元素。
数据元素同属一个集合。
ADT StaticSearchTable {
静态查找表
基本操作 P:
构造一个含 n 个数据元素的静态查找表ST。
Create(&ST, n);
操作结果:
销毁表ST。
Destroy(&ST);
初始条件:
静态查找表ST存在;
操作结果:
} ADT StaticSearchTable
若 ST 中存在其关键字等于key 的数据元素,则函数值为该元素的值或在表中的位置,否则为“空”。
Search(ST, key);
初始条件:
操作结果:
静态查找表ST存在,kval 为和查找表中元素的关键字类型相同的给定值;
按某种次序对ST的每个元素调用函数Visit( )一次且仅一次,一旦Visit( )失败,则操作失败。
Traverse(ST, Visit( ));
初始条件:
操作结果:
静态查找表ST存在,Visit是对元素操作的应用函数;
//------静态查找表的顺序存储结构-------
typedef struct {
ElemType *elem;// 数据元素存储空间基址,建表时
// 按实际长度分配,0号单元留空
int length; // 表的长度
}SSTable;
顺序表的查找(顺序存储)
数据元素类型的定义:
Typedef struct {
KeyType key ;//关键字
…//其它域
} ElemType ;
顺序查找?
顺序表或线性链表