Counting the sign changes in a list in C

Question

I have to get the number of sign changes in a list of doubles. For example if there is a list like that: "1, -1, -1, 1" there are 2 sign changes, between the adjacent elements. I tried it like this but for some reason the program crashes if I try to compile it:

int number_of_sign_changes(DoubleList* list) {
    int changes = 0;
    for (DoubleNode *n = list->first; n != NULL; n = n->next) {
        if ((n->value >= 0) && (n->next->value < 0)) {
            changes += 1;
        } else if ((n->value < 0) && (n->next->value >= 0)) {
            changes += 1;
        } 
    }
    return changes;
}

The loop definitely works. I tried it in other functions but here it won't work. Does anyone have an idea? Btw you could actually put the 2 if statements into 1 and I tried that aswell but same problem.

Answer 1

This is in essence a fence post problem. The number of possible sign changes is one less than the number of elements in the list, so as you are checking on each item, you can tell you are doing something wrong. The problem in fact occurs when checking the last item on the list - it attempts to check for a sign change to the 'next' item, and there isn't one, as n->next is NULL.

This can be fixed by a simple change to the terminating condition in the for loop as follows:

int number_of_sign_changes(DoubleList* list) {
    int changes = 0;
    for (DoubleNode *n = list->first; n != NULL && n->next != NULL; n = n->next) {
        if ((n->value >= 0) && (n->next->value < 0)) {
            changes += 1;
        } else if ((n->value < 0) && (n->next->value >= 0)) {
            changes += 1;
        } 
    }
    return changes;
}