c - 我在双向链表中查找最后一个元素的代码抛出段错误

Question

我对编程还很陌生，正在学习 C。我正在尝试构建一个功能齐全的双向链表模块，但在获取最后一个元素时出现段错误。

我的功能相同

void get_last(struct Node *node)
{
    if (node)
    {
        while (node->next)
        {
           node = node->next;
        }
    }
    printf("%d",node->prev->value);
}

现在每次我运行它都会抛出一个段错误，我无法成功调试它，尽管我发现这在概念上是正确的，因为当循环结束时节点最终将指向 NULL，并且我的代码将打印上一个项目。 如果我的概念有误，请纠正我。 谢谢

编辑:我在 printf() 中使用了 "%d"，因为这些值是我创建的链表中的整数值

编辑1:这里是创建链表的代码:

void create_list(struct Node *node)
{
    int i;

    first.next=NULL;
    first.prev=NULL;

    node=&first;

    for(i=1;i <=10;i++)
    {
        node->next=(struct Node *)malloc(sizeof(struct Node));
        node->next->prev=node;
        node=node->next;

        node->value=rand()%20;
        node->next=NULL;
    }
}

Answer 1

将 printf 语句移到 if (node) block 中，否则如果使用空指针调用，肯定会出现段错误。

接下来，大概这是为了打印列表中最后一个条目的值，而不是获取最后一个条目。

在您的代码中，您已选择在最后一个条目中将 next 设置为 NULL(并且大概这意味着您将 prev 设置为 NULL 在列表头部？)。如果是这样，您将失去双向链表相对于单链表的主要优势之一(不必遍历列表以找到最后一项。

如果您有一个固定的“头”节点，并且在 next 中让您的最后一项指向它，并且头的 prev 指向最后一项，那么您可以使用一条语句获取最后一项:

last = head.prev;

迭代(例如线性搜索)可以在 node->next == &head 时终止。

但是，您的代码将按如下方式退出

• 如果列表为空(node == NULL)，它将在 printf 上发生段错误
• 如果 node 是非空的，但是 node->next == NULL 那么大概是 node->prev == NULL 所以它将再次出现段错误。
• 如果列表中有一些条目，并且 while 正确终止，它只会在 node->prev 为 NULL 时出现段错误(这表明您的错误也可能在于 add 方法。

在实现任何数据结构或任何通用“类”时(即使是在 C 中)，实现 的部分定义需要是一组不变量。这些是您的实现保证始终为真的事情。

在双向链表的情况下，这些可能是

• 列表中的节点由两个指针(next 和 prev)和一个有效负载组成。
• 每个列表都有一个众所周知的节点，称为head。
• 头节点没有有效负载(关联值)。
• 对于列表中的所有节点，(prev != NULL) && (next != NULL)
• 对于任何节点 n，n->prev->next == n 和 n->next->prev == n
• 在空列表中，(head->next == head->prev) && (head->next == head)

因此您可以为任何列表中的链接定义一个基本的、通用的结构

// Forward declaration so the structure can point to itself
struct dll_links;

// The actual overhead of a DLL
typedef struct dll_links
{
    struct dll_links *next;
    struct dll_links *prev;
    struct dll_links *head;
} dll_links, dll_head;

// A simple macro to cast linkable datastructures as a set of links.
#define AS_LINKS(n) ((dll_links *) n)

并使用它来定义您自己的 Node 数据结构。请注意，我包括对列表的引用 进入每个节点。这允许实现检测违反不变量的尝试(例如删除 head 元素)。

typedef struct
{
    dll_links link;
    int value;
} Node;

现在，给定一个 Node *n，您可以访问 n->link.prev 和 n->link.next 的链接>.

因此，鉴于上述情况，初始化新列表的函数将是

void dll_init(dll_head *list)
{
    list->next = list.prev = list;
    list->head = list;
}

并且会这样使用:

...
dll_head myList;
dll_init(&myList);
...

请注意，这会强制执行所有不变量。

在双向链表上执行的唯一其他操作是插入和删除

// Insert a new node in front of an existing one
void dll_insert(dll_links *newNode, dll_links *before)
{
    dll_links *orignalPrevious = before->prev;

    // First set up the links in the new node
    newNode->prev = originalPrevious;
    newNode->next = before;
    newNode->head = before->head;

    // Now link it in by adjusting the pointers of the surrounding nodes
    before->prev = newNode;
    originalPrevious->next = newNode;
}

// Remove a specified node from a list (and return it)
dll_links *dll_remove(dll_links *node)
{
    // Check the assertion that you can not remove the head element
    assert (node->head != node);

    dll_links *successor = node->next;
    dll_links *predecessor = node->prev;

    // Remove the element from the list
    predecessor->next = successor;
    successor->prev = predecessor;

    // Ensure no dangling pointers in the removed element
    node->next = node->prev = node->head = NULL;
    return node;
}

有了这三个函数，您的 create_list 函数如下所示:

void create_list(dll_head *list)
{
    int i;

    dll_init(list);

    for(i=1;i <=10;i++)
    {
        Node *node = malloc(sizeof(struct Node));
        node->value=rand()%20;
        dll_insert(AS_LINKS(node), list); // Append the new node to the list
    }
}

...
{
    dll_head myList;
    create_list(&myList);
    ...
}

遍历列表、提取第一个或最后一个条目等留作练习。但是考虑一下 添加条目是在 头部之前插入，在前面插入是在 head->next 之前插入， head 元素立即知道哪些节点位于列表的开头和结尾，等等。

dll_links 方法的使用意味着任何操作都不需要了解实际的任何信息 节点结构和有效载荷。这些函数可以链接任何(包括异构列表)。