当前位置：网站首页>Mass lucky hash game system development - conflict resolution (code analysis)

Mass lucky hash game system development - conflict resolution (code analysis)

2022-06-27 19:57:00 【KFZ433】

3.2 Chain address

The chain address method is to store all the conflicting keywords in the corresponding positions in the same single chain table .

Set the keyword sequence to 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, The hash function is taken as h ( k e y ) = k e y m o d    11 h(key) = key \mod 11h(key)=keymod11, Deal with conflicts by separating links .

20190816231812121.png

Table has 9 Nodes only need 1 Search times ,5 Nodes need 2 Search times , So the average number of successful searches is ：

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

Reference code ：

#include <iostream>

#include <string>

#include <vector>

#include <cmath>

#include <malloc.h>

using namespace std;

#define MAXTABLESIZE 10000 // Maximum hash table length allowed

#define KEYLENGTH 100 // The maximum length of a keyword

typedef int ElementType;

struct LNode

{

ElementType data;
LNode *next;

};

typedef LNode *PtrToNode;

typedef PtrToNode LinkList;

struct TblNode

{

int tablesize;  // The maximum length of the table 
LinkList heads; // An array of hash cell data

};

typedef struct TblNode *HashTable;

/ Return is greater than the n And no more than MAXTABLESIZE The minimum prime number of /

int NextPrime(int n)

{

int p = (n % 2) ? n + 2 : n + 1; // From greater than n Start with the next odd number 
int i;
while (p <= MAXTABLESIZE)
{
    for (i = (int)sqrt(p); i > 2; i--)
    {
        if ((p % i) == 0)
            break;
    }
    if (i == 2)
        break; // The explanation is prime , end 
    else
        p += 2;
}
return p;

}

/ Create a new hash table /

HashTable CreateTable(int table_size)

{

HashTable h = (HashTable)malloc(sizeof(TblNode));
h->tablesize = NextPrime(table_size);
h->heads = (LinkList)malloc(h->tablesize * sizeof(LNode));
// Initialize the header node 
for (int i = 0; i < h->tablesize; i++)
{
    h->heads[i].next = NULL;
}
return h;

}

/ Find the initial location of the data /

int Hash(ElementType key, int n)

{

// This is only for case 
return key % 11;

}

/ Find element location /

LinkList Find(HashTable h, ElementType key)

{

int pos;
pos = Hash(key, h->tablesize); // Initial hash position 
LinkList p = h->heads[pos].next; // Start with the first node of the list 
while (p && key != p->data)
{
    p = p->next;
}
return p;

}

/ Insert new elements /

bool Insert(HashTable h, ElementType key)

{

LinkList p = Find(h, key); // To find the first key Whether there is 
if (!p)
{
    // Keyword not found , You can insert 
    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 << " Key value already exists ！" << endl;
    return false;
}

}

/ Destroy the list /

void DestroyTable(HashTable h)

{

int i;
LinkList p, tmp;
// Release each node 
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]); // Insert elements 
}
for (int i = 0; i < h->tablesize; i++)
{
    LinkList p = h->heads[i].next;
    while (p)
    {
        cout << p->data << " "; // Print hash table elements 
        p = p->next;
    }
    cout << endl;
}
return 0;

}

原网站

版权声明
本文为[KFZ433]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/178/202206271756572825.html

边栏推荐

猜你喜欢

随机推荐