?? p377.cpp
字號(hào):
#ifndef DefaultSize
#define DefaultSize 100
#endif
template <class Type> class HashTable;
template <class Type> class ListNode { //各桶中同義詞子表的鏈結(jié)點(diǎn)(表項(xiàng))定義
friend class HashTable<Type>;
private:
Type key; //表項(xiàng)的關(guān)鍵碼
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;
} //構(gòu)造函數(shù)
~HashTable ( ) { delete [ ] ht; } //析構(gòu)函數(shù)
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 ); //散列函數(shù): 計(jì)算含x表項(xiàng)的初始桶號(hào)
Type* Find ( const Type & x);
private:
int buckets; //容量(桶的個(gè)數(shù))
ListPtr *ht; //散列表定義
void AllocateHt ( ) { ht = new ListPtr[buckets ]; } //為散列表分配存儲(chǔ)空間
};
template <class Type> int HashTable<Type>::Insert (const Type & x ) {
//在ht表中搜索x。若找到則不再插入, 若未找到, 但表已滿, 則不再插入, 以上兩種情況, 返回0; 若找到
//位置的標(biāo)志是Empty或Deleted, 不論表是否已滿, x插入, 返回1。
if ( Find (x) ) return 0; //表中已有該項(xiàng), 不再插入
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, 但它已經(jīng)邏輯刪除過(guò), 則返回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中搜索表項(xiàng)x。函數(shù)返回一個(gè)指向散列表中某表項(xiàng)的指針; 若表項(xiàng)不存在, 則返回0。
int j = FindPos ( x ); //通過(guò)一個(gè)散列函數(shù)HashFunc( )計(jì)算桶號(hào)
ListPtr p = ht[j];
while ( p != NULL ) // p!=NULL時(shí)在同義詞子表中尋找
if ( p->key == x ) return & p->key; //找到返回
else p = p->link; //否則, 循鏈向下找
return 0; //整個(gè)鏈都搜索完, 未找到x, 返回0
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -