Я получил эту цепочечную хаст-таблицу с реализованной функцией rehash ().
Моя функция перефразирования должна возвращать указатель на новую хеш-таблицу, и эта новая хеш-таблица должна использоваться вmain
Я вставляю некоторые элементы (1,5,9,3,52,65, ....) и затем, когда я обнаруживаю, что у меня есть 5 элементов, сохраненных в одной клавише, я делаю перефразировкуПосле перефразирования я должен продолжить добавлять элементы в новую таблицу.
Прямо сейчас после перефразирования main по-прежнему использует старую таблицу вместо новой.
#include <stdio.h>
#include <stdlib.h>
//#define MAX 10
#define CAPACITY 5
#define FACTOR 0.7
int flag = 0;
int MAX = 20;
typedef struct hast_table_item
{
int data;
int key;
struct hast_table_item *next_data;
}HASH_TABLE_ITEM;
int hash_function(int value)
{
return value % MAX;
}
void display_hash_table(HASH_TABLE_ITEM **hash_table);
HASH_TABLE_ITEM* rehash(HASH_TABLE_ITEM **old_hash_table) {
int current_capacity = MAX;
int old_capacity = current_capacity;
int new_capacity = old_capacity*2;
HASH_TABLE_ITEM *new_hash_table[new_capacity];
int i_my_hash;
MAX *= 2;
flag = 1;
/* Clear the table */
for (i_my_hash=0; i_my_hash<new_capacity; i_my_hash++) {
new_hash_table[i_my_hash] = NULL;
}
HASH_TABLE_ITEM *p, *next;
/* Do Rehash */
for (i_my_hash=0; i_my_hash<old_capacity; i_my_hash++) {
for (p = old_hash_table[i_my_hash]; NULL != p; p = next) {
next = p->next_data;
insert_hti(new_hash_table, p->data);
}
}
flag = 0;
display_hash_table(new_hash_table);
return new_hash_table; // This should return me pointer on a new hash table and I need to use it in my main() but it does not return the pointer correctly
}
HASH_TABLE_ITEM *check_capacity(HASH_TABLE_ITEM **hash_table, HASH_TABLE_ITEM *new_item)
{
int count = 0;
HASH_TABLE_ITEM *current = new_item;
int i;
for (i=0; i<MAX; i++) {
if (hash_table[i] != NULL) {
while (current != NULL) {
count++;
current = current->next_data;
if (count == 5) { // If I have 5 or more elements on one key, do rehash
printf("--- REHASHING ---\n");
if (flag == 0){
rehash(hash_table);
return NULL;
}
}
}
}
count = 0;
}
return NULL;
}
void insert_hti(HASH_TABLE_ITEM **hash_table, int value)
{
HASH_TABLE_ITEM *new_item = NULL;
new_item = (HASH_TABLE_ITEM*)malloc(sizeof(HASH_TABLE_ITEM));
new_item->data = value;
new_item->key = hash_function(value);
new_item->next_data = NULL;
HASH_TABLE_ITEM *a = hash_table[new_item->key];
if (hash_table[new_item->key] == NULL) {
hash_table[new_item->key] = new_item;
printf("Inserted element %d in table.\n", new_item->data);
}
else {
while (a != NULL){
if(a->data == value){
return;
}
a = a->next_data;
}
new_item->next_data = hash_table[new_item->key];
hash_table[new_item->key] = new_item;
printf("Inserted element %d in table.\n", new_item->data);
check_capacity(hash_table,new_item);
//HASH_TABLE_ITEM *b = check_capacity(hash_table,new_item);
//if (b != NULL){
// *hash_table = b;
//}
}
}
HASH_TABLE_ITEM *find_hti(HASH_TABLE_ITEM **hash_table, int value)
{
HASH_TABLE_ITEM *current = NULL;
int hash_key = hash_function(value);
if (hash_table[hash_key] == NULL) {
return NULL;
}
if (hash_table[hash_key]->data == value) {
printf("Našla som element %d na kľúči %d.\n", value, hash_key);
return hash_table[hash_key];
}
current = hash_table[hash_key];
while (current->next_data) {
if (current->next_data->data == value) {
printf("Našla som element %d na kľúči %d.\n", value, hash_key);
return current->next_data;
}
else {
current = current->next_data;
current->next_data = current->next_data->next_data;
}
}
return NULL;
}
void display_hash_table(HASH_TABLE_ITEM **hash_table)
{
HASH_TABLE_ITEM *current = NULL;
int i;
for (i=0; i<MAX; i++) {
if (hash_table[i] != NULL) {
current = hash_table[i];
printf("Table Key (%d) --> ", i);
while (current != NULL) {
printf(" | Data: %d |", current->data);
current = current->next_data;
}
printf("\n");
}
}
}
void main() {
/* Declare My Hash */
int insert_value_my_hash = 0;
int i_my_hash;
HASH_TABLE_ITEM *hash_table[MAX];
/* Insert into My Hash */
for (i_my_hash=0; i_my_hash<MAX; i_my_hash++) {
hash_table[i_my_hash] = NULL;
}
while (scanf("%d", &insert_value_my_hash) == 1) {
insert_hti(&hash_table, insert_value_my_hash); // Here the hash table should be updated after rehashing
//display_hash_table(hash_table);
}
display_hash_table(hash_table);
//find_hti(hash_table, 21);
printf("\n\n");
}