Я реализовал свой стек, используя двусвязный список, и я не знаю, почему он не печатается, я думаю, что это как-то связано с правильным синтаксисом C или что-то в этом роде?
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
//---------------------Stack---------------------
typedef struct Stack {
int size;
Node* head;
Node* tail;
int top;
} Stack;
const Stack stack_init = { .size = 0, .head = NULL, .tail = NULL, .top = -1 };
Node* create_node(int elm) {
Node* node = malloc(sizeof * node);
if (!node) return node;
node->data = elm;
node->prev = NULL;
node->next = NULL;
return node;
}
void push(Stack s, int elm) {
Node* updated_head = create_node(elm);
if (!s.head) {
s.head = updated_head;
s.tail = s.head;
}
else {
updated_head->next = s.head;
s.head->prev = updated_head;
s.head = updated_head;
}
s.size++;
s.top = s.head->data;
// printf("%d ", s.tail->data);
}
int pop(Stack s) {
Node* node = s.head;
int elm = node->data;
s.head = s.head->next;
if (s.head) {
s.head->prev = NULL;
s.top = s.head->data;
}
else {
s.tail = NULL;
s.top = -1;
}
s.size--;
free(node);
return elm;
}
int top(Stack s) {
return s.top;
}
void clear_s(Stack s) {
while (s.tail)
pop(s);
}
Stack reverse_s(Stack s) { // iterative
Stack s2= stack_init;
while (s.tail) {
push(s2, pop(s));
}
while (s2.tail) {
push(s, pop(s2));
}
return s;
}
int is_empty_s(Stack s) {
return s.tail == NULL;
}
void print_s(Stack s) {
Node* trav = s.head;
while (trav) {
printf("%d ", trav->data);
trav = trav->next;
}
printf("\n");
}
int main() {
Stack s1 = stack_init;
push(s1, 5);
push(s1, 4);
push(s1, 3);
push(s1, 2);
push(s1, 1);
print_s(s1);
return 0;
}
Как видите, стек основан на моем двусвязном списке, который функционален и работает, но функция печати при запуске из узла head ничего не выводит.
PS: reverse_s() не будет делать то, что вы думаете...
Что делать, если происходит слишком много вызовов pop()?
Да, я забыл чек is_empty_s
«почему это?»... Если вы сейчас изменили код для передачи указателей на вспомогательные функции, указатель s в этих функциях уже является указателем. Вы передаете этот указатель (по значению!) Любым нижестоящим функциям БЕЗ взятия его адреса...
C использует вызов по значению, что означает, что push(s1, 5) фактически передаст копию s1 и 5 are в функцию. Поскольку вы хотите мутировать, вам нужно передать адрес s1. Копии могут быть дорогими, поэтому даже для не мутации вы можете предпочесть (также для согласованности) передать указатель на стек, но отметить это const:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
typedef struct Stack {
int size;
Node* head;
Node* tail;
int top;
} Stack;
const Stack stack_init = { .size = 0, .head = NULL, .tail = NULL, .top = -1 };
Node* create_node(int elm) {
Node* node = malloc(sizeof * node);
if (node) {
node->data = elm;
node->prev = NULL;
node->next = NULL;
}
return node;
}
void push(Stack *s, int elm) {
Node* updated_head = create_node(elm);
if (!s->head) {
s->head = updated_head;
s->tail = s->head;
} else {
updated_head->next = s->head;
s->head->prev = updated_head;
s->head = updated_head;
}
s->size++;
s->top = s->head->data;
}
void print_s(Stack *s) {
Node* trav = s->head;
while (trav) {
printf("%d ", trav->data);
trav = trav->next;
}
printf("\n");
}
int main() {
Stack s1 = stack_init;
push(&s1, 5);
push(&s1, 4);
push(&s1, 3);
push(&s1, 2);
push(&s1, 1);
print_s(&s1);
}
И в результате получается:
1 2 3 4 5
Как указывает @Fe2O3 ниже, рассмотрите возможность исключения int top из вашего struct Stack, поскольку это избыточно с s->head->data;.
Int size также является избыточным, но требует O(n) для вычислений во время выполнения, так что это более приемлемый выбор. Тем не менее, вы платите цену за обновление размера при каждой мутации, и если вам это никогда не понадобится, это чистые накладные расходы. Только если вы вызываете его более одного раза, имеет смысл кэшировать размер. Для меня это намек на то, что вызывающая сторона должна кэшировать size, если это необходимо.
Предпочтительно использовать for-петли, когда это применимо. Например, print_s() можно записать так:
for(Node* trav = s->head; trav; trav = trav->next)
printf("%d%s", trav->data, trav->next ? " " : "\n");
}
По возможности избегайте глобальных значений. Тем не менее, это хороший призыв сделать это const. Вы можете заменить stack_init одноименной функцией. Это скрывает детали реализации, что упрощает изменение кода.
Для библиотеки рекомендуется ставить перед каждым символом пространство имен. В вашем случае возможно "Стек"? Я предпочитаю случай со змеей, а не случай с верблюдом, поэтому мой предпочтительный префикс будет «stack_» и, возможно, даже что-то более описательное, поскольку стек обычно реализуется либо как массив, либо как один связанный список.
В push()... s->top = s->head->data; Что происходит, когда значение данных не совпадает так удобно???
Не уверен, что вы спрашиваете. Можете ли вы уточнить, пожалуйста?
Просто беспокоит, что s->top - это бесполезное дублирование данных, открывающее дверь для плохого кода, который использует неверное значение... ОП написал слишком сложную реализацию, включающую size, top и prev, но не продумал отказ reverse_s() выполнять его функция... Мягкий выговор уместен, имхо...
Кроме того, как вы можете изменить reverse_s независимо от того, выполняет ли он свою работу.
Если malloc() не сможет выделить место, указатель NULL будет разыменован в любом случае... Слишком много внимания к "двойному" и недостаточно внимания к KISS, имхо... :-)
@ Fe2O3 Fe2O3 Не уверен, где проходит грань между простым ответом на вопрос оператора с минимальными изменениями для простоты понимания и переписыванием кода для исправления каждой найденной проблемы. Вполне возможно, что мой ответ недостаточно хорош, кстати.
Не стесняйтесь указывать любые возможные возможные исправления
Согласен... Вчерашний "Алгоритм Луна" тому пример... Часть ответа в таких случаях, тем не менее, должна указывать, что "эта корректирующая заплатка исправит одну вещь, но не заставит код работать безупречно". Несомненно, эта «золотая середина» состоит из зыбучих песков! :-)
Можете ли вы показать, как reverse должен быть синтаксически правильным. У нас Stack* reverse_s(Stack *s), то у меня while (s->tail) с предупреждением под ->, почему?
@user21078706 user21078706 Пожалуйста, задайте новый вопрос. Обратите внимание, как я свел ваш код только к решению проблемы. Так нам будет проще вам помочь.
@AllanWind Вот оно stackoverflow.com/questions/75447790/…
push()
получает свои аргументы по значению. Так что это изменение копииs1
. Функции, изменяющие стек, должны получать указатель на стек.