C中的链表（内存问题）

Question

我正在用 C 创建一个简单的链表，以便习惯一些内存管理。我定义了一个节点结构，其中包含 char* 键、char* 值和节点* next。

void newnode(node *n, int x, int y)
{
    n->key = malloc(x*sizeof(char));
    n->value = malloc(y*sizeof(char)); 
}

//This how i create a new node given a key and value to make sure that I have allocated the proper amount of space. x and y are the strlengths of the key and value being added.

// In the add function I use the following two lines (when it is valid to add a new key value pair)

current->next = malloc(sizeof(node));
node_newnode(current->next,strlen(key),strlen(value));

// My remove function then searches for a key and if that key exists in the structure it removes that node. I use a delete point to keep track of the node needing deletion.

void remove(dict *d, const char *key)
{
    node* delete;
    node* current;
    current = d->head;

    while(current->next != NULL){

        if(strcmp(current->next->key,key)==0){
            delete = current->next;
            if(current->next->next != NULL)
                current = current->next->next;
            else
                current->next = NULL;
            node_destroy(delete);
            break;
        }

        current = current->next;
    }
}

// Here is the node_destroy function I used in remove. 

void node_destroy(node* delete)
{ 
    free(delete->key); 
    free(delete->value); 
    free(delete); 
} 

我在使用此删除功能时遇到问题。从本质上讲，它似乎没有正确删除键值节点，而是留下了节点的残余部分，而不是完全删除它。我不知道为什么这是可能的，特别是当我将指针设置为指向需要删除的节点之后。在最坏的情况下，我觉得我应该泄漏内存，但不知何故这些节点没有被删除，并且当我打印出字典时仍然是结构的一部分。我对必须注意内存布局有点陌生，而且我真的看不出出了什么问题。

有什么建议吗？

PS 我的节点销毁函数没有正确释放内存吗？

Answer 1

当前->下一个 = malloc(sizeof(node));

我假设你的意思是 sizeof(node*)？另外，我可以看看您用来定义节点的结构吗？或者也许是整个计划？

Answer 2

current->next = malloc(sizeof(node));

应该是
当前->下一个 = calloc(1,sizeof(node)); /* 因为 ->next 的安全 NULL 测试！ */

void newnode(node *n, int x, int y)
{
    n->key = malloc(x*sizeof(char));
    n->value = malloc(y*sizeof(char)); 
}

应该是

void newnode(node *n, int x, int y)
{
    n->key = malloc(x+1); /* because x comes from strlen() and sizeof(char)==1 */
    n->value = malloc(y+1); /* because x comes from strlen() and sizeof(char)==1 */ 
}

Answer 3

一方面，您没有为字符串末尾的 null 分配空间...

另一个可能的问题是您应该确保初始化 n->next = NULL;

最后，

current = current->next->next;

应该是

current->next = ...

Answer 4

您永远不会从链表中删除已删除的节点。它应该类似于（检查边缘情况）：

current->next = current->next->next;

例如，如果您有：

{foo:bar} => {栏：baz} => {goo:gai}

并且要删除 {bar:baz}，您需要将 foo 的 next 指针设置为指向 goo。除非删除后 current 成为最后一个元素，否则您不会设置 current->next。

因此，释放的内存仍然存在于您的列表中，您稍后会读取它。这是未定义的行为，但正如您所见，内存可能不会立即重用。

Answer 5

可以立即说的是，如果您的键和值是字符串（根据您的代码，它们是字符串），那么要将长度为 N 的字符串存储在内存中，您需要分配 N+1 个字节，而不是 N 个字节。零终止符需要额外的字节。在代码中，您将相应字符串的 strlen 作为 x 和 y 参数传递给分配函数，然后准确分配 x< /code> 和 y 字符表示键和值。这已经是错误的了。

您没有显示如何填写分配的键和值内存（可能是通过 strcpy），但它肯定会一直超出分配的内存 1 个字节，从而带来灾难性的后果。

在C语言中，可以通过malloc()和calloc()函数获取内存。
有关更多详细信息，请访问http://scanftree.com/Data_Structure/linked-list