реализация стека - связанный список - PullRequest
Новая
       14

реализация стека - связанный список

1 голос
/ 24 марта 2020

Я пытаюсь выяснить, почему моя структура стека не выталкивает элементы и считает, что стек равен NULL (я получаю условие else из pop (), выполняющегося оба раза)? Я запутался, потому что printf показывает, что элементы добавляются в стек. 

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
        int element;
        struct node *pnext;
} node_t;

void push(node_t *stack, int elem){
        node_t *new = (node_t*) malloc(sizeof(node_t)); // allocate pointer to new node memory 
        if (new == NULL) perror("Out of memory");
        new->pnext = stack; 
        new->element = elem;
        stack = new; // moves the stack back to the top 
        printf("%d\n", stack->element);
}

int pop(node_t *stack) {
        if (stack != NULL) {
                node_t *pelem = stack;
                int elem = stack->element;
                stack = pelem->pnext; // move the stack down 
                free(pelem);  // free the pointer to the popped element memory 
                return elem;
        }
        else {
                printf("fail");
                return 0; // or some other special value
        }
}

int main(int argc, char *argv[]){
        node_t *stack = NULL ; // start stack as null 
        push(stack, 3);
        push(stack, 5);
        int p1 = pop(stack);
        int p2 = pop(stack);
        printf("Popped elements: %d %d\n", p1, p2);
        return 0 ;
}

1 Ответ

1 голос
/ 24 марта 2020

Как сказано в замечании, когда вы выходите push / pop переменная stack в main не изменяется, так что вы ничего не сделали, кроме утечка памяти в pu sh

Чтобы иметь новый стек в main после pu sh, эта функция может вернуть новый стек, но это не так возможно для pop , уже возвращающего всплывающее значение, поэтому чтобы иметь одинаковое решение для обоих, просто дайте адрес переменной в параметре функциям, чтобы позволить его изменить, так что двойной указатель, а не простой 

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
        int element;
        struct node *pnext;
} node_t;

void push(node_t ** stack, int elem){
        node_t *new = (node_t*) malloc(sizeof(node_t)); // allocate pointer to new node memory 
        if (new == NULL) {
          perror("Out of memory");
          exit(-1);
        }
        new->pnext = *stack; 
        new->element = elem;
        *stack = new; // moves the stack back to the top 
        printf("%d\n", (*stack)->element);
}

int pop(node_t ** stack) {
        if (*stack != NULL) {
                node_t *pelem = *stack;
                int elem = (*stack)->element;
                *stack = pelem->pnext; // move the stack down 
                free(pelem);  // free the pointer to the popped element memory 
                return elem;
        }
        else {
                printf("fail");
                return 0; // or some other special value
        }
}

int main(int argc, char *argv[]){
        node_t *stack = NULL ; // start stack as null 
        push(&stack, 3);
        push(&stack, 5);
        int p1 = pop(&stack);
        int p2 = pop(&stack);
        printf("Popped elements: %d %d\n", p1, p2);
        return 0 ;
}

Компиляция и исполнение: 

% gcc -Wall s.c
% ./a.out
3
5
Popped elements: 5 3
...