文档介绍：第九章查找表
查找表
是由同一类型的数据元素(或记录)构成的集合。
对查找表经常进行的操作:
1)查询某个“特定的”数据元素是否在查找表中;
2)检索某个“特定的”数据元素的各种属性;
3)在查找表中插入一个数据元素;
4)从查找表中删去某个数据元素。
静态查找表
仅作上述1)和2)操作的查找表
动态查找表
有时在查询之后,还需要将“查询”结果为“不在查找表中”的数据元素插入查找表;或者,从查找表中删除其“查询”结果为“在查找表中”的数据元素
关键字
是数据元素(或记录)中某个数据项的值,用以标识(识别)一个数据元素(或记录)
若此关键字可以识别唯一的一个记录,则称之谓“主关键字”
若此关键字能识别若干记录,则称之谓“次关键字”
查找
根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素或(记录)
若查找表中存在这样一个记录,则称“查找成功”,查找结果:给出整个记录的信息,或指示该记录在查找表中的位置;否则称“查找不成功”,查找结果:给出“空记录”或“空指针”
如何进行查找?
取决于查找表的结构,即:记录在查找表中所处的位置。
然而,查找表本身是一种很松散的结构,因此,为了提高查找的效率,需要在查找表中的元素之间人为地附加某种确定的关系,换句话说,用另外一种结构来表示查找表。
本章讨论的重点:
查找表的各种表示方法及其相应的查找算法
静态查找表
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
C++
的语言描述:
template<class Elem>
class SSTable
{
public:
virtual Elem *Search(KeyType key);
// 若静态查找表中存在其关键字和key相等的
// 元素,则返回指向该元素的指针,否则返回
//“空”指针。
virtual void Traverse(void visit(Elem& item));
// 按某种次序对静态查找表中每个元素调用
// 函数visit( )一次且仅一次。
}; // SSTable
下面讨论静态查找表的各种实现方法
一、顺序查找表
以顺序表或线性链表表示静态查找表
template<class Elem>
class SqSTable:public SSTable
{
private:
SqList< Elem > ST;
public:
SqSTable(int size); // 构造函数
SqSTable(SqSTable ra); // 复制构造函数
SqSTable(int size, const Elem * elemVal);
// 构造一个含size个元素的静态查找表,
// 其元素值由elemVal给出。
~SqSTable(void){}; // 析构函数
virtual Elem *Search(KeyType key);
// 若顺序查找表中存在其关键字和 key相等
// 的数据元素,则返回指向该元素的指针,
// 否则返回“空指针”。
virtual void Traverse(void visit(Elem& item));
// 对顺序查找表中每个元素,依次顺序调用函数
// visit一次,并且仅调用一次
}; // SqSTable
在此重点讨论“查找”算法的实现。
template<class Elem>
Elem *SqSTable<Elem>::Search(KeyType k