C中的新对象被初始化为现有对象

Question

我试图在C中实现一个循环双链接列表。插入一个元素很好，但是当插入第二个元素时，curr具有与prev相同的地址。

struct ListNode {
    void *item;
    struct ListNode *next;
    struct ListNode *prev;
};

struct List {
    int num_members;
    ListNode head;

    /* function pointers */
    ...
};

int  ListAppend(List* list, void* item){
    ListNode* node = &(list->head);
    ListInsertBefore(list,item,node);
    
    return 0;
}

int  ListInsertBefore(List* list, void* item, ListNode* node){
    ListNode* prev = node->prev;
    ListNode curr;
    curr.item = item;
    
    node->prev = &curr;
    curr.next = node;
    prev->next = &curr;
    curr.prev = prev;

    list->num_members += 1;

    return 0;
}

全球开发银行的产出：

62      curr.item = item;
7: node = (ListNode *) 0xbfffef08
8: *node = {item = 0x0, next = 0xbfffee70, prev = 0xbfffee70}
9: &curr = (ListNode *) 0xbfffee70
10: curr = {item = 0x0, next = 0xbfffef08, prev = 0xbfffef08}
11: prev = (ListNode *) 0xbfffee70
12: *prev = {item = 0x0, next = 0xbfffef08, prev = 0xbfffef08}

Answer 1

ListNode curr in ListInsertBefore是一个局部变量，它将在函数作用域的末尾被销毁。在函数范围外获取、存储和取消引用其地址，使程序具有未定义的行为。您需要使用malloc动态分配内存，例如：

ListNode *ListInsertBefore(List *list, void* item, ListNode *node) {
    ListNode* curr = malloc(sizeof *curr); // allocate memory dynamically
    if(curr) {
        *curr = (ListNode) {item, node, node->prev};

        node->prev->next = curr;
        node->prev = curr;

        list->num_members++;
    }
    return curr;
}

注意:我让它返回一个指向新创建的ListNode的指针，而不是总是返回0。现在可以使用该返回值来检查插入是否实际成功。

还要注意:动态分配的内存也需要使用free释放

List *ListCreate() {
    List *list = malloc(sizeof *list);
    if(list) *list = (List) {0, {NULL, &list->head, &list->head}};
    return list;
}

void ListFree(List *list) {
    for(ListNode *next, *curr = list->head.next; curr != &list->head; curr = next) {
        next = curr->next;
        free(curr);
    }
    free(list);
}

演示

Answer 2

通常，当您添加到这样的链接列表时，有两种情况需要处理。第一个是当列表是空时。这里的程序类似于：

• 分配一个新节点
• 使节点指向有效负载项
• 因为它是一个双链接循环列表：
  • 节点的prev和next指向自己(作为唯一的节点)

• 使列表指向新节点
• 增加列表大小计数器

当列表不是空的时候，现在代码需要将新节点插入到列表的头上。此外，当前的头和尾节点也需要指向新节点。

• 分配一个新节点
• 使节点指向有效负载项
• 因为它是一个双链接循环列表：
  • 新节点的next指向列表的头
  • 新节点的prev指向列表的尾部(list->head->prev)
  • 列表的头节点(list->head) prev指向新节点
  • 列表的尾节点(list->head->prev) next指向新节点
  • 列表的头指向新节点

• 增加列表大小计数器

如果你每一步都在纸上画出来，这真的会很有帮助。为你的指针画箭头。

为了帮助您调试这一点，当您创建一个新的List和ListNode时，可以设置所有指向NULL的指针，并使用assert()函数来检查假定为非空的指针实际上是您所认为的指针。