Блог

Главная - Вопросы по программированию - Язык C — пытался создать структуру данных стека массива для реализации «прототипа» отмены / повтора, почему это не работает? :(

Язык C — пытался создать структуру данных стека массива для реализации «прототипа» отмены / повтора, почему это не работает? :(

#c #data-structures #stack

#c #структуры данных #стек

Вопрос:

По сути, я создал функцию create_app() для выделения 2 узлов в стеке, каждый из которых имеет указатель на массив [max]; undo() извлекает последний элемент и, прежде чем вернуть его, добавляет его в массив узла ПОВТОРА. redo() делает обратное, извлекает последний элемент в своем массиве, помещая его в массив отмены, прежде чем возвращать его. Что я сделал не так?

 #include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define EMPTY_TOS (-1)

typedef struct node *node_ptr;

struct node
{
    int arr_size;
    int tos;
    int *arr_stack;
    node_ptr next;

};

typedef node_ptr STACK;

STACK
create_app(int max)
{
    STACK UNDO = (STACK) malloc(sizeof(struct node));
    STACK REDO = (STACK) malloc(sizeof(struct node));
    
    {
        UNDO->arr_stack == (int *) malloc(max * sizeof(int));
        REDO->arr_stack == (int *) malloc(max * sizeof(int));

        if(UNDO->arr_stack != NULL){printf("Out of space!");}
        else
        {
            UNDO->tos = EMPTY_TOS;
            REDO->tos = EMPTY_TOS;
            UNDO->arr_size = max;
            REDO->arr_size = max;
            UNDO->next = REDO;
            REDO->next = UNDO;
            return UNDO;
        }
        

    }
    
}

int
isEmpty(STACK S)
{
    return(S->tos==-1);
}

int
isFull(STACK S)
{
    return(S->tos>=S->arr_size-1);
}

void
push(int x, STACK S)
{
    if(isFull(S)){printf("Stack full!");}
    else
    {
        S->arr_stack[  S->tos] = x;
    }
    
}

int
undo(STACK S)
{
    if(isEmpty(S)){printf("Nothing to undo!");}
    else
    {
        S->next->arr_stack[  S->next->tos] = S->arr_stack[S->tos];
        printf("%d",S->arr_stack[S->tos--]);

    }
    
}

int
redo(STACK S)
{
    if(isEmpty(S->next)){printf("Nothing to redo!");}
    else
    {
        int temp = S->next->arr_stack[S->next->tos];
        push(S->next->arr_stack[S->next->tos], S);
        S->next->tos--;
        printf("%d",temp);
    }
    
}




int main()
{
    
    
    STACK app = create_app(5);
    push(1,app);
    push(2,app);
    push(3,app);
    
    undo(app);
    undo(app);
    redo(app);
    redo(app);

    /* Expected output: 3223 */

    return 0;
   
    
        
}

Ответ №1:

В вашем коде были некоторые небольшие ошибки, подобные этим, create_app() которые кажутся опечатками.

 UNDO->arr_stack == (int *) malloc(max * sizeof(int));
REDO->arr_stack == (int *) malloc(max * sizeof(int));
                 ^
                 |

if(UNDO->arr_stack != NULL){printf("Out of space!");}
                    ^
                    |
...

и некоторые int возвращаемые функции ничего не возвращали в той else части, которая выдавала некоторые предупреждения.

Вот измененный код, который отлично работал для меня

 #include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define EMPTY_TOS (-1)

typedef struct node* node_ptr;
struct node
{
    int arr_size;
    int tos;
    int *arr_stack;
    node_ptr next;

};
typedef node_ptr STACK;

STACK
create_app(int max)
{
    STACK UNDO = (STACK) malloc(sizeof(struct node));
    STACK REDO = (STACK) malloc(sizeof(struct node));
    
    {
        UNDO->arr_stack = (int *) malloc(max * sizeof(int));
        REDO->arr_stack = (int *) malloc(max * sizeof(int));

        if(UNDO->arr_stack == NULL){printf("Out of space!");
            return NULL;}
        else
        {
            UNDO->tos = EMPTY_TOS;
            REDO->tos = EMPTY_TOS;
            UNDO->arr_size = max;
            REDO->arr_size = max;
            UNDO->next = REDO;
            REDO->next = UNDO;
            return UNDO;
        }
        
    }
    
}

int
isEmpty(STACK S)
{
    return (S->tos == -1);
}

int
isFull(STACK S)
{
    return (S->tos >= S->arr_size-1);
}

void
push(int x, STACK S)
{
    if(isFull(S)){printf("Stack full!");}
    else
    {
        S->arr_stack[  S->tos] = x;
    }
    
}

void
undo(STACK S)
{
    if(isEmpty(S)){printf("Nothing to undo!");}
    else
    {
        S->next->arr_stack[  S->next->tos] = S->arr_stack[S->tos];
        printf("%d",S->arr_stack[S->tos--]);
    }
    
}

void
redo(STACK S)
{
    if(isEmpty(S->next)){printf("Nothing to redo!");}
    else
    {
        int temp = S->next->arr_stack[S->next->tos];
        push(S->next->arr_stack[S->next->tos], S);
        S->next->tos--;
        printf("%d",temp);
    }
    
}




int main()
{
    
    
    STACK app = create_app(5);
    push(1,app);
    push(2,app);
    push(3,app);
    
    undo(app);
    undo(app);
    redo(app);
    redo(app);

    /* Expected output: 3223 */

    return 0;
   
    
        
}

Результат:

 3223

Однако всегда принимайте меры предосторожности при освобождении malloc используемой памяти free() .

Комментарии:

1. Спасибо! Совершенно забыл освободить память. @swag2198 Если я освобожу (приложение), я освобожу оба узла для ОТМЕНЫ и ПОВТОРА?

2. Нет. Вы должны освободить каждый из стеков ОТМЕНЫ и повтора по отдельности. Также вам нужно освободить массивы, которые вы выделили внутри них. По сути, для каждого malloc потребуется соответствующий free.

3. хорошо, итак, free (S) free (S-> next) и установка tos для каждого arr на -1 (или free (S-> arr_stack) и free (S-> next-> arr_stack)) достаточно?

4. ДА. Сначала освободите arr_stack массивы, а затем S->next и S . Обратите внимание, что установка tos значения -1 не освобождает массивы.

5. Понял! Большое спасибо 🙂