3

I'm working on this piece of code as part of my coursework, ideally any advice I get for this would be educational in some way; I don't want an exact answer, just need someone who knows more than I do to point me in the right direction of where this all might be going wrong.

The problem I'm working on is returning the mode of a linked list of floats in C, and my approach so far goes like this:

  • Sort the list in ascending order.
  • Create an array containing only the unique values in the list.
  • Create an array of equal size to the uniques array filled with zeroes to act as a set of counters for each value in uniques.
  • Run a for-loop through the uniques array, going from i = 0 to i < arraylen.
  • Inside the for-loop, traverse the list until the data == NULL and compare each value in it to uniques[i].
  • If the value in the list is a match, increment counters[i] by 1.
  • Otherwise, move forward in the list without incrementing anything.
  • Once the list has been fully traversed, the for-loop moves onto the next value of i and the list is reset back to head.
  • Set an index tracker k = 0 that stores the index of the highest value in the counters array.
  • Run a for-loop through counters that compares the data of each value to that of the data in the k index.
  • If the current value in counters is higher than the data of the k index, sets k as the index of the current value.
  • Otherwise, continues through the list.
  • Takes the mode as uniques[k] and prints that value.

For some reason though, trying to run this code gives me the error message

[C kernel] Executable exited with code -11

and I don't understand why. Below is the full code; if anyone could help me find what's causing this problem I'd greatly appreciate it.
(Note: Bubblesort and Lengthfinder are two functions that I've written and tested, they both work perfectly fine and aren't the cause of the error as far as I can tell.)
(I am also aware that this is probably more complicated than it really needs to be but I'm not sure of how to simplify it.)

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

struct Node {
    float data;
    struct Node *next;
};

//Establish lengthfinder function.
int Lengthfinder(struct Node *head) {
    int len = 0;
    struct Node *travel = head;
    while (travel != NULL) {
        len++;
        travel = travel->next;
    }
    return len;
}

void Bubblesort(struct Node *head) {
    struct Node *current = head;
    int len = Lengthfinder(head);
    float sort[len];
    //creates an array of equal length to the list.
    while (current != NULL) {
        for (int i = 0; i < len; i++) {
            sort[i] = current->data;
            current = current->next;
        }
        //copies the list to the sort array.
    }
    for (int j = 1; j <= len; j++) {
        //Starts a primary for-loop that will read through the values of Input starting from entry 1.
        for (int k = 0; k <= j; k++) {
            //Starts a secondary for-loop that will read through the values of Input starting from entry 0.
            if (sort[j - 1] < sort[k]) {
                /*Compares the current value of the secondary loop to the previous value of the primary loop; if
                the previous primary loop entry is greater than the current secondary loop entry, starts the if
                statement*/
                float temp = sort[k];
                /*Assigns the data entry corresponding to the current iteration of the secondary loop to a
                placeholder*/
                sort[k] = sort[j - 1];
                sort[j - 1] = temp;
                /*Swaps the previous entry of the primary loop and the current entry of the secondary loop
                by overwriting the current entry of the secondary loop and then assigning the previous entry of 
                the primary loop with the temp value*/
            } else {
                continue;
                //Skips the current entry for the secondary loop if it is >= the previous entry of the primary loop
            }
        }
    }
    //Nested loops have sorted the array in ascending order.
    
    struct Node *curr = head;
    int l = 0;
    while (curr != NULL) {
        curr->data = sort[l];
        curr = curr->next;
        l++;
    }
}

void Mode(struct Node *head) {
    Bubblesort(head);
    int len = Lengthfinder(head);
    //Creates an array that can be filled with the unique values in the bubble-sorted list.
    float uniques[len];
    //Creates an integer that acts as the index for the uniques array.
    int i = 0;
    struct Node *curr = head;
    //While loop to traverse the array.
    while (curr != NULL) {
        //If the current item of the list is the head, adds it to the uniques array. 
        if (curr == head) {
            uniques[i] = curr->data;
            //Increases the index position by 1.
            i++;
            //Sets the list position to the next item.
            curr = curr->next;
        }
        //If the data in the list item following the current is different to the current, adds that to uniques.
        else if (curr->data != curr->next->data) {
            uniques[i] = curr->next->data;
            i++;
            curr = curr->next;
        }
        //If neither of the above conditions are fulfilled, moves the list forward.
        else {
            curr = curr->next;
        }
    }
    //Creates a parallel array of empty values equal in size to the uniques array.//
    int counters[len];
    //Fills the counters array with zeroes so that each value of it can be appended.
    for (int j = 0; j < len; j++) {
        counters[j] = 0;
    }
    //Traverses the list.
    for (int j = 0; j < len; j++) {
        struct Node *travel = head;
        //Traverses the array and compares the current index of the uniques array with all the values of the list.
        while (travel != NULL) {
            /*If the data of the current index is equal to the data of any list values, adds 1 to the current index
            of the counters array and moves the list forward.*/
            if (uniques[j] == travel->data) {
                counters[j] = counters[j] + 1;
                travel = travel->next;
            }
            //Otherwise, moves the list forward.
            else {
                travel = travel->next;
            }
        }
    }
    //Sets up an index that keeps track of which counters value is the highest; automatically starts as 0.
    int k = 0;
    //Traverses the counters array.
    for (int j = 1; j <= len; j++) {
        //If the current value is greater than the index of k, sets k to the current value of j.
        if (counters[j] > counters[k]) {
            k = j;
        }
    }
    //Sets the mode as the k index of uniques and returns it.
    float mode = uniques[k];
    printf("Mode = %f\n", mode);
}

//Constructing a list based on input values.
struct Node *createNode(float x) {
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
    newNode->data = x;
    newNode->next = NULL;
    return newNode;
}

int main() {
    //Creating a hard-coded list that can be edited for whatever values you want to put in.
    struct Node *head = createNode(0.1);
    head->next = createNode(0.9);
    head->next->next = createNode(0.5);
    head->next->next->next = createNode(0.7);
    head->next->next->next->next = createNode(0.9);
    Bubblesort(head);
    struct Node *curry = head;
    while (curry != NULL) {
        printf("%f ", curry->data);
        curry = curry->next;
    }
    Mode(head);
    return 0;
}
9
  • 1
    Having said that: The mysterious message "[C kernel] Executable exited with code -11" is not coming from your program. It's coming from some kind of "wrapper" that was provided to you by your instructors. I am willing to bet one (1) cookie that "code -11" actually means signal 11, better known by its infamous error message "Segmentation fault". "Segmentation fault" means your program is accessing memory incorrectly. Not being able to test your program myself, I can't be more specific than that, but here's some advice: Commented Nov 15 at 17:06
  • 1
    I've now added the struct Node definition. For extra context, all of this is running on SciServer as a compiler. Commented Nov 15 at 17:07
  • 1
    Go to your instructors and tell them that I told you to ask them how to run your program, not the wrapper, with valgrind instrumentation. Then run your program that way. valgrind's purpose is to catch incorrect access to memory and tell you specifically what was incorrect. Fix the very first error valgrind prints, run the program again, keep doing that until valgrind reports no more errors. Then you can move on from incorrect memory access to logic bugs. Commented Nov 15 at 17:10
  • 2
    (Also tell them that I told you that their wrapper is buggy and it should have printed "segmentation fault" instead of "code -11".) Commented Nov 15 at 17:10
  • 1
    FYI, the way things work around here is, if you discover a different problem with your code at this point, you should ask a completely new question about it. The idea is that this question, discussion, and the answer you got from someone else should be preserved as is, in case someone else in the future trips over the same problem. Commented Nov 15 at 18:09

2 Answers 2

5

Here

    else if (curr->data != curr->next->data) {
        uniques[i]=curr->next->data;
        i++;
        curr=curr->next;
    }

curr->next gets NULL and program crashes.

You need to check curr->next for being NULL before accessing data

Sign up to request clarification or add additional context in comments.

1 Comment

thank you so much sir, you solve my problem
3

There are multiple problems in the code that trigger undefined behavior:

  • the first loop in Bubblesort is incorrect: the first element of the list is copied to all entries in the array and the while exits. You should instead initialize i outside the while loop and remove the inner for-loop.

  • then the nested loops test j <= len and k <= j: this is incorrect as the code reads and potentially writes sort[k] which is the element beyond the end of the array when k reaches the value len. This has undefined behavior and could cause the kind of error you report. You should simplify the code, use an outer loop for (int j = 0; j < len; j++), an inner loop for (int k = j + 1; k < len; k++) and compare and swap sort[j] and sort[k].

  • in the Mode function, you test if (curr->data != curr->next->data) which causes a null pointer dereference on the last element in the list, when curr->next is null. This is most probably the cause of the error you report. You should instead compare curr->data with uniques[i - 1].

  • both functions use VLAs with a length of len, the number of elements in the list. You should test if the list is empty to avoid creating an array of length 0, which has undefined behavior, and return 0.0 or NAN in Mode instead of uniques[k] which has undefined behavior in this case.

Also note these remarks:

  • Bubblesort does not implement the algorithm known as Bubble Sort where only adjacent elements are compared and swapped. It is also different from Insertion Sort but has the same quadratic performance.

  • Bubblesort sorts the values in the list nodes, not the nodes themselves. This would be incorrect if the nodes held other data associated with the values. You should sort the nodes by updating the next pointers and possibly the head pointer. This is easier to implement using the merge sort algorithm, which is much more efficient for large lists.

  • Bubblesort uses a VLA (variable length array) to hold a copy of the value to sort: this feature might not be available on all compilers and the array length might be too large for the system, causing a StackOverflow error for very large lists.

  • Comments in C code are usually inserted before the code they refer to or on the same line, not after.

  • you should use for loops to traverse the lists instead of while loops with multiple updates to the curr pointer.

  • There is no need for intermediary arrays in Mode: you can walk the list and count the number of duplicates for the current value, updating the mode whenever this number exceeds the maximum count seen so far.

  • Mode calls Bubblesort, which is a side effect on the list and has been performed already in main. Instead of sorting the list values, you could allocate an array in Mode, copy the values to it, sort it, determine the mode value, free the array and return the mode value.

  • Sorting the values with a quadratic algorithm offers little benefit over scanning the list and counting duplicates of every value, which can be done without modifying the array and without memory allocation.

  • the list can have more than one mode, in this case, you should probably list all values that have the most occurrences.

  • in createNode, you should check for allocation failure and report the error and exit gracefully.

Try and update your code from the above comments.

I shall post a modified version tomorrow.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.