Структура стека, указывающая на себя - Что здесь происходит?

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 всегда будет (а) указывает на динамический узел на «вершине» своего стека, или (б) NULL, если стек пуст.
• Когда newely выделен узел 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 = %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 указатель присваивается адрес новой структуры. После завершения структура была «нажата» на стек, и верхний верхний стек отражает это. Кроме того, указатель 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 оно будет таким же, как указано выше.

В основном это метод add_at_beginsingle linklist. Здесь каждый раз стек присваивается адресом текущего узла, а следующий раз назначается указателю next, который создает ссылку.