?? hashtable.h
字號:
#ifndef HASH_TABLE_CLASS
#define HASH_TABLE_CLASS
#include <stdlib.h>
#include "array.h"
#include "dclinkedlist.h"
template <class T>
class HashTable
{
protected:
// “桶”的個數,表示哈希表的大小
int numBuckets;
// 哈希表為鏈表構成的數組
Array< DCLinkedList<T> > buckets;
// 哈希函數及指向當前數據項的指針、當前的哈希值
unsigned long (*hf)(T key); // 除以哈希表大小的工作在內部完成
T *current;
int hashval;
// 表中元素個數
int size;
public:
// 參數為哈希表大小及哈希函數的構造函數
HashTable(int nbuckets, unsigned long hashf(T key));
// 處理表的方法
void Insert(const T& key);
bool Find(T& key); // 檢索時只要設置結構中與關鍵字有關的成員,該函數會返回哈希表中對應的完整項
void DeleteAt(void); // 刪除當前成員
void Delete(const T& key);
void ClearList(void);
void Update(const T& key); // 對已經在哈希表中的元素進行更新
};
template <class T>
HashTable<T>::HashTable(int nbuckets, unsigned long hashf(T key)):
numBuckets(nbuckets), buckets(nbuckets), hf(hashf), current(NULL), hashval(0)
{}
// 如果數據已存在,則更新它,否則將其插入
template <class T>
void HashTable<T>::Insert(const T& key)
{
// hashval 為哈希值(桶索引)
hashval = int(hf(key) % numBuckets);
// lst 為 buckets[hashval] 的別名,可避免下標尋址
DCLinkedList<T>& lst = buckets[hashval];
for (lst.Reset(); !lst.EndOfList(); lst.Next())
{
// 若找到匹配值,修改其數據后返回(/* 如果關鍵字相同即認為是同一條目(認為兩者相等)*/)
if (lst.Data() == key)
{
lst.Data() = key; // 將數據區也設為相等
current = &lst.Data();
return;
}
}
// 若沒有找到,則將數據項加入表中
lst.InsertRear(key);
current = &lst.Data();
size++;
}
template <class T>
bool HashTable<T>::Find(T& key)
{
// 計算鍵值的哈希值并將 lst 指向它對應的 DCLinkedList
hashval = int(hf(key) % numBuckets);
DCLinkedList<T>& lst = buckets[hashval];
// 在鍵表中掃描結點并尋找與 key 匹配的記錄
for (lst.Reset(); !lst.EndOfList(); lst.Next())
{
// 若找到匹配值,則取其數據值,將 current 指向該記錄
if (lst.Data() == key)
{
key = lst.Data();
current = &lst.Data();
return true;
}
}
return false;
}
template <class T>
void HashTable<T>::Delete(const T& key)
{
hashval = int(hf(key) % numBuckets);
DCLinkedList<T>& lst = buckets[hashval];
for (lst.Reset(); !lst.EndOfList(); lst.Next())
{
if (lst.Data() == key) // 如果關鍵字匹配,刪除結點
{
lst.DeleteAt();
current = &lst.Data();
size--;
return;
}
}
}
template <class T>
void HashTable<T>::DeleteAt(void)
{
DCLinkedList<T>& lst = buckets[hashval];
if (current != NULL && !lst.EndOfList())
{
lst.DeleteAt();
current = &lst.Data();
size--;
}
}
template <class T>
void HashTable<T>::ClearList(void)
{
for (int i = 0; i < numBuckets; i++)
buckets[i].ClearList();
size = 0;
current = NULL;
}
template <class T>
void HashTable<T>::Update(const T& key)
{
DCLinkedList<T>& lst = buckets[hashval];
if (current != NULL && !lst.EndOfList() && *current == key)
*current = key;
else
Insert(key);
}
#endif // HASH_TABLE_CLASS
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -