如何在 C 中初始化哈希表

Question

我有一个C程序可以创建一个哈希表。 memset没关系，但是，我想用 for 循环初始化。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HSZ 127
#define HASHING(x) ((x)%HSZ)
struct node_t{
    int val;
    struct node_t *next;
};
struct node_t *hash_table[HSZ];
void init(void){
    int i;
    //memset(hash_table,0,sizeof(hash_table));
    for(i=0; i<HSZ; i++){
        hash_table[i]->val = 0;
        hash_table[i]->next = NULL;
    }
}
void insert_hash(int value){
    int key = HASHING(value);
    struct node_t *newNode = (struct node_t*)malloc(sizeof(struct node_t));
    newNode->val = value;
    newNode->next = NULL;
    if(hash_table[key] == NULL){
        hash_table[key] = newNode;
    } else {
        newNode->next = hash_table[key];
        hash_table[key] = newNode;
    }
}
int delete_hash(int value){
    int key = HASHING(value);
    if (hash_table[key] == NULL)
        return 0;
    struct node_t *delNode = NULL;
    if (hash_table[key]->val == value){
        delNode = hash_table[key];
        hash_table[key] = hash_table[key]->next;
    } else {
        struct node_t *node = &hash_table[key];
        struct node_t *next = hash_table[key]->next;
        while (next){
            if (next->val == value){
                node->next = next->next;
                delNode = next;
                break;
            }
            node = next;
            next = node->next;
        }
    }
    return 1;
    free(delNode);
}
void PrintAllHashData()
{
    printf("###Print All Hash Data###n");
    for (int i = 0; i < HSZ; i++){
        if (hash_table[i] != NULL){
            printf("idx : %d ", i);
            struct node_t *node = hash_table[i];
            while (node->next){
                printf("%d ", node->val);
                node = node->next;
            }
            printf("%dn", node->val);
        }
    }
}
int main(void){
    init();
    insert_hash(1);
    insert_hash(3);
    insert_hash(128);
    PrintAllHashData();
}

看看这个代码。

for(i=0; i<HSZ; i++){
    hash_table[i]->val = 0;
    hash_table[i]->next = NULL;
}

当我编译代码时，我正在使用的 IDE 不会引发编译错误，但在执行过程中代码出错并被终止/拖拉。我尝试调试代码，它在这一行出错并停止，我认为错误的访问指向分段错误。

然后，我把这一行改成了

for(i=0; i<HSZ; i++){
    hash_table[i].val = 0;
    hash_table[i]->next = NULL;
}

但是，然后我得到了编译错误，指出'structure type require instead of 'struct node_t *'

我认为我对 C 中的struct没有清楚地了解。如何解决这个问题？

Answer 1

您正在处理的是未定义的行为。

看，struct node_t *hash_table[HSZ];因此，hash_table是数据类型为 struct node_t 的 HSZ (127( 指针的数组。

当你这样做时，

for(i=0; i<HSZ; i++){
    hash_table[i]->val = 0;
    hash_table[i]->next = NULL;
}

hash_table[0]到hash_table[126]指针都没有指向任何东西。因此，应首先初始化它们中的每一个(或全部(以指向struct node_t类型的对象，然后您可以初始化它们。就此而言，使用 memset 不会导致问题，因为memset用全零填充指针的内容。用所有零填充指针和将所有零填充到指针指向的内存是有区别的。

试试这个，

for(i=0; i<HSZ; i++){
    hash_table[i].val = 0;
    hash_table[i]->next = NULL;
}

是完全错误的。

要解决您面临的问题，您需要使用 malloc 动态分配内存。您可以在for循环中执行此操作。

for(i = 0; i < HSZ; i++) 
{
    //Allocate memory of the size struct_node_t
    hash_table[i] = malloc(sizeof(struct node_t)); //Do not cast!
    //Check if memory is allocated
    if(hash_table[i] == NULL)
    {
        //Memory not allocated, set some error state to handle and break
        break;
    }
    //Initialize to zero
    hash_table[i]->val = 0;
    hash_table[i]->next = NULL;
}

Answer 2

struct node_t{
    int val;
    struct node_t *next;
};
struct node_t *hash_table[HSZ];

当你有*hash_table[HSZ]时，这个可变hash_table是一个指针。 所以无论你的动作是什么，使用hash_table->，语法作为指针，意思是指向某处。建议使用指针时应始终分配内存hash_table[i] = malloc(sizeof(struct node_t));

struct node_t hash_table;

但是如果你像这样启动你的变量，你可以使用hash_table.val = 0

所以赋值的方式取决于你如何声明你的变量

Answer 3

struct node_t *hash_table[HSZ];为您提供未设置的指针数组(即不指向任何内容(

void init(void) {
    int i;
    // memset(hash_table,0,sizeof(hash_table));
    for (i = 0; i < HSZ; i++) {
        hash_table[i]->val = 0;
        hash_table[i]->next = NULL;

尝试写入无效指针，这会给出未定义的行为。

要么使数组成为结构数组(而不是指针(：

struct node_t hash_table[HSZ];
...
/* note use of . instead of -> since we have structs not pointers */
hash_table[i].val = 0;

或者分配必要的结构，以便数组指向某些内容：

for (i = 0; i < HSZ; i++) {
    hash_table[i] = malloc(sizeof(struct node_t));
    hash_table[i]->val = 0;
    hash_table[i]->next = NULL;
}