创建一个重复链表 returns SIGSEGV

Question

所以我试图创建一个链表的副本，其中包含指向数据的空指针定义是：

typedef struct SinglyLinkedListNode {
    void *data;
    struct SinglyLinkedListNode *next;
}SinglyLinkedListNode;

typedef struct SinglyLinkedList {
    int size;
    struct SinglyLinkedListNode *front;
}SinglyLinkedList;

我克隆链表的函数受到了的启发，唯一的区别是，我的列表没有尾部实现。

这是我的实现

SinglyLinkedListNode *cloneList(SinglyLinkedList *list, SinglyLinkedListNode *head) {
    if(head == NULL)
        return NULL;
    SinglyLinkedListNode *result = (SinglyLinkedListNode *)malloc(sizeof(SinglyLinkedListNode));
    result->data = head->data;
    if(head->next)
        result->next = cloneList(list, head->next);
    return result;
}

SinglyLinkedList *cloneFullList(SinglyLinkedList *list) {
    if(list == NULL)
        return NULL;
    SinglyLinkedList *result = (SinglyLinkedList *)malloc(sizeof(SinglyLinkedList));
    result->size = list->size;
    if(list->front != NULL)
        list->front = cloneList(result, list->front);
    return result;
}

但是当尝试像这样访问数据时

SinglyLinkedList *list1 =  (SinglyLinkedList *)malloc(sizeof(SinglyLinkedList));
list1 = cloneFullList(list); //where list is an already existing list which works correctly
SinglyLinkedListNode *curr1 = (SinglyLinkedListNode *)malloc(sizeof(SinglyLinkedListNode));
curr1 = list1->front;

正在尝试访问 curr1->data returns 出现分段错误。但是当我尝试通过 curr1 = list->front 访问数据时，数据被正确访问。我克隆链表的函数哪里出错了？

Answer 1

我认为你没有正确理解事情是如何运作的…… malloc 为您的对象分配内存，但不对其进行初始化。 list1 = cloneFullList(列表); 这会将指针分配给一个新的目的地，但会丢失分配的轨道 space，而不会对其进行初始化。

此外，您的 cloneList 不会在最后一个元素上设置 next 指针（当 next 为 null 时），因此它仍未初始化。对于 cloneFullList 也是如此（你应该只删除 if(list->front != NULL），因为 cloneList 已经处理了 NULL 的情况）。

Answer 2

这部分变量名有误:

if(list->front != NULL)
    list->front = cloneList(result, list->front);
    // in previous line you modify list not result.
    // so result->front contents is undefined
    // you also missed the else when list->front is null
return result;

在这两个函数中，您可以使用 calloc 将 NULL 指针或 0 整数作为初始值

Answer 3

几个问题：

在您的主代码中，您为 *list1 分配了内存，但随后立即为 list1 分配了一个不同的值，泄漏了分配的内存。
您的代码犯了与 curr1
类似的错误
函数仅在条件为真时才对next（或分别为front）进行赋值，但这些属性应该总是得到一个值。
有一个分配给 list->front，应该分配给 result->front。

没问题，但是 cloneList 的第一个版本确实不需要第一个参数（列表）。你可以只用节点参数来做。

这里是更新的代码：

// No need for the list as first argument:
SinglyLinkedListNode *cloneList(SinglyLinkedListNode *head) {
    if(head == NULL)
        return NULL;
    SinglyLinkedListNode *result = (SinglyLinkedListNode *)malloc(sizeof(SinglyLinkedListNode));
    result->data = head->data;
    result->next = cloneList(head->next); // No condition here
    return result;
}

SinglyLinkedList *cloneFullList(SinglyLinkedList *list) {
    if(list == NULL)
        return NULL;
    SinglyLinkedList *result = (SinglyLinkedList *)malloc(sizeof(SinglyLinkedList));
    result->size = list->size;
    result->front = cloneList(list->front); // No condition here
    return result;
}

int main(void) {
    // ... code that creates `list` comes here ...
    // 
    // No calls to malloc here...
    SinglyLinkedList *list1 = cloneFullList(list);
    SinglyLinkedListNode *curr1 = list1->front;
    // ...
    return 0;
}

创建一个重复链表 returns SIGSEGV

Creating a duplicate linked list returns SIGSEGV

c

algorithm

pointers

linked-list

clone