c - 关于链表的基本概念查询

一个节点就像一个饮料杯垫。现在想象一大堆那些杯垫，散落在桌子上：

您可以使用绳子和胶带自由地连接它们。

我没有显示双向链接列表中的反向链接，因为它们会增加混乱。下面的讨论对于单链表和双链表都是通用的。

很明显，所有过山车（节点）都可以断开连接并完全孤立，或者可以连接到“前身”和“后继者”——但这样的命名是完全任意的。如果你有 10 个杯垫，如果它们都在一条“线”中相互连接，它们可以组成一个链表，或者如果它们不相连，它们可以组成 10 个链表，或者它们可以组成 10 到 1 之间的任何其他数量的链表- 这仅取决于连接的数量与未连接的数量。

合并/连接/拆分链表的过程只是添加字符串以连接杯垫的编程等价物。

表上的杯垫和 C 中的链表节点之间的主要区别在于，典型示例不提供“表”：没有一个共同的地方可以让所有链表节点都可供检查。对于杯垫，我们有想象中的桌子，它们靠在上面（这里：桌子是一件家具，而不是在页面上组织信息的一种方式）。

因此，您可能接触到链表及其节点的方式 - 远景更像是下面这样：一块难看的绿色桌布覆盖了大部分节点。我们只是瞥见其中两个从下面粘住。

“桌子”绝对有助于将事物形象化——没有桌布。用于“教授”链表的通用 C 代码看起来就像这个丑陋的绿色桌布：

#include <stdlib.h>
typedef struct Node { struct Node *prev, *next; } Node;

Node *appendNode(Node *prev) {
  Node *newNode = calloc(1, sizeof(Node));
  prev->next = newNode;
  newNode->prev = prev;
  return newNode;
}

int main()
{
  Node *first = appendNode(NULL);
  Node *last = first;
  last = appendNode(last);
  last = appendNode(last);
}

此时我们只“看到”列表中的第一个和最后一个节点：它们是从桌布下“伸出”的节点。我让桌布有点透明，但我们在中间（第二个）节点上并没有真正的清晰“把手”。我们知道它在那里，我们可以想象它在那里，但它只能通过来自其他节点的链接访问：

当然，这只是糟糕地教授这门学科的一种方式。不需要桌布。您可以直接创建所有节点，无需任何动态分配。这里我们创建三个没有任何链接的节点：

#include <stdlib.h>
typedef struct Node { struct Node *prev, *next; } Node;
int main()
{
  Node node1 = {}, node2 = {}, node3 = {};
}

初始化 ( ) 的目的与使用而不是= {}动态分配节点的目的相同：我们想要的最后一件事是未初始化的指针。将内存初始化为零，因此动态分配的节点中的指针为 NULL。手动初始化 via做同样的事情。不，你不需要在牙套里放任何东西。你可以写，但那是不必要的。如果初始化列表中没有提供任何值，C 语言被定义为仅对所有内容进行零初始化。callocmalloccalloc= {}= {NULL, NULL}

否则，很容易忘记初始化指针，而且如果没有合适的工具，没有人会费心在介绍性材料中教授这些错误，就很难找到这些错误。如果您使用例如 Asan (Address Sanitizer)，未初始化的指针取消引用将立即被捕获。但我敢打赌，没有人告诉过你关于 Asan 的事情，即使它是免费的并且不难使用——所以我们必须遵从防御性编程。这总是比追逐错误要好。

现在我们清楚地看到了三个节点，我们可以将它们连接起来：

#include <stdlib.h>
typedef struct Node { struct Node *prev, *next; } Node;
void connect(Node *from, Node *to)
{
  from->next = to;
  to->prev = from;
}
int main()
{
  Node node1 = {}, node2 = {}, node3 = {};
  connect(&node1, &node2);
  connect(&node2, &node3);
}

如您所见，很容易拥有任意数量的链表：如果您有三个没有任何连接的节点，它们将形成三个非常孤立的链表，每个链表只有一个元素。但是当你将它们连接在一起时，你会得到一个单一的链表，即使存在相同数量的节点。

您现在可以在自己的列表中添加一些额外的节点：

#include <assert.h>
#include <stdlib.h>
typedef struct Node { struct Node *prev, *next; } Node;
void connect(Node *from, Node *to)
{
  from->next = to;
  to->prev = from;
}
int main()
{
  Node node1 = {}, node2 = {}, node3 = {};
  connect(&node1, &node2);
  connect(&node2, &node3);
  // Create a second list
  Node node4 = {}, node5 = {};
  connect(&node4, &node5);

此时，链表如下所示：

假设我们现在想在第二个和第三个节点之间“拼接”这一秒：

  // Splice the new list between node2 and node3
  connect(&node2, &node4);
  connect(&node5, &node3);

  // Verify that the spliced list has the shape we expect:
  Node *const expected[] = {&node1, &node2, &node4, &node5, &node3, NULL};
  for (Node *toCheck = &node1, **stencil = expected; ;)
  {
    assert(toCheck == *stencil);
    if (!*stencil) break;
    toCheck = toCheck->next;
    ++stencil;
  }
}

