Проблемы с цепочками хеш-таблиц

Question

У меня большие проблемы с выяснением, как сделать это правильно. Вывод был пока недолго загадан ошибками. Мне удалось исправить большинство из них, но у меня все еще осталось два, и, вероятно, куча логических ошибок.

У меня также есть проблемы с моим алгоритмом хеширования, поэтому я заменил его на простой временный код. Инструкции для правильного:

Используемая хеш-функция имеет вид h(k) = m(k · A mod 1), где A = (√5 - 1)/2 и k · A mod 1 возвращает дробную часть k · A.

Я предполагаю, что я не реализовал это должным образом.

Вот код:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define TABLE_SIZE 8

typedef struct stItem item;
struct stItem {
    int key;
    item *next;
};

void init(item * H[]) {

    int i = 0;
    for (i; i < TABLE_SIZE; i++)
        H[i] = NULL;
}

int h(int k) {

    // this does not work at all, currently using testcode

    /*
    int m = TABLE_SIZE;
    int A = ( sqrt(5.0) - 1) / 2;

    return m * (k * A % 1);
    */

    return k % TABLE_SIZE;
}

void insert(int key, item * H[]) {

    int keyHashed = h(key);

    if (H[keyHashed] == NULL) {

        item * temp = malloc(sizeof(item));
        temp->key = key;
        temp->next = NULL;

        H[keyHashed] = temp;

        free(temp);
    }

    else {

        item * temp = malloc(sizeof(item));
        temp->next = H[keyHashed]->next;

        while (temp != NULL) {
            temp = temp->next;
        }

        temp->key = key;
        temp->next = NULL;
    }
}

int search(int key, item * H[]) {

        int keyHashed = h(key);

        if (H[keyHashed] == NULL)
            return -1;

        else if (H[keyHashed]->key != key) {

            item * temp = malloc(sizeof(item));
            temp->next = H[keyHashed]->next;

            while (temp->key != key && temp != NULL)
                temp = temp->next;

            if (temp->key == key) {
                free(temp);
                return keyHashed;
            }

            else {
                free(temp);
                return -1;
            }
        }

        else
            return keyHashed;
}

void printHash(item * H[]) {

    printf("Table size: %d", TABLE_SIZE);

    int i = 0;

    for (i; i < TABLE_SIZE; i++) {

        if (H[i] != NULL) {
            printf("i: %d          key: %d",i,H[i]->key);

            if (H[i]->next != NULL) {

                item * temp = malloc(sizeof(item));
                temp->next = H[i]->next;

                while (temp != NULL) {
                    printf(" -> %d", temp->key);
                }

                printf("\n");
            }

            else
                printf("\n");
        }
    }
}

void test() {

    // a)
    int array[7] = {111,10112,1113,5568,63,1342,21231};

    item *h[TABLE_SIZE];
    init(h);

    int i = 0;
    for (i; i < 7; i++)
        insert(array[i], h);


    // b)

    printHash(h);


    // c)

    printf("Search result for 1: %d", search(1, h));
    printf("Search result for 10112: %d", search(10112, h));
    printf("Search result for 1113: %d", search(1113, h));
    printf("Search result for 5568: %d", search(5568, h));
    printf("Search result for 337: %d", search(337, h));
}

int main() {
    test();
}

РЕДАКТИРОВАТЬ: Благодаря исправлению user3386109, код теперь компилируется без ошибок, но происходит то, что командная строка просто выскакивает, в ней ничего не отображается и вообще ничего не происходит. Это не закрывается либо. Даже после нескольких минут ожидания.

РЕДАКТИРОВАТЬ 2: После некоторого дополнительного тестирования это выглядит как зависание на функцию вставки. Ничего после цикла test() выполнен.

Если я добавлю это printf("init done %d", h[1]); сразу после init() в тестовой функции я получаю "init done 0" вместо "init done NULL", может ли это быть одной из проблем?

Answer 1

Определение структуры искажено. Я бы предложил следующее

typedef struct stItem item; 
struct stItem {
    int key;
    item *next;
};