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