哈希表操作

#include<iostream>

using namespace std;


#define DEFAULT_SIZE 31        //哈希表的默认长度

//定义哈希表指向的链表结点
typedef struct LNode
{
	int key;
	void* data;


	struct LNode* next;
}LNode,*List;

//定义哈希表
typedef struct HashTable
{
	int TableSize;  //哈希表的长度
	List* Thelists;   //指向指针数组的指针，因为预先无法确定数组的大小
}HashTable;


//散列（哈希）函数
int Hash(int key, int TableSize);

//初始化哈希表
HashTable* InitHash(int TableSize);

//根据关键值查找哈希表中的元素
LNode* HashSearch(HashTable* HT, int key);

//哈希表中插入新元素
void HashInsert(HashTable* HT, int key, void* value);

//哈希表中删除指定元素
void HashDelete(HashTable* HT, int key);

//哈希表元素中提取数据
void* HashRetrieve(LNode* e);

//销毁哈希表
void DestroyHash(HashTable* HT);


int main()
{
	//数据名竟然能够跟数据类型一样
	HashTable* HashTable = NULL;
	//初始化哈希表
	HashTable = InitHash(31);

	return 0;
}


//散列（哈希）函数
int Hash(int key, int TableSize)
{
	return (key % TableSize);
}

//初始化哈希表
HashTable* InitHash(int TableSize)
{
	//如果指定的哈希表长度小于等于0，那么就使用默认的长度值
	if (TableSize <= 0)
	{
		TableSize = DEFAULT_SIZE;
	}
	HashTable* hTable = new HashTable; //申请存储哈希表的空间
	if (hTable == NULL)
	{
		cout << "错误" << endl;
		return NULL;
	}
	//哈希表的大小
	hTable->TableSize = TableSize;
	//为哈希桶分配内存空间，哈希桶是一个指针数组
	//为指向哈希表的指针申请一个数组，该数组内存放指向链表的指针
	hTable->Thelists = new List[TableSize];
	//如果申请内存空间失败
	if (NULL == hTable->Thelists)
	{
		cout << "错误" << endl;
		//记得将之前申请的空间释放
		delete hTable;
		return NULL;
	}
	//为每一个链表申请头结点
	for (int i = 0; i < TableSize; i++)
	{
		hTable->Thelists[i] = new LNode;
		//如果申请头结点空间失败，释放之前申请的所有空间并退出
		if (NULL == hTable->Thelists[i])
		{
			cout << "哈希表初始化错误" << endl;
			delete[] hTable->Thelists;
			delete hTable;
			return NULL;
		}
		else
		{
			//将头结点中的所有数据全部初始化为0
			memset(hTable->Thelists[i], 0, sizeof(LNode));
		}

	}
	return hTable;
}



//根据关键值查找哈希表中的元素
LNode* HashSearch(HashTable* HT, int key)
{
	//根据哈希函数找到散列地址
	int i = Hash(key, HT->TableSize);
	//根据散列地址找到对应的链表头指针
	List L = HT->Thelists[i];
	//查找链表中的首元结点
	LNode* e = L->next;
	//按关键值查找元素
	while (e != NULL && e->key != key)
	{
		e = e->next;
	}
	//经过以上循环，要么找到指定元素，要么找不到，找不到则e为空
	return e;
}

//哈希表中插入新元素
void HashInsert(HashTable* HT, int key, void* value)
{
	//首先确定哈希表中是否已存在相同元素
	LNode* e = HashSearch(HT, key);
	//如果e为空表明哈希表中不存在相同元素，执行插入操作
	if (e == NULL)
	{
		//申请一个新的空间存储来存储插入元素
		LNode* temp = new LNode;
		if (temp == NULL)
		{
			cout << "错误" << endl;
			return;
		}
		//找到key对应的散列地址,该散列地址中存放着链表的头节点地址或者说该地址代表的数组元素就是头指针
		List L = HT->Thelists[Hash(key, HT->TableSize)];
		//为申请的新结点*temp赋值
		temp->data = value;
		temp->key = key;
		//头插法插入新结点
		temp->next = L->next;
		L->next = temp;
	}
	else
	{
		cout << "该关键字已经存在" << endl;
	}
}

//哈希表中删除指定元素
void HashDelete(HashTable* HT, int key)
{
	int i = Hash(key, HT->TableSize);
	//L指向key所在链表的头节点
	List L = HT->Thelists[i];
	//e指向首元结点
	LNode* e = L->next;
	//last指向待删除结点的上个结点
	LNode* last = L;
	//找到
	while (e != NULL && e->key != key)
	{
		last = last->next;  //或者last=e;
		e = e->next;
	}
	//经过以上循环,要么找到待待删除元素的结点位置，要么找不到，找不到时e为空
	if (e)
	{
		//修改指针并释放结点e
		last->next = e->next;
		delete e;
	}
}

//哈希表元素中提取数据
void* HashRetrieve(LNode* e)
{
	if (e)
	{
		return e->data;
	}
	return NULL;
}

//销毁哈希表
void DestroyHash(HashTable* HT)
{
	for (int i = 0; i < HT->TableSize; i++)
	{
		//L指向链表i中的头结点
		List L = HT->Thelists[i];
		//p首先指向首元结点
		LNode* p;
		//从头结点开始依次释放所有结点
		while (L)
		{
			//p先指向头结点
			p = L;
			//L指向头结点的下个元素
			L = L->next;
			//删除原先的头结点
			delete L;
		}
	}
	//释放哈希表中的指针数组
	delete[] HT;
}