Ошибка при реализации стека с использованием связанного списка в C

Question

Я получаю неправильный вывод, пытаясь вытолкнуть данные в стеке с помощью этой программы. Несмотря на то, что размер стека равен 5, печать элементов стека выполняется в бесконечный цикл при задании неправильных значений. Какая ошибка?

#include <stdio.h> 
#include <stdlib.h> 

struct node { 
    int data; 
    struct node *next; 
}; 

struct node *top = NULL; 

int count = 0; 

void push(int num) { 
    struct node *newNode = (struct node*)malloc(sizeof(int)); 
    newNode->data = num; 
    newNode->next = NULL; 

    if (top == NULL) { 
     top = newNode; 
    } else { 
     struct node *temp = (struct node*)malloc(sizeof(int)); 
     temp = top; 
     top = newNode; 
     top->next = temp; 
     free(temp); 
    } 
    count++; 
} 

int pop() { 
    if (top == NULL) { 
     printf("\nUnderflow- Stack is empty!"); 
     return -1; 
    } 
    struct node *temp = (struct node*)malloc(sizeof(int)); 
    temp = top; 
    top = top->next; 
    return temp->data; 
} 

int stackTop() { 
    if (top == NULL) { 
     printf("\nStack is empty"); 
     return -1; 
    } 
    return top->data; 
} 

void printStack() { 
    if (top == NULL) { 
     printf("\nStack is empty. Nothing to print"); 
    } 
    printf("\n"); 
    while (top != NULL) { 
     printf("%d ", top->data); 
     top = top->next; 
    } 
} 

/* Count stack elements */ 
void stack_count() { 
    printf("\n No. of elements in stack : %d", count); 
} 

int main(void) { 
    int poppedValue, topValue; 
    push(1); 
    push(2); 
    push(3); 
    push(4); 
    push(5); 

    stack_count(); 

    printStack(); 

    poppedValue = pop(); 
    topValue = stackTop(); 

    printf("\nPop item : %d", poppedValue); 
    printf("\nTop Value: %d", topValue); 

    return 0; 
} 

Выход:

No. of elements in stack : 5 
5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 .... 

Answer 1

Вам не нужно использовать temp узел внутри вашего push() function.You просто тратить память, используя его.

Ниже приведен улучшенный код и он успешно работает.

#include <stdio.h> 
#include <stdlib.h> 

struct node{ 
    int data; 
    struct node* next; 
}; 
struct node* top = NULL; 

int count = 0; 

void push(int num){ 
    struct node* newNode = (struct node*)malloc(sizeof(struct node)); 
    newNode->data = num; 
    newNode->next =top; 
    top=newNode; 
    count++; 
} 

int pop(){ 
    if(top == NULL){ 
     printf("\nUnderflow- Stack is empty!"); 
     return -1; 
    } 

    int ans=top->data; 
    struct node *temp = top; 
    top = top->next; 
    free(temp); 
    count--; 
    return ans; 
} 

int stackTop(){ 
    if(top == NULL){ 
     printf("\nStack is empty"); 
     return -1; 
    } 
    return top->data; 
} 


void printStack(){ 
    struct node *t=top; 
    if(t == NULL){ 
     printf("\nStack is empty. Nothing to print"); 
    } 
    printf("\n"); 
    while(t != NULL){ 
     printf("%d ",t->data); 
     t=t->next; 
    } 
} 

/* Count stack elements */ 
    void stack_count() 
    { 
     printf("\n No. of elements in stack : %d", count); 
    } 

int main(void) { 

    int poppedValue, topValue; 
    push(1); 
    push(2); 
    push(3); 
    push(4); 
    push(5); 

    stack_count(); 


    printStack(); 

    poppedValue = pop(); 
    topValue = stackTop(); 

    printf("\nPop item : %d", poppedValue); 
    printf("\nTop Value: %d", topValue); 

    return 0; 
} 

ВЫВОД

No. of elements in stack : 5 
5 4 3 2 1 
Pop item : 5 
Top Value: 4 

Answer 2

Ваша программа имеет несколько проблем:

• вы выделить node структуры с неправильным размером: sizeof(int). Отбрасывание возвращаемого значения malloc() не требуется в C и считается плохим. Вы должны использовать этот метод, который гарантирует правильный размер:

  struct node *newNode = malloc(sizeof(*newNode)); 
  

  одна эта проблема вызывает неопределенное поведение, которое могло бы объяснить наблюдаемую проблему.

• Вы печатаете новые строки перед своими сообщениями, это не ошибка, но приводит к запутанному выводу. Вы должны поместить новую строку в конце своих сообщений.

• Функция push выделяет память для temp, но не использует ее. temp сразу же перезаписывается другим значением, которое вы free преждевременно, что приводит к потенциальным множественным вызовам free для того же объекта. Это определенно ошибка, приводящая к неопределенному поведению.

• Функция pop также вмешивается в стек и не освобождает верхний узел.

• Вы забываете декремент count при появлении элементов из стека.

• Функция printStack() изменяет стек top, память больше не доступна. Вы должны использовать временную переменную.

Вот модифицированная версия:

#include <stdio.h> 
#include <stdlib.h> 

struct node { 
    int data; 
    struct node *next; 
}; 

struct node *top = NULL; 
int count = 0; 

void push(int num) { 
    struct node *newNode = malloc(sizeof(*newNode)); 
    if (newNode == NULL) { 
     printf("Memory allocation failed\n"); 
     return; 
    } 
    newNode->data = num; 
    newNode->next = top; 
    top = newNode; 
    count++; 
} 

int pop(void) { 
    if (top == NULL) { 
     printf("Underflow. Stack is empty!\n"); 
     return -1; 
    } else { 
     int data = top->data; 
     struct node *temp = top; 
     top = top->next; 
     free(temp); 
     count--; 
     return data; 
    } 
} 

int stackTop(void) { 
    if (top == NULL) { 
     printf("Stack is empty\n"); 
     return -1; 
    } 
    return top->data; 
} 

void printStack(void) { 
    if (top == NULL) { 
     printf("Stack is empty. Nothing to print\n"); 
     return; 
    } 
    struct node *temp = top; 
    while (temp != NULL) { 
     printf("%d ", temp->data); 
     temp = temp->next; 
    } 
    printf("\n"); 
} 

/* Count stack elements */ 
void stack_count(void) { 
    printf("No. of elements in stack: %d\n", count); 
} 

int main(void) { 
    int poppedValue, topValue; 

    push(1); 
    push(2); 
    push(3); 
    push(4); 
    push(5); 
    stack_count(); 
    printStack(); 
    poppedValue = pop(); 
    topValue = stackTop(); 
    printf("Popped item: %d\n", poppedValue); 
    printf("Top Value: %d\n", topValue); 

    return 0; 
} 

Выход:

No. of elements in stack: 5 
5 4 3 2 1 
Popped item: 5 
Top Value: 4