hashtable.h

安全数组 普通链表 哈希表 二叉搜索树 AVL树 集合类 通用自动机 所有类均使用模板编写

#ifndef HASH_TABLE_CLASS
#define HASH_TABLE_CLASS

#include <stdlib.h>
#include "array.h"
#include "linkedlist.h"

template <class T>
class HashTable
{
	protected:
		// “桶”的个数，表示哈希表的大小
		int numBuckets;
		
		// 哈希表为链表构成的数组
		Array< LinkedList<T> > buckets;
		
		// 哈希函数及当前桶、与当前桶对应的当前链表的指针、指向当前数据项的指针
		unsigned long (*hf)(const T& key);  // 除以哈希表大小的工作在内部完成
		int currentBucket;
		LinkedList< T > *currBucketPtr;
		T *current;
		
		// 表中元素个数
		int size;
		
		// 取下一个非空结点的例程（用于遍历，内部使用）
		void SearchNextNode(int cb);
		
	public:
		// 参数为哈希表大小及哈希函数的构造函数
		HashTable(int nbuckets, unsigned long hashf(const T& key));
		
		// 处理表的方法
		void Insert(const T& key);
		bool Find(T& key);			// 检索时只要设置结构中与关键字有关的成员，该函数会返回哈希表中对应的完整项
		void Delete(const T& key);
		void ClearList(void);
		void Update(const T& key);  // 对已经在哈希表中的元素进行更新
		
		// 遍历表的函数
		void Reset(void);
		void Next(void);
		bool EndOfList(void) const;
		
		// 访问当前数据（这里只提供访问，不可更改，否则如更改了 key 值，有可能造成哈系表的混乱）
		const T& Data(void);
		
		// 检查表状态的函数
		int ListSize(void) const;
		bool ListEmpty(void) const;
};

template <class T>
HashTable<T>::HashTable(int nbuckets, unsigned long hashf(const T& key)):
numBuckets(nbuckets), buckets(nbuckets), hf(hashf), currentBucket(-1), currBucketPtr(NULL), current(NULL), size(0)
{}

// 如果数据已存在，则更新它，否则将其插入
template <class T>
void HashTable<T>::Insert(const T& key)
{
	currentBucket = int(hf(key) % numBuckets);
	currBucketPtr = &buckets[currentBucket];
	
	for (currBucketPtr->Reset(); !currBucketPtr->EndOfList(); currBucketPtr->Next())
	{
		// 若找到匹配值，修改其数据后返回（/* 如果关键字相同即认为是同一条目（认为两者相等）*/）
		if (currBucketPtr->Data() == key)
		{
			currBucketPtr->Data() = key;  // 将数据区也设为相等
			current = &currBucketPtr->Data();
			return;
		}
	}
	
	// 若没有找到，则将数据项加入表中
	currBucketPtr->InsertRear(key);
	current = &currBucketPtr->Data();
	size++;
}

template <class T>
bool HashTable<T>::Find(T& key)
{
	// 计算键值的哈希值并将 lst 指向它对应的 LinkedList
	int hashval = int(hf(key) % numBuckets);
	LinkedList<T>& lst = buckets[hashval];
	
	// 在键表中扫描结点并寻找与 key 匹配的记录
	for (lst.Reset(); !lst.EndOfList(); lst.Next())
	{
		// 若找到匹配值，则取其数据值，将 current 指向该记录
		if (lst.Data() == key)
		{
			key = lst.Data();
			current = &lst.Data();
			currentBucket = hashval;
			currBucketPtr = &lst;
			return true;
		}
	}
	return false;
}

template <class T>
void HashTable<T>::Delete(const T& key)
{
	int hashval = int(hf(key) % numBuckets);
	LinkedList<T>& lst = buckets[hashval];
	
	for (lst.Reset(); !lst.EndOfList(); lst.Next())
	{
		if (lst.Data() == key)  // 如果关键字匹配，删除结点
		{
			lst.DeleteAt();
			currentBucket = hashval;
			currBucketPtr = &lst;
			size--;
			Next();	// 自动找到下一个非空值
			return;
		}
	}
}

template <class T>
void HashTable<T>::ClearList(void)
{     
	for (int i = 0; i < numBuckets; i++)
		buckets[i].ClearList();
	size = 0;
	currentBucket = -1;
	currBucketPtr = NULL;
	current = NULL;
}

template <class T>
void HashTable<T>::Update(const T& key)
{     
	if (current != NULL && *current == key)
		*current = key;
	else
		Insert(key);
}

// 返回当前数据值
template <class T>
const T& HashTable<T>::Data(void)
{
	if (current == NULL)
		throw "HashTable::Data: invalid reference!";
	
	return (*current);
}

// 从下标 cb 开始寻找下一个非空表进行扫描
template <class T>
void HashTable<T>::SearchNextNode(int cb)
{
	// 此函数仅在内部使用
	currentBucket = -1;	// 如果找不到就是 endoflist 状态了
	currBucketPtr = NULL;
	current = NULL;
	
	for(int i = cb; i < numBuckets; i++)
	{
		if (!buckets[i].ListEmpty())
		{
			// 返回前，置 currentBucket 为 i 并置 current 成员为桶中第一个数据项
			currentBucket = i;
			currBucketPtr = &buckets[currentBucket];
			currBucketPtr->Reset();
			current = &currBucketPtr->Data();
			return;
		}
	}
}

// 指向表中下一个数据结点
template <class T>
void HashTable<T>::Next(void)
{
	// 将当前表移向下一结点或表尾
	currBucketPtr->Next();
	
	// 若已到表尾，调用 SearchNextNode 找下一非空桶
	if (currBucketPtr->EndOfList())
		SearchNextNode(currentBucket + 1);
	else
		current = &currBucketPtr->Data();
}

template <class T>
void HashTable<T>::Reset(void)
{
	SearchNextNode(0);
}

template <class T>
bool HashTable<T>::EndOfList(void) const
{
	return (currentBucket == -1);
}

template <class T>
int HashTable<T>::ListSize(void) const
{
	return size;
}

template <class T>
bool HashTable<T>::ListEmpty(void) const
{
	return (size == 0);
}

#endif	// HASH_TABLE_CLASS