第10章索引与散列 if( this I=&ht2)t delete]ht; Tables ize=ht2. Tablesize; Allocate(;∥重新分配目标散列表存储空间 for int i=0; i<TableSize; i++)hto=ht2. ht O: ∥从源散列表向目标散列表传送 Currents ize= ht2 currents ize ∥传送当前表项个数 return "th ∥返回目标散列表结构指针 template <class Type> int Hash Table<Type>: Find const Type&x)( ∥共有函数:找下一散列位置的函数 int i=0, q=( TableSize-1)/2, h0 ∥i为探查次数 int Current Pos=h0= HashPos(x ); ∥利用散列函数计算x的散列地址 while(ht[CurrentPos] info I= Empty & ht( CurrentPos) Element I=x)( /搜索是否要求表项 ∥求“下一个”桶 CurrentPos =h0+( q-1)*(q-1) while( Current Pos>= Tables ize) CurrentPos-= Tablesize;∥实现取模 CurrentPos=h0-(1-q)*(1-9) while( CurrentPos <0)Current Pos + Tablesize; ∥实现取模 if( ht[CurrentPos) info - Active & ht[CurrentPos]Element ==x) ∥返回桶号 ht[Current Pos]. info Active: ht[ CurrentPos] Element =x; 插入x if(++CurrentSize TableSize /2)return CurrentPos; ∥当前己有项数加1,不超过表长的一半返回 HashEntry *Oldht=ht ∥分裂空间处理:保存原来的散列表 int Old Tablesize Tables ize: CurrentSize =0 Tablesize= NextPrime(2* oldTablesize);原表大小的2倍,取质数 Allocateht ( 建立新的二倍大小的空表 for (i=0; i< Old TableSize; i++) ∥原来的元素重新散列到新表中 if( OldhtO] info = Active )i Find( oldht[ Element ) ∥递归调用 if( Oldht[ Element ==x )CurrentPos=i: delete Oldht; 求下一个大于参数表中所给正整数N的质数的算法 int NextPrime( intN) 求下一个>N的质数,设N>=5 if(N%2=0)N++; 偶数不是质数 for(: !IsPrime(N: N+=2); 寻找质数第 10 章 索引与散列 9 if ( this != &ht2 ) { delete [ ] ht; TableSize = ht2.TableSize; AllocateHt ( ); //重新分配目标散列表存储空间 for ( int i = 0; i < TableSize; i++ ) ht[i] = ht2.ht[i]; //从源散列表向目标散列表传送 CurrentSize = ht2.CurrentSize; //传送当前表项个数 } return *this; //返回目标散列表结构指针 } template <class Type> int HashTable<Type> :: Find ( const Type& x ) { //共有函数： 找下一散列位置的函数 int i = 0, q = ( TableSize -1 ) / 2, h0; // i 为探查次数 int CurrentPos = h0 = HashPos ( x ); //利用散列函数计算 x 的散列地址 while ( ht[CurrentPos].info != Empty && ht[CurrentPos].Element != x ) { /搜索是否要求表项 if ( i <= q ) { //求“下一个”桶 CurrentPos = h0 + (q - i ) * ( q - i ); while ( CurrentPos >= TableSize ) CurrentPos -= TableSize; //实现取模 } else { CurrentPos = h0 - ( i -q ) * ( i - q ); while ( CurrentPos < 0 ) CurrentPos += TableSize; //实现取模 } i++; } if ( ht[CurrentPos].info == Active && ht[CurrentPos].Element == x ) return CurrentPos; //返回桶号 else { ht[CurrentPos].info = Active; ht[CurrentPos].Element = x; //插入 x if ( ++CurrentSize < TableSize / 2 ) return CurrentPos; //当前已有项数加 1, 不超过表长的一半返回 HashEntry *Oldht = ht; //分裂空间处理: 保存原来的散列表 int OldTableSize = TableSize; CurrentSize = 0; TableSize = NextPrime ( 2 * OldTableSize ); //原表大小的 2 倍，取质数 Allocateht ( ); //建立新的二倍大小的空表 for ( i = 0; i < OldTableSize; i++) //原来的元素重新散列到新表中 if ( Oldht[i].info == Active ) { Find ( Oldht[i].Element ); //递归调用 if ( Oldht[i].Element == x ) CurrentPos = i; } delete [ ] Oldht; return CurrentPos; } } 求下一个大于参数表中所给正整数 N 的质数的算法。 int NextPrime ( int N ) { //求下一个>N 的质数，设 N >= 5 if ( N % 2 == 0 ) N++; //偶数不是质数 for ( ; !IsPrime (N); N += 2 ); //寻找质数