Как правильно использовать указатель на вершину стека в виде локальной переменной?

Question

В общем, программа должна определять, принадлежит ли элемент стеку. Но почему-то работает неправильно, то есть если элемент и принадлежит, то выдается сообщение об обратном. Посмотрел в отладчике: после каждого добавления элемента стек сбрасывается, то есть элемент не добавляется, а состояние стека становится изначальным. Не пойму, как это исправить.

#include <stdio.h>
#include <locale.h>

struct list
{
   int elem;
   list *next;
   list(int _elem = 0, list *_next = NULL) : elem(_elem), next(_next) {};
};
typedef list stack;

inline bool IsEmpty(stack* s)
{
   return s == NULL;
}

void Push(stack* s, int elem)
{
   stack *l = new stack(elem);
   l->next = s;
   s = l;
}

int Pop(stack* s)
{
   if (IsEmpty(s))
      return 2;
   else
   {
      stack *l = s;
      int elem = s->elem;
      s = s->next;
      delete l;
      return elem;
   }
}

bool isInStack(stack* s, int x)
{
   list *l = s;
   for (l = s; l && l->elem != x; l = l->next);
   return l != NULL;
}

int main()
{
   setlocale(LC_ALL, "");
   char ch = '@';
   int elem, x;
   stack* s = new stack;
   puts("Заполняем стек: ");
   do
   {
      scanf_s("%d", &elem);
      Push(s, elem);
   } while (ch = getchar() != '\n');

   if (IsEmpty(s))
   {
      puts("Стек пуст!");
      return 0;
   }
   else
   {
      printf("Какой элемент проверить на принадлежность стеку?: ");
      scanf_s("%d", &x);
      if (isInStack(s, x) == true)
      {
         while(!IsEmpty(s))
            printf("%d   ", Pop(s));
         printf("\nДа, элемент %d есть в стеке.\n", x);
      }
      else
         printf("\nЭлемента %d нет в стеке.\n", x);
   }
   return 0;
}

Answer 1

Когда вы выполняете методы Push и Pop, вам нужно переместить указатель на вершину стека. Если вы просто передаёте в эти функции этот указатель, то изменить его значение так, чтобы вне функции поменялась вершина, у вас не получится. Чтобы это сделать, нужно передавать двойной указатель. То есть адрес на вершину стека.

#include <stdio.h>
#include <locale.h>

struct list
{
    int elem;
    list* next;
    list(int _elem = 0, list * _next = NULL) : elem(_elem), next(_next) {};
};
typedef list stack;

inline bool IsEmpty(stack* s)
{
    return s == NULL;
}

void Push(stack** s, int elem)
{
    stack* l = new stack(elem);
    l->next = *s;
    *s = l;
}

int Pop(stack** s)
{
    if (IsEmpty(*s))
        return 2;
    else
    {
        stack* l = *s;
        int elem = (*s)->elem;
        *s = (*s)->next;
        delete l;
        return elem;
    }
}

bool isInStack(stack* s, int x)
{
    list* l = s;
    for (l = s; l && l->elem != x; l = l->next);
    return l != NULL;
}

int main()
{
    setlocale(LC_ALL, "");
    char ch = '@';
    int elem, x;
    stack* s = new stack;
    puts("Заполняем стек: ");
    do
    {
        scanf_s("%d", &elem);
        Push(&s, elem);
    } while (ch = getchar() != '\n');

    if (IsEmpty(s))
    {
        puts("Стек пуст!");
        return 0;
    }
    else
    {
        printf("Какой элемент проверить на принадлежность стеку?: ");
        scanf_s("%d", &x);
        if (isInStack(s, x) == true)
        {
            while (!IsEmpty(s))
                printf("%d   ", Pop(&s));
            printf("\nДа, элемент %d есть в стеке.\n", x);
        }
        else
            printf("\nЭлемента %d нет в стеке.\n", x);
    }
    return 0;
}

Или ещё проще, можно передавать указатель по ссылке.

void Push(stack* &s, int elem)
{
    stack* l = new stack(elem);
    l->next = s;
    s = l;
}

int Pop(stack* &s)
{
    if (IsEmpty(s))
        return 2;
    else
    {
        stack* l = s;
        int elem = s->elem;
        s = s->next;
        delete l;
        return elem;
    }
}

БЛОГ НА HUSL

Как правильно использовать указатель на вершину стека в виде локальной переменной?

Ответы (1 шт):