Sort Linked List Algorithm.

This is a discussion on Sort Linked List Algorithm. within the C++ Programming forums, part of the General Programming Boards category; I've written a sort for a linked list (at least i thought i did), and can not figure out what ...

  1. #1
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589

    Question Sort Linked List Algorithm.

    I've written a sort for a linked list (at least i thought i did), and can not figure out what is wrong. If I could get any help it would be appreciated.

    html posted code
    [edit]
    below is excerpt from the source code. what i'm trying to do is call this public class member from another public class member that extracts the data from 2 other instansiated link list objects. the objects and the new sorted linked list are from the same class. i'm passing the object that I want the final list to be. basically i'm combining 2 already built lists and sorting them in the below function after i've extracted each individual node. it isn't working. i'm not getting any compile errors, but the logic must not be correct. when i run it it doesn't crash, but it doesn't fill the list with anything. I have been accused of not being percise enough, but i hope the details i'm providing cover the full aspect of my frustration. I know there are some genises that answer questions here so I beg you for your input.
    Code:
     
    void linklist::orderedlist(linklist *CopyC)
    {  	//
    	link *current , *previous;
    	current = previous = head;
    
    	link *newlink = new link;
    	
    	for(x=0;x<=SIZE;x++)
    	{
    		newlink->fname[x] = buffer1[x]; 
    	}
    
    	for(x=0;x<=SIZE;x++)
    	{
    		newlink->lname[x] = buffer2[x];
    	}
    
    	for(x=0;x<=SIZE;x++)
    	{
    		newlink->ssnumber[x] = buffer3[x];
    	}
    
    	newlink->age=age;
    	newlink->weight=weight;
    
    	newlink->next = NULL;
    
    	if (head == NULL) //this tells me I have an empty list
    	{
    		head = newlink;
    		tail = head;
    	}
    	else
    	{
    		//find the position to insert it
    		while ( strcmp(current->lname,buffer2)==1 && current->next !=NULL)
    		{
    			previous = current;
    			current = current->next;
    		}
    
    		if (current==head)//it will become the new head
    		{
    			newlink->next=head;
    			head=newlink;
    		}
    		else
    		{
    			if (current->next==NULL)//becomes the new tail
    			{
    				tail->next=newlink;
    				tail = newlink;
    			}
    			else
    			{
    				previous->next=newlink;
    				newlink->next=current;
    			}
    		}
    	}
    }
    i also tried this, but it doesn't work either.
    Code:
     
    void linklist::orderedlist(linklist *CopyC)
    {  	//
    
    	*CopyC->current = *CopyC->previous = *CopyC->head;
    
    	*CopyC->link->node = new link;
    	
    	for(x=0;x<=SIZE;x++)
    	{
    		*CopyC->link->fname[x] = buffer1[x]; 
    	}
    
    	for(x=0;x<=SIZE;x++)
    	{
    		*CopyC->link->lname[x] = buffer2[x];
    	}
    
    	for(x=0;x<=SIZE;x++)
    	{
    		*CopyC->link->ssnumber[x] = buffer3[x];
    	}
    
    	*CopyC->link->age=age;
    	*CopyC->link->weight=weight;
    
    	*CopyC->link->next = NULL;
    
    	if (*CopyC->head == NULL) //this tells me I have an empty list
    	{
    		*CopyC->head = *CopyC->link;
    		*CopyC->tail = *CopyC->head;
    	}
    	else
    	{
    		//find the position to insert it
    		while ( strcmp(*CopyC->current->lname,buffer2)==1 && *CopyC->current->next !=NULL)
    		{
    			*CopyC->previous = *CopyC->current;
    			*CopyC->current = *CopyC->current->next;
    		}
    
    		if (*CopyC->current==*CopyC->head)//it will become the new head
    		{
    			*CopyC->link->next=*CopyC->head;
    			*CopyC->head=*CopyC->link;
    		}
    		else
    		{
    			if (*CopyC->current->next==NULL)//becomes the new tail
    			{
    				*CopyC->tail->next=*CopyC->link;
    				*CopyC->tail = *CopyC->link;
    			}
    			else
    			{
    				*CopyC->previous->next=*CopyC->link;
    				*CopyC->link->next=*CopyC->current;
    			}
    		}
    	}
    }
    [\edit]
    Last edited by xviddivxoggmp3; 10-09-2003 at 03:37 AM.
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  2. #2
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    source code .cpp file
    Attached Files Attached Files
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  3. #3
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    If you want to copy a linked list, it should look something like this.
    Code:
    void linklist::copy(linklist *new_list)
    {
       link *current;
       link *new_current;
    
       if (head == NULL)
          cout << "Empty list." << endl;
       {
          cout << "********** COPYING *********" << endl;
          current = head;
          while (current != NULL)
          {
             new_current = new link;
             new_current->next = NULL;
             if (new_list->head == NULL)
                new_list->head = new_current;
             else
                new_list->tail->next = new_current;
             new_list->tail = new_current;
    
             strcpy(new_current->fname, current->fname);
             strcpy(new_current->lname, current->lname);
             strcpy(new_current->ssnumber, current->ssnumber);
             new_current->age = current->age;
             new_current->weight = current->weight;
             current = current->next;
          }
       }
    }
    To sort a linked list, you have to decide:
    1. What sort algorithm to use (bubble, quick, heap)
    2. What item to sort by (name, ssnumber, etc)

  4. #4
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    Swoopy,

    Thanks for the response... you always come through.
    I'm looking to fix a sort that is ill.
    As you can see I'm very confused.
    below is my newest version that still doesn't work.
    I have traced the code with node depictions and pointers over and over. It works in my head, but not in the program.
    What the code is sapposed to do is merge two linked lists into a third ordered list. In the main i have two calls that pass two lists by reference. not at the same time, but one after the other. our teacher gave us this sort algorithm, but it doesn't work.
    all it does is merge the two together without sorting.
    i have ran numerous tests. i have determined that the data passes correctly. the buffers are filled. the strcmp() is spitting out correct test data, but it still will not sort. I believe my pointer combinations are off. but my trace works. i'm completely lost.
    a follow up question is when do i get into the cool programming and not the confusing programming. hehehe i know that isn't a real question.
    Code:
    void linklist::orderedlist(linklist *list)
    	{  
    		initializeData();
    
    		list->current=list->head;
    
    		while (list->current != NULL)  
    		{		
    			for(x=0;x<=SIZE;x++)
    			{
    				buffer1[x]=list->current->fname[x]; 
    			}
    
    			for(x=0;x<=SIZE;x++)
    			{
    				buffer2[x]=list->current->lname[x];
    			}
    
    			for(x=0;x<=SIZE;x++)
    			{
    				buffer3[x]=list->current->ssnumber[x];
    			}
    
    			age=list->current->age;
    			weight=list->current->weight;
    
    			list->current = list->current->next;
    			
    			current = previous = head;
    
    			link* newlink = new link;
    		    
    			for(x=0;x<=SIZE;x++)
    			{
    				newlink->fname[x] = buffer1[x]; 
    			}
    
    			for(x=0;x<=SIZE;x++)
    			{
    				newlink->lname[x] = buffer2[x];
    			}
    
    			for(x=0;x<=SIZE;x++)
    			{
    				newlink->ssnumber[x] = buffer3[x];
    			}
    
    			newlink->age=age;
    			newlink->weight=weight;
    
    			newlink->next = NULL;
    
    			if (head == NULL) //this tells me I have an empty list
    			{
    				head = newlink;
    				tail = head;
    			}
    			else
    			{
    				//find the position to insert it
    				while ( strcmp(current->lname,buffer2)==1 && current->next !=NULL)
    				{
    					previous = current;
    					current = current->next;
    				}
    
    				if (current==head)//it will become the new head
    				{
    					newlink->next=head;
    					head=newlink;
    				}
    				else
    				{
    					if (current->next==NULL)//becomes the new tail
    					{
    						tail->next=newlink;
    						tail = newlink;
    					}
    					else
    					{
    						previous->next=newlink;
    						newlink->next=current;
    					}
    				}
    			}
    		}
    	}
    Attached Files Attached Files
    Last edited by xviddivxoggmp3; 10-10-2003 at 11:51 AM.
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  5. #5
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    why can we not attach more than one file at a time?
    Attached Files Attached Files
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  6. #6
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    i split it into 3 files for my teacher.
    her is the last of the three
    Attached Files Attached Files
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  7. #7
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    > //find the position to insert it
    > while ( strcmp(current->lname,buffer2)==1 && current->next !=NULL)

    I don't think it will help, but instead you might try:
    //find the position to insert it
    while ( strcmp(current->lname,buffer2)>0 && current->next !=NULL)

  8. #8
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    To sort a linked list, you have to decide:
    1. What sort algorithm to use (bubble, quick, heap)
    2. What item to sort by (name, ssnumber, etc)
    Swoopy,

    I believe what I recreated was a bubble sort with a linked list.
    I'm sorry I didn't see this part of the post until just now.
    I have rewritten this using strcpy(), but it hangs on the new revision. I accidently started a new thread due to I just found this one again.
    new thread addresssing the same question.
    check out the new thread for the revised code. I've been out of town and finally got back so I do appologize for this thread getting old.
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Not Saving Value as Int
    By bar338 in forum C Programming
    Replies: 4
    Last Post: 05-04-2009, 07:53 PM
  2. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  3. sort linked list using BST
    By Micko in forum C Programming
    Replies: 8
    Last Post: 10-04-2004, 02:04 PM
  4. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 09:33 PM
  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