Bubble sorting singly link list

This is a discussion on Bubble sorting singly link list within the C Programming forums, part of the General Programming Boards category; Hello All, Following is the bubble sorting program. It is crashing is sort function. Please let me know, where I;m ...

  1. #1
    Registered User
    Join Date
    Feb 2003
    Posts
    175

    Bubble sorting singly link list

    Hello All,

    Following is the bubble sorting program. It is crashing is sort function. Please let me know, where I;m goig wrong.

    Code:
    # include <stdio.h>
    # include <stdlib.h>
    
    void append(struct node **,struct node *);
    void display(struct node *);
    int Delete_nth_node(struct node **,int i);
    void sort(struct node **);
    void delTree(struct node *);
    
    //struct node *merge_list(struct node **ppHead1,struct node **ppHead2);
    //struct node *merge(struct node *current1,struct node *current2);
    //int length(struct node *walk);
    
    struct node
    {
    	int data;
    	struct node *next;
    }node;
    
    void main(void)
    {
    	int i, result;
    	struct node *pHead1, *new_node;
    
    	pHead1 = NULL;
    
    	printf("Enter the numbers for list 1:\n");
    	if ( scanf("%d",&i) == 1 )
    	{
    		while (i)
    		{	
    			new_node = calloc(1,sizeof(node));
    			new_node->data = i;
    			append(&pHead1,new_node);
    			if ( scanf("%d",&i) == 1 )
    				continue;
    			else
    				break;
    		}
    		display(pHead1);
    	}
    
    //	printf("\nAfter deleting 2nd node\n");
    	
    //	result = Delete_nth_node(&pHead1,2);
    //	if ( result )
    //		display(pHead1);
    
    	sort(&pHead1);
    	display(pHead1);
    
    	delTree(pHead1);
    }
    
    void sort(struct node **ppHead)
    {
    	struct node *current,*forward,*save;
    
    	current = *ppHead;
    	forward = current->next;
    	save = NULL;
    
    	while(current)
    	{
    		while(forward)
    		{
    			if (current->data > forward->data)
    			{
    				struct node *temp;
    				temp = forward->next;
    				forward->next = current;
    				current->next = temp;
    				forward = temp;
    				if (save)
    					save->next = current;
    			}
    			else
    				forward = forward->next;
    		}
    		save = current;
    		current = current->next;
    		forward = current->next;
    	}
    }
    
    
    // Inserts, appends or prepends depending upon its value.
    void append(struct node **ppHead, struct node *new_node)
    {
    	struct node *current;
    
    	// First time when not even single node is generated
    	if ( *ppHead == NULL )
    	{
    		new_node->next = NULL;
    		*ppHead = new_node;
    	}
    	else 
    	{
    		current = *ppHead;
    		
    		while (current->next != NULL)
    			current = current->next;
    		
    		current->next = new_node;
    	}
    }
    
    
    int Delete_nth_node(struct node **ppHead,int i)
    {
    	struct node *current,*nth_node,*save;
    
    	nth_node = NULL;
    	current = *ppHead;
    
    	while ( current )
    	{
    		if ( current == NULL && (!nth_node) )
    			return 0;
    		else if ( !i )
    		{
    			save = nth_node = *ppHead;
    
    			while (1)
    			{
    				if ( current->next == NULL )
    					break;
    				current = current->next;
    				save = nth_node;
    				nth_node = nth_node->next;
    			}
    			if ( save == nth_node)
    			{
    				*ppHead = save->next;
    				return 1;
    			}
    			save->next = nth_node->next;
    			free(nth_node);
    			return 1;
    		}
    		current = current->next;
    		i--;
    	}
    	return 0;
    }
    
    // Displays entire link list
    void display(struct node *walk)
    {
    	printf("\nLink list is:\n");
    	while (walk)
    	{
    		printf("%d\t",walk->data);
    		walk = walk->next;
    	}
    }
    
    void delTree(struct node *walk)
    {
    	struct node *save;
    	while (walk)
    	{
    		save = walk->next;
    		free(walk);
    		walk = save;
    	}
    }

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,175
    This is where I find pencil and paper very handy. I draw little boxes on the paper representing the nodes with an arrow pointing from each box to the one after it, creating the list. Then I walk through each step in the sorting routine one at a time in my head and draw what the list would look like after moving one node. Then just keep repeating that process until you find the reason the routine is blowing up on you
    If you understand what you're doing, you're not learning anything.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Bubble sorting singly link list
    Why are you trying to bubble sort anything to begin with? Insertion sort is easier to code and faster than bubble sort for linked lists.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 06:55 PM
  2. Linked List, Please Help!
    By CodeMonkeyZ in forum C Programming
    Replies: 5
    Last Post: 02-17-2009, 06:23 AM
  3. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  4. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

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