Стек с использованием двусвязного списка впервые в C без печати

Я реализовал свой стек, используя двусвязный список, и я не знаю, почему он не печатается, я думаю, что это как-то связано с правильным синтаксисом 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 ничего не выводит.

push() получает свои аргументы по значению. Так что это изменение копии s1. Функции, изменяющие стек, должны получать указатель на стек.
Barmar 14.02.2023 01:06

PS: reverse_s() не будет делать то, что вы думаете...

Fe2O3 14.02.2023 01:20

Что делать, если происходит слишком много вызовов pop()?

Fe2O3 14.02.2023 01:39

Да, я забыл чек is_empty_s

user21078706 14.02.2023 01:43

user21078706 14.02.2023 01:46

«почему это?»... Если вы сейчас изменили код для передачи указателей на вспомогательные функции, указатель s в этих функциях уже является указателем. Вы передаете этот указатель (по значению!) Любым нижестоящим функциям БЕЗ взятия его адреса...

Fe2O3 14.02.2023 01:56
Асинхронная передача данных с помощью sendBeacon в JavaScript
Асинхронная передача данных с помощью sendBeacon в JavaScript
В современных веб-приложениях отправка данных из JavaScript на стороне клиента на сервер является распространенной задачей. Одним из популярных...
Как подобрать выигрышные акции с помощью анализа и визуализации на Python
Как подобрать выигрышные акции с помощью анализа и визуализации на Python
Отказ от ответственности: Эта статья предназначена только для демонстрации и не должна использоваться в качестве инвестиционного совета.
Принципы ООП в JavaScript
Принципы ООП в JavaScript
Парадигма объектно-ориентированного программирования имеет 4 основных принципа,
Пройдите собеседование по Angular: Общие вопросы и ответы экспертов
Пройдите собеседование по Angular: Общие вопросы и ответы экспертов
Можете ли вы объяснить разницу между ngOnInit и конструктором в Angular?
Laravel с Turbo JS
Laravel с Turbo JS
Turbo - это библиотека JavaScript для упрощения создания быстрых и высокоинтерактивных веб-приложений. Она работает с помощью техники под названием...
Типы ввода HTML: Лучшие практики и советы
Типы ввода HTML: Лучшие практики и советы
HTML, или HyperText Markup Language , является стандартным языком разметки, используемым для создания веб-страниц. Типы ввода HTML - это различные...
0
6
77
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

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; Что происходит, когда значение данных не совпадает так удобно???

Fe2O3 14.02.2023 01:24

Не уверен, что вы спрашиваете. Можете ли вы уточнить, пожалуйста?

Allan Wind 14.02.2023 01:26

Просто беспокоит, что s->top - это бесполезное дублирование данных, открывающее дверь для плохого кода, который использует неверное значение... ОП написал слишком сложную реализацию, включающую size, top и prev, но не продумал отказ reverse_s() выполнять его функция... Мягкий выговор уместен, имхо...

Fe2O3 14.02.2023 01:30

Кроме того, как вы можете изменить reverse_s независимо от того, выполняет ли он свою работу.

user21078706 14.02.2023 01:32

Если malloc() не сможет выделить место, указатель NULL будет разыменован в любом случае... Слишком много внимания к "двойному" и недостаточно внимания к KISS, имхо... :-)

Fe2O3 14.02.2023 01:35

@ Fe2O3 Fe2O3 Не уверен, где проходит грань между простым ответом на вопрос оператора с минимальными изменениями для простоты понимания и переписыванием кода для исправления каждой найденной проблемы. Вполне возможно, что мой ответ недостаточно хорош, кстати.

Allan Wind 14.02.2023 01:46

Не стесняйтесь указывать любые возможные возможные исправления

user21078706 14.02.2023 01:47

Согласен... Вчерашний "Алгоритм Луна" тому пример... Часть ответа в таких случаях, тем не менее, должна указывать, что "эта корректирующая заплатка исправит одну вещь, но не заставит код работать безупречно". Несомненно, эта «золотая середина» состоит из зыбучих песков! :-)

Fe2O3 14.02.2023 01:52

Можете ли вы показать, как reverse должен быть синтаксически правильным. У нас Stack* reverse_s(Stack *s), то у меня while (s->tail) с предупреждением под ->, почему?

user21078706 14.02.2023 02:18

@user21078706 user21078706 Пожалуйста, задайте новый вопрос. Обратите внимание, как я свел ваш код только к решению проблемы. Так нам будет проще вам помочь.

Allan Wind 14.02.2023 02:20

@AllanWind Вот оно stackoverflow.com/questions/75447790/…

user21078706 14.02.2023 14:23

Другие вопросы по теме