Хеш стол с цепочкой в ​​C

Question

Моя домашняя работа для вводного класса C состоит в том, чтобы завершить реализацию хэш-таблицы в C с динамическим распределением. Я должен использовать предоставленный заголовочный файл, и я не уверен, что я делаю неправильно. Заголовочный файл:

/// structure for the nodes of the chains
struct node_s {
    char *key;
    int value;
    struct node_s *link;
};

/// This is the main structure for the overall table.
struct table_s {
    /// This should be used as a pointer to a dynamically
    /// allocated array of pointers to node structures.
    struct node_s **table;

    /// This is for storing the maximum number of buckets/lists in the table.
    size_t bins;

    /// This is for storing the current number of elements in the table
    size_t size;
};
    /// A convenience declaration for referring to a pointer to a HT..
    typedef struct table_s *hash_t;

Что мне нужно и что я пытаюсь реализовать:

/// Allocate a table with some initial empty bins.
/// @param bins -- the number of bins in the table (initally empty)
/// @return -- a pointer to a dynamically allocated hash table
hash_t create_table(int bins){
        struct node_s *nodes[bins];
        for(int i = 0; i < bins; i++){
                nodes[i] = NULL;
        }
        hash_t table = malloc(sizeof(hash_t));
        table -> table = nodes;
        table -> bins = bins;
        table -> size = 0;
        return table;
}

/// Set the value for a key in a given hash table.
/// @note -- if this is the first time setting this key, then the
///          table must make a dynamic copy of the string.  This
///          copy must be freed when the table is freed.
/// @note -- if the table exceeds a load factor of 1 after setting
///          the key/value pair, then this function should trigger
///          rehashing into a larger table.  It will then deallocate
///          the table field in the table_s structure, but it will
///          NOT free the table address in the table parameter.
/// @param table -- a pointer to a hash table

void set(hash_t table, char *key, int value){
        int index = hash(key) % table -> bins;
        printf("Index: %d\n", index);
        struct node_s *node = table -> table[index];
        struct node_s *newNode = malloc(sizeof(newNode));
        newNode -> key  = key;
        newNode -> value = value;
        newNode -> link = NULL;

        printf("New node, key: %s\n", newNode -> key);
        if(node == NULL){
                printf("Filled bucket!\n");
                table -> table[index] = newNode;
                table -> size = table -> size + 1;
        }else{
                printf("Chained!\n");
                while(node -> link != NULL){
                        node = node -> link;
                }
                node -> link  = newNode;
        }
        printf("\n");
}

Что работает:

 char key[max_key];
    hash_t table = create_table(10);
    for (int i = 0; i < trials; i++) {
        int sample = rand() % max_num;
        sprintf(key, "%d", sample);
        set(table, key, sample);
    }

Вывод при запуске:

Index: 7
New node, index: 7, key: 83
NULL!
New bucket filled!

Index: 0
New node, index: 0, key: 86
NOT NULL!
Segmentation fault (core dumped)

Ожидаемое:

Index: 7
New node, index: 7, key: 83
NULL!
New bucket filled!

Index: 0
New node, index: 0, key: 86
NULL!
New bucket filled!

И так до тех пор, пока не возникнет коллизия, когда узел в индексе не равен NULL, поэтому newNode сцепляется, заменяя ссылку NULL * последнего присутствующего узла.

Я знаю, что моя цепочка еще не совсем правильная и требует расширения, но я просто очень запутался, почему он не регистрирует NULL в позиции и не размещает новый узел связанного списка, а вместо этого пытается добавить в связанный список, как будто произошло столкновение.

Answer 1

Совет по кодированию: не ставьте пробел до / после оператора . или стрелки ->.

Вместо этого:

table -> bins

This:

table->bins

Ваша настоящая проблема заключается в следующем.create_table неправильно распределяет память для бинов.Хуже того, он использует массив в стеке.Эта память является неопределенным поведением, как только возвращается create_table.Лучше:

hash_t create_table(int bins){
        hash_t table = malloc(sizeof(hash_t));
        table->table = calloc(sizeof(struct node_s*) * bins); //malloc and zero-init
        table->bins = bins
        table->size = 0;
        return table;
}

Кроме того, вместо этого:

        if(node == NULL){
                printf("Filled bucket!\n");
                table -> table[index] = newNode;
                table -> size = table -> size + 1;
        }else{
                printf("Chained!\n");
                while(node -> link != NULL){
                        node = node -> link;
                }
                node -> link  = newNode;
        }

Просто сделайте это:

printf("%s\n", (table->table[index] ? "Filled bucked!" : "Chained!"));
newNode->link = table->table[index];
table->table[index] = newNode;

Каждый раз, когда новый узел добавляется в корзину,он становится главным элементом в связанном списке корзины.Сцепление происходит в начале списка каждой корзины, а не сзади.