c - C中的双向链表

Question

我正在自学 C，现在正在尝试学习双向链表。按照本书的教程，我发现了一些问题:

typedef struct _seg {
   int  bits[256];
   struct _seg *next, *prev;
} seg;
EXTERN seg *head;
EXTERN seg *last;

基于这样的代码，我知道要从头开始遍历链表，我可以这样做:

seg *p;
p = head;
for ( i = 0; i < k; i++)              
p = p->next;

但是，如何从最后一个节点(定义为最后一个)反向遍历链表？

Answer 1

你可以对称地推理，然后编写代码，例如

seg *p = last;
for (int j=0; j < k && p != NULL; j++)
  p = p->prev;

我添加了测试 p != NULL 以避免 undefined behavior (当列表中的元素少于 k 时；在许多系统上，如果您在这种情况下省略测试，您将遇到 segmentation violation 崩溃)。

不要忘记在编译时启用所有警告和调试信息(例如使用 gcc -Wall -g 编译)并学习如何使用调试器(例如 gdb ).

顺便说一句，C++11是不同于 C99 或 C11 的语言(但有一些兼容性)并为使用 std::list 的链接列表提供语言支持(通过其标准库) .