1 Востаннє редагувалося pika1989 (02.01.2016 01: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 13: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), але мені її завести не вдалося, можете спробувати.

Мій блог про ОС сімейства *nix - http://nixtravelling.blogspot.com/
Подякували: pika19891

4 Востаннє редагувалося pika1989 (02.01.2016 16: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 21:45:18)

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

koala написав:

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

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

8

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

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

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

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

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

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

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

10

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

pika1989 написав:

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

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

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

тут спілкуються українці (серед них є програмісти)
https://discord.gg/Zk29v4P

11 Востаннє редагувалося koala (03.01.2016 00: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();

14

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

Прихований текст
Давно-давно писав на чистому C (досконало не дебажив, робить і годі), може щось і почерпнете із моїх роздумів.

Вважайте так:
- stack_init() - конструктор
- stack_deinit() - деструктор

stack.h

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <ctype.h>
#include <string.h>

#define STACK_SIZE 100      // максимальное кол-во элементов в стеке (S_ITEM)


#define stack_init() S_PSTACK pStack = st_init()

#define push(a, b) st_push(pStack, a, b)
#define pop() st_pop(pStack)

#define stack_size() st_get_size(pStack)

#define stack_deinit() st_deinit(pStack)


// тестовая структура для занесения в стек
typedef struct _S_EXAMPLE_STRUCT {
    int age;
    char name[100];
} S_EXAMPLE_STRUCT, *S_PEXAMPLE_STRUCT;

// какие типы данных можно заносить в стек
typedef enum _E_TYPE {
    TYPE_INT,               // int
    TYPE_CHAR,              // char
    TYPE_STR,               // char* (строка)
    TYPE_EXAMPLE            // S_EXAMPLE_STRUCT (тестовая структура)
} E_TYPE;

// обьединение, котороые может хранить одно из перечисленных типов данных
typedef union _U_DATA {
    int t_int;
    char t_char;
    char *t_pchar;
    S_PEXAMPLE_STRUCT t_pexample;
} U_DATA, *U_PDATA;

// данные и тип этих данных
typedef struct _S_ITEM {
    U_DATA u_data;
    E_TYPE s_type;
} S_ITEM, *S_PITEM;

// главная структура стека, содержащая указатель на текущий и начальный элементы
typedef struct _S_STACK {
    S_ITEM **esp;
    S_ITEM **esp_first;
} S_STACK, *S_PSTACK;


S_PITEM add_int_val(int);
S_PITEM add_char_val(char);
S_PITEM add_str_val(char*);
S_PITEM add_example_val(S_PEXAMPLE_STRUCT);
char *get_type(E_TYPE);
S_PEXAMPLE_STRUCT add_example_node(int, char[]);
S_PSTACK st_init();
void st_deinit(S_PSTACK);
void st_push(S_PSTACK, E_TYPE, ...);
void st_pop(S_PSTACK);
int st_get_size(S_PSTACK);

stack.c

#include "stack.h"

S_PITEM add_int_val(int n) {
    S_PITEM pt = malloc(sizeof(S_ITEM));
    if (pt == NULL) {
        printf("malloc error!\n");
        exit(EXIT_FAILURE);
    }

    pt->u_data.t_int = n;
    pt->s_type = TYPE_INT;

    return pt;
}

S_PITEM add_char_val(char c) {
    S_PITEM pt = malloc(sizeof(S_ITEM));
    if (pt == NULL) {
        printf("malloc error!\n");
        exit(EXIT_FAILURE);
    }

    pt->u_data.t_char = c;
    pt->s_type = TYPE_CHAR;

    return pt;
}

S_PITEM add_str_val(char *s) {
    S_PITEM pt = malloc(sizeof(S_ITEM));
    if (pt == NULL) {
        printf("malloc error!\n");
        exit(EXIT_FAILURE);
    }

    pt->u_data.t_pchar = s;
    pt->s_type = TYPE_STR;

    return pt;
}

S_PITEM add_example_val(S_PEXAMPLE_STRUCT s) {
    S_PITEM pt = malloc(sizeof(S_ITEM));
    if (pt == NULL) {
        printf("malloc error!\n");
        exit(EXIT_FAILURE);
    }

    pt->u_data.t_pexample = malloc(sizeof(S_EXAMPLE_STRUCT));

    pt->u_data.t_pexample->age = s->age;
    strcpy(pt->u_data.t_pexample->name, s->name);
    pt->s_type = TYPE_EXAMPLE;
    free(s);

    return pt;
}

char *get_type(E_TYPE st) {
    char *r;

    switch (st) {
        case TYPE_INT:
            r = "integer";
            break;

        case TYPE_CHAR:
            r = "character";
            break;

        case TYPE_STR:
            r = "string";
            break;

        case TYPE_EXAMPLE:
            r = "example";
            break;
    }

    return r;
}

S_PEXAMPLE_STRUCT add_example_node(int age, char name[]) {
    S_PEXAMPLE_STRUCT a = malloc(sizeof(S_EXAMPLE_STRUCT));
    a->age = age;
    strcpy(a->name, name);

    return a;
}

// инициализация стека
S_PSTACK st_init() {
    S_PSTACK pStack = malloc(sizeof(S_STACK));
    if (pStack == NULL) {
        printf("malloc error!\n");
        exit(EXIT_FAILURE);
    }

    pStack->esp = malloc(STACK_SIZE * sizeof(S_ITEM));
    if (pStack->esp == NULL) {
        printf("malloc error!\n");
        exit(EXIT_FAILURE);
    }

    pStack->esp_first = pStack->esp;

    return pStack;
}

// освобождение всех данных
void st_deinit(S_PSTACK pStack) {
    free(pStack->esp_first);
    free(pStack);
}

// внести обьект
void st_push(S_PSTACK pStack, E_TYPE n, ...) {
    va_list arg;

    va_start(arg, n);

    if (pStack->esp == (pStack->esp_first + STACK_SIZE)) {
        printf("stack overflow!\n");
        exit(EXIT_FAILURE);
    }

    switch (n) {
        case TYPE_INT:
            *pStack->esp = add_int_val(va_arg(arg, int));
            printf("push(): type - %s, val - %d\n",
                   get_type((**pStack->esp).s_type),
                   **pStack->esp);
            pStack->esp++;
            break;

        case TYPE_CHAR:
            *pStack->esp = add_char_val(va_arg(arg, char));
            printf("push(): type - %s, val - %c\n",
                   get_type((**pStack->esp).s_type),
                   **pStack->esp);
            pStack->esp++;
            break;

        case TYPE_STR:
            *pStack->esp = add_str_val(va_arg(arg, char*));
            printf("push(): type - %s, val - %s\n",
                   get_type((**pStack->esp).s_type),
                   **pStack->esp);
            pStack->esp++;
            break;

        case TYPE_EXAMPLE:
            *pStack->esp = add_example_val(va_arg(arg, S_PEXAMPLE_STRUCT));
            printf("push(): type - %s, age - %d, name - %s\n",
                   get_type((**pStack->esp).s_type),
                   (**pStack->esp).u_data.t_pexample->age,
                   (**pStack->esp).u_data.t_pexample->name);
            pStack->esp++;
            break;
    }

    va_end(arg);
}

// извлечь обьект
void st_pop(S_PSTACK pStack) {
    if (pStack->esp == pStack->esp_first) {
        printf("stack empty!\n");
        exit(EXIT_FAILURE);
    }

    pStack->esp--;

    switch ((**pStack->esp).s_type) {
        case TYPE_INT:
            printf("pop(): type - %s, val - %d\n",
                   get_type((**pStack->esp).s_type),
                   **pStack->esp);
            free(*pStack->esp);
            break;

        case TYPE_CHAR:
            printf("pop(): type - %s, val - %c\n",
                   get_type((**pStack->esp).s_type),
                   **pStack->esp);
            free(*pStack->esp);
            break;

        case TYPE_STR:
            printf("pop(): type - %s, val - %s\n",
                   get_type((**pStack->esp).s_type),
                   **pStack->esp);
            free(*pStack->esp);
            break;

        case TYPE_EXAMPLE:
            printf("pop(): type - %s, age - %d, name - %s\n",
                   get_type((**pStack->esp).s_type),
                   (**pStack->esp).u_data.t_pexample->age,
                   (**pStack->esp).u_data.t_pexample->name);
            free(*pStack->esp);
            break;
    }
}

// кол-во элементов в стеке
int st_get_size(S_PSTACK pStack) {
    return pStack->esp - pStack->esp_first;
}

main.c

#include "stack.h"

int main() {

    stack_init();

    push(TYPE_EXAMPLE, add_example_node(23, "Ivan"));
    push(TYPE_INT, 11111111);
    push(TYPE_INT, 22222222);
    push(TYPE_INT, 33333333);
    push(TYPE_STR, "Hello!!");
    push(TYPE_CHAR, 'U');
    push(TYPE_INT, 44444444);
    push(TYPE_EXAMPLE, add_example_node(51, "Vasya"));

    printf("stack_size(): %d\n", stack_size());

    pop();
    pop();
    pop();
    pop();
    pop();
    pop();
    pop();
    pop();

    printf("stack_size(): %d\n", stack_size());

    stack_deinit();

    return 0;
}

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