当 C 中发生冲突（使用单独的链接）时，无法释放我的散列 table 中的节点

Question

好的，所以我有一个用 C 编写的散列 table。我正在使用单独的链接（链表）来解决冲突。我注意到如果没有冲突并且每个项目都散列到它自己的索引，我可以释放整个 table。但是如果发生冲突并且我在一个索引处有多个值，它只能释放第一个值而不是该索引中的其余值。该程序在尝试释放该索引处的其他程序时崩溃。我尝试调试它，我意识到那些其他值已设置为 NULL，我不确定这是为什么，因为当我将它们插入 table 时，我正在使用 malloc。我知道我错过了什么。如果有人可以提供帮助那将是非常棒的，因为我已经尝试解决这个问题几个小时了：/

代码如下：

int symTabSearch(struct hashTable * h, char * label);
int insertToSymTab(struct hashTable * h, char * label, int locctr);

struct listNode
{
    char * label;
    int address;
    struct listNode * next;
};

struct hashTableNode
{
    int blockCount;         //number of elements in a block
    struct listNode * firstNode;
};

struct hashTable
{
    int tableSize;
    int count;              //number of elements in the table
    struct hashTableNode * table;
};

struct hashTable * createHashTable(int size)
{
    struct hashTable * ht;
    ht = (struct hashTable*)malloc(sizeof(struct hashTable));

    if (!ht)
        return NULL;

    ht->tableSize = size;
    ht->count = 0;
    ht->table = (struct hashTableNode *)malloc(sizeof(struct hashTableNode) * ht->tableSize);

    if (!ht->table)
    {
        printf("Memory error\n");
        return NULL;
    }

    int i;
    for (i = 0; i < ht->tableSize; i++)
    {
        ht->table[i].blockCount = 0;
        ht->table[i].firstNode = NULL;
    }

    return ht;
}

/*hash function: adds up the ascii values of each
character, multiplies by a prime number (37) and mods the sum wih the table size*/
int hash(char * label, int tableSize)
{
    int hashVal = 0;
    size_t i;

    for (i = 0; i < strlen(label); i++)
        hashVal = 37 * hashVal + label[i];

    hashVal %= tableSize;
    if (hashVal < 0)
        hashVal += tableSize;

    return hashVal;
}

int symTabSearch(struct hashTable * h, char * label)
{
    struct listNode * temp;
    temp = h->table[hash(label, h->tableSize)].firstNode; //temp points to the first listNode in table[hashedIndex]

    while (temp)
    {
        if (strcmp(temp->label, label) == 0)
            return 1;   //found

        temp = temp->next;      //go to next link
    }
    return 0;   //not found
}

int insertToSymTab(struct hashTable * h, char * label, int locctr)
{
    int index;
    struct listNode * currentNode, *newNode;

    index = hash(label, h->tableSize);
    currentNode = h->table[index].firstNode;

    newNode = (struct listNode *)malloc(sizeof(struct listNode));
    newNode->label = (char *)malloc(sizeof(char) * 7);  //allocates 7 chars to store label up to 6 chars long (0-5), last one is for the '[=11=]'

    if (!newNode)   //if new node is null
    {
        printf("Error creating new node\n");
        return 0;
    }

    strcpy(newNode->label, label);
    newNode->address = locctr;

    if (h->table[index].firstNode == NULL)      //if first node at table index is empty
    {
        h->table[index].firstNode = newNode;
        h->table[index].firstNode->next = NULL;
    }
    else
    {                                           //firstNode was not empty, so chain newNode to the next empty node
        while (currentNode != NULL)             //go to next available node
            currentNode = currentNode->next;

        currentNode = newNode;
        currentNode->next = NULL;
    }

    h->table[index].blockCount++;
    h->count++;
    return 1;
}

void freeHashTable(struct hashTable * h)        //might not free memory properly, might crash too, test later
{
    int i, j;
    struct listNode * current, *temp;
    char * tempStr;

    if (!h)     //make sure table even has memory to be freed
        return;

    for (i = 0; i < h->tableSize; i++)
    {
        current = h->table[i].firstNode;
        for (j = 0; j < h->table[i].blockCount; j++)
        {
            temp = current;
            tempStr = current->label;
            current = current->next;
            free(temp);
            free(tempStr);
            temp = NULL;
            tempStr = NULL;
        }
    }

    free(h->table);
    h->table = NULL;
    free(h);
    h = NULL;
}

Answer 1

问题出在 insertToSymTab 函数中，当您尝试将节点附加到列表时。

这里的问题是这个循环：

while (currentNode != NULL)             //go to next available node
    currentNode = currentNode->next;

当该循环完成后，您 已通过 列表末尾并且 currentNode 的值为 NULL。更改该指针不会将新节点附加到列表的末尾。

相反，您需要将循环更改为例如

while (currentNode->next != NULL)
    currentNode = currentNode->next;

然后当循环结束时，currentNode 将成为列表中当前的最后一个节点，您可以通过更改 currentNode->next:

来追加新节点

currentNode->next = newNode;

不要忘记将 newNode->next 设置为 NULL。

Answer 2

您的错误在此处的 insertToSymTab 中：

    while (currentNode != NULL)             //go to next available node
        currentNode = currentNode->next;

    currentNode = newNode;
    currentNode->next = NULL;

您将 currentNode 设置为 currentNode->next（复制指针值），然后将 is 设置为新节点。但是 currentNode 没有链接到之前的 currentNode->next，它只是一个 NULL 指针，然后您将其分配给 newNode。

您要么必须为列表的最后一个节点设置 currentNode->Next = newNode，要么使用 struct listnode ** 指针来实现类似于我认为您在此处尝试的内容。

编辑：Joachim 更快地提供了答案

当 C 中发生冲突（使用单独的链接）时，无法释放我的散列 table 中的节点

Cannot free nodes in my hash table when there are collisions (using separate chaining) in C

c

free

hash

memory-management

hashtable