Thread: Radix Sort, Strings, and Linked Lists

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    2

    Radix Sort, Strings, and Linked Lists

    Hi. I'm trying to implement a Radix Sort in C++ that sorts strings passed into the module from a linked list. The key problem is that I need to know how to modify the code in the numerical implementation of the Radix Sort to accept strings. I'm using the AP classes for strings (apstring.h apstring.cpp), and a precoded implemetation of the Radix Sort and linked lists.

    Code:
    void radixSort(LinkedList<int> &list)
    {
            int k, temp;
            BinStructureType bins;
    
    
            // For k loop controls digit used to classify data. 
            for (k = 1; k <= 4; ++k)
            {
                    list.first();
    
                    // Inner loop iterates through all numbers
                  //putting  them into
                    // bin determined by kth digit. 
                    while (! list.empty() )
                    {
                            temp = list.remove();
                            addToBin (bins, temp, digit(temp, k));
                    }
                    collectBins (list, bins);
            }
    }       
    
    void addToBin(BinStructureType bins, int number, int place)
    {
            bins[place].insert(number);
            bins[place].next();
    }
    
    void collectBins(LinkedList<int> &list, BinStructureType bins)
    {
            int place = 0;
            
            for (int i = 0; i < 10; ++i)     // Loop through all bins
            {
                    bins[i].first();
                    while ( !bins[i].empty() ) // Loop through numbers 
                       //in a bin
                    {
                            list.insert(bins[i].remove());                         
                        // Append number from bin to list
                            list.next();                                                           
                      // Goto next place in list
                    }       
            }
    }
    
    // Class declaration file: linklist.h
    
    #include <assert.h>
    
    #ifndef LINKLIST_H
    
    template <class E> class LinkedList
    {
            public:
      
            // constructors
    
            LinkedList();
            LinkedList(const LinkedList<E> &list);
    
            // destructor
    
            ~LinkedList();
        
            // assignment
    
            LinkedList<E>& operator = 
                    (const LinkedList<E> &rhs);
    
            // accessors
        
            int  length() const;
            bool empty() const;
            bool atEnd() const;
            E access();
      
            // modifiers
        
            void first();
            void next();
            void modify(const E &item);
            void insert(const E &item);     
            E remove();    
    
            protected:
    
            // Data members
    
            /*struct node;          // Definition of the node type
            typedef node * nodePtr;        
             // Definition of type pointer to node type */
            struct node                    
            // Completion of the node type definition
            {
                    E data;
                    //nodePtr next;
                    node * next;
            };
    
            // External pointers to the list
            
            node * myFirst; 
            node * myCurrent;
            node * myPrevious;
    
            // The number of nodes in the list
    
            int mySize;
    
            // Member functions
    
            node *  getNode(const E &item);                                             
    };
    
    template <class E>
    LinkedList<E>::LinkedList()
    : myFirst(0), myCurrent(0), myPrevious(0), mySize(0)
    {
    }
            
    
    template <class E>
    LinkedList<E>::LinkedList(const LinkedList<E> &list)
    : myFirst(0), myCurrent(0), myPrevious(0), mySize(0)
    {
            // Temporary pointer to first node in list
    
            node *  probe = list.myFirst;
            
            // Loop until end of list is reached
    
            while (probe != 0)
            {
    
                    // Insert data from node in list
    
                    insert(probe->data);
    
                    // Advance to end of receiver
    
                    next();
    
                    // Move probe to next node in list
    
                    probe = probe->next;
            }
    }
    
    template <class E>
    LinkedList<E>& LinkedList<E>::operator = 
                    (const LinkedList<E> &rhs)
    {
            // Temporary pointer to first node in list
    
            node *  probe = rhs.myFirst;
            
            // Loop until end of list is reached
    
            while (probe != 0)
            {
    
                    // Insert data from node in list
    
                    insert(probe->data);
    
                    // Advance to end of receiver
    
                    next();
    
                    // Move probe to next node in list
    
                    probe = probe->next;
            }
            return *this;
    }
    
    
    template <class E>
    LinkedList<E>::~LinkedList()
    {
    
            E item;
    
            first();
            while (! empty())
                    item = remove();
    }
    
    template <class E>
    void LinkedList<E>::first()
    {
            if (myCurrent != myFirst)
            {
                    myCurrent = myFirst;
                    myPrevious = 0;
            }
    }
    
    
    template <class E>
    void LinkedList<E>::next()
    {
            assert (myCurrent != 0);
            myPrevious = myCurrent;
            myCurrent = myCurrent->next;
    }
    
    
    template <class E>
    E LinkedList<E>::access()
    {
            assert(myCurrent != 0);
            return myCurrent->data;
            
    }
    
    template <class E>
    void LinkedList<E>::modify(const E &item)
    {
            assert(myCurrent != 0);
            myCurrent->data = item;
            
    }
    
    
    template <class E>
    bool LinkedList<E>::atEnd() const
    {
            return (empty() || myCurrent == 0);
    }
    
    
    template <class E>
    bool LinkedList<E>::empty() const
    {
            return mySize == 0;
    }
    
    template <class E>
    int LinkedList<E>::length() const
    {
            return mySize;
    }
    
    
    template <class E>
    void LinkedList<E>::insert(const E &item)
    {
            node *  newNode = getNode(item);
    
            if (empty() || (myFirst == myCurrent))
                    myFirst = newNode;
            else
                    myPrevious->next = newNode;
            newNode->next = myCurrent;
            myCurrent = newNode;
            ++mySize;
    }
    
    
    template <class E>
    LinkedList<E>::node *  LinkedList<E>::getNode
            (const E &item)
    {
            node *  newNode = new node;
    
            assert(newNode != 0);
            newNode->data = item;
            newNode->next = 0;
            return newNode;
    }
    
    
    template <class E>
    E LinkedList<E>::remove()
    {
            assert (myCurrent != 0);
            E data = myCurrent->data;
            node *  garbage = myCurrent;
    
            if (myFirst == myCurrent)
                    myFirst = myCurrent->next;
            else
                    myPrevious->next = myCurrent->next;
            myCurrent = myCurrent->next;
            delete garbage;
            --mySize;
            return data;
    }
    
        
    #define LINKLIST_H
    #endif
    You can find the AP Classes for strings at the collegeboard website. If someone can help me, I would really appreciate it.
    Last edited by dark paladin; 04-24-2003 at 03:28 PM.

  2. #2
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490

  3. #3
    Registered User
    Join Date
    Apr 2003
    Posts
    2
    Thanx for the tip.
    Last edited by dark paladin; 04-24-2003 at 03:28 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Storing strings in a linked list
    By dws90 in forum C Programming
    Replies: 1
    Last Post: 02-21-2009, 07:06 PM
  2. Replies: 7
    Last Post: 06-16-2006, 09:23 PM
  3. Sort strings in double linked list. (Optimize code)
    By netstar in forum C++ Programming
    Replies: 15
    Last Post: 02-28-2005, 01:40 AM
  4. help with linked lists
    By jdiaz_1 in forum C Programming
    Replies: 1
    Last Post: 10-15-2003, 04:15 PM
  5. Problems with linked lists from *.dat
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 05-03-2002, 05:22 PM