C中的链表结构 [英] Structure In C for linked list

问题描述

很抱歉提出这样一个愚蠢的问题，但我真的很困惑。

Sorry for asking such a stupid question but I am really confused.

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

此处都是 * link 和 * start 用来指向链表的一个节点，但是两者之间有什么区别，为什么我们不能放 * start 是否在结构体内？

Here both *link and *start are used to point to a node of a linked list, but what's the difference between these two and why can't we put *start inside the structure body?

推荐答案

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

The link is a member of the structure type. Every structure of type struct Amit has one.

开始是类型为指向 struct Amit 的指针的变量。在任何给定时间，最多可以看到一个名为 start 的变量。

The start is a variable of type 'pointer to struct Amit'. At any given time, there can be at most one variable called start visible.

您可以输入 start 在结构内部，但它将成为结构的成员（如 link ），并且您仍然需要声明变量

You could put start inside the structure, but it would become a member of the structure (like link), and you would still need to declare variables of the structure type, or pointers to them.

这个想法是，列表中除最后一个结构之外的每个结构都包含一个链接指向列表中下一个结构的指针。通常，列表上的最后一个结构具有 link 指针，该指针为NULL（0）。向下搜索列表时，您会查看值，当需要下一个项目时，请跟随链接到列表，在链接时停止为NULL。

The idea is that each structure on a list except the last contains a link pointer to the next structure on the list. Normally, the last structure on the list has a link pointer that is NULL (0). When searching down a list, you look at the values, and when you need the next item, you follow the link to it, stopping when the link is NULL.

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

可以构建一个循环链接列表，该列表具有不同的停止条件。

It is possible to build a circular linked list instead, which has a different stop criterion.

看着评论，并解释更多...

Looking at the comments, and explaining a bit more...

创建列表的一种方法是：

One way to create a list is:

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

变量 root 是一个初始化为 root.a == 0 和 root.link == NULL （或等效地， root.link == 0 ）。指针变量 start 指向 root （存储其地址）。给定一个新节点：

The variable root is a structure initialized with root.a == 0 and root.link == NULL (or, equivalently, root.link == 0). The pointer variable start points to (stores the address of) root. Given a new node:

struct Amit next = { 1, NULL };

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

we can add that to the front of the list which start points to:

next.link = start;
start = &next;

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

A more plausible way to create a list is by dynamically allocating nodes, including the root node. Consistency is crucial because you have to free the dynamically allocated nodes, and having some nodes dynamically allocated and others not is messy. (I'm assuming that function void *emalloc(size_t nbytes); is a cover function for malloc() that never returns a null pointer - so it does the error checking for me.)

// 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;

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

You'd normally package this stuff up into functions which manage the allocation, initialization and linking of the nodes.

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);

等。

这篇关于C中的链表结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！