hashtable.cpp

用C语言实现了哈希表的存储和读取

#include "StdAfx.h"
#include ".\hashtable.h"

CHashTable::CHashTable(int size)
{
	if(size < MAX_HASH_LENGTH)
	{
		size = MAX_HASH_LENGTH;
	}
	this->m_pHashSlots = new CHashElem*[size];
	for(int i=0;i<size;i++)
	{
		this->m_pHashSlots[i] = NULL;
	}
	this->m_HashSize = size;
	this->m_ElemNum = 0;
}

CHashTable::~CHashTable(void)
{
	if (m_pHashSlots)
	{
		CHashElem *phe;
		for (int i=0;i<this->m_HashSize;i++)
		{
			phe = m_pHashSlots[i];
			while (phe != NULL)
			{
				CHashElem *pNext = phe->pNext;
				delete phe;
				phe = pNext;
			}
		}
		delete m_pHashSlots;
		m_pHashSlots = 0;
	}

}

/***
 **根据键值查询哈希表，如果对应的字符与传入的字符相同，则返回这个哈希表的元素
 */

CHashElem* CHashTable::QueryByKey(char *in_value)
{
	CHashElem * elem = NULL;
	int key = this->GetHashKey(in_value);
	unsigned int num = (unsigned int)key % this->m_HashSize;

	if(num >= 0)
	{
		CHashElem *pElem = this->m_pHashSlots[num];
		while(pElem!=NULL)
		{
			if(strcmp(pElem->value,in_value)==0)
			{
				elem = pElem;
				break;
			}
			else
			{
				pElem = pElem->pNext;
			}
		}
	}
	return elem;
}

/***
 **把字符串插入哈希表中，相同键值的字符串用一个链表保存
 */
bool CHashTable::Insert(char *in_value)
{
	if((int)strlen(in_value) > MAX_WORD_LENGTH) return false; //处理的字符串过长
	bool res = false;
	int key = this->GetHashKey(in_value);
	unsigned int num = (unsigned int)key%this->m_HashSize;
	if(num >= 0)
	{
		if(this->m_pHashSlots[num] != NULL)
		{
			CHashElem *pElem = this->m_pHashSlots[num];
			while(pElem->pNext != NULL)
			{
				///已经存在相同的键值
				if(strcmp(pElem->value,in_value) == 0)
					return false;
				pElem = pElem->pNext;
			}
			if(strcmp(pElem->value,in_value) == 0)
				return false;

			pElem->pNext = new CHashElem();
			pElem->pNext->key = key;
			strcpy(pElem->pNext->value,in_value);
			pElem->pNext->value[(int)strlen(in_value)+1] = '\0';
			pElem->pNext->pNext = NULL;
			//pElem->pNext->count = 1;

			this->m_ElemNum++;
			res = true;
		}
		else
		{
			this->m_pHashSlots[num] = new CHashElem();
			this->m_pHashSlots[num]->key = key;
			strcpy(this->m_pHashSlots[num]->value,in_value);
			this->m_pHashSlots[(int)strlen(in_value)+1] = '\0';
			this->m_pHashSlots[num]->pNext = NULL;
			//this->m_pHashSlots[num]->count = 1;

			this->m_ElemNum++;
			res = true;
		}
	}
	return res;
}

/***
 **除去字符串
 */
bool CHashTable::Remove(char * in_value)
{
	bool res = false;
	int key = this->GetHashKey(in_value);
	unsigned int num = (unsigned int)key % this->m_HashSize;

	if(num >= 0)
	{
		CHashElem *pElem = this->m_pHashSlots[num];
		CHashElem *pPrev = NULL;
		while(pElem != NULL)
		{
			//printf("value of elem:%s\t value of in_value:%s",pElem->value,in_value);
			if(strcmp(pElem->value,in_value) == 0)
			{
				if(pPrev != NULL)
				{
					pPrev->pNext = pElem->pNext;
				}
				else
				{
					this->m_pHashSlots[num] = pElem->pNext;
				}
				delete pElem;
                res=true;
				this->m_ElemNum--;
                break;
			}
			pPrev = pElem;
			pElem = pElem->pNext;
		}
	}
	return res;
}

/***
 ** 返回哈希表中元素的个数
 */
int CHashTable::GetLength()
{
	return this->m_ElemNum;
}

/***
 ** 返回哈希表的最大键值数
 */
int CHashTable::GetHashSize()
{
	return this->m_HashSize;
}

/***
 ** 计算哈希表中元素的键值
 */
int CHashTable::GetHashKey(char *value)
{
	int key = 0;
	for(int i=0;value[i] != '\0';i++)
	{
		key +=	toascii(value[i]);
	}
	key = key - 97; //a 的ascii值是97，保证可以从0开始
	return key; 
}

/**
 **判断是否存在键值
 */
bool CHashTable::ExitKey(char *in_value)
{
	bool res = false;
	int key = this->GetHashKey(in_value);
	unsigned int num = (unsigned int)key % this->m_HashSize;

	if(num >= 0)
	{
		CHashElem *pElem = this->m_pHashSlots[num];
		while(pElem != NULL)
		{
			//printf("value of elem:%s\t value of in_value:%s",pElem->value,in_value);
			if(strcmp(pElem->value,in_value) == 0)
			{
                res=true;
                break;
			}
			pElem = pElem->pNext;
		}
	}
	return res;
}