#ifndef DefaultSize
#define DefaultSize 100
#endif
		template <class Type>
		class HashTable {									//散列表類定義
		public:
		   enum KindOfEntry { Active, Empty, Deleted };				//表項分類 (活動 / 空 / 刪)
		   HashTable ( int sz=DefaultSize ) : TableSize ( sz ) { AllocateHt ( );  CurrentSize = 0; }		//構造函數
		   ~HashTable ( ) { delete [ ] ht; }						//析構函數
		   const HashTable & operator = ( const HashTable & ht2 );		//重載函數：表賦值
		   int Find ( const Type & x );							//在散列表中搜索x
		   int Insert ( const Type & x );							//在散列表中插入x
		   int Remove ( const Type & x );						//在散列表中刪除x
		   int IsIn ( const Type & x ) { return (  Find (x)  >= 0 ) ? 1 : 0; }	//判x在散列表中否
		   void MakeEmpty ( );								//置散列表為空
		   int FindPos ( const Type & x ); 					//散列函數: 計算含x表項的初始桶號
		private:
		   struct HashEntry {								//表項定義
		      Type Element;								//表項的數據, 即表項的關鍵碼
		      KindOfEntry info;								//三種狀態: Active, Empty, Deleted
		      int operator== ( HashEntry & );			//重載函數：表項判等運算
		      int operator!= ( HashEntry & );				//重載函數：表項判不等運算
		      HashEntry ( ) : info (Empty ) { }						//表項構造函數, 置空
		      HashEntry (const Type & E, KindOfEntry i = Empty ) : Element (E), info (i) { }
		   };
		   enum { DefualtSize = 11 };
		   HashEntry *ht;									//散列表存儲數組
		   int CurrentSize, TableSize;							//當前桶數及最大桶數
		   void AllocateHt ( ) { ht = new HashEntry[TableSize ]; }			//為散列表分配存儲空間
		};
		template <class Type> int HashTable<Type>::Find ( const Type & x ) {
		//使用線性探查法在散列表ht (每個桶容納一個表項)中搜索x。如果x在表中存在, 則函數返回x所在
		//位置j, 即ht[j]=x。如果x不在表中, 則返回 -j。
		   int i = FindPos ( x ),  j = i; 						//i是計算出來的散列地址, j是下一空桶
		   while ( ht[j].info != Empty && ht[j].Element != x ) {		//ht[j]不空, 且不等于x，沖突
			 j = ( j + 1 ) % TableSize;						//當做循環表處理, 找下一個空桶 
			 if ( j == i ) return -TableSize-1;					//轉一圈回到開始點, 表已滿, 失敗
		   }
		   if ( ht[j].info == Active ) return j;					//找到滿足要求的表項, 返回桶號j
		   else return -j-1;									//失敗
		}
//	在利用散列表進行各種處理之前，必須首先將散列表中原有的內容清掉，這時我們可以將表中所有表項的info域置為Empty即可。因為散列表存放的是表項集合，不應有重復的關鍵碼，所以在插入新表項時，如果發現表中已經有關鍵碼相同的表項，則不再插入。	特別要注意的是，在閉散列的情形下不能隨便物理刪除表中已有的表項。因為若刪除表項會影響其它表項的搜索。如在圖10.26所示的例子中，若把關鍵碼為Broad的表項真正刪除，把它所在位置的info域置為Empty，那么以后在搜索關鍵碼為Blum和Alton的表項時就查不下去，從而會錯誤地判斷表中沒有關鍵碼為Blum和Alton的表項。所以若想刪除一個表項時，只能給它做一個刪除標記deleted，進行邏輯刪除。但這樣做的副作用是：在執行多次刪除后，表面上看起來散列表很滿，實際上有許多位置沒有利用。因此，當散列表經常變動時，最好不用閉散列方法處理溢出，可改用開散列方法來處理溢出。
//	下面給出散列表其它一些操作的實現。
		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;									//返回目標散列表結構指針
		}
      
		template <class Type> int HashTable<Type>::Insert (const Type & x ) {
		//在ht表中搜索x。若找到則不再插入, 若未找到, 但表已滿, 則不再插入, 以上兩種情況, 返回0; 若找到
		//位置的標志是Empty或Deleted, 不論表是否已滿, x插入, 返回1。
		   int i = Find (x);
		   if ( i >= 0 ) return 0;					//表中已有該項, 不再插入
		   i++;
		     if ( i != -TableSize && ht[-i].info != Active ) {			//否則若表項為空插入, i為負數
			 ht[-i].Element = x;  ht[-i].info = Active;  CurrentSize++;		//插入
			 return 1;									//返回插入成功標志1
		   }
		   else return 0; 									//表滿不插入, 返回不成功標志
		}

		template <class Type> int HashTable<Type>::Remove ( const Type & x ) {
		//在ht表中刪除元素x。若表中找不到x, 或雖然找到x, 但它已經邏輯刪除過, 則返回0, 否則在表中刪除
		//元素x, 返回1。
			int i = Find (x);
		   if ( i >= 0 ) 
		   {						//找到要刪元素, 且是活動元素
			 ht[i].info = Deleted;  CurrentSize--;					//做邏輯刪除標志, 并不真正物理刪除
			 return 1;									//刪除操作完成, 返回成功標志
		   }
		   else return 0;									//表中無被刪表項, 返回不成功標志
		}