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

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:here是创建链表的代码：

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) 块内，否则如果使用空指针调用，肯定会出现段错误。

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

根据您的代码，您已选择在最后一个条目中将 next 设置为 NULL（这可能意味着您在列表头部将 prev 设置为 NULL ？）。如果是这样，您将失去双重 linked 列表相对于单 linked 列表的主要优势之一（不必遍历列表以找到最后一项。

如果你有一个固定的 "head" 节点，并且你的最后一个项目在 next 中指向它，并且头部的 prev 指向最后一个项目，那么你可以使用一条语句获取最后一项：

last = head.prev;

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

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

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

当实现任何数据结构或任何泛型 'class'（即使它在 C 中）时，实现的部分定义需要是一组不变量.这些是您的实施保证始终正确的事情。

在双重 linked 列表的情况下，这些可能是

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

因此您可以为任何列表

中的link定义一个基本的、通用的结构

// 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，您可以访问 link 作为 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);
...

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

对双重 linked 列表执行的唯一其他操作是插入和删除

// 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 方法意味着 none 的操作需要知道任何关于实际节点结构和有效载荷。这些函数可以link 任何东西（包括异构列表）。

Answer 2

不要使用这种语法printf("%d",node->prev->value);这样做不好

 struct Node *previous = node->prev;
 if (previous != NULL) 
     printf("%d\n", previous->value);

更好，因为当 node 是第一个节点时，node->prev == NULL，那里会有问题。

另外，您的最后一个元素是 node，因为您一直迭代到 node->next == NULL，这应该发生在最后一个元素处，但是您的代码无法解释您描述的行为，还需要更多

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

My code for finding the last element in doubly linked list is throwing segmentation fault

c

segmentation-fault

doubly-linked-list