Help Sorting A Linked List

This is a discussion on Help Sorting A Linked List within the C++ Programming forums, part of the General Programming Boards category; Hello I'm trying to sort a linked list. I'm having some trouble figuring out how to swap an array of ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    11

    [SOLVED]Help Sorting A Linked List

    Hello I'm trying to sort a linked list. I'm having some trouble figuring out how to swap an array of char. I know I should have used "string" but this is an assignment for school and we aren't allowed to change it to "string".

    Edit: I fixed it I just needed to use "strcpy" to swap the names.

    Code:
    #ifndef _ASSIGNMENT_9_CPP_
    #define _ASSIGNMENT_9_CPP_
    
    #include <iostream>
    #include <fstream>
    #include <string>
    #include <iomanip>
    #include <cstdlib>
    
    using namespace std;
    
    struct Node 
    { 
         char name[30];
         long ID;
         Node * next;
         
         Node();
    };
    
    class LIST 
    { 
         private:
              Node *link;
              int lsize; 
         public:
              LIST(); 
              void OpenFile(ifstream & myfile); 
              bool ReadFile(ifstream & myfile); 
              Node*Nodebuild (char name[], long ID); 
              void LinkList(Node *ptr); 
              void sortList(); 
              void showList();
    };
    
    LIST::LIST()
    {
         link = NULL;
    }
    
    Node::Node()
    {
         next = NULL;
    }
    
    void LIST::OpenFile(ifstream & myfile)
    {
         myfile.open("a9.txt");
    }
    
    bool LIST::ReadFile(ifstream & myfile)
    {
        
        if(myfile.peek() == EOF)
        {
              return false;
        }
        
        char name[30];
        long ID;
        
        myfile>>name;
        myfile>>ID;
        
        LinkList(Nodebuild(name,ID));
        
       
         if(myfile)
         {
              return true;
         }
         else 
         {
              return false;
         }
         
         
    }
    
    Node *LIST::Nodebuild(char name[],long ID)
    {
         Node *ptr = new Node;
         
         strcpy(ptr->name, name);     
         ptr->ID = ID;
         ptr->next = NULL;
         return ptr;
    }
    
    void LIST::LinkList(Node *ptr)
    {
         if(link == NULL)
         {
              link = ptr;
              return;
         }
         
         Node *t_v;
         t_v = link;
         
         while(t_v->next!=NULL)
         {
              t_v = t_v->next;
         }
         
         t_v->next = ptr;
    }
    
    void LIST::sortList() 
    {
         
    	Node *curr;
    	char tempName;
    	
    	for(bool didSwap = true; didSwap; ) 
    	{
    		didSwap = false;
    		for(curr = link; curr->next != NULL; curr = curr->next) 
    		{
    			if(curr->ID > curr->next->ID) 
    			{
    				tempName = curr->name;
    				curr->name = curr->next->name;
    				curr->next->name = tempName;
    				
    				swap(curr->ID, curr->next->ID);
    				
    				didSwap = true;
    			} 
    		}
    	}
    }
    
    void LIST::showList()
    {
         Node *t = link;
         
         while(t != NULL)
         {
              cout<<t->name<<" "<<t->ID<<endl;        
              t = t->next;
         }
    }
    
    int main()
    {
         LIST myList;      
         ifstream myfile;
         
         myList.OpenFile(myfile);
         while(myList.ReadFile(myfile)); 
         myList.sortList();
         myList.showList();
         
         cout<<endl;
         
    return 0;
    }
    
    #endif
    Last edited by Sherina; 12-11-2009 at 06:48 PM.

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    If you are sorting a linked list, why are you swapping char arrays? Methinks the point of the exercise would be to swap pointers.
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  3. #3
    Registered User
    Join Date
    Nov 2009
    Posts
    11
    This is the way I'm use to it swapping linked list. The book I'm reading from doesn't really explain how to swap linked list and my professor doesn't explain how to swap them either.

  4. #4
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,262
    Ok. All a linked list element is is a pointer, right? And all an pointer is is a pointer to a place in memory. So consider the array being your list buffer (this example is not dynamic, just to show you the principle behind pointer swapping), and the pointers being some nodes in the list.

    Code:
    int main( void ) {
      // Initialise some variables
      int arr[10] = {0};
      arr[2] = 2;
      arr[8] = 8;
      int *ela = &arr[2];
      int *elb = &arr[8]; 
    
      // Print
      std::cout<< "Before swap: a("<< *ela << "), b(" << *elb << ")\n"; 
    
      // Swap the pointers
      int *tmp = ela;
      ela = elb;
      elb = tmp;
    
      // Print
      std::cout<< "After swap:  a("<< *ela << "), b(" << *elb << ")\n"; 
    
      return 0;
    }
    
    /* My output:
    
    Before swap: a(2), b(8)
    After swap:  a(8), b(2)
    */
    Consider modifying the swap snippet to swap elements of your linked list in order to sort it.
    Last edited by twomers; 12-12-2009 at 04:49 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Circularly-Doubly Linked List implementation
    By BlackOps in forum C Programming
    Replies: 4
    Last Post: 07-19-2009, 04:45 AM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 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