bubble sort with link list

Question

I'm a C freshman and learn the link-list now. When I bubble-sort a linked-list, segment fault occurs， GDB point to the function bubble (),i = ptr->elem. I don't know what cause this. please help to figure out.

`

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

define      i_track(n)  printf ("The %s's is %d.\n", #n, (n))
define      s_track(n)  printf ("%s.\n", #n);


typedef struct tag_node
{
    int elem;
struct tag_node *next;
}NODE, *SLINK; 

void  node_track (SLINK list);
NODE *node_generate (void);
void init_list (SLINK *header, int len);
SLINK locate_cur (SLINK list, int target_elem);
void insert_node (SLINK *list, int new_elem, int tag_elem);
SLINK traverse_list (SLINK list);
void list_info (SLINK list, int node_elem);
void bubble (SLINK list);
void swap (int *a, int *b);

int main (int argc, char *argv[])
{
int len;
SLINK list = node_generate ();
printf ("Input a number for length of the link.\n");
scanf ("%d", &len);
s_track(init_start.);
init_list (&list, len);
s_track(init_end.);
traverse_list (list);
bubble (list);

return EXIT_SUCCESS;
}   /* ----------  end of function main  ---------- */          

NODE *node_generate (void) /* generate a node */
{
NODE *new_node = malloc (sizeof (NODE));
if (NULL == new_node)
{
    printf ("ERROR: malloc failed.\n");
    exit (EXIT_FAILURE);
}
memset (new_node, 0, sizeof(NODE));
return new_node;
}

void insert_node (SLINK *list, int new_elem, int tag_elem)
/* insert a node */
{
NODE *new_node = node_generate ();
NODE *cur = *list;
new_node->elem = new_elem;
if ((int)NULL == tag_elem)
{
    new_node->next = (*list)->next;
    (*list)->next = new_node;
}
else
{
    *list = locate_cur (cur, tag_elem);
    new_node->next = (*list)->next;
    (*list)->next = new_node;
}
}

void init_list (SLINK *header, int len)
/* generate a linked-list and assign it*/
{
srand ((unsigned) time(0));
int elem;
for (int i = 0; i < len; i++)
    /* skip number 4 since I dislike it */
    {
        elem = rand () % 100;

        if (4 == elem / 10)
        {
            elem = elem + 50;
        }
        if (4 == elem % 10)
        {
            elem = elem + 5;
        }
        if (0 == elem % 100)
        {
            elem = elem + 999;
        }
        insert_node (header, elem, (int)NULL);  
    }
}

SLINK traverse_list (SLINK list)
/*traverse list */
{
SLINK ptr = list;
for (int node_num = 0; ptr != NULL; ptr = ptr->next)
{
    ++node_num;
    list_info (ptr, node_num);
}
return list;
}

void list_info (SLINK list, int node_num)
/* used for traversed_list () */
{
if (1 == node_num % 10 && 11 != node_num)
{
    printf ("The %dst element is %d.\n", node_num, list->elem);
}
else if (2 == node_num % 10 && 12 != node_num)
{
    printf ("The %dnd element is %d.\n", node_num, list->elem);
}
else if (3 == node_num % 10 && 13 != node_num)
{
    printf ("The %drd element is %d.\n", node_num, list->elem);
}
else
{
    printf ("The %dth element is %d.\n", node_num, list->elem);
}
}

SLINK locate_cur (SLINK list, int target_elem)
/* locate previous of a node */
{
NODE *prev, *cur;
prev = node_generate ();
cur = node_generate ();
for (prev = list, cur = list->next; NULL != cur && target_elem != cur->elem; prev = cur, cur = cur->next)
    ;
return cur;
}

void node_track (NODE *flag)
{
printf ("The flag element is %d.\n", flag->elem);
}

void bubble (SLINK list) /* bubble sort */
{
s_track(bubble_start);
list = list->next;
SLINK ptr, header;
ptr = list; /*GDB point to here*/
int i =0, j = 0;
for (; NULL != list; list = list->next)
{
    for (ptr = list; NULL != ptr; ptr = ptr->next);
    {
        j = list->elem;
        i = ptr->elem;
    //  if (ptr->elem > list->elem)
        if (i > j)
            swap (&(ptr->elem), &(list->elem));
    }
}
s_track(bubble_end);
}

void swap (int *a, int *b)
{
*a = (*a)^(*b);
*b = (*a)^(*b);
*a = (*a)^(*b);
}

`

Answer 1

The purpose of the tag_elem in init_list() is very unclear. I modified the code to eliminate that variable, and then ran it and specified 5 as the input value. It gives:

Input a number for length of the link.
5
init_start..
init_end..
The 1st element is 0.
The 2nd element is 12.
The 3rd element is 8.
The 4th element is 99.
The 5th element is 7.
The 6th element is 63.
bubble_start.
Segmentation fault: 11

Why are 6 items printed when 5 were requested? With repeated execution, the value in the 1st element is always 0 (3 repeats).

That problem can be fixed by revising traverse_list() like this:

SLINK traverse_list(SLINK list)
{
    assert(list != 0); 
    SLINK ptr = list->next;
    for (int node_num = 0; ptr != NULL; ptr = ptr->next)
        list_info(ptr, ++node_num);
    return list;
}

Interestingly, the code in bubble() already skips that first item on the list.

However, the inner loop in bubble() has a mistake:

for (ptr = list; NULL != ptr; ptr = ptr->next);
{
    j = list->elem;
    i = ptr->elem;
//  if (ptr->elem > list->elem)
    if (i > j)
        swap (&(ptr->elem), &(list->elem));
}

It might be easier to see if you write it as:

for (ptr = list; NULL != ptr; ptr = ptr->next)
    ;
{
    j = list->elem;
    i = ptr->elem;  // When this is executed, ptr == NULL!
    if (i > j)
        swap (&(ptr->elem), &(list->elem));
}

You don't want that semi-colon. With that fixed, the code runs OK:

Input a number for length of the link.
5
init start.
init end.
The 1st element is 12.
The 2nd element is 19.
The 3rd element is 99.
The 4th element is 92.
The 5th element is 28.
traverse 1 end.
bubble_start.
bubble_end.
sort end.
The 1st element is 99.
The 2nd element is 92.
The 3rd element is 28.
The 4th element is 19.
The 5th element is 12.
traverse 2 end.

Clearly, a slightly modified set of diagnostic printing, but the data is sorted in descending order. It looks like it works on larger sets too; I tried 55 with no crash, some repetition in the data, and the output sorted in descending order.