C 中链表的结构

Question

很抱歉问了这么愚蠢的问题，但我真的很困惑。

struct Amit
{
  int a;
  struct Amit *link;
}
*start;

这里*link和*start都是用来指向链表的一个节点，但是这两个有什么区别，为什么我们不能把*start 在结构体内？

Answer 1

link 是结构类型的成员。每个 struct Amit 类型的结构都有一个。

start 是“指向struct Amit 的指针”类型的变量。在任何给定时间，最多可以有一个名为 start 的变量可见。

您可以将 start 放入结构中，但它将成为结构的成员（如 link），并且您仍然需要声明结构类型的变量，或者指向他们的指针。

这个想法是，列表中除最后一个之外的每个结构都包含一个指向列表中下一个结构的link指针。通常，列表中最后一个结构的 link 指针为 NULL (0)。向下搜索列表时，您会查看值，当您需要下一项时，您可以按照 link 找到它，当 link 为 NULL 时停止。

struct Amit *item = start;
while (item != NULL && item->a != value_wanted)
    item = item->link;

可以改为构建一个循环链表，它具有不同的停止标准。

---

查看注释，并解释更多一点...

创建列表的一种方法是：

struct Amit root = { 0, NULL };
struct Amit *start = &root;

变量 root 是一个用 root.a == 0 初始化的结构，并且root.link == NULL（或者等效地，root.link == 0）。指针变量start指向（存储）root的地址。给定一个新节点：

struct Amit next = { 1, NULL };

我们可以将其添加到 start 指向的列表的前面：

next.link = start;
start = &next;

创建列表的更合理的方法是动态分配节点，包括根节点。一致性至关重要，因为您必须释放动态分配的节点，并且动态分配某些节点而另一些则不动态分配会很混乱。 （我假设函数 void *emalloc(size_t nbytes); 是 malloc() 的一个覆盖函数，它永远不会返回空指针 - 所以它会进行错误检查对我来说。）

// Create the empty list
start = emalloc(sizeof(*start));
start->a = 0;
start->link = NULL;

// Create a node
struct Amit *node = emalloc(sizeof(*node));
node->a = 42;
node->link = NULL:

// Add the node to the font of the list
node->link = start;
start = node;

您通常会将这些东西打包成管理节点分配、初始化和链接的函数。

struct Amit *add_node(struct Amit *start, int value)
{
    struct Amit *node = emalloc(sizeof(*node));
    node->a = value;
    node->link = start;
    return start;
}

start = add_node(start, 42);
start = add_node(start, 30);
start = add_node(start, 18);

for (node = start; node->link != 0; node = node->link)
    printf("Node: %d (%p)\n", node->a, node->link);

ETC。

Answer 2

这基本上定义了三件事：

• struct（顺便说一下，不要将其大写为 Struct）
• 结构内的成员变量，名为 link
• 结构外部的变量，名为start

您可以通过将结构体的定义与 start 变量的声明分开来减少混乱，如下所示：

struct Amit
{
  int a;
  struct Amit *link;
};

struct Amit *start;

Answer 3

如果您将“链接”重命名为“下一个”，可能会帮助您更好地理解它。链表就像一条链 - 您的“开始”（或通常称为列表“头”）是链的第一个环，链的下一个环通过您的“下一个”指针链接到它（在你的情况下，你的“链接”指针）。当没有其他环时（链接为 NULL），您知道您到达了链上的最后一个项目。

Answer 4

Start 指向列表顶部，并且可供您的程序全局使用。而链接仅跟踪下一个项目，并且在引用特定“节点”时可用。看看这张图，也许可以帮助你直观地理解！

link 在内部跟踪后续项目，该项目跟踪下一个组件的位置，因为它不一定像数组那样连续。

+------+     +------+     +------+
| data |     | data |     | data |
+------+     +------+     +------+
| link |---->| link |---->| link |----> NULL
+------+     +------+     +------+
   ^
   |
 START (Keep track of the whole list.)

希望这有助于澄清。