C 中的链表 – 方法

Question

假设我们有节点的双向链接列表

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int value;
    struct Node* next;
    struct Node* prev;
} Node;
typedef struct LinkedList {
    Node *first;
    Node *last;
} LinkedList;
void initList(LinkedList* l) {
    l->first = NULL;
    l->last = NULL;
}

我必须编码方法，该方法将一个具有给定值的新节点插入列表末尾并返回指向新节点的指针。我的尝试如下：

Node *insert(LinkedList *list, int value) {
    Node node;
    node.value = value;
    node.prev = list->last;
    node.next = NULL;
    if (list->last != NULL){
        (list->last)->next = &node;
    }else{
        list->first = &node;
        list->last = &node;
    }
    return &node;
}

似乎，在空列表中插入有效，但不适用于非空列表。

（有实现测试，它告诉我插入是否成功。我可以发布他们的代码，但不要认为这很重要）。

那么拜托，错误在哪里？

日志中有一个警告（第 51 行是带有"return &node"的警告）

C:...main.c|51|warning: function returns address of local variable [-Wreturn-local-addr]|

这是严重的问题吗？以及如何删除它？

---

感谢您的回答，但我认为非空列表仍然存在问题，因为根据测试，这失败了：

void test_insert_nonempty(){
    printf("Test 2: ");
    LinkedList l;
    initList(&l);
    Node n;
    n.value = 1;
    n.next = NULL;
    l.first = &n;
    l.last = &n;
    insert(&l, 2);
    if (l.last == NULL) {
        printf("FAILn");
        return;
    }
    if ((l.last->value == 2) && (l.last->prev != NULL)) {
        printf("OKn");
        free(l.last);
    }else{
        printf("FAILn");
    }
}

Answer 1

Node node;是函数insert中的局部变量。一旦您的函数终止并且不再定义，它就会被"销毁"。返回指向函数局部变量的指针是未定义的行为。您必须分配动态内存。动态分配内存是保留的，直到您free它：

Node *insert(LinkedList *list, int value) {
    Node *node = malloc( sizeof( Node ) ); // allocate dynamic memory for one node
    if ( node == NULL )
        return NULL; // faild to allocate dynamic memory
    node->value = value;
    node->prev = list->last;
    node->next = NULL;
    if ( list->first == NULL )
        list->first = node;      // new node is haed of list if list is empty
    else // if ( list->last != NULL ) // if list->first != NULL then list->last != NULL
        list->last->next = node; // successor of last node is new node
    list->last = node;           // tail of list is new node
    return node;
}

注意：为避免内存泄漏，您必须在销毁列表时free列表的每个节点。

Answer 2

您正在返回非静态局部变量的地址，该地址将在从函数返回时消失，并且在从函数返回后取消引用该地址会调用未定义的行为。

您必须分配一些缓冲区并返回其地址。

Node *insert(LinkedList *list, int value) {
    Node *node = malloc(sizeof(Node));
    if (node == NULL) return NULL;
    node->value = value;
    node->prev = list->last;
    node->next = NULL;
    if (list->last != NULL){
        (list->last)->next = node;
    }else{
        list->first = node;
        list->last = node;
    }
    return node;
}

Answer 3

您必须动态分配新节点。

否则函数中的可变node

Node *insert(LinkedList *list, int value) {
    Node node;
    //...

是函数的局部变量，退出函数后将不处于活动状态。因此，指向用于访问它的变量的任何指针都将无效。

该函数可能看起来像

Node * insert( LinkedList *list, int value ) 
{
    Node *node = malloc( sizeof( Node ) );
    if ( node != NULL )
    {
        node->value = value;
        node->prev = list->last;
        node->next = NULL;
        if ( list->last != NULL )
        {
            list->last->next = node;
        }
        else
        {
           list->first = node;
        }
        list->last = node;
    }
    return node;
}