C语言 挑战节点语法

Question

以下是一种语法，是C编程语言中链表的一部分

struct tag-name
{
type member1;
type member2;
.......
.......
struct tag-name *next;
};

为什么我们必须在下一个指针变量之前再次写入结构标签名称。 为什么我们不能使用 void *next 或 int *next 或类似的东西？

Answer 1

对于链表，next条目(或其名称(必须指向下一个节点。在您的情况下，节点类型为tag-name。

所以你需要<type> next;

在 C 中(与 C++ 不同(，请求指向名为 x 的结构的指针的方式是执行struct x *。因此，您看到的代码使您感到困惑/不安。你能简化它吗？是的，你可以。C 有typedef.你可以做

typedef struct tag-name node;

现在你可以拥有

struct tag-name
{
type member1;
type member2;
.......
.......
node *next;
};

你问，我能void* next吗.是的，但为什么要这样做？您将不得不继续将该指针强制转换为指向结构的指针(编译器不知道它隐式指向什么(，代码的读者也会感到惊讶，因为他们希望下一个指针是指向节点的指针。

你问能不能int next.不，它不能，下一个对象是一个节点，而不是一个整数

Answer 2

想想链表的典型插图：

node                node                node
+------+------+     +------+------+     +------+------+
| data | next | --> | data | next | --> | data | next | --> ...
+------+------+     +------+------+     +------+------+

列表中的每一项都是某种类型的节点，该节点包含一个显式指向列表中下一个节点的next成员。 在 C 中，这通常转换为struct类型，例如

struct node 
{
T data; // for some type T
struct node *next;
};

IOW，每个struct node都有一个指向另一个struct node类型的对象的next成员 - 不是int，不是void等，这就是为什么我们不将next声明为int *，或void *，或其他什么。

然而。。。

根据您实现列表的方式，您可以使用struct node *以外的其他内容作为next项。 通常，当我们实现列表时，我们会根据需要使用malloc动态分配每个节点。 但是，如果您知道您的列表永远不会大于某个已知的、相当小的值，则可以留出一个数组struct node作为您的"堆"，并且您的next成员可以是数组索引值：

struct node
{
T data;
int next; // holds the *index* of the next element
} heap[SOME_SIZE];

然后初始化"堆"，以便每个元素明确指向数组中的下一个元素：

for ( int i = 0; i < SOME_SIZE-1; i++ )
{
heap[i].next = i+1;
}
heap[SOME_SIZE-1].next = -1; // use -1 to indicate "null"

现在，您只需要几个整数，一个指向数组中的第一个可用元素，另一个指向列表的头部：

int avail = 0;  // initially points to the first element in the "heap"
int head  = -1; // initially "null"

然后，"分配"一个节点就变成了在"堆"中找到第一个空闲节点的问题：

int node = avail;         // get the index of the next available node in the "heap";
avail = heap[avail].next; // update avail to point to the next available node

"释放"节点只是意味着将该索引添加回avail列表的头部：

heap[node].next = avail; // set this node point to the first free element
avail = node;            // make this node the first free element;

请记住，node和avail不是节点对象，它们只是节点对象数组的索引。

我们通常不会这样做，因为从概念上讲，next直接指向另一个struct node对象比成为数组的索引更简单。 我们仍然可以使用固定大小的数组作为我们的"堆"，我们只使用每个元素的地址而不是它的索引。