现在应该很清楚程序中如何存在多个链表了。将这个单链表转换为 5 个单独的链表非常容易：

#include <assert.h>
#include <stdlib.h>
typedef struct Node { struct Node *prev, *next; } Node;
void connect(Node *from, Node *to)
{
  from->next = to;
  to->prev = from;
}
void unlink(Node *node)
{
    node->prev = node->next = NULL;
}
int main()
{
  Node node1 = {}, node2 = {}, node3 = {};
  connect(&node1, &node2);
  connect(&node2, &node3);
  // Create a second list
  Node node4 = {}, node5 = {};
  connect(&node4, &node5);
  // Splice the new list between node2 and node3
  connect(&node2, &node4);
  connect(&node5, &node3);
  // Separate all the nodes
  unlink(&node1);
  unlink(&node2);
  unlink(&node3);
  unlink(&node4);
  unlink(&node5);

  // Verify that the nodes have no links
  Node *const toCheck[] = {&node1, &node2, &node3, &node4, &node5, NULL};
  for (Node *const *node = *toCheck; *node; ++node)
  {
    assert(!(*node)->prev); // idiomatic way of writing (*node->prev == NULL)
    assert(!(*node)->next); // ditto
  }
}

现在你会问：但是，这一切都很好，但是如果我们想要拥有完全任意数量的节点怎么办？不一定是 5，而是说，500？然后怎样呢？我们应该写 500 个Node变量声明吗？

好吧，你可以有一个数组：

Node nodes[500];

但这不是很灵活。您通常想要的是某种列表的“句柄”——一种“抓取”列表中末端节点的方法。

当然，这需要一种新的数据类型：

typedef struct List { Node *first, *last } List;

现在我们可以编写一些使用这种“句柄”的函数：

#include <assert.h>
#include <stdlib.h>

typedef struct Node { struct Node *prev, *next; } Node;
void connect(Node *from, Node *to)
{
  from->next = to;
  to->prev = from;
}
void unlink(Node *node)
{
    node->prev = node->next = NULL;
}

typedef struct List { Node *first, *last; } List;
Node *appendNode(List *list) {
  Node *node = calloc(1, sizeof(Node));
  if (list->last)
    connect(list->last, node);
  else {
    // the list is empty - there's no last node, and neither can there be a first one
    assert(!list->first);
    list->first = node;
  }
  list->last = node;
  return node;
}

Node *prependNode(List *list) {
  Node *node = calloc(1, sizeof(Node));
  if (list->first)
    connect(node, list->first);
  else {
    // the list is empty - there's no first node, and neither can there be a last one
    assert(!list->last);
    list->last= node;
  }
  list->first = node;
  return node;
}

太好了 - 现在我们可以创建两个列表：

int main()
{
  List list1 = {};
  appendNode(&list1);
  appendNode(&list1);
  appendNode(&list1);

  List list2 = {};
  appendNode(&list2);
  appendNode(&list2);

此时，我们将列表分开：

现在我们可以将它们拼接在一起：

  // Splice the new list between second and third node in list1
  Node *node2 = list1.last->prev;
  Node *node4 = list2.first;
  connect(node2, node4);
  Node *node5 = list2.last;
  Node *node3 = list1.last;
  connect(node5, node3);

  // Verify that the spliced list has the shape we expect:
  Node *const expected[] = {list1.first, node2, node4, node5, node3, NULL};
  for (Node *toCheck = list1.first, **stencil = expected; ;)
  {
    assert(toCheck == *stencil);
    if (!*stencil) break;
    toCheck = toCheck->next;
    ++stencil;
  }
}

当然，此时list2句柄只是半有用的：它不代表一个独立的列表。如果我们想更精确一点，我们可以说以下两个不变量适用于“正确的”列表句柄：

void checkHandle(const List *list)
{
  assert(!list->first == !list->last);
  // The list handle must either have no first and last element, or both (they may
  // be equal - we don't check that here.
  assert(!list->first || !list->first->prev);
  // Either the list has no first element, or the first element has no predecessor.
  assert(!list->last || !list->last->next);
  // Either the list has no last element, or the last element has no successor.
}

鉴于这些不变量，我们需要立即将list2句柄与元素分离，因为它们现在是另一个列表的一部分：

  // after verifying that the spliced list has the expected shape
  list2->first = list2->last = NULL;
}

c - 关于链表的基本概念查询

问题描述

解决方案

推荐阅读