Thread: linked list sorting function causes segfault

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.

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

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...

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

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;
    }

}

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.