0 / 0 / 0
Регистрация: 18.10.2023
Сообщений: 7
1

Реализация стека

11.02.2024, 21:20. Показов 1489. Ответов 2

Author24 — интернет-сервис помощи студентам
Здравствуйте.
Дали задание (в университете) - реализовать стек (в виде линейного связного списка, выводить в обычном и обратном порядке, удалить выбранный элемент из стека).
Пытался опираться на реализацию Однонаправленного Линейного Списка, но думаю, что это было ошибкой.
Вот такое намудрил, но ругается на добавление элемента в функции add_x (а именно на
C++
1
temp->next = (*stk)->head;
). Пытался и через глобальный счётчик кол-ва элементов, и через значение на передаваемый стек (наверно, самый глупый способ), но безуспешно.
Подскажите направление, в котором следует мыслить. Заранее спасибо
Вот сам код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
 
struct stack
{
    int x; // значение (value) элемента
    int cnt; // количество элементов
    stack* next; // указатель (link) на следующий элемент
    stack* head; // голова (head) списка
};
 
//void initialize_x(stack* stk)
//{
//    stk->cnt = 0;
//    stk->next = NULL;
//    stk->head = NULL;
//}
 
void add_x(int num, stack** stk)
{
    stack* temp = new stack;    // выделение памяти под новый элемент
    
    if (temp->cnt == 0)
    {
        temp->x = num;
        temp->next = NULL;
        (*stk)->head = temp;
    }
    else
    {
        temp->x = num;                    // Сначала вводим элемент и задаём ему значение (num).
        temp->next = (*stk)->head;  // Далее говорим, что после (num) следует голова стека.
        (*stk)->head = temp;            // И в конце утверждаем, что голова стека = (num)
    }
 
    temp->cnt += 1;
}
 
void delete_x(stack* num, stack* stk)
{
    stack* temp;                            // объявляем стек
    temp = stk->head;                       // указываем на голову стека
 
    if (stk->cnt > 0)                       // проверка, если список не пуст
    {
        while (temp->next != num)           // ищем элемент, ссылающийся на удаляемый
        {
            temp = temp->next;
        }
        temp->next = num->next;             // ссылка на след элемент предыдущего элемента будет
    }                                       // отсылать к след элементу удаляемого
    else
    {
        printf_s("Stack is empty!!!\n");
    }
    stk->cnt -= 1;                          // уменьшаем кол-во элементов на 1.
}
 
void number_x(stack* stk)
{
    int count = stk->cnt;
    printf_s("Number of elements in stack is -> %d\n", count);
}
 
void show_x(stack* stk)
{
    stack* temp = new stack;
    temp = stk->head;
 
    while (temp != NULL)
    {
        printf_s("%d ", temp->x);
        temp = temp->next;
    }
    printf_s("\n");
}
 
void show_x_reverse(stack* stk)
{
    stack* temp = new stack;
    temp = stk->head;
 
    int i = stk->cnt;
 
    while (i > 0)
    {
        int j = 0;
        while (j < i-1)
        {
            j++;
            temp = temp->next;
        }
        printf_s("%d ", temp->x);
        i--;
    }
    printf_s("\n");
}
 
