c - 如何使用指针释放链表

Question

我试图迭代地为链表释放内存。该列表有一个看起来像这样的结构，在这个链表中，如果它在这个列表中，我不添加一个 url。

struct Node {
    char *url;
    struct Node *next;
};

处理完这个链表后，我试图释放它，但得到了分割错误，我仍然在学习c，除了直接搜索相关主题之外，我对如何调试此类错误没有太多线索。引用了一些SO，这个，这个和这个，仍然无法弄清楚它在哪里崩溃了。

这是我的代码。如果您认为我在此实现中遗漏了任何内容，请随意添加评论。

void url_push(struct Node *head, const char *url, size_t url_size) {
    struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
    new_node->url = malloc(url_size);
    new_node->next = NULL;
    for (int i = 0; i < url_size; i++)
        *(new_node->url + i) = *(url + i);
    struct Node *current = head;
    while(1) {
        if (strcmp(current->url, new_node->url) == 0) {
            printf("Seen page %s!!!!!n", new_node->url);
            free(new_node);
            break;
        } else if (current->next == NULL) {
            current->next = new_node;
            break;
        } else {
            current = current->next;
        }
    }
}
int main() {
    struct Node *head = (struct Node*)malloc(sizeof(struct Node));
    head->url = "/";
    head->next = NULL;
    char *url = "www.google.com";
    url_push(head, url, strlen(url));
    url = "www.yahoo.com";
    url_push(head, url, strlen(url));
    url = "www.google.com";
    url_push(head, url, strlen(url));
    url = "www.wsj.com";
    url_push(head, url, strlen(url));
    struct Node *current = NULL;
    while ((current = head) != NULL) {
        printf("url: %sn", head->url);
        head = head->next;
        free(current->url);
        free(current);
    }
}

编辑：为了减少混乱，我修改了结构。使用strcmp的目的是避免添加已看到的 URL。

Answer 1

head->url = "/";

这不是错误定位的数据，因此您无法释放它！

您的另一个问题是url_push() new_node->url = malloc(url_size);它没有为字符串中的终止 0 分配足够的空间(它也不会复制终止的 0，因此您最终不会"踩踏内存"，但确实有未终止的字符串......请尝试new_node->url = strdup(url);。

风格明智：在url_push()中计算url_size，而不是让每个调用者调用strlen()在被调用的函数中执行一次(请注意，如果您使用strdup()那么您根本不需要url_size。

最后说明：像valgrind这样的工具很容易找到这两个问题。

Answer 2

代码中存在多个问题：

• 您没有为 url_push 中的new_node->url字符串分配空终止符空间，导致strcmp()也有未定义的行为。
• 第一个节点构造不正确：未分配其url指针。
• 你所以不检查内存分配失败

您应该使url_push()更通用：它应该通过返回新的head指针来处理空列表。 您不需要传递url字符串的长度，只需使用 strdup() ，并且您应该避免在检查重复项之前分配新节点。

这是一个修改版本：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Node {
    char *url;
    struct Node *next;
};
struct Node *url_push(struct Node *head, const char *url) {
    struct Node *current = head;
    if (current != NULL) {
        for (;;) {
            if (strcmp(current->url, url) == 0) {
                printf("Seen page %s before!!!!!n", url);
                return head;
            } else if (current->next == NULL) {
                break;
            } else {
                current = current->next;
            }
        }
    }
    struct Node *new_node = malloc(sizeof(struct Node));
    if (new_node == NULL || (new_node->url = strdup(url)) == NULL) {
        fprintf(stderr, "memory allocation failuren");
        exit(1);
    }
    new_node->next = NULL;
    if (current == NULL) {
        head = new_node;
    } else {
        current->next = new_node;
    }
    return head;
}
int main() {
    struct Node *head = NULL;
    head = url_push(head, "/");
    head = url_push(head, "www.google.com");
    head = url_push(head, "www.yahoo.com");
    head = url_push(head, "www.google.com");
    head = url_push(head, "www.wsj.com");
    while (head != NULL) {
        printf("url: %sn", head->url);
        struct Node *current = head;
        head = head->next;
        free(current->url);
        free(current);
    }
    return 0;
}