sorting a singly linked list

This is a discussion on sorting a singly linked list within the C Programming forums, part of the General Programming Boards category; Hello, I am trying to sort a singly linked list for the following typedef typedef struct message { int messageId; ...

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    6

    sorting a singly linked list

    Hello,
    I am trying to sort a singly linked list for the following typedef
    typedef struct message {
    int messageId;
    char * messageText;
    struct message * next;
    } message;
    I have successfully implemented add, delete, print, and search functions for the linked list but I am not sure why I am stuck with this one.


    I posted my code below. I get a BUS error in the second iteration of the while loop. I am quite new to linked list so I will appreciate any explanation.

    Thank you

    Code:
    	if(first != NULL && first->next != NULL) /* less than two nodes */
    	{		
    		message *a = first;
    		message *b = first->next;
    		message *beforeA =  NULL;
    
    		while(b != NULL)
    		{
    			if(a->messageId > b->messageId)
    			{
    				a->next = b->next;
    				b->next = a;
    				if(a == first && beforeA == NULL)
    				{
    					first = b;
    					beforeA = first;
    				}
    				else if (beforeA != NULL)
    				{
    					beforeA->next = b;
    				}
    				/* Move to the next couple of nodes */
    				b = a->next;
    				beforeA = beforeA->next;
    			}else if (a->messageId < b->messageId)
    			{
    
    				a = a->next;
    				b = b->next;
    			}
    		}
    	}

  2. #2
    uint64_t...think positive xuftugulus's Avatar
    Join Date
    Feb 2008
    Location
    Pacem
    Posts
    355
    You didn't advance beforeA when a->messageId < b->messageId, so when you fo to the second iteration beforeA is NULL and doesn't get updated because a is not first anymore. So at the line where beforeA = beforeA->next, you access NULL->next and get a bus error.

    Proposed fix:
    Code:
    			}else if (a->messageId < b->messageId)
    			{
                                    beforeA = a;
    				a = a->next;
    				b = b->next;
    			}
    Code:
    ...
        goto johny_walker_red_label;
    johny_walker_blue_label: exit(-149$);
    johny_walker_red_label : exit( -22$);
    A typical example of ...cheap programming practices.

  3. #3
    Registered User
    Join Date
    Feb 2008
    Posts
    6
    Thank you for your reply. That was indeed one of the problems but I still have a Bus error.
    I am sure that the error is in the conditional statement. (After some debugging I guess this is the problem.)
    Code:
    			if(a->messageId > b->messageId)
    			{
    				a->next = b->next;
    				b->next = a;
    				if(a == first && beforeA == NULL)
    				{
    					first = b;
    					beforeA = first;
    				}
    				else if (beforeA != NULL)
    				{
    					beforeA->next = b;
    				}
    				/* Move to the next couple of nodes */
    				b = a->next;
    				beforeA = beforeA->next;
    			}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  2. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 05:37 PM
  3. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 05:40 PM
  4. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21