MASS竞猜幸运哈希游戏系统开发中冲突的解决方法
3.2 链地址法
链地址法就是将相应位置上冲突的所有关键词存储在同一个单链表中。
设关键字序列为 47 , 7 , 29 , 11 , 16 , 92 , 22 , 8 , 3 , 50 , 37 , 89 , 94 , 21 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89, 94, 2147,7,29,11,16,92,22,8,3,50,37,89,94,21，散列函数取为h ( k e y ) = k e y m o d 11 h(key) = key \mod 11h(key)=keymod11，用分离链接法处理冲突。
表中有9个结点只需1次查找，5个结点需要2次查找，所以查找成功的平均查找次数为：
A S L s = ( 9 + 5 ∗ 2 ) / 14 ≈ 1.36
参考代码：
#include
#include
#include
#include
#include
using namespace std;
#define MAXTABLESIZE 10000 //允许开辟的最大散列表长度
#define KEYLENGTH 100 //关键字的最大长度
typedef int ElementType;
struct LNode
{
ElementType data;
LNode *next;
};
typedef LNode *PtrToNode;
typedef PtrToNode LinkList;
struct TblNode
{
int tablesize; //表的最大长度
LinkList heads; //存放散列单元数据的数组
};
typedef struct TblNode *HashTable;
/返回大于n且不超过MAXTABLESIZE的最小素数/
int NextPrime(int n)
{
int p = (n % 2) ? n + 2 : n + 1; //从大于n的下一个奇数开始
int i;
while (p <= MAXTABLESIZE)
{
for (i = (int)sqrt(p); i > 2; i--)
{
if ((p % i) == 0)
break;
}
if (i == 2)
break; //说明是素数，结束
else
p += 2;
}
return p;
}
/创建新的哈希表/
HashTable CreateTable(int table_size)
{
HashTable h = (HashTable)malloc(sizeof(TblNode));
h->tablesize = NextPrime(table_size);
h->heads = (LinkList)malloc(h->tablesize * sizeof(LNode));
//初始化表头结点
for (int i = 0; i < h->tablesize; i++)
{
h->heads[i].next = NULL;
}
return h;
}
/查找数据的初始位置/
int Hash(ElementType key, int n)
{
//这里只针对大小写
return key % 11;
}
/查找元素位置/
LinkList Find(HashTable h, ElementType key)
{
int pos;
pos = Hash(key, h->tablesize); //初始散列位置
LinkList p = h->heads[pos].next; //从链表的第一个节点开始
while (p && key != p->data)
{
p = p->next;
}
return p;
}
/插入新的元素/
bool Insert(HashTable h, ElementType key)
{
LinkList p = Find(h, key); //先查找key是否存在
if (!p)
{
//关键词未找到，可以插入
LinkList new_cell = (LinkList)malloc(sizeof(LNode));
new_cell->data = key;
int pos = Hash(key, h->tablesize);
new_cell->next = h->heads[pos].next;
h->heads[pos].next = new_cell;
return true;
}
else
{
cout << "键值已存在！" << endl;
return false;
}
}
/销毁链表/
void DestroyTable(HashTable h)
{
int i;
LinkList p, tmp;
//释放每个节点
for (i = 0; i < h->tablesize; i++)
{
p = h->heads[i].next;
while (p)
{
tmp = p->next;
free(p);
p = tmp;
}
}
free(h->heads);
free(h);
}
int main(int argc, char const *argv[])
{
int a[] = {47, 7, 29,29, 11, 16, 92, 22, 8, 3, 50, 37, 89, 94, 21};
int n = 15;
HashTable h = CreateTable(n);
for (int i = 0; i < n; i++)
{
Insert(h, a[i]); //插入元素
}
for (int i = 0; i < h->tablesize; i++)
{
LinkList p = h->heads[i].next;
while (p)
{
cout << p->data << " "; //打印哈希表元素
p = p->next;
}
cout << endl;
}
return 0;
}
审核编辑：符乾江
-
代码
+关注
关注
30文章
4779浏览量
68519 -
哈希函数
+关注
关注
0文章
43浏览量
9446
发布评论请先 登录
相关推荐
mac的常见问题解决方法
诊断系统开发咨询服务
Ubuntu系统常见问题及解决方法
常见伺服系统故障及解决方法
嵌入式系统开发中的测试方法 嵌入式系统开发与AI结合应用
嵌入式系统开发与硬件的关系 嵌入式系统开发常见问题解决
常见晶振故障及解决方法 晶振在物联网中的应用
以太网组网常见故障及解决方法
常见GPU问题及解决方法
ChatGPT 在游戏开发中的创新应用
IP地址冲突解决方法图示
CMM三坐标测量机MASS多测头系统
接地网阻值偏大的原因及解决方法
液压系统由哪几部分组成 液压系统常见故障及解决方法
康谋方案 | 加速自动驾驶系统开发的技术解决方案
工商网监
评论