相关定义:根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“象” 作为记录在表中的存储位置,这种表便称为散列表(或称哈希表),这一映象过程称为散列造表或散列,所得的存储位置称散列地址。
构造哈希函数的方法:
1. 直接寻址法
2. 数字分析法
3. 平方取中法
4. 折叠法
5. 随机数法
6. 除留余数法
处理冲突的方法:
1. 开放寻址法:Hi=(H(key) + di) MOD m,i=1,2,…,k(k<=m-1),其中H(key)为散列函数,m为散列表长,di为
增量序列,可有下列三种取法:
1.1. di=1,2,3,…,m-1,称线性探测再散列;
1.2. di=1^2,-1^2,2^2,-2^2,⑶^2,…,±(k)^2,(k<=m/2)称二次探测再散列;
1.3. di=伪随机数序列,称伪随机探测再散列。
2. 再散列法:Hi=RHi(key),i=1,2,…,k RHi均是不同的散列函数,即在同义词产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计算时间
3. 链地址法
4. 建立一个公共溢出区
代码:
// HashTable.cpp : 定义控制台应用程序的入口点
//哈希表的实现
//哈希函数采用除留余数法构造
//使用链地址法解决冲突
#include "stdafx.h"
#include <iostream>
using namespace std;
const int MAXSIZE = 100;
int a[MAXSIZE];
//哈希表的结点类型
class HashNode
{
public:
HashNode():next(NULL){};//默认构造函数
HashNode(int item):data(item), next(NULL){};//一般构造函数
private:
int data;
HashNode *next;
friend class HashTable;
};
//哈希表类型
class HashTable
{
public:
HashTable();
void Create(int *a, int n);//创建哈希表
bool Find(int data);//查找
void Insert(int data);//插入
void Delete(int data);//删除
private:
HashNode *value[10];//哈希表长度为10
};
HashTable::HashTable()//默认构造函数
{
memset(value, NULL, 10*sizeof(HashNode*));
}
void HashTable::Create(int *a, int n)
{
cout << "请输入n个元素:" << endl;
for (int i=0; i<n; i++)
{
cin >> a[i];
Insert(a[i]);
}
}
bool HashTable::Find(int data)
{
HashNode *pNode = NULL;
if (value[data%10] == NULL)//该结点不存在,则返回false
{
return false;
}
pNode = value[data%10];//获取所在位置对应的链表的第一个结点
while(pNode ->next != NULL && pNode->data != data)
{
pNode = pNode->next;
}
if (pNode != NULL)
{
return true;
}
else
{
return false;
}
}
void HashTable::Insert(int data)
{
HashNode *pNode = NULL;
if (value[data%10] == NULL)//获取所在位置对应的链表为空,则插入
{
pNode = new HashNode;
pNode->data = data;
value[data%10] = pNode;
}
else//所在位置对应的链表不空
{
if (Find(data))//检查该数值是否已经存在,若存在则返回
{
return;
}
else//否则插入链表尾端
{
pNode = value[data%10];
while(pNode->next != NULL)
{
pNode = pNode->next;
}
HashNode *newNode = new HashNode(data);
pNode->next = newNode;
}
}
}
void HashTable::Delete(int data)
{
HashNode *pNode = NULL;//定位到待删除的结点
HashNode *pPre = NULL;//定位到待删除结点的前一个结点
if (!Find(data))
{
cout << "该数值的结点不存在!" << endl;
}
else
{
pNode = value[data%10];//初始值为所在位置对应的链表的第一个结点
if(pNode->data == data)//头结点即为待删除的结点
{
value[data%10] = pNode->next;
cout << data << "删除成功!" << endl;
}
else//否则指针后移,找到待删除的结点
{
pPre = pNode;
while(pNode->next != NULL && pNode->next->data != data)
{
pPre = pNode;
pNode = pNode->next;
}
pPre->next = pNode->next;
delete pNode;
pNode = NULL;
cout << data << "删除成功!" << endl;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int n = 0;
cout << "请输入哈希表元素的个数:";
cin >> n;
HashTable *ht = new HashTable;
ht->Create(a, n);
cout << ht->Find(9) << endl;
cout << ht->Find(3) << endl;
ht->Delete(10);
ht->Delete(8);
cout << ht->Find(8) << endl;
system("pause");
return 0;
}
分享到:
相关推荐
问题描述: 设计哈希表实现电话号码查找系统。 基本要求: (1)设每个记录有下列数据项:电话号码、用户名、地址; (2)从文件中读取各记录,分别以电话号码和用户名为关键字建立不同的哈希表; (3)采用链地址法...
C语言设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 1) 记录由外部输入。 2) 将生成...
数据结构的课程设计 哈希表实现电话号码查询系统
设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 (1)记录由外部输入。 (2)生成的哈希...
(1)每个人的信息至少包括姓名,...(2)假设人名为汉语拼音全拼形式,待插入哈希表的长度为你所在班级的人数。哈希函数用除留余数法构造,采用链地址法或二次探测再散列法解决冲突。 (3)完成菜单设计。操作有必要的提示。
数据结构课程设计C++基于哈希表实现的通讯录系统源码+课程设计报告(高分项目).zip代码完整,报告全面,下载即用。 数据结构课程设计C++基于哈希表实现的通讯录系统源码+课程设计报告(高分项目).zip代码完整,...
每组测试数据有两行,第一行有两个数n,m(0,m),第二行包含n个处于区间[−500000,500000]的整数,每个数后有一个空格。
问题描述: 设计哈希表实现电话号码查询系统。 基本要求: 1、设每个记录有下列数据项:电话号码、用户名、地址; 2、从键盘输入各记录,分别以电话号码和用户名为关键字建立哈希表; 3、采用再哈希法解决冲突; 4、...
数据结构 (课程设计)哈希表实现数据结构 (课程设计)哈希表实现
C语言基于哈希表实现通讯录--附源码
设计哈希表实现电话号码查询系统 数据结构课程设计
本文为大家分享了C语言基于哈希表实现通讯录的具体代码,供大家参考,具体内容如下 1.需求分析 本演示程序用C语言编写,完成哈希表的生成,电话号码的插入、以及查找等功能。 (1)按提示输入相应的联系人的相关...
2、从键盘输入各记录,分别以电话号码和用户名为关键字建立哈希表;3、采用再哈希法解决冲突; 4、查找并显示给定电话号码的记录; 5、查找并显示给定用户名的记录。6、在哈希函数确定的前提下,尝试各种不同类型...
哈希表查找,使用哈希表实现学生学籍管理======================
2、从键盘输入各记录,分别以电话号码和用户名为关键字建立哈希表; 3、采用再哈希法解决冲突; 4、查找并显示给定电话号码的记录; 5、查找并显示给定用户名的记录。 6、在哈希函数确定的前提下,尝试各种不同类型...
哈希表实现电话号码查询系统方案.doc
数据结构课程设计C++基于哈希表实现的通讯录系统源码+课程设计报告(95分以上).zip本系统为电话号码查找系统,本系统最频繁的操作为查询功能,查询速度的快慢对此系统有至关重要的影响,因此应该选择合适的数据结构...