堆栈的链表，head->next 一直为空 [英] Linked list for stack, head->next keeps becoming null

问题描述

//Colin James P. Naranjo
//CMSC123 CD-1L
//This program demonstrates postfix evaluation through pop and push functions

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

typedef struct node{                                    //Uses a combination of typedef and tagged structure for the singly linked list
    char value;
    struct node *next;
}stack;


char evaluate(char a, char b, char c){
    int ans;
    if(c == '*'){
        ans = (int)a * (int)b;
    }
    if(c == '+'){
        ans = (int)a + (int)b;
    }
    if(c == '-'){
        ans = (int)a - (int)b;
    }
    if(c == '/'){
        ans = (int)a / (int)b;
    }
    if(c == '%'){
        ans = (int)a % (int)b;
    }
    return (char)ans;
}

char pop(stack *head){          //For popping a value in the stack, create a temporary variable to take over the head   
    stack *temp;
    char x;
    printf("Your sequence is mostly likely not in order.
");
    temp = head;                        //Then the new head will be the value next to it. Save its value in x then free the temporary variable and return x
    printf("Your sequence is mostly likely not in order.
");
        head = head->next;

    x = temp->value;
    free(temp);
    return x;
}

void push(stack *head, char op){        //For pushing a value to the stack, create a temporary variable to store the new value
    stack *temp, *h;
    temp=(stack*)malloc(sizeof(stack));                     
    temp->value = op;                   //Tthe temporary value will be the new head, and the previous head will be placed next to it
    if (head == NULL){
         head=temp;
         head->next=NULL;
    }else{
        temp->next=head;
        head=temp;
    }
    h = head;
    while(h!=NULL){
        printf("%c-->",h->value);
        h = h->next;
    }
    printf("
");
}

main(){
    int i = 0;
    char op[50], a, b, c, answer;

    stack *head = NULL;

    printf("Enter the operators and operands: 
");                         //Asks for the sequence and checks if there's an invalid character
    scanf("%s", op);
    while(op[i] != 0){
        printf("%c
", op[i]);
        if(op[i] < 48 || op[i] > 57){       
            if(op[i] != '*' && op[i] != '+' && op[i] != '-' && op[i] != '/' && op[i] != '%'){
                printf("You may have entered an invalid character.
");
                exit(0);
            }
        }
        i++;
    }   
    i = 0;

    while(op[i] != 0){                                                              
            if(op[i] >= 48 && op[i] <= 57){
                printf("test: %c 
", op[i]);
                push (head, op[i]);
                printf("
");
            }else if(op[i] == '*' || op[i] == '+' || op[i] == '-' || op[i] == '/' || op[i] == '%'){                 
                    push (head, op[i]);
                    if((op[i-1] >= 48 && op[i-1] <= 57) && (op[i-2] >= 48 && op[i-2] <= 57)){
                        printf("test: %c 
", op[i]);           
                        c = pop (head);
                        b = pop (head);
                        a = pop (head);
                        answer = evaluate (a, b, c);
                        printf("test: %d + %d = %d
", a, b, answer);
                        push (head, answer);
                    }else{
                        printf("Your sequence is mostly likely not in order or is missing something.
");
                    }   
            }
            i++;
        }
    answer = pop(head);
    printf("%d
", answer);
}

This is a program for a stack and its function is to insert and delete at head using linked list. My problem it keeps giving a status access violation and I found out that my program keeps removing the previous nodes that I've input. I've done this before I don't know what going on with this one.

void push(stack *head, char op){        //For pushing a value to the stack,       create a temporary variable to store the new value
    stack *temp, *h;
    temp=(stack*)malloc(sizeof(stack));                     
    temp->value = op;                   //Tthe temporary value will be the new head, and the previous head will be placed next to it
    h = head;
    if (h == NULL){
         h=temp;
         h->next=NULL;
    }else{
        temp->next=h;
        h=temp;
    }
    h = head;
    while(h!=NULL){
        printf("%c-->",h->value);
        h = h->next;
    }
    printf("
");
}

Here's the edited part, it's still not working. The only thing being printed is the last node I added, the rest is gone.

EDIT: I can't post another question for another 90 min so I'm going to ask it here. On the evaluate part, I need to do an arithmetic equation on character variables. Is it better to have them integer and just temporarily change them to char or the other way around. The code's above, on the evaluate part

解决方案

You've fallen in C's pass-by-value function calls while writing push and pop. Parameters inside functions are copies of the outside variables you pass in. This means that...

char pop(stack *head) {
    //...
    head = head->next; // The original pointer is not modified !
    //...
}

... and since you free() the former first node, the head pointer in main() is now dangling, and eventually segfaults when you try to access the now-gone node.

To fix it, simply pass it by address so the function can update it from the inside :

char pop(stack **head) {
    stack *oldHead = *head;

    char x = oldHead->value;
    *head = oldHead->next;

    free(oldHead);
    return x;
}

Do the same for push() and modify call sites accordingly.

这篇关于堆栈的链表，head->next 一直为空的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！