# Thread: linked list sorting function causes segfault

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

2. After that you should at least be able to say, "I expected to see this, but saw that"

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

4. i appreciate that it might not be the best way to do it but its all i could think of

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

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

{
struct Node *tail;

enum Flag {FALSE = 0, TRUE = 1};

struct Node *get_memory(void);
int get_age(void);
void print_list(const 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);

int main()
{
//declare my lists

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

{
list->tail = NULL;
sorted_list->tail = NULL;

}

{

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

}

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

{
int count = 1;
Node *tmp;

printf("freeing memory.....\n");
{
printf("freeing element %d\n", count);
count++;
}
printf("memory freed\n");
}

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

{
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)
{

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

{
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
{
current->next = NULL;
}
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");
}
}

{
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);
/*
{
}
{
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. 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. this is getting bloody stupid now
Code:
{
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;
{
}
{
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. i give up this is absolutely stupid i cant even get it to print the bloody list right
Code:
{
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. 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