第六章查找 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 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 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 const Type vector: operator [( int index)const i Exception( index≤0‖ index> Arraysize,“ Out of boundary!”); return Arraylindex template const Vector& Vector:: operator =( const Vector 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 const Type & Vector :: operator [ ] ( int index ) const { Exception( index ≤0 || index > ArraySize, “Out of boundary!”); return Array[index]; } template const Vector & Vector :: operator = ( const Vector 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 void Vector: Resize( int NewSize Type s oldArray =Array const int minsize=Min( ArraySize, NewSize);∥取二者小者 ArraySIze NewSize Get Array( forint k=1; k void Vector: Get Array )i Array =new Type[ArraySize+1 template Vector:: Vector( int Size)( ArraySize Size; GetArray(
静态查找表(ADT) • 部分操作的实现： template void Vector :: Resize( int NewSize ){ Type * oldArray = Array; const int minsize = Min(ArraySize, NewSize); // 取二者小者。 ArraySize = NewSize; GetArray( ); for(int k = 1; k void Vector :: GetArray( ){ Array = new Type[ArraySize+1]; } template Vector :: Vector( int Size){ ArraySize = Size; GetArray( ); }
顺序查找 应用范围:顺序表或线性链表表示的静杰查找表。表内元素之间无序或有序。 template int SeqSearch( const Vector&A, const Type key, int N A[0=key;∥将待査key置于哨兵单元,可省掉越界检査。 设置哨兵的好处: for(int k=N; Ak!= key;--k) 在顺序表中总可以找到 return k; 待查结点。否则,必须将 ∥返回0,查找失败。否则,找到关键字为key的结点的下标 判断条件i>=0加进for 语句。 eg:查找x=8的结点所在的数组元素的下标 key 向量 Vector810010 3 2 n-3n-2n-1n
顺序查找 • 应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。 ……………… 0 1 2 n-3 n-2 n-1 n i 向量 Vector key e.g: 查找 x = 8 的结点所在的数组元素的下标。 8 100 10 0 7 1 3 设置哨兵的好处： 在顺序表中总可以找到 待查结点。否则，必须将 判断条件i >= 0 加进 for 语句。 template int SeqSearch( const Vector & A, const Type key,int N ){ A[0] = key; // 将待查 key 置于哨兵单元，可省掉越界检查。 for ( int k = N; A[k] != key; --k ) return k; // 返回0，查找失败。否则，找到关键字为key 的结点的下标 }
顺序查找 应用范围:顺序表或线性链表表示的静杰查找表。表内元素之间无序或有序。 template int SeqSearch( const Vector&A, const Type key, int N A[0=key;∥将待査key置于哨兵单元,可省掉越界检査。 设置哨兵的好处: for(int k=N; Ak!= key;--k) 在顺序表中总可以找到 return k; 待查结点。否则,必须将 ∥返回0,查找失败。否则,找到关键字为key的结点的下标 判断条件i>=0加进for 语句。 eg:查找x=8的结点所在的数组元素的下标 key 向量 Vector810010 3 2 n-3n-2n-1n
顺序查找 • 应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。 ……………… 0 1 2 n-3 n-2 n-1 n i 向量 Vector key e.g: 查找 x = 8 的结点所在的数组元素的下标。 8 100 10 0 7 1 3 设置哨兵的好处： 在顺序表中总可以找到 待查结点。否则，必须将 判断条件i >= 0 加进 for 语句。 template int SeqSearch( const Vector & A, const Type key,int N ){ A[0] = key; // 将待查 key 置于哨兵单元，可省掉越界检查。 for ( int k = N; A[k] != key; --k ) return k; // 返回0，查找失败。否则，找到关键字为key 的结点的下标 }
顺序查找 应用范围:顺序表或线性链表表示的静杰查找表。表内元素之间无序或有序。 template int SeqSearch( const Vector&A, const Type key, int N A[0=key;∥将待査key置于哨兵单元,可省掉越界检査。 设置哨兵的好处: for(int k=N; Ak!= key;--k) 在顺序表中总可以找到 return k; 待查结点。否则,必须将 ∥返回0,查找失败。否则,找到关键字为key的结点的下标 判断条件i>=0加进for 语句。 eg:查找x=8的结点所在的数组元素的下标 key 向量 Vector810010 3 2 n-3n-2n-1n
顺序查找 • 应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。 ……………… 0 1 2 n-3 n-2 n-1 n i 向量 Vector key e.g: 查找 x = 8 的结点所在的数组元素的下标。 8 100 10 0 7 1 3 设置哨兵的好处： 在顺序表中总可以找到 待查结点。否则，必须将 判断条件i >= 0 加进 for 语句。 template int SeqSearch( const Vector & A, const Type key,int N ){ A[0] = key; // 将待查 key 置于哨兵单元，可省掉越界检查。 for ( int k = N; A[k] != key; --k ) return k; // 返回0，查找失败。否则，找到关键字为key 的结点的下标 }
顺序查找 应用范围:顺序表或线性链表表示的静杰查找表。表内元素之间无序或有序。 template int SeqSearch( const Vector&A, const Type key, int N A[0=key;∥将待査key置于哨兵单元,可省掉越界检査。 设置哨兵的好处: for(int k=N; Ak!= key;--k) 在顺序表中总可以找到 return k; 待查结点。否则,必须将 ∥返回0,查找失败。否则,找到关键字为key的结点的下标 判断条件i>=0加进for 语句。 eg:查找x=8的结点所在的数组元素的下标 key 向量 Vector810010 3 2 n-3n-2n-1n
顺序查找 • 应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。 ……………… 0 1 2 n-3 n-2 n-1 n i 向量 Vector key e.g: 查找 x = 8 的结点所在的数组元素的下标。 8 100 10 0 7 1 3 设置哨兵的好处： 在顺序表中总可以找到 待查结点。否则，必须将 判断条件i >= 0 加进 for 语句。 template int SeqSearch( const Vector & A, const Type key,int N ){ A[0] = key; // 将待查 key 置于哨兵单元，可省掉越界检查。 for ( int k = N; A[k] != key; --k ) return k; // 返回0，查找失败。否则，找到关键字为key 的结点的下标 }
顺序查找 应用范围:顺序表或线性链表表示的静杰查找表。表内元素之间无序或有序。 template int SeqSearch( const Vector&A, const Type key, int N A[0=key;∥将待査key置于哨兵单元,可省掉越界检査。 设置哨兵的好处: for(int k=N; Ak!= key;--k) 在顺序表中总可以找到 return k; 待查结点。否则,必须将 ∥返回0,查找失败。否则,找到关键字为key的结点的下标 判断条件i>=0加进for 语句。 eg:查找X=8的结点所在的数组元素的下标 key 向量 Vector810010 3 2 n-3n-2n-1n
顺序查找 • 应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序或有序。 ……………… 0 1 2 n-3 n-2 n-1 n i 向量 Vector key e.g: 查找 x = 8 的结点所在的数组元素的下标。 8 100 10 0 7 1 3 设置哨兵的好处： 在顺序表中总可以找到 待查结点。否则，必须将 判断条件i >= 0 加进 for 语句。 template int SeqSearch( const Vector & A, const Type key,int N ){ A[0] = key; // 将待查 key 置于哨兵单元，可省掉越界检查。 for ( int k = N; A[k] != key; --k ) return k; // 返回0，查找失败。否则，找到关键字为key 的结点的下标 }
