首页 > 代码库 > 【算法与数据结构】哈希表-链地址法
【算法与数据结构】哈希表-链地址法
哈希表的链地址法来解决冲突问题
将所有关键字为同义词的记录存储在同一个线性链表中,假设某哈希函数产生的哈希地址在区间[0, m - 1]上,则设立一个至振兴向量
Chain ChainHash[m];
数据结构
//链表结点
typedef struct _tagNode
{
int data; //元素值(关键字)
struct _tagNode* next; //下一个结点
}Node, *PNode;
//哈希表结点
typedef struct _tagHashTable
{
//这里用一个联合体来解释一下,其index也即哈希值
union{
int index; //哈希表index(这里也是哈希值)
int nHashValue; //也即哈希值
}INDEX;
Node* firstChild; //该哈希结点在第一个子节点,即哈希值为该结点INDEX字段的
struct _tagHashTable* next; //指向下一个哈希结点
}HashTable, *PHashTable;
构造哈希表,输入为头结点指针的引用
//pHashTable 哈希表头结点
//length 哈希表长度
//pArr 关键字元素数组
//nums 关键字元素数组长度
void CreateHashTable(PHashTable& pHashTable, int length, int* pArr, int nums)
{
pHashTable = new HashTable();
if(NULL == pHashTable) { cerr << "Create Hashtable error! \n"; return;}
pHashTable->firstChild = NULL;
pHashTable->INDEX = 0;
pHashTable->next = NULL;
PHashTable pTemp = pHashTable;
for (int i = 1; i < length; ++ i)
{
PHashTable pt = new HashTable();
if(NULL == pt) {cerr << "Create Hahstable error ! \n"; return;}
pt->firstChild = NULL;
pt->INDEX = i;
pt->next = NULL;
pTemp->next = pt;
pTemp = pt;
} //for
//Hash(key) = key MOD length;
for(int i = 0; i < nums; ++ i)
{
//计算哈希值
int nHashValue = http://www.mamicode.com/pArr[i] % length;
PHashTable pTemp2 = NULL;
if(NULL != (pTemp2 = LocateHashNode(pHashTable, nHashValue)) )
{
Insert(pTemp2, pArr[i]);
}
else
{
cerr << "元素值为 "<< pArr[i]<< " 的元素,哈希值为 "<< nHashValue<< ", 查找其所在哈希结点失败"<<endl;
}
}
}
向某个哈希表结点(不一定是头结点)中插入元素
//将关键字插入所在的pHashtable结点的链表
//返回其在该链表上的位置(下标从1开始)
int Insert(PHashTable& pHashtable, int data)
{
if(NULL == pHashtable){cerr << "当前哈希表结点为空 \r\n"; return -1;}
int nIndex = 1;
PNode pNewNode = new Node();
if(NULL == pNewNode){cerr << "建立新链表结点失败"<<endl; return -1;}
pNewNode->data =http://www.mamicode.com/ data;
pNewNode->next = NULL;
PNode pNode = pHashtable->firstChild;
if (NULL == pNode)
{
pHashtable->firstChild = pNewNode;
}
else
{
while(pNode->next != NULL)
{
++ nIndex;
pNode = pNode->next;
}
++nIndex;
pNode->next = pNewNode;
}
cout << "元素 "<< data << " 插入在了哈希表结点 "<< pHashtable->INDEX<< " 的第 "<< nIndex<< " 个位置"<<endl;
return nIndex;
}
根据哈希值,返回其所在结点的指针,输入为表示该哈希表的头结点指针的引用
//根据哈希值,返回该值应该所在的哈希表结点指针
//pHashtable 哈希表头结点
//nHashValue 元素的哈希值
PHashTable LocateHashNode(PHashTable& pHashtable, int nHashValue)
{
if(NULL == pHashtable) {cerr << "哈希表头结点为空"<<endl; return NULL;}
PHashTable pTemp = pHashtable;
do
{
if (pTemp->INDEX == nHashValue) return pTemp;
pTemp = pTemp->next;
} while (pTemp != NULL);
return NULL;
}
从头结点为pHashtable的哈希表中,查找关键字为data,哈希值为nHashValue的元素
在哈希表中的位置,返回值为在该哈希结点的链表中的位置(下标从1开始)
//查找头结点为pHashtable的哈希表
//其数据为data,哈希值为nHashValue的元素
//在哈希表某个结点的链表中的位置(下标从1开始)
int Find(PHashTable& pHashtable, int data, int nHashValue)
{
if(NULL == pHashtable){cerr << "哈希表头结点为空"<<endl; return -1;}
PHashTable pHashNode = LocateHashNode(pHashtable, nHashValue);
if(NULL == pHashNode) {cerr << "找不到元素 " << data << " ,其哈希值为 "<<nHashValue<< " 在哈希表中的位置"; return -1;}
int nINDEX = 1;
PNode pNode = pHashNode->firstChild;
if (NULL == pNode)
{
{cerr << "找不到元素 " << data << " ,其哈希值为 "<<nHashValue<< " 在哈希表中的位置"; return -1;}
}
else
{
bool b = false;
while(pNode != NULL)
{
if(pNode->data =http://www.mamicode.com/= data)
{
b = true;
break;
}
++ nINDEX;
pNode = pNode->next;
}
if (false == b)
{
cerr << "找不到元素 " << data << " ,其哈希值为 "<<nHashValue<< " 在哈希表中的位置";
return -1;
}
else
{
cout << "元素 "<< data << " 插入在了哈希表结点 "<< pHashNode->INDEX<< " 的第 "<< nINDEX<< " 个位置"<<endl;
}
}
return nINDEX;
}
int _tmain(int argc, _TCHAR* argv[])
{
PHashTable pHashtable = NULL;
int length = 0;
int nums = 0;
cout <<endl<< "请输入元素个数:";
cin >> nums;
int* pArr = new int[nums]();
if(NULL == pArr) {cerr<<"申请元素空间错误"; return -1;}
ZeroMemory(pArr, sizeof(int) * nums);
for (int i = 0; i < nums; ++ i)
{
int data = http://www.mamicode.com/0;
cout << "请输入第 "<< i << " 个元素的值:";
cin >> data;
pArr[i] = data;
}
cout << endl<<"输入完毕"<<endl;
cout << "请输入哈希表长度:";
cin >> length;
cout << endl <<endl <<"开始构造哈希表"<<endl;
CreateHashTable(pHashtable, length, pArr, nums);
cout <<endl<<"哈希表构造完毕"<<endl<<endl;
cout<<endl<<endl;
int value = http://www.mamicode.com/0;
for (int i = 0; i < nums * 10; ++ i)
{
cout << "请输入要查查找的元素:";
cin >> value;
Find(pHashtable, value, value % length);
cout<<endl;
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。