第六章查找 61静态查找技术 62二叉排序树 63平衡二叉排序树(AVL树) 64红-黑树 265B树和B+树 66哈希(Hash)方法
6.1 静态查找技术 6.2 二叉排序树 6.3 平衡二叉排序树(AVL树) *6.4 红-黑树 *6.5 B-树和B+树 6.6 哈希(Hash)方法 第 六 章 查找
静态查找技术 搜索 在数据集合之中,搜索具有特定关键字的结点。 ·通常分为静态搜索表:集合中的结点总数是固定的或者很少发生变化。可以无序或组 织成有序表。 动态搜索表:集合中的结点总数是经常在发生变化。组织成树形结构。 在内存中进行的搜索:重点减少比较、或查找的次数。评价标准:平均搜索长度。 在外存中进行的搜索:重点在于减少访问外存的次数。评价标准:读盘次数 2、静态搜索结构: 采用静态向量(或数组),0号单元用作哨兵单元,1号单元到n号单元保存结点。 哨兵单元 Vector: 8 10010 2 n-3n-2n-1n
静态查找技术 1、搜索: • 在数据集合之中,搜索具有特定关键字的结点。 • 通常分为静态搜索表:集合中的结点总数是固定的或者很少发生变化。可以无序或组 织成有序表。 动态搜索表:集合中的结点总数是经常在发生变化。组织成树形结构。 • 在内存中进行的搜索:重点减少比较、或查找的次数。评价标准:平均搜索长度。 • 在外存中进行的搜索:重点在于减少访问外存的次数。评价标准:读盘次数。 2、静态搜索结构: ……………… 0 1 2 n-3 n-2 n-1 n i Vector 哨兵单元 采用静态向量(或数组),0号单元用作哨兵单元,1号单元到n号单元保存结点。 8 100 10 0 7 1 3
静态查找表(ADT template <class type> class Vector i Vector( int size),∥/构造函数,静态査找表的结点个数为size Vector(( delete Array,) const Type& operator[]( int index) const,∥具有越界检查的下标操作。 const vector& operator=( const vector&R),∥大小相等的向量的复制。 int Length() const( return ArraySize,) void Double(){ Resize( ArraySize*2);}∥在向量的单元用完时,容量加倍 void Resize( int Newsize) ∥/修改向量的大小。 void Sentinel(( const Type key){Aray[0]=key,}∥置0号单元的内容为待查key rotected: Type*Aray,∥保存结点的数组 int Arraysize;∥/大小 void Get Array () Vector( const Vector&R);∥/冻结使用构造函数复制另一向量的功能
静态查找表(ADT) template <class Type> class Vector { public: Vector ( int size); // 构造函数,静态查找表的结点个数为 size. ~ Vector ( ) { delete [ ]Array; } const Type & operator [ ] ( int index ) const; //具有越界检查的下标操作。 const Vector & operator = ( const Vector & R); //大小相等的向量的复制。 int Length( ) const { return ArraySize; } void Double( ) { Resize( ArraySize * 2 );} // 在向量的单元用完时,容量加倍。 void Resize( int Newsize); // 修改向量的大小。 void Sentinel( const Type key ){ Array[0] = key; } //置0号单元的内容为待查 key。 protected: Type * Array; // 保存结点的数组 int ArraySize; // 大小。 void GetArray( ); Vector(const Vector & R ); // 冻结使用构造函数复制另一向量的功能。 };
静态查找表(ADT) 部分操作的实现: template <class Type> const Type vector< Type>: operator [( int index)const i Exception( index≤0‖ index> Arraysize,“ Out of boundary!”); return Arraylindex template <class Tvpe> const Vector< Type>& Vector< Type>:: operator =( const Vector< Type> R )i if( this I=&R)( Exception( arraySize I=R ArraySize, " Size is not same!); forint k=1; k <= ArraySize,, k++) Arraylk]=r. arraylk] return *this
静态查找表(ADT) • 部分操作的实现: template <class Type> const Type & Vector<Type> :: operator [ ] ( int index ) const { Exception( index ≤0 || index > ArraySize, “Out of boundary!”); return Array[index]; } template <class Type> const Vector<Type> & Vector<Type> :: operator = ( const Vector<Type> R ){ if ( this != &R ) { Exception( ArraySize != R.ArraySize, “Size is not same!”); for(int k = 1; k <= ArraySize; k++ ) Array[k] = R.Array[k]; } return *this; }
静态查找表(ADT) 部分操作的实现: template <class Type> void Vector< Type>: Resize( int NewSize Type s oldArray =Array const int minsize=Min( ArraySize, NewSize);∥取二者小者 ArraySIze NewSize Get Array( forint k=1; k<= minsize; k++)Array[]=oldArrayk delete joldArray; template <class Type> void Vector< Type>: Get Array )i Array =new Type[ArraySize+1 template <class Type> Vector<Type>:: Vector( int Size)( ArraySize Size; GetArray(
静态查找表(ADT) • 部分操作的实现: template <class Type> void Vector<Type> :: Resize( int NewSize ){ Type * oldArray = Array; const int minsize = Min(ArraySize, NewSize); // 取二者小者。 ArraySize = NewSize; GetArray( ); for(int k = 1; k <= minsize; k++ ) Array[k] = oldArray[k]; delete [ ]oldArray; } template <class Type> void Vector<Type> :: GetArray( ){ Array = new Type[ArraySize+1]; } template <class Type> Vector<Type> :: Vector( int Size){ ArraySize = Size; GetArray( ); }