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 的 prior 值(并更改为 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 = %p\n", stack, new);
    new->value = newvalue;
    new->next = stack;
    stack = new;
    printf("push.2: stack = %p, new->next = %p\n", 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 指针指定为新结构的地址。一旦完成，该结构就被“推”到堆栈上，新的堆栈顶部反射(reflect)了这一点。此外，该结构的下一个指针现在提供了指向原始堆栈顶部的指针，从而提供了数据结构所需的链表链。