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;									//返回目標散列表結構指針
		}