MASS幸运哈希游戏系统开发丨冲突解决方法（代码分析）

2022-06-27 17:16:37 浏览数 (1)

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，用分离链接法处理冲突。

20190816231812121.png20190816231812121.png

表中有9个结点只需1次查找，5个结点需要2次查找，所以查找成功的平均查找次数为：

A S L s = ( 9 5 ∗ 2 ) / 14 ≈ 1.36

参考代码：

#include <iostream>

#include <string>

#include <vector>

#include <cmath>

#include <malloc.h>

using namespace std;

#define MAXTABLESIZE 10000 //允许开辟的最大散列表长度

#define KEYLENGTH 100 //关键字的最大长度

typedef int ElementType;

struct LNode

{

代码语言：txt复制
ElementType data;
代码语言：txt复制
LNode *next;

};

typedef LNode *PtrToNode;

typedef PtrToNode LinkList;

struct TblNode

{

代码语言：txt复制
int tablesize;  //表的最大长度
代码语言：txt复制
LinkList heads; //存放散列单元数据的数组

};

typedef struct TblNode *HashTable;

/返回大于n且不超过MAXTABLESIZE的最小素数/

int NextPrime(int n)

{

代码语言：txt复制
int p = (n % 2) ? n   2 : n   1; //从大于n的下一个奇数开始
代码语言：txt复制
int i;
代码语言：txt复制
while (p <= MAXTABLESIZE)
代码语言：txt复制
{
代码语言：txt复制
    for (i = (int)sqrt(p); i > 2; i--)
代码语言：txt复制
    {
代码语言：txt复制
        if ((p % i) == 0)
代码语言：txt复制
            break;
代码语言：txt复制
    }
代码语言：txt复制
    if (i == 2)
代码语言：txt复制
        break; //说明是素数，结束
代码语言：txt复制
    else
代码语言：txt复制
        p  = 2;
代码语言：txt复制
}
代码语言：txt复制
return p;

}

/创建新的哈希表/

HashTable CreateTable(int table_size)

{

代码语言：txt复制
HashTable h = (HashTable)malloc(sizeof(TblNode));
代码语言：txt复制
h->tablesize = NextPrime(table_size);
代码语言：txt复制
h->heads = (LinkList)malloc(h->tablesize * sizeof(LNode));
代码语言：txt复制
//初始化表头结点
代码语言：txt复制
for (int i = 0; i < h->tablesize; i  )
代码语言：txt复制
{
代码语言：txt复制
    h->heads[i].next = NULL;
代码语言：txt复制
}
代码语言：txt复制
return h;

}

/查找数据的初始位置/

int Hash(ElementType key, int n)

{

代码语言：txt复制
//这里只针对大小写
代码语言：txt复制
return key % 11;

}

/查找元素位置/

LinkList Find(HashTable h, ElementType key)

{

代码语言：txt复制
int pos;
代码语言：txt复制
pos = Hash(key, h->tablesize); //初始散列位置
代码语言：txt复制
LinkList p = h->heads[pos].next; //从链表的第一个节点开始
代码语言：txt复制
while (p && key != p->data)
代码语言：txt复制
{
代码语言：txt复制
    p = p->next;
代码语言：txt复制
}
代码语言：txt复制
return p;

}

/插入新的元素/

bool Insert(HashTable h, ElementType key)

{

代码语言：txt复制
LinkList p = Find(h, key); //先查找key是否存在
代码语言：txt复制
if (!p)
代码语言：txt复制
{
代码语言：txt复制
    //关键词未找到，可以插入
代码语言：txt复制
    LinkList new_cell = (LinkList)malloc(sizeof(LNode));
代码语言：txt复制
    new_cell->data = key;
代码语言：txt复制
    int pos = Hash(key, h->tablesize);
代码语言：txt复制
    new_cell->next = h->heads[pos].next;
代码语言：txt复制
    h->heads[pos].next = new_cell;
代码语言：txt复制
    return true;
代码语言：txt复制
}
代码语言：txt复制
else
代码语言：txt复制
{
代码语言：txt复制
    cout << "键值已存在！" << endl;
代码语言：txt复制
    return false;
代码语言：txt复制
}

}

/销毁链表/

void DestroyTable(HashTable h)

{

代码语言：txt复制
int i;
代码语言：txt复制
LinkList p, tmp;
代码语言：txt复制
//释放每个节点
代码语言：txt复制
for (i = 0; i < h->tablesize; i  )
代码语言：txt复制
{
代码语言：txt复制
    p = h->heads[i].next;
代码语言：txt复制
    while (p)
代码语言：txt复制
    {
代码语言：txt复制
        tmp = p->next;
代码语言：txt复制
        free(p);
代码语言：txt复制
        p = tmp;
代码语言：txt复制
    }
代码语言：txt复制
}
代码语言：txt复制
free(h->heads);
代码语言：txt复制
free(h);

}

int main(int argc, char const *argv[])

{

代码语言：txt复制
int a[] = {47, 7, 29,29, 11, 16, 92, 22, 8, 3, 50, 37, 89, 94, 21};
代码语言：txt复制
int n = 15;
代码语言：txt复制
HashTable h = CreateTable(n);
代码语言：txt复制
for (int i = 0; i < n; i  )
代码语言：txt复制
{
代码语言：txt复制
    Insert(h, a[i]); //插入元素
代码语言：txt复制
}
代码语言：txt复制
for (int i = 0; i < h->tablesize; i  )
代码语言：txt复制
{
代码语言：txt复制
    LinkList p = h->heads[i].next;
代码语言：txt复制
    while (p)
代码语言：txt复制
    {
代码语言：txt复制
        cout << p->data << " "; //打印哈希表元素
代码语言：txt复制
        p = p->next;
代码语言：txt复制
    }
代码语言：txt复制
    cout << endl;
代码语言：txt复制
}
代码语言：txt复制
return 0;

}

hashtable include int key typedef

0 人点赞