Функция перефразирования не возвращает правильный указатель - PullRequest
0 голосов
/ 10 ноября 2019



Я получил эту цепочечную хаст-таблицу с реализованной функцией 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");
}
...