0

So earlier today I posted this link of a segmentation error I was having: Segmentation Fault error - Implementing Stack using Linked lists

The answers I got were amazing and I got rid of the error following the answers given....but then it came back.

Here's my new code (I added to main()):

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

typedef struct Link{
    int value;
    struct Link *next;
}Link;

typedef struct LList1{
    int size;
    Link *head;
}LList1;

typedef struct LListStack{
    LList1 *llist;
}LListStack ;



LListStack *initLListStack(void)
{
    LListStack *stack = (LListStack *) malloc(sizeof(LListStack)) ;
    stack->llist = (LList1 *) malloc (sizeof(LList1));
    stack->llist->size = 0;
    stack->llist->head = NULL;
    return(stack);
}


void removefront(LList1 *llist)
{
    if(llist->head != NULL){
        llist->head = llist->head->next;
        llist->size--;
    }
}

Link *FindLastLink(LList1 *llist, Link *link)
{
    if(link = NULL){
        return(NULL);
    }
    else if(link->next == NULL){
        return(link);
    }
    else{
        return(FindLastLink(llist, link->next));
    }
}

Link *FindSecondLastLink(LList1 *llist, Link *link)
{
    if(link = NULL){
        return(NULL);
    }
    else if(link->next->next == NULL){
        return(link);
    }
    else{
        return(FindSecondLastLink(llist, link->next));
    }
}

void removelast(LList1 *llist)
{
    Link *secondlastlink = (Link *) malloc(sizeof(Link));
    secondlastlink = FindSecondLastLink(llist, llist->head);
    secondlastlink->next = NULL;
    llist->size--;

}



void prepend(int newValue, LList1 *templist)
{
    Link *node = (Link *) malloc(sizeof(Link));
    node->value = newValue;
    node->next = templist->head;
    templist->head = node;
    templist->size++;
}

void append(int newValue, LList1 *templist)
{
    Link *node = (Link *) malloc(sizeof(Link));
    Link *lastlink = (Link *) malloc(sizeof(Link));
    lastlink = FindLastLink(templist, templist->head);
    node->value = newValue;
    lastlink->next = node;
    node->next = NULL;
    templist->size++;
}


void prepush(int value, LListStack *stack)
{
    prepend(value, stack->llist);
}

void apppush(int value, LListStack *stack)
{
    append(value, stack-> llist);
}

int prepop(LListStack *stack)
{
    int result ;

    if ((!isEmpty(stack)))
    {
        removefront(stack->llist);
        result = 1 ;

    }
    else {
        result = 0 ;
    }
    return(result) ;
}

int isEmpty(LListStack *stack)
{
    int empty;

    if (stack->llist->head == NULL)
        return( 1 ) ;
    else
        return( 0 ) ;
}

int apppop(LListStack *stack)
{
    int result ;

    if ((!isEmpty(stack)))
    {
        removelast(stack->llist);
        result = 1 ;
    }
    else
        result = 0 ;

    return(result) ;
}

void PrintList(LList1 *llist, Link *link){
    if (link->next != NULL){
        printf("%d \n", link->value);
        PrintList(llist, link->next);
    }

}

//*******MAIN**********//

int main()
{
    LListStack *stack = (LListStack *) malloc (sizeof(LListStack));

    stack = initLListStack(); //if I take this away, I can run the program

    int pre, app, i, n=10;

    for(i=0;i<10;i++){
        prepush(i, stack);

    } 

    app = apppop(stack); //this cause a segmentation fault
    for(i=4;i>0;i--){
        apppush(i, stack); //so does this
        prepush(i, stack);
    }
    PrintList(stack->llist, stack->llist->head);

    return(0);
}

now looking in the main(), when I call 'prepush()' or 'prepull()' everything works great. However, I get a segmentation fault if I call 'apppush()' or 'apppull()'. Tracing through the functions has lead me to believe the culprits are the functions FindLastLink() and FindSecondLastLink()specifically since they both contain recursion. I don't know why, because I'm very new to this, so any help to fix this would be awesome.

Thanks again guys!

Community
  • 1
  • 1
dvdmarc12
  • 3
  • 1
  • A couple of problems: When calling `removefront` you have a potential memory leak. Don't cast the return value of `malloc`. The member `llist` in the `LListStack` structure doesn't have to be a pointer. – Some programmer dude Sep 30 '13 at 05:07
  • And you have more memory leaks, for example in `removelast` where you allocate memory and assign it to `secondlastlink` then promptly reassign that pointer, thereby loosing the memory you just allocated. There are also more similar leaks in other parts of the program. – Some programmer dude Sep 30 '13 at 05:10
  • 1
    And finally, if your program crashes, you should build it with debug information (add the `-g` flag to gcc) and run your program in a debugger. The debugger will then stop at the site of the crash. If it's not in your code, then you can walk up the function call stack until you reach your code, where you will be able to examine values of variables. – Some programmer dude Sep 30 '13 at 05:12

1 Answers1

2

I think your problem is in FindSecondLastLink function. You forgot to check the second pointer to NULL. When you access link->next->next, if link->next == NULL, it causes a segfault.

Link *FindSecondLastLink(LList1 *llist, Link *link)
{
if(link = NULL){ // One more problem is that you assigning NULL value to link variable instead of compare it. It should be link == NULL
    return(NULL);
}
else if(link->next->next == NULL){ // The problem is here. You forgot to check if link->next == NULL
    return(link);
}
else{
    return(FindSecondLastLink(llist, link->next));
}
}
Evgeny Shavlyugin
  • 421
  • 1
  • 4
  • 9