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