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