user181796 user181796 - 3 months ago 13
C Question

Why does this cause segmentation fault?

I'm doing an excersise with linked lists. It works when I enter value at the beginning of the list and values which are smaller than the values in the list. But when number is bigger I get a segmentation fault. Anybody thoughts on what is wrong with code below?

//Header (called headeroef):

typedef struct node
{
int n;
struct node* next;
} node;


//Other code

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

#include "headeroef.h"

void insert(void);
void traverse(void);

node* first = NULL;

int main (void)

{

int c;
do

{
printf("Print instructions: \n"
"1. insert\n"
"2. Delete\n");

printf("Command: ");
c = GetInt();

switch(c)

{
case 1: insert(); break;
}
}

while (c!=0);

}
void insert(void)

{
node* newPtr = malloc(sizeof(node));
printf("Number to insert: \n");
newPtr->n = GetInt();
newPtr->next = NULL;

if (first == NULL)
{
first = newPtr;
}

else if(newPtr->n < first->n)
{
newPtr->next = first;
first = newPtr;
}

else
{
node* predPtr = first;

//Dit houdt dus als in als aan deze else wordt voldaan!
while (true)

{
if (predPtr->n == newPtr->n)
{
free(newPtr);
break;
}
else if (predPtr->next->n > newPtr->n)
{
//Hiermee doe je weer die swap
newPtr->next = predPtr->next;
predPtr->next = newPtr;
break;
}
//Uitzoeken waarom hier een segmentation fault komt.s
}
}
traverse();

}

void traverse(void)

{
printf("The list is now\n");
node* ptr = first;
while (ptr!=NULL)

{
printf("%i\n", ptr->n);
ptr = ptr->next;
}
}

Answer

Let's say you have the single number 5 in the list and you want to add 7.

Because first isn't NULL and the number you're trying to insert isn't less than the first, it ends up in the final block:

node* predPtr = first;
//Dit houdt dus als in als aan deze else wordt voldaan!
while (true)
{
    if (predPtr->n == newPtr->n)
    {
        free(newPtr);
        break;
    }
    else if (predPtr->next->n > newPtr->n)
    {
        //Hiermee doe je weer die swap
        newPtr->next = predPtr->next;
        predPtr->next = newPtr;
        break;
    }
    //Uitzoeken waarom hier een segmentation fault komt.s           
}          

Because you're not trying to insert a duplicate, the first if statement is irrelevant. The combination of:

node* predPtr = first;
while (true) {
    :
    else if (predPtr->next->n > newPtr->n)

is what's causing your crash, because predPtr->next is NULL (there's only the 5 element), so predPtr->next->n will dereference the null pointer.

You basically need to detect this before you try that dereference. If you get to the last element and it's still less than the one you're trying to insert, you need to append it rather than run off the end of the list.

Probably the easiest way to do that with your current code is to change the while loop to something like:

while (true) {
    // gooi als identiek.

    if (predPtr->n == newPtr->n) {
        free(newPtr);
        break;
    }

    // voegen als aan het einde van de lijst

    if (predPtr->next == NULL) {
        predPtr->next = newPtr;
        break;
    }

    // steek indien minder

    if (predPtr->next->n > newPtr->n) {
        newPtr->next = predPtr->next;
        predPtr->next = newPtr;
        break;
    }

    // vooruit naar volgend element.

    predPtr = predPtr->next;
}

You'll notice I've also added the statement at the bottom of the loop to advance through the list. Without this, you'll almost certainly end up with an infinite loop at some point.

You could also refactor your loop to use a different ending condition but that would require more work, and I'm not that keen on doing more than I have to, unless I'm paid by the hour :-)

Comments