第10章索引与散列 定值x来搜索一个大小为m的散列表。如果x不在表中,则将它插入到表中。 【解答】 (1)将探查序列分两部分讨论: (h+q2),(h+(q-1)2),…,(h+1),h和(h-1),(h-2),…,(h-q2)。 对于前一部分,设其通项为h+(q-d),d=0,1,…,q,则相邻两个桶之间地址相减所 得的差取模: (h+(q-(d-1)2-(h+(q-d)2))%m=((q-(d-1))2-(q-d)2)%m (2*q-2*d+1)%m=(m-2*d)%m.(代换q=(m-1)2) 代入d=1,2,…,q,则可得到探查序列如下 对于后一部分,其通项为h-(q-d)2,d=q,q+1,…,2q,则相邻两个桶之间地址相减 所得的差取模: (h-(q-d)2-(h-(q-(d+1)2))%m=((q-(d+1)2-(q-d)2)%m =(2+d-2*q+1)%m=(2*d-m+2)%m(代换q=(m-1)/2) 代入d=q,q+1,…,2q-1,则可得到 2*d-m+2=2*q-m+2=m-1-m+2=1, 2d-m+2=2*q+2-m+2=m-1+2-m+2=3,… 2+d-m+2=2*(2*q-1)-m+2=2+m-1-1)-m+2=2m-4-m+2=m-2。〖证毕〗 (2)编写算法 下面是使用二次探查法处理溢出时的散列表类的声明。 template <class Type> class Hash Table i /散列表类的定义 enum KindofEntry Active, Empty, Deleted 3: ∥表项分类(活动/空/删) HashTable(): Tables ize( DefaultS ize){ Allocate(; Currentsize=0;}∥构造函数 - HashTable (i delete [ht; ∥析构函数 const hashTable& operator=( const hashTable&h2);∥重载函数:表赋值 int Find( const Type &x ); ∥在散列表中搜索 int IsEmpty(return I CurrentSize ?1: 0; 3 ∥判散列表空否,空则返回1 priva struct HashEntry i 散列表的表项定义 pe Element; ∥表项的数据,即表项的关键码 KindofEntry info; 三种状态: Active, Empty, Deleted HashEntry () info(Empty) ∥表项构造函数 }; HashEntry *ht; /散列表存储数组 ∥数组长度,要求是满足4k+3的质数,k是整数 已占据散列地址数目 void AllocateHt){ht= new HashEntry[ Tablesize;}∥为散列表分配存储空间; nt FindPos( const Type &x ) /散列函数 template <class Type> const Hash Table<type>& Hash Table<Type operator=( const Hash Table<Type>&ht2)i ∥重载函数:复制一个散列表h2第 10 章 索引与散列 8 定值 x 来搜索一个大小为 m 的散列表。如果 x 不在表中，则将它插入到表中。 【解答】 (1) 将探查序列分两部分讨论： (h + q2 ), (h + (q-1)2 ), …, (h+1), h 和 (h-1), (h-2 2 ), …, (h-q 2 )。 对于前一部分，设其通项为 h + ( q – d ) 2 , d = 0, 1, …, q，则相邻两个桶之间地址相减所 得的差取模： ( h + (q – (d -1) )2 – ( h + (q – d )2 ) ) % m = ( (q – (d -1 ) )2 – (q – d )2 ) % m = (2*q -2*d +1) % m = ( m – 2*d ) % m. ( 代换 q = (m-1)/2 ) 代入 d = 1, 2, …, q，则可得到探查序列如下： m-2, m-4, m-6, …, 5, 3, 1。 ( m – 2*q = m – 2* (m-1)/2 = 1 ) 对于后一部分，其通项为 h – ( q – d )2 , d = q, q+1, …, 2q，则相邻两个桶之间地址相减 所得的差取模： ( h – ( q – d )2 – ( h – ( q – (d+1) )2 ) ) % m = ( ( q – (d+1)2 – (q – d )2 ) % m = ( 2*d – 2*q +1) % m = ( 2*d – m + 2) % m ( 代换 q = (m-1)/2 ) 代入 d = q, q+1, …, 2q-1，则可得到 2*d–m+2 = 2*q – m +2 = m – 1 – m +2 = 1, 2*d–m+2 = 2*q + 2 – m +2 = m – 1 + 2 – m +2 = 3, ……, 2*d–m+2 = 2*(2*q-1) – m +2 = 2*(m–1–1) – m + 2 = 2*m – 4 – m +2 = m – 2。〖证毕〗 (2) 编写算法 下面是使用二次探查法处理溢出时的散列表类的声明。 template <class Type> class HashTable { //散列表类的定义 public: enum KindOfEntry { Active, Empty, Deleted }; //表项分类 (活动 / 空 / 删) HashTable ( ) : TableSize ( DefaultSize ) { AllocateHt ( ); CurrentSize = 0; } //构造函数 ~HashTable ( ) { delete [ ] ht; } //析构函数 const HashTable & operator = ( const HashTable & ht2 ); //重载函数：表赋值 int Find ( const Type & x ); //在散列表中搜索 x int IsEmpty ( ) { return !CurrentSize ? 1 : 0; } //判散列表空否，空则返回 1 private: struct HashEntry { //散列表的表项定义 Type Element; //表项的数据, 即表项的关键码 KindOfEntry info; //三种状态: Active, Empty, Deleted HashEntry ( ) : info (Empty ) { } //表项构造函数 HashEntry ( const Type &E, KindOfEntry i = Empty ) : Element (E), info (i) { } }; enum { DefualtSize = 31; } HashEntry *ht; //散列表存储数组 int TableSize; //数组长度，要求是满足 4k+3 的质数，k 是整数 int CurrentSize; //已占据散列地址数目 void AllocateHt ( ) { ht = new HashEntry[TableSize ]; } //为散列表分配存储空间; int FindPos ( const Type & x ); //散列函数 }; template <class Type> const HashTable<Type> & HashTable<Type> :: operator = ( const HashTable<Type> &ht2 ) { //重载函数：复制一个散列表 ht2