Thread: linked list sorting function causes segfault

  1. #16
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    I think that this is something that you need to be able to do yourself.

    Go make yourself a coffee/tea and come back.
    With a pen and paper write down what you expect for the code to happen - Not just the start and finish, but at the end of each loop

    Now, run your code in debugging mode and step through it. Be sure to say to yourself what you expect to happen as going through it.

    Take advantage of the Code::Blocks watch window - Type in every variable that you need to see.


    It's a slow and tedious task, but you need to be able to do it.
    Fact - Beethoven wrote his first symphony in C

  2. #17
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    After that you should at least be able to say, "I expected to see this, but saw that"
    Fact - Beethoven wrote his first symphony in C

  3. #18
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    ok i have drawn out the steps involved
    Code:
    /*
        Function called
    
        current_loop_node and current_node point here
        |
       \|/
     ------    ------    ------   ------    ------
     | 66 |--->| 55 |--->| 11 |-->| 22 |--->| 44 |
     ------    ------    ------   ------    ------
    
     1st itteration of current_loop node: current node works its way through the list to find 11 and removes it by setting the node before's pointer to its
     next node then removes it from the list then as index is 0 it prepends it to the list
    
                   current_loop_node and current_node point here
                   |
                  \|/
     ------     ------     ------     ------     ------
     | 11 |---->| 66 |---->| 55 |---->| 22 |---->| 44 |
     ------     ------     ------     ------     ------
    
     2nd itteration of current_loop_node current node works its way through the list to find 22 and removes it by setting the node before's pointer to its
     next node then removes it from the list then as index is 1 it inserts the node into the indexed position
    
                              current_loop_node and current_node point here
                              |
                             \|/
     ------     ------     ------     ------     ------
     | 11 |---->| 22 |---->| 66 |---->| 55 |---->| 44 |
     ------     ------     ------     ------     ------
    
     3rd itteration of current_loop_node current node works its way through the list to find 44 and removes it by setting the node before's pointer to its
     next node then removes it from the list then as index is 2 it inserts the node into the indexed position
    
                                        current_loop_node and current_node point here
                                        |
                                       \|/
     ------     ------     ------     ------     ------
     | 11 |---->| 22 |---->| 44 |---->| 66 |---->| 55 |
     ------     ------     ------     ------     ------
    
     4th itteration of current_loop_node current node works its way through the list to find 55 and removes it by setting the node before's pointer to its
     next node then removes it from the list then as index is 3 it inserts the node into the indexed position
    
                                                   current_loop_node and current_node point here
                                                   |
                                                  \|/
     ------     ------     ------     ------     ------
     | 11 |---->| 22 |---->| 44 |---->| 55 |---->| 66 |
     ------     ------     ------     ------     ------
    
     5th itteration of current_loop_node current node works its way through the list to find 66 and removes it by setting the node before's pointer to its
     next node then removes it from the list then as index is 4 so it prepends the node onto the tail of the list
    Last edited by cooper1200; 05-27-2019 at 03:57 AM.

  4. #19
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    i appreciate that it might not be the best way to do it but its all i could think of
    Last edited by cooper1200; 05-27-2019 at 03:58 AM.

  5. #20
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    ok i can now see why its quitting at early because the third nodes next pointer on the 4th iteration is null. however as to how i end up with 55 and 44 in the sorted list and as to why its changing the origonal list i have no idea
    Last edited by cooper1200; 05-27-2019 at 04:00 AM.

  6. #21
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    first go is correct it finds 11 and prepends it to the head of the list. second go is wrong it finds 22 correctly however for some reason 55 is now the head of the list 22 is in its correct position 66 55 (a second time) and 44 remain un changed it just ties its self up into a bigger mess the more it goes on.

  7. #22
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    ok i have big issues and i really don't want to play around any more till i get some good advice because i think if im not careful i can really screw things up

    this is how the code looks at the moment
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node
    {
        int age;
        struct Node *next;
    }Node;
    
    typedef struct LinkedList
    {
        struct Node *head;
        struct Node *tail;
    }LinkedList;
    
    enum Flag {FALSE = 0, TRUE = 1};
    
    void initalize_list(LinkedList *list, LinkedList *sorted_list);
    struct Node *create_head(void);
    struct Node *get_memory(void);
    int get_age(void);
    void print_list(const LinkedList list);
    void delete_list(LinkedList *list);
    void append_to_list(LinkedList *list);
    void prepend_to_list(LinkedList *list);
    void delete_node(LinkedList *list);
    int find_node(int age, Node **current, Node **previous);
    void remove_node(Node *current, Node *previous, LinkedList **list);
    void insert_node_in_middle(int index, LinkedList *list);
    void insert_node(int index, LinkedList **list, Node **tmp_node);
    void sort_list(LinkedList *list, LinkedList *sorted_list);
    
    int main()
    {
        //declare my lists
        LinkedList list;
        LinkedList sorted_list;
    
        //list.head = create_head();
        initalize_list(&list, &sorted_list);
        append_to_list(&list);
        //append_to_list(&list);
        //prepend_to_list(&list);
        prepend_to_list(&list);
        print_list(list);
        delete_node(&list);
        print_list(list);
        append_to_list(&list);
        prepend_to_list(&list);
        print_list(list);
        printf("\n inserting a node\n");
        insert_node_in_middle(0, &list);
        print_list(list);
        printf("\nsorting list\n");
        sort_list(&list, &sorted_list);
        printf("printing sorted list.....\n");
        print_list(sorted_list);
        //delete_node(&list);
        printf("\n printing origonal list.....\n");
        print_list(list);
        delete_list(&list);
    
        return 0;
    }
    
    void initalize_list(LinkedList *list, LinkedList *sorted_list)
    {
        list->head = NULL;
        list->tail = NULL;
        sorted_list->head = NULL;
        sorted_list->tail = NULL;
    
        list->head = create_head();
        list->head->next = NULL;
        list->tail = list->head;
    
        list->head->age = get_age();
    }
    
    struct Node *create_head(void)
    {
        Node *head_tmp;
    
        head_tmp = get_memory();
        if (!head_tmp)
        {
            fprintf(stderr, "error allocating memory\n");
            exit(EXIT_FAILURE);// if it cant allocate memory for the head node at startup somthing really wrong so bug out
        }
    
        return head_tmp;
    }
    
    struct Node *get_memory(void)
    {
        return malloc(sizeof(Node));
    }
    
    int get_age(void)
    {
        int age;
    
        printf("PLease enter an age: ");
        scanf(" %d", &age);
    
        return age;
    }
    
    void print_list(const LinkedList list)
    {
        int count = 1;
        Node *tmp = list.head;
    
        while (tmp)
        {
            printf("person%d's age is %d\n", count, tmp->age);
            count++;
            tmp = tmp->next;
        }
    }
    
    void delete_list(LinkedList *list)
    {
        int count = 1;
        Node *tmp;
    
        printf("freeing memory.....\n");
        while (list->head)
        {
            tmp = list->head->next;
            printf("freeing element %d\n", count);
            free(list->head);
            list->head = tmp;
            count++;
        }
        printf("memory freed\n");
    }
    
    void append_to_list(LinkedList *list)
    {
        Node *tmp_node = NULL;
    
        tmp_node = get_memory();
    
        if(!tmp_node)
        {
            fprintf(stderr, "Unable to get memory for node to append\n");
            return;
        }
    
        tmp_node->age = get_age();
        list->tail->next = tmp_node; //set the tail's next pointer to point at the new node
        list->tail = tmp_node; //set tail to the new node;
    
        // if its the second node in the list list->head->next will be NULL so set the next pointer to point at tmp_node as well
        if (!list->head->next)
        {
            list->head->next = tmp_node;
        }
    }
    
    void prepend_to_list(LinkedList *list)
    {
        Node *tmp_node = NULL;
    
        tmp_node = get_memory();
    
        if(!tmp_node)
        {
            fprintf(stderr, "Unable to get memory for node to prepend\n");
            return;
        }
    
        tmp_node->age = get_age();
        tmp_node->next = list->head; //set tmp_node's next pointer to point at the current head pointer
        list->head = tmp_node; //set head to point to the new head/node
    }
    void insert_node_in_middle(int index, LinkedList *list)
    {
        Node *tmp_node = NULL;
    
        tmp_node = get_memory();
    
        if(!tmp_node)
        {
            fprintf(stderr, "Unable to get memory for node to prepend\n");
            return;
        }
    
        tmp_node->age = get_age();
        insert_node(index, &list, &tmp_node);
    }
    
    void insert_node(int index, LinkedList **list, Node **tmp_node)
    {
        int count = 0;
        Node *current_node = (*list)->head, *previous_node = NULL;
    
        if (index == 0)
        {
    
            (*tmp_node)->next = (*list)->head;
            (*list)->head = (*tmp_node);
            return;
        }
        while (current_node)
        {
            if (count == index)
            {
                break;
            }
            previous_node = current_node;
            current_node = current_node->next;
            count++;
        }
    
        if (!current_node)
        {
            (*list)->tail->next = (*tmp_node);
            (*list)->tail = (*tmp_node);
            return;
        }
    
        (*tmp_node)->next = previous_node->next;
        previous_node->next = (*tmp_node);
        (*tmp_node)->next = current_node;
    }
    
    void delete_node(LinkedList *list)
    {
        int age;
        Node *current = list->head, *previous = NULL;
    
        printf("Please enter the age you wish to delete: ");
        scanf(" %d", &age);
    
        if (find_node(age, &current, &previous))
        {
            remove_node(current, previous, &list);
            free(current);
            printf("node deleted\n");
        }
        else
        {
            printf("Invalid age as no node found!\n");
        }
    }
    
    int find_node(int age, Node **current, Node **previous)
    {
        while (*current)
        {
            if ((*current)->age == age)
            {
                return TRUE;
            }
            *previous = *current;
            *current = (*current)->next;
        }
    
        return FALSE;
    }
    
    void remove_node(Node *current, Node *previous, LinkedList **list)
    {
        if (!previous) // current is pointing at the head
        {
            (*list)->head = current->next;
            current->next = NULL;
            printf("freeing head node\n");
        }
        else if(!current->next) // current is pointing at the tail (the last node)
        {
            (*list)->tail = previous;
            (*list)->tail->next = NULL;
            printf("freeing tail node\n");
        }
        else //its somewhere in the middle of the list
        {
            previous->next = current->next;
            current->next = NULL;
            printf("freeing middle node\n");
        }
    }
    
    void sort_list(LinkedList *list, LinkedList *sorted_list)
    {
        int x = 0, y = 0, index = 0, loop_count;
        Node *current_loop_node = list->head, *current_node = NULL, *previous_node;
        Node *current_youngest_node = list->head, *tmp_node = NULL,*previous_youngest_node = NULL;
    
        while (current_loop_node)
        {
            loop_count = 1;
            current_node = current_loop_node;
            previous_node = NULL;
            current_youngest_node->age = current_loop_node->age;
            x = current_youngest_node->age;
            while (current_node)
            {
                y = current_node->age;
                if (current_youngest_node->age >= current_node->age)
                {
                    x = current_node->age;
                    current_youngest_node = current_node;
                    previous_youngest_node = previous_node;
                    tmp_node = current_node;
                }
                previous_node = current_node;
                current_node = current_node->next;
                loop_count++;
            }
    
            printf("current youngest = %d\n", current_youngest_node->age);
            remove_node(current_youngest_node, previous_youngest_node, &list);
            insert_node(index, &list, &tmp_node);
            print_list(*list);
    /*
            if (!sorted_list->head)
            {
                sorted_list->head = tmp_node;
                sorted_list->head->next = NULL;
                sorted_list->tail = sorted_list->head;
            }
            else if (!sorted_list->head->next)
            {
                sorted_list->head->next = tmp_node;
                tmp_node->next = NULL;
                sorted_list->tail = tmp_node;
            }
            else
            {
                sorted_list->tail->next = tmp_node;
                tmp_node->next = NULL;
            }
    //*/
            current_loop_node = current_loop_node->next;
            index++;
        }
    }
    as said above it correctly sets the head node to 11. however and this is where iim concerned because on line 297 im setting the pointer current_youngest_node->age = current_loop_node->age (which on 1st iteration is = list->head) then line 305 i set current_youngest_node = current_node. and on the 1st iteration all is ok its what i want (but obviously not properly). second iteration again line 297 im now setting current_youngest_node-> = current_loop_node->age but as current_youngest_node is pointing at the head of the list it changes the head pointer to point at the node currently pointed at by current_loop_node hence therefor and otherwise i loose track of the node that was at the head (11)..

    any advice geatly appreciated
    coop

  8. #23
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    I don't have a computer to go through it for you, but open a text editor, copy and paste the function there. Now you can break the code as much as you like. Remember - there are no consequences for breaking the code - None.

    It might pay to rewrite the function from scratch. It happens. Write just a little bit and then test it. Every time you do a new task, test it. Don't move on until it does what you want.

    I feel that we are starting to make you a bad programmer by continuously giving you the answer...

  9. #24
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    this is getting bloody stupid now
    Code:
    void cheating_sorted_list(LinkedList *list, LinkedList *sorted_list)
    {
        int youngest;// tmp_age;
        Node *current_loop_node = list->head, *current_node = list->head, *tmp_node;
    
        while (current_loop_node)
        {
            youngest = current_loop_node->age;
            current_node = current_loop_node;
            while (current_node)
            {
                if (youngest > current_node->age)
                {
                    youngest = current_node->age;
                    tmp_node = current_loop_node;
                }
                current_node = current_node->next;
            }
            tmp_node->age = youngest;
            if (!sorted_list->head)
            {
                sorted_list->head = tmp_node;
                sorted_list->head->next = NULL;
                sorted_list->tail = sorted_list->head;
            }
            else if (!sorted_list->head->next)
            {
                sorted_list->head->next = tmp_node;
                tmp_node->next = NULL;
                sorted_list->tail = tmp_node;
            }
            else
            {
                sorted_list->tail->next = tmp_node;
                tmp_node->next = NULL;
            }
            printf("\n");
            print_list(*sorted_list);
            printf("\n");
            current_loop_node = current_loop_node->next;
        }
    }
    someone tell me where i am changing the original list in the above function because somehow current_loop_node->next suddenly decides to point to address 0x8
    coop

  10. #25
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    i give up this is absolutely stupid i cant even get it to print the bloody list right
    Code:
    void sort_list(LinkedList *list)
    {
        int youngest;
        Node *current_loop_node = list->head, *previous_node = NULL, *tmp_node = NULL, *current_node;
        //Node *current_youngest_node, *previous_youngest_node;
    
        while (current_loop_node)
        {
            youngest = current_loop_node->age;
            current_node = current_loop_node;
            printf("\n");
            while (current_node)
            {
                if (youngest > current_node->age)
                {
                    youngest = current_node->age;
                    printf("%d ", youngest);
                }
    
                current_node = current_node->next;
            }
            printf("\n");
            current_loop_node = current_loop_node->next;
        }
    
    }

  11. #26
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    its no good i have wasted a whole day at this and got no where no matter what i do all of a sudden it goes bananas and screws everything up it clearly cannot be done.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Segfault on a linked list insert operation
    By anstmich in forum C Programming
    Replies: 6
    Last Post: 03-25-2011, 09:20 AM
  2. Segfault with Linked List Program
    By kbrandt in forum C Programming
    Replies: 1
    Last Post: 06-23-2009, 07:13 AM
  3. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  4. segfault from linked list function
    By kataya in forum C Programming
    Replies: 7
    Last Post: 04-16-2008, 04:30 AM
  5. Segfault when trying to free a double linked list
    By Rpog in forum C Programming
    Replies: 1
    Last Post: 04-19-2005, 07:37 AM

Tags for this Thread