c - C链表遍历中移除条目并释放桶节点时出错

Question

我正在尝试开发一个具有链式链表散列的散列表来纠正冲突，但我的remove_entry函数似乎出现错误。我几乎只使用指针，因此我会根据需要动态分配和释放内存。

以下是我的表和存储桶数据类型的结构:

typedef struct bucket {
char *key;
void *value;
struct bucket *next;
} Bucket;

typedef struct {
   int key_count;
   int table_size;
   void (*free_value)(void *);
   Bucket **buckets;
} Table;

这是我的删除功能。我尝试添加评论来解释正在发生的事情:

int remove_entry(Table *table, const char *key) {

    int hash;
    Bucket *cur, *prev;

    if (table == NULL || key == NULL) {
        return FAILURE;
    }

    hash = hash_code(key) % (table->table_size);

    /* case: key not present at lead bucket position */
    if (table->buckets[hash] == NULL) {
        return FAILURE;

    } else {
        cur = table->buckets[hash];
        /* traverse thru the chain from table->buckets[hash]
         * to see if the key exists somewhere. loop only can run the 
         * first time if its key does not match the paramteter key, so
         * if they do match then we proceed to the logic below this
         * loop (2nd if statement), acting on the FIRST (lead) bucket */
        while (strcmp(cur->key, key) != 0 && cur != NULL) {
            prev = cur;
            cur = cur->next;
        }

        /* case - key not found anywhere (cur == null) */
        if (cur == NULL) {
            return FAILURE;
        }
        /* case - key found in chain (strcmp returned 0, keys match) */
        if (strcmp(cur->key, key) == 0) {
            if (table->free_value != NULL) {
                table->free_value(cur->value);
                cur->value = NULL;
            }
            free(cur->key);
            cur->key = NULL;
            if (cur->next != NULL) {
                prev->next = cur->next;
            }
            free(cur);
            cur = NULL;
            table->key_count -= 1;
            return SUCCESS;
        }
    }
    return FAILURE;
}

valgrind 告诉我在函数底部调用 cur 上的 free() 时出现问题，但我不明白为什么这是一个问题。我发现我遇到的总体问题是，即使 cur 发生了变化，存储桶的地址(在适当的索引“哈希”处)也没有发生变化。

提前致谢。

Answer 1

我认为您的错误涉及当存在多个存储桶时删除第一个存储桶。

在此代码段中:

 cur = table->buckets[hash];
 while (strcmp(cur->key, key) != 0 && cur != NULL) {
     prev = cur;
     cur = cur->next;
 }

如果key确实等于cur指针指向的第一个bucket，那么你的WHILE循环的内部代码永远不会被调用。结果是指针 prev 未定义...您从未将其预先设置为 NULL，并且它没有在被绕过的循环中设置。

接下来的代码片段:

if (cur->next != NULL) {
    prev->next = cur->next;
}

将会失败，因为 prev 中要么有零 (NULL)，要么有一些未定义的内存位置存储在其中。

而且上面代码片段的逻辑也不太正确；如果这是最后一个被删除的存储桶(因此cur->next确实等于NULL)，您仍然希望将该NULL移回prev->next (或列表头)，以便prev“知道”它现在是链接列表的末尾。

当第一个存储桶是一个被移除。这是一个常见的错误，就在本周我已经多次回答过这个错误。

所以我认为你需要将代码更改为:

int remove_entry(Table *table, const char *key) {

    int hash;
    Bucket *cur;
    Bucket *prev = NULL;

    if (table == NULL || key == NULL) {
        return FAILURE;
    }

    hash = hash_code(key) % (table->table_size);

    /* case: key not present at lead bucket position */
    if (table->buckets[hash] == NULL) {
        return FAILURE;

    } else {
        cur = table->buckets[hash];
        /* traverse thru the chain from table->buckets[hash]
         * to see if the key exists somewhere. loop only can run the 
         * first time if its key does not match the paramteter key, so
         * if they do match then we proceed to the logic below this
         * loop (2nd if statement), acting on the FIRST (lead) bucket */
        while (strcmp(cur->key, key) != 0 && cur != NULL) {
            prev = cur;
            cur = cur->next;
        }

        /* case - key not found anywhere (cur == null) */
        if (cur == NULL) {
            return FAILURE;
        }
        /* case - key found in chain (strcmp returned 0, keys match) */
        if (strcmp(cur->key, key) == 0) {
            if (table->free_value != NULL) {
                table->free_value(cur->value);
                cur->value = NULL;
            }
            free(cur->key);
            cur->key = NULL;
            if (prev != NULL) {
                prev->next = cur->next;  // even want to copy-back when cur->next == NULL
            }
            else
            {
                table->buckets[hash] = cur->next;  // even want to copy-back when cur->next == NULL
            }
            free(cur);
            cur = NULL;
            table->key_count -= 1;
            return SUCCESS;
        }
    }
    return FAILURE;
}

我不确定为什么free(cur)会给你一个错误，但是一旦你修复了代码以正确处理链接列表并且没有>prev 指针未正确初始化，您也许能够找出仍然错误的地方。

还有一个小问题，您确实不需要以下独立的 IF 语句:if (strcmp(cur->key, key) == 0) {。当退出 WHILE 循环时，唯一的两个条件是 cur 确实 == NULL，或 strcmp(cur->key, key) 确实 == 0。需要第二个 IF 语句。这并没有错，只是效率有点低。