1 Востаннє редагувалося pika1989 (02.01.2016 00:33:40)

Тема: Видалення елементів стеку у класі

Вітаю всіх з Новим роком!!!

І я до вас знову з проблемкою :[

Задача: Створити клас Стек на основі структури та функцій, розроблених на занятті.
Визначити клас, як шаблонний.

Ось те, що ми робили на парі:

Прихований текст
struct Stack
{
int value;
Stack* next;
};

Stack* MakeStack(int n)
{
int value;
cout<<"Enter "<<n<<" elements: "<<endl;
if(n>0)
{
Stack *top=new Stack;
top->next=NULL;
cin>>value;
top->value=value;
n--;
Stack *p=top;
while(n>0)
{
Stack* el = new Stack;
cin>>value;
el->value=value;
el->next=p;
p=el;
n--;
}
top=p;
return top;
}
return NULL;
}

void Push(Stack*&top, int value)
{
Stack* el = new Stack;
el->value=value;
el->next=top;
top=el;
}

Stack* Pop(Stack *&top)
{
Stack *el=top;
top=top->next;
return el;
}

void Show(Stack *top)
{
cout<<"Stack:\n";
Stack *p=top;
while(p!=NULL)
{
cout<<p->value<<endl;
p=p->next;
}
cout<<endl;
}

void DelStack(Stack*& s)
{
if(s!=NULL)
{
Stack* el, *p=s;
while(p!=NULL)
{
el=p;
p=p->next;
delete el;
}
s=NULL;
}
}


int main()
{
Stack* stack=MakeStack(3);
Show(stack);
Push(stack, 4);
Push(stack, 5);
Show(stack);
cout<<"Main while: "<<endl;
while(stack)
{
Stack* el = Pop(stack);
cout<<el->value<<endl;
delete el;
}
DelStack(stack);

return 0;
}

А ось те, що зробила я (реалізовано поки метод Show, ну і, конструктор і деструктор):

Прихований текст
#include <iostream>

using namespace std;

template <typename T>
class Stack
{
    T value;
    Stack *next;
    
public:

    Stack(int number_elements = 0)
    {
        if (number_elements > 0)
        {
            Stack *top = new Stack;

            cout << "Enter value: ";
            cin >> top->value;

            top->next = NULL;
            number_elements--;

            Stack *p = top;
            while (number_elements > 0)
            {
                Stack* element = new Stack;
                cout << "Enter value: ";
                cin >> element->value;
                element->next = p;
                p = element;
                number_elements--;
            }
            *this = *p;
        }
        else
        {
            this->value = 0;
            next = NULL;
        }
    }

    void Push(T value)
    {
        Stack* element = new Stack;
        element->value = value;
        element->next = this;
        this = element;
    }

    Stack* Pop()
    {
        Stack *element = this;
        this = this->next;
        return element;
    }

    void Show()
    {
        cout << "Stack:\n";
        Stack *p = this;
        while (p != NULL)
        {
            cout << p->value << "\n";
            p = p->next;
        }
        cout << "\n";
    }


    void DeleteStack()
    {
        if (this != NULL)
        {
            Stack* element, *p = this;
            while (p != NULL)
            {
                element = p;
                p = p->next;
                delete element;
            }
            *this = NULL;
        }
    }

    ~Stack()
    {
        if (this != NULL)
            DeleteStack();
    }
};

int main()
{
    int number_elements;
    cout << "Enter the number of elements in the list: ";
    cin >> number_elements;

    Stack <int>stack(number_elements);
    system("cls");
    stack.Show();

    return 0;
}

І, власне, сама проблема: в мене програма вилітає на ось цьому рядку

delete element;

Підкажіть, будь ласка, чому і як правильно реалізувати видалення елементів стеку у класі.
Дякую.

2

Re: Видалення елементів стеку у класі

У вас же була абсолютно та сама проблема зі списками: деструктор викликає DeleteStack, який в циклі робить delete і знову викликає деструктор, який викликає DeleteStack і т.д. - тобто рекурсія в циклі. А вам потрібна або рекурсія, або цикл, але не обидва.

Подякували: pika19891

3 Востаннє редагувалося Master_Sergius (02.01.2016 12:03:23)

Re: Видалення елементів стеку у класі

Я не сіплюсплюшник, але там дійсно кака виходить:

По завершенню main() - автоматично викликається той деструктор, а коли йде виклик

delete element

, де елемент - це цей же клас по суті, то знову ж викликається цей деструктор, який далі продовжує ганяти ту всю біду.

Ось http://www.cprogramming.com/snippets/so … inked-list знайшов доволі схожу реалізацію, теоретично повинна працювати (It has been viewed 35013 times. Rating of 7.7 with 353 votes), але мені її завести не вдалося, можете спробувати.

Подякували: pika19891

4 Востаннє редагувалося pika1989 (02.01.2016 15:26:37)

Re: Видалення елементів стеку у класі

Я всім дякую за допомогу, але проблема вирішилась після того як я додала, до полів класу, вказівник на верхівку стеку.
Ось так:

Прихований текст
#include <iostream>

using namespace std;

template <typename T>
class Stack
{
    T value;
    Stack *next;
    Stack *top;
    
public:

    Stack(int number_elements = 0)
    {
        if (number_elements > 0)
        {
            this->top = new Stack;

            cout << "Enter value: ";
            cin >> top->value;

            top->next = NULL;
            number_elements--;

            Stack *p = top;
            while (number_elements > 0)
            {
                Stack* element = new Stack;
                cout << "Enter value: ";
                cin >> element->value;
                element->next = p;
                p = element;
                number_elements--;
            }
            top = p;
        }
        else
        {
            value = 0;
            next = NULL;
            top = NULL;
        }
    }

    void Push(T value)
    {
        Stack* element = new Stack;
        element->value = value;
        element->next = this;
        top = element;
    }

    Stack* Pop()
    {
        Stack *element = top;
        top = top->next;
        return element;
    }

    void Show()
    {
        if (top != NULL)
        {
            cout << "Stack:\n";
            Stack *p = top;
            while (p != NULL)
            {
                cout << p->value << "\n";
                p = p->next;
            }
            cout << "\n";
        }
        else
            cout << "Stack is empty!\n";
    }


    void DeleteStack()
    {
        if (top != NULL)
        {
            Stack *p = top;
            while (p != NULL)
            {
                //Stack *element = p;
                top = top->next;
                delete p;
                p = top;
            }

            top = NULL;
        }
    }

    ~Stack()
    {
        if (top != NULL)
            DeleteStack();
    }
};

int main()
{
    int number_elements;
    cout << "Enter the number of elements in the list: ";
    cin >> number_elements;

    Stack <int>stack(number_elements);
    system("cls");
    stack.Show();

    return 0;
}

5

Re: Видалення елементів стеку у класі

Цікаво, викладач це зарахує? У вас тут, фактично, немає стеку, а є список з назвою "стек".

Подякували: FakiNyan, leofun012

6

Re: Видалення елементів стеку у класі

koala написав:

Цікаво, викладач це зарахує?

Та йому мабуть ПО... На не розуміння кімось там концепції...

7 Востаннє редагувалося pika1989 (02.01.2016 20:45:18)

Re: Видалення елементів стеку у класі

koala написав:

У вас тут, фактично, немає стеку, а є список з назвою "стек".

Я читала, що стеки можна реалізувати як список або як масив.
Як правильно зробити, щоб стек був стеком? Направте, будь ласка.
Дякую.

8

Re: Видалення елементів стеку у класі

Зі стеком можна робити всього 2 операції: push і pop. Ви створюєте стек в конструкторі, без використання push, і знищуєте в деструкторі, без використання pop. Тобто це не стек, а статична конструкція. Напишіть в main меню "додати елемент, дістати елемент, показати вміст стеку" - тоді буде видно, що це стек. До речі, "показати вміст" - це не стекова операція, але зручна для перевірки.
Ну і стек - це не елемент стеку, тут потрібні 2 різні типи. Хоча теоретично можна і так.

Подякували: pika19891

9 Востаннє редагувалося pika1989 (02.01.2016 22:15:58)

Re: Видалення елементів стеку у класі

Дуже Вам дякую, спробую щось зробити.

Але тоді виходить, що я не дотримаюсь завдання, що нам дав викладач, адже нам потрібно створити клас на основі структури і функцій, що робили на парі.

10

Re: Видалення елементів стеку у класі

pika1989 написав:

Дяже Вам дякую, спробую щось зробити.

Але тоді виходить, що я не дотримаюсь завдання, що нам дав викладач, адже нам потрібно створити клас на основі структури і функцій, що робили на парі.

то зробіть два варіанти

11 Востаннє редагувалося koala (02.01.2016 23:18:49)

Re: Видалення елементів стеку у класі

На парі якраз Push і Pop використовувалися. Щоправда, непослідовно. Але у вас - взагалі без них, вони тільки проголошуються.

12

Re: Видалення елементів стеку у класі

koala написав:

На парі якраз Push і Pop використовувалися. Щоправда, непослідовно. Але у вас - взагалі без них, вони тільки проголошуються.

То був чорновий варіант: я розбиралась з видаленням, а ось остаточний:

Прихований текст
#include <iostream>

using namespace std;

template <typename T>
class Stack
{
    T value;
    Stack *next;
    Stack *top;
    
public:

    Stack(int number_elements = 0)
    {
        if (number_elements > 0)
        {
            this->top = new Stack;

            cout << "Enter value: ";
            cin >> top->value;

            top->next = NULL;
            number_elements--;

            Stack *p = top;
            while (number_elements > 0)
            {
                Stack* element = new Stack;
                cout << "Enter value: ";
                cin >> element->value;
                element->next = p;
                p = element;
                number_elements--;
            }
            top = p;
        }
        else
        {
            value = 0;
            next = NULL;
            top = NULL;
        }
    }

    void Push(T value)
    {
        Stack* element = new Stack;
        element->value = value;
        element->next = top;
        top = element;
    }

    Stack* Pop()
    {
        Stack *element = top;
        top = top->next;
        return element;
    }

    void Show()
    {
        if (top != NULL)
        {
            cout << "Stack:\n";
            Stack *p = top;
            while (p != NULL)
            {
                cout << p->value << "\n";
                p = p->next;
            }
            cout << "\n";
        }
        else
            cout << "Stack is empty!\n";
    }


    void DeleteStack()
    {
        if (top != NULL)
        {
            Stack *p = top;
            while (p != NULL)
            {
                //Stack *element = p;
                top = top->next;
                delete p;
                p = top;
            }

            top = NULL;
        }
    }

    ~Stack()
    {
        if (top != NULL)
            DeleteStack();
    }
};

int main()
{
    int number_elements;
    cout << "Enter the number of elements in the list: ";
    cin >> number_elements;

    Stack <int>stack(number_elements);
    system("cls");
    stack.Show();

    cout << "\n\tPop\n\n";
    stack.Pop();
    stack.Show();

    cout << "\n\tPush\n\n";

    int push_element;
    cout << "Enter element that you want add to stack: ";
    cin >> push_element;

    stack.Push(push_element);
    stack.Show();

    return 0;
}

13

Re: Видалення елементів стеку у класі

Зауваження:
- код не компілюється з нечисловими параметрами шаблону (зокрема, через рядок value = 0);
- ось цей код викликає падіння програми:

    Stack <int> stack;
    for(int i = 0; i<1000000000; ++i){
        stack.Push(1);
        stack.Pop();
    }
    stack.Show();