c语言 - 指向自身的堆栈结构 - 这是怎么回事？

Question

typedef struct _s {     // same definition as before   
    int         value;
    struct _s   *next;
}  STACKITEM;
STACKITEM    *stack = NULL;
 ....
void push_item(int newvalue)
{
    STACKITEM  *new = malloc( sizeof(STACKITEM) );  
    if(new == NULL) {     // check for insufficient memory   
        perror("push_item");
        exit(EXIT_FAILURE);
    }
    new->value   = newvalue;
    new->next    = stack;
    stack        = new;
}

这两行的目的是什么：

new->next    = stack;
stack        = new;

从我所看到的，新 STACKITEM 结构的下一个字段设置为指向堆栈。然后，堆栈设置为指向 STACKITEM 结构 新？这是对的吗？

如果是这样，我不明白这有什么意义。它似乎正在"包裹"堆栈并"关闭"它。换句话说，当我们尝试访问堆栈中的下一个结构时，由于这实际上是最后一个可用的结构，它只能访问自身？

谢谢。

Answer 1

关注这一点：

• stack将始终 (a( 指向堆栈"顶部"的动态节点，或者 (b( 如果堆栈为空，则为 NULL。
• 当要推送新分配的 STACKSTRUCT 节点时，最终stack必须指向该节点，但首先，新分配的结构的next指针必须指向添加(并更改为 stack(之前的先前值 stack (。

我的ascii艺术很糟糕，所以我不会打扰。相反，我准备了一个简单的示例，它使用您的代码，但添加了一个print_stack，以便在添加每个新节点时转储堆栈的当前状态：

#include <stdio.h>
#include <stdlib.h>
typedef struct _s {     // same definition as before
    int         value;
    struct _s   *next;
}  STACKITEM;
STACKITEM    *stack = NULL;
void print_stack()
{
    STACKITEM const* item = stack;
    for (; item != NULL; item = item->next)
        printf("%p : { value=%d; next=%p }n", item, item->value, item->next);
    fputc('n', stdout);
}
void push_item(int newvalue)
{
    STACKITEM *new = malloc( sizeof(STACKITEM) );
    if(new == NULL) // check for insufficient memory
    {
        perror("push_item");
        exit(EXIT_FAILURE);
    }
    printf("push.1: stack = %p, new = %pn", stack, new);
    new->value = newvalue;
    new->next = stack;
    stack = new;
    printf("push.2: stack = %p, new->next = %pn", stack, new->next);
    print_stack();
}
int main()
{
    for (int i=1; i<=5; ++i)
        push_item(i);
}

_{注意：这故意泄漏每个节点。 内存管理不是重点;节点管理是。}

其输出将因实现和计算机而异(打印大量指针值(。按照指针值查看它们是如何连接在一起的。请记住，此输出按自上而下的顺序显示堆栈(即每个打印输出中的第一项是堆栈的"顶部"(。另请注意，这些转储中的每一个都从推送完成后stack指向的节点开始。

示例输出

push.1: stack = 0x0, new = 0x1001054f0
push.2: stack = 0x1001054f0, new->next = 0x0
0x1001054f0 : { value=1; next=0x0 }
push.1: stack = 0x1001054f0, new = 0x100105500
push.2: stack = 0x100105500, new->next = 0x1001054f0
0x100105500 : { value=2; next=0x1001054f0 }
0x1001054f0 : { value=1; next=0x0 }
push.1: stack = 0x100105500, new = 0x100105510
push.2: stack = 0x100105510, new->next = 0x100105500
0x100105510 : { value=3; next=0x100105500 }
0x100105500 : { value=2; next=0x1001054f0 }
0x1001054f0 : { value=1; next=0x0 }
push.1: stack = 0x100105510, new = 0x100105520
push.2: stack = 0x100105520, new->next = 0x100105510
0x100105520 : { value=4; next=0x100105510 }
0x100105510 : { value=3; next=0x100105500 }
0x100105500 : { value=2; next=0x1001054f0 }
0x1001054f0 : { value=1; next=0x0 }
push.1: stack = 0x100105520, new = 0x100200000
push.2: stack = 0x100200000, new->next = 0x100105520
0x100200000 : { value=5; next=0x100105520 }
0x100105520 : { value=4; next=0x100105510 }
0x100105510 : { value=3; next=0x100105500 }
0x100105500 : { value=2; next=0x1001054f0 }
0x1001054f0 : { value=1; next=0x0 }

请注意，在每种情况下，新结构的next指针被分配stack的当前值，然后stack指针被分配新结构的地址。完成后，结构被"推"到堆栈上，新的堆栈顶部反映了这一点。此外，该结构的next指针现在提供指向原始堆栈顶部的指针，从而提供数据结构所需的链接列表链。

Answer 2

new->next    = stack;
stack        = new;

上面的代码行对于在两个节点之间创建链接非常重要。这里发生的事情是让我们用一个例子来理解。

假设您正在为仅1,2和3的值创建链接列表。因此，当您按1传递第一个值时会发生什么，值1将存储在节点 1 new->value =1，并且节点的下一个成员指针将被赋予值为 new->next = stack; ，这意味着指针现在对于第一个节点为 null，全局stack具有第一个节点的地址。

现在您输入第二个值作为2所以现在，第一个内存将为new分配，然后值 2 将被分配为 new->value =2，next指针将包含第一个节点的地址stack因为包含第一个节点的地址。并且stack被分配了第二个节点的地址。所以现在第一个节点和第二个节点之间的链接已经创建。

对于第三个值3它与上述相同。

基本上这是single linklist add_at_begin方法。在这里，每次堆栈都被分配了当前节点的地址，下一次被分配给正在创建链接的next指针。