《数据结构》第七章 搜索结构.ppt

1
第七章搜索结构
数据结构电子教案
2
静态搜索表
二叉搜索树
最优二叉搜索树
AVL树
伸展树
红黑树
第七章搜索结构
3
搜索(Search)的概念
静态搜索表
所谓搜索,就是在数据集合中寻找满足某种条件的数据对象。
搜索的结果通常有两种可能:
搜索成功,即找到满足条件的数据对象。这时,作为结果,可报告该对象在结构中的位置, 还可给出该对象中的具体信息。
搜索不成功,或搜索失败。作为结果,应报告一些信息, 如失败标志、位置等。
4
通常称用于搜索的数据集合为搜索结构,它是由同一数据类型的对象(或记录)组成。
在每个对象中有若干属性,其中有一个属性,其值可唯一地标识这个对象。称为关键码。使用基于关键码的搜索,搜索结果应是唯一的。但在实际应用时,搜索条件是多方面的,可以使用基于属性的搜索方法,但搜索结果可能不唯一。
实施搜索时有两种不同的环境。
静态环境,搜索结构在插入和删除等操作的前后不发生改变。静态搜索表
5
动态环境,为保持较高的搜索效率, 搜索结构在执行插入和删除等操作的前后将自动进行调整,结构可能发生变化。
动态搜索表
在静态搜索表中,数据元素存放于数组中,利用数组元素的下标作为数据元素的存放地址。搜索算法根据给定值 k,在数组中进行搜索。直到找到 k 在数组中的存放位置或可确定在数组中找不到 k 为止。
静态搜索表
6
数据表与搜索表的类定义
#include <>
#include <>
const int defaultSize = 100;
template <class E, class K>
class dataList; //数据表类的前视定义
template <class E, class K >
class dataNode { //数据表中结点类的定义
friend class dataList<E, K>; //声明其友元类为dataList
public:
7
dataNode (const K x) : key(x) { } //构造函数
K getKey() const { return key; } //读取关键码
void setKey (K x) { key = x; } //修改关键码
private:
K key; //关键码域
E other; //其他域(视问题而定)
};
template <class E, class K >
class dataList { //数据表类定义
public:
8
dataList (int sz = defaultSize)
: ArraySize(sz), CuurentSize(0) {
Element = new dataNode<E, K>[sz];
assert (Element != NULL);
}
dataList (dataList<E, K>& R); //复制构造函数
virtual ~dataList() { delete []Element; }
//析构函数
virtual int Length() { return CurrentSize; }
//求表的长度
virtual K getKey (int i) const { //提取第 i(1开始)元素值
9
assert (i > 0 || i <= CurrentSize);
return Element[i-1].key;
}
virtual void setKey (K x, int i) { //修改第 i(1开始)元素值
assert (i > 0 || i <= CurrentSize);
Element[i-1].key = x;
}
virtual int SeqSearch (const K x) const; //搜索
virtual bool Insert (E& e1); //插入
virtual bool Remove (K x, E& e1); //删除
friend ostream& operator << (ostream& out,
const dataList<E, K>& OutList); //输出
10
friend istream& operator >> (istream& in,
dataList<E, K>& InList); //输入
protected:
dataNode<E, K> *Element; //数据表存储数组
int ArraySize, CurrentSize; //数组最大长度和当前长度
};
templat