int main()
{
    stack* stk{}; //initialize_x(stk);
    printf_s("Input the size of stack -> ");
    int n; scanf_s("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        int val; scanf_s("%d", &val);
        add_x(val, &stk);
        printf_s("Element num. %d of the stack is -> %d", i, val);
 
        //int val; add_x(scanf_s("%d", &val), &stk);
    }
 
    show_x(stk);
    show_x_reverse(stk);
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.02.2024, 21:20
Ответы с готовыми решениями:

Реализация стека
Помогите создать структуру данных типа &quot;стек&quot;, элементы которого занимают 10 кб. Операции,...

реализация стека
всем привет! народ помогите с программой (не пойму в чем ошибка, помогите исправить) #include...

Реализация стека
Здравствуйте, помогите пожалуйста с реализацией стека без использования STL. Стек отображен в...

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

2
...
1906 / 1326 / 965
Регистрация: 12.02.2013
Сообщений: 2,171
12.02.2024, 05:40 2
IsenceonlyCPP, ну, только по add_x

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void add_x(int num, stack** stk)
{
    stack* temp = new stack;
 
    if (temp->cnt == 0) // Вы только что выделили память под temp, значение cnt не определено - "undefined behavior"
    {
        temp->x = num;
        temp->next = NULL;
        (*stk)->head = temp; // Как вы можете обращаться к полю stk если он nullptr?
 
        // А что с (*stk)->next ?
    }
    else
    {
        temp->x = num;
        temp->next = (*stk)->head;
        (*stk)->head = temp;
 
        // Опять про (*stk)->next забываем
    }
 
    // cnt не инициализировано, но даже если вы его инициализируете то значение всегда будет одно и то же
    temp->cnt += 1;
}
Добавлено через 3 минуты
IsenceonlyCPP, и вообще, если вы реализуете стек, то зачем вам два указателя head и next? Да, и зачем хранить размерность стека cnt в каждом из узлов?
0
4761 / 2571 / 891
Регистрация: 29.11.2010
Сообщений: 5,551
13.02.2024, 10:09 3
Цитата Сообщение от IsenceonlyCPP Посмотреть сообщение
C++
1
2
3
4
int x; // значение (value) элемента
    int cnt; // количество элементов
    stack* next; // указатель (link) на следующий элемент
    stack* head; // голова (head) списка
Для стека и указанного задания вам не понадобится ни счетчик, ни указатель на "голову" в каждой ноде.


Если вы хотите в процедурном стиле реализацию, вам достаточно реализовать четыре классических операции над стеком и одну очищающую -- push, pop, top, empty, clear.
В методы передавать указатель на стек по ссылке, чтоб он изменялся внутри метода. И все.

Задачи реверса вывода и удаления каких-то значений в стеке -- классические алгоритмические задачи, выполняются через дополнительный стэк.

Например как-то так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream> 
 
template<typename T>
struct StackNode {
    StackNode *next;
    T value;
};
 
template<typename T>
void push(StackNode<T> *&stack, const T &value) {
    stack = new StackNode<T>{stack, value};
}
 
template<typename T>
void pop(StackNode<T> *&stack) {
    auto temp = stack;
    stack = stack->next;
    delete temp;
}
 
template<typename T>
const T &top(StackNode<T> *&stack) {
    return stack->value;
}
 
template<typename T>
bool isEmpty(StackNode<T> *&stack) {
    return stack == nullptr;
}
 
template<typename T>
void clear(StackNode<T> *&stack) {
    while (!isEmpty(stack)) {
        pop(stack);
    }
}
 
template<typename T>
void println(std::ostream &out, StackNode<T> *&stack) {
    // немного читерства, чтоб не перекладывать из стека в стек, 
    // можно пройтись по связному списку один раз
    for (StackNode<T> *i = stack; i != nullptr;) {
        out << i->value;
        if ((i = i->next) != nullptr) {
            out << ", ";
        }
    }
    out << "\n";
}
 
template<typename T>
void printlnReverse(std::ostream &out, StackNode<T> *&stack) {
    // немного читерства, чтоб не перекладывать из стека в стек, 
    // можно пройтись по связному списку один раз
    StackNode<T> *temp = nullptr;
    for (StackNode<T> *i = stack; i != nullptr; i = i->next) {
        push(temp, i->value);
    }
    println(out, temp);
    clear(temp);
}
 
 
 
template<typename T, typename Predicate>
void removeIf(StackNode<T> *&stack, Predicate predicate) {
    // "полновесный" пример алгоритма с удалением значения из стека
    // с перекладыванием из стека в стек
    StackNode<T> *temp = nullptr;
    while (!isEmpty(stack)) {
        if (predicate(top(stack))) {
            push(temp, top(stack));
        }
        pop(stack);
    }
    while (!isEmpty(temp)) {
        push(stack, top(temp));
        pop(temp);
    }
}
 
 
 
int main() {
    StackNode<int> *stack = nullptr;
 
    for (int i = 0; i < 10; ++i) {
        push(stack, i);
    }
 
    println(std::cout, stack);
    printlnReverse(std::cout, stack);
 
    removeIf(stack, [](const auto &value) { return value % 2 == 0; });
    println(std::cout, stack);
 
    return 0;
}
Тут ещё можно добавить проверки на stack underflow, но я уже запостил код.
0
13.02.2024, 10:09
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.02.2024, 10:09
Помогаю со студенческими работами здесь

Реализация стека
Подскажите, как создать класс, который реализует стек? А также методы включения и выключения...

Реализация стека
Всем доброго времени суток! Нашел в на просторах интернета исходник реализации стека. Но не совсем...

Реализация стека
вот такие ошибки при реализации: stack.h(26) : error C2953: 'Stack' : class template has already...

Реализация стека
Не получается исправить ошибки #include &lt;stdio.h&gt; #include &lt;locale.h&gt; #include &lt;conio.h&gt;...

Реализация стека
Реализация стека (добавить 1 элемент, вытащить 1 элемент в стеке, определить, когда стек будет ...

Реализация класса стека
Приветствую! Пробую написать класс стека, но работает не совсем так, как задумывалось. Что-то не...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru