int IsPrime ( int N ) {					//測試N是否質數		   for ( int i=3; i*i<=N; i+=2 )				//若N能分解為兩個整數的乘積, 其中一個一定 			 if ( N % i == 0 ) return 0;			//N能整除i, N不是質數		   return 1;							//N是質數		}		int NextPrime ( int N ) {					//求下一個>N的質數，設N >= 5		   if ( N % 2 == 0 ) N++;				//偶數不是質數		   for ( ; !IsPrime (N); N+=2 );				//尋找質數		   return N;		}		template <class Type> class HashTable {				//散列表類的定義		public:		   enum KindOfEntry { Active, Empty, Deleted };			//表項分類 (活動 / 空 / 刪)		   int Find ( const Type & x );				//在散列表中搜索x		   int IsEmpty ( ) { return !CurrentSize ? 1 : 0; }			//判散列表空否，空則返回1 		   int IsFull ( ) { return CurrentSize == TableSize ? 1 : 0; }	//判散列表滿否，滿則返回1		   int Insert ( const Type & x );		   int Remove ( const Type & x );		   int IsIn ( const Type & x );		   int WasFound ( ) const { return LastFindOK;	}		//判最近一次搜索是否成功		   //其它共有函數與定義10.6聲明線性探查散列表類相同		   HashTable ( int sz=DefaultSize ) : TableSize ( sz ) { AllocateHt ( );  CurrentSize = 0; }		//構造函數		   ~HashTable ( ) { delete [ ] ht; }						//析構函數		   const HashTable & operator = ( const HashTable & ht2 );		//重載函數：表賦值		   int FindPos ( const Type & x ); 					//散列函數: 計算含x表項的初始桶號		   void MakeEmpty ( );								//置散列表為空		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 = 11; };		   HashEntry *ht; 								//散列表存儲數組		   int TableSize;								//數組長度，要求是滿足4k+3的質數，k是整數		   int CurrentSize;								//已占據散列地址數目		   int LastFindOK;							//若最近一次搜索成功成功, 則返回1		   void AllocateHt ( ) { ht = new HashEntry[TableSize ]; }	//分配散列表存儲空間的函數		};		template <class Type> int HashTable<Type>::Find ( const Type & x ) {		//共有函數： 找下一散列位置的函數		   int i = 0,  odd = 0 ;								// i為探查次數，odd是控制加減標志		   int CurrentPos = FindPos ( x );						//利用散列函數計算x的散列地址		   while ( ht[CurrentPos].info != Empty && ht[CurrentPos].Element != x ) {	//搜索是否要求表項			 if ( !odd ) {									// odd == 0為(H0 + i2)%TableSize情形			   CurrentPos += 2*++i - 1;   odd = 1;				//求“下一個”桶		 	   while ( CurrentPos >= TableSize ) CurrentPos -= TableSize;	//實現取模			 }			 else {										// odd == 1為(H0 - i2)%TableSize情形			   CurrentPos -= 2*i-1;  odd = 0;					//求“下一個”桶			   while ( CurrentPos < 0 ) CurrentPos += TableSize; 		//實現取模			 }		   }		   LastFindOK = ht[CurrentPos].info == Active;				//記下最后是否搜索成功信息		   return CurrentPos;								//返回桶號		};		template <class Type> int HashTable<Type>::Insert ( const Type & x ) {		//將x插入到散列表中, 若x在表中已存在, 則返回0, 否則返回1。		   int CurrentPos = Find (x);		   if (LastFindOK ) return 0;						//該項在表中已經存在, 不再加入		   ht[CurrentPos] = HashEntry ( x, Active );				//插入x		   if ( ++CurrentSize < TableSize/2) return 1;				//當前已有項數加1, 不超過表長的一半返回		   HashEntry *Oldht = ht;						//分裂空間處理: 保存原來的散列表		   int OldTableSize = TableSize;		   CurrentSize = 0;		   TableSize = NextPrime ( 2 * OldTableSize );			//原表大小的2倍，取質數		   AllocateHt ( );								//建立新的二倍大小的空表		   for (int i=0; i<OldTableSize; i++)					//原來的元素重新散列到新表中		      if ( Oldht[i].info == Active ) Insert ( Oldht[i].Element );	//遞歸調用		   delete [ ] Oldht;		   return 1;		}		template <class Type> int HashTable<Type>::IsIn ( const Type & x ) {		//判斷x是否在散列表中。若在表中, 則返回1, 否則返回0。		   int CurrentPos = Find ( x );		   return LastFindOK;		}		template <class Type> int HashTable<Type>::Remove ( const Type & x ) {		//將x從散列表中刪除。若刪除成功, 則返回1, 否則返回0。		   int CurrentPos = Find (x);		   if (!LastFindOK ) return 0;						//該項在散列表中沒有		   ht[CurrentPos].info = Deleted;  return 1;				//作刪除標記, 刪除成功		}		//以下來自線性探查法		template <class Type> void HashTable<Type>::MakeEmpty ( ) {		//清除散列表		   for ( int i=0; i<TableSize; i++) ht[i].info = Empty;		   CurrentSize = 0;		}		template <class Type> const HashTable<Type> & HashTable<Type>::operator= ( const HashTable<Type> &ht2 ) {		//重載函數：復制一個散列表ht2		   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;									//返回目標散列表結構指針		}