#ifndef DefaultSize
#define DefaultSize 100
#endif

		template <class Type> class HashTable;
		template <class Type> class ListNode {			//各桶中同義詞子表的鏈結點(表項)定義
		friend class HashTable<Type>;
		private:
		   Type key;		//表項的關鍵碼
		   ListNode *link;		//鏈指針
		};
 

		template <class Type>
		class HashTable {									//散列表類定義
		typedef ListNode<Type> * ListPtr;					//鏈表指針
		public:

		   HashTable ( int sz=DefaultSize ) : buckets ( sz ) 
		   { 
			   AllocateHt ( );
			   for (int i=0;i<sz;i++) ht[i]=NULL;				   			   
		   }		//構造函數
		   ~HashTable ( ) { delete [ ] ht; }						//析構函數
		   int Insert ( const Type & x );							//在散列表中插入x
		   int Remove ( const Type & x );						//在散列表中刪除x
		   int IsIn ( const Type & x ) { return (  Find (x)) ? 1 : 0; }	//判x在散列表中否
		   int FindPos ( const Type & x ); 					//散列函數: 計算含x表項的初始桶號
	       Type* Find ( const Type & x);
		private:
		   int buckets;							//容量(桶的個數)
		   ListPtr *ht;						//散列表定義
		   void AllocateHt ( ) { ht = new ListPtr[buckets ]; }			//為散列表分配存儲空間
		};

		template <class Type> int HashTable<Type>::Insert (const Type & x ) {
		//在ht表中搜索x。若找到則不再插入, 若未找到, 但表已滿, 則不再插入, 以上兩種情況, 返回0; 若找到
		//位置的標志是Empty或Deleted, 不論表是否已滿, x插入, 返回1。
		   if ( Find (x) ) return 0;					//表中已有該項, 不再插入
		   int j=FindPos ( x  );
		   ListPtr p = ht[j];
		   ht[j]=new ListNode<Type>;
		   ht[j]->key=x;
		   ht[j]->link=p;
		   	return 1;
		}

		template <class Type> int HashTable<Type>::Remove ( const Type & x ) {
		//在ht表中刪除元素x。若表中找不到x, 或雖然找到x, 但它已經邏輯刪除過, 則返回0, 否則在表中刪除
		//元素x, 返回1。
		   if ( !Find (x) ) return 0;					
		   int j=FindPos ( x  );
		   ListPtr p= ht[j];

		   if (ht[j]->key==x) 
			   ht[j]=p->link;
		   else
		   {
			   ListPtr q;
			   while (p->key!=x)
			   {
				   q=p;
				   p=p->link;
			   }
			   q->link=p->link;			
		   }
		   delete p;
		   return 1;
		}


		template <class Type> Type *HashTable<Type>::Find ( const Type & x) {
		//在散列表ht中搜索表項x。函數返回一個指向散列表中某表項的指針; 若表項不存在, 則返回0。
		   int j = FindPos ( x  );				//通過一個散列函數HashFunc( )計算桶號
		   ListPtr p = ht[j];
		   while ( p != NULL )						// p!=NULL時在同義詞子表中尋找
			 if ( p->key == x ) return & p->key;			//找到返回
			 else p = p->link;						//否則, 循鏈向下找
			 return 0;							//整個鏈都搜索完, 未找到x, 返回0
		}