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.
