#include <iostream>
#include <>
using namespace std;
// Node class template
template <class ElemType>
struct Node
{
// Data Member:
ElemType data; // Data domain
Node<ElemType> *next; // Pointer field
// Constructor template:
Node(); // constructor template without parameters
Node(ElemType item, Node<ElemType> *link = NULL); // Create structure with known data element values and pointers
};
// Implementation part of node class template
template <class ElemType>
Node<ElemType>::Node()
// Operation result: Construct a node with empty pointer field
{
next = NULL;
}
template <class ElemType>
Node<ElemType>::Node(ElemType item, Node<ElemType> *link)
// Operation result: Construct a node with the data domain as item and the pointer domain as link
{
data = item;
next = link;
}
// Linear linked list template
template <class ElemType>
class LinkList
{
protected:
// Data members implemented by linked list:
Node<ElemType> *head; // Header node pointer
mutable int curPosition; // The serial number of the current location
mutable Node<ElemType> *curPtr; // Pointer to the current position
int count; // Number of elements
// Helper function template:
Node<ElemType> *GetElemPtr(int position) const; // Returns a pointer to the position node
public:
// Abstract data type method declaration and overload compilation system default method declaration:
LinkList(); // constructor template without parameters
virtual ~LinkList(); // Destructor template
int Length() const; // Find the length of the linear table
bool Empty() const; // Determine whether the linear table is empty
void Clear(); // Clear the linear table
void Traverse(void (*visit)(const ElemType &)) const; // traverse linear tables
int GetCurPosition() const; // Return to the current location
bool GetElem(int position, ElemType &e) const; // Find the element at the specified position
bool SetElem(int position, const ElemType &e); // Set the element value of the specified position
bool Delete(int position, ElemType &e); // Delete elements
bool Insert(int position, const ElemType &e); // Insert element
LinkList(const LinkList<ElemType> ©); // Copy the constructor template
LinkList<ElemType> &operator=(const LinkList<ElemType> ©); // Overload the assignment operator
};
// Implementation part of linked list template
template <class ElemType>
Node<ElemType> *LinkList<ElemType>::GetElemPtr(int position) const
// Operation result: Return a pointer to the position node
{
if (curPosition > position)
{ // After the current position is in the searched position, you can only start the operation from the table header
curPosition = 0;
curPtr = head;
}
for (; curPosition < position; curPosition++)
curPtr = curPtr->next; // Find location position
return curPtr;
}
template <class ElemType>
LinkList<ElemType>::LinkList()
// Operation result: Construct an empty linked table
{
head = new Node<ElemType>; // Construct the head pointer
curPtr = head;
curPosition = 0; // Initialize the current location
count = 0; // Initialize the number of elements
}
template <class ElemType>
LinkList<ElemType>::~LinkList()
// Operation result: Destroy the linear table
{
Clear(); // Clear the linear table
delete head; // Release the space pointed by the head node
}
template <class ElemType>
int LinkList<ElemType>::Length() const
// Operation result: Return the number of linear table elements
{
return count;
}
template <class ElemType>
bool LinkList<ElemType>::Empty() const
// Operation result: If the linear table is empty, return true, otherwise return false
{
return head->next == NULL;
}
template <class ElemType>
void LinkList<ElemType>::Clear()
// Operation result: Clear the linear table
{
ElemType tmpElem; // Temporary element value
while (!Empty())
{ // If the table is not empty, delete the first element.
Delete(1, tmpElem);
}
}
template <class ElemType>
void LinkList<ElemType>::Traverse(void (*visit)(const ElemType &)) const
// Operation result: Call function (*visit) on each element of the linear table in turn
{
for (Node<ElemType> *tmpPtr = head->next; tmpPtr != NULL; tmpPtr = tmpPtr->next)
{ // Use tmpPtr to point to each element in turn
(*visit)(tmpPtr->data); // Call function (*visit) on each element of the linear table
}
}
template <class ElemType>
int LinkList<ElemType>::GetCurPosition() const
// Operation result: Return to the current location
{
return curPosition;
}
template <class ElemType>
bool LinkList<ElemType>::GetElem(int position, ElemType &e) const
// Operation result: When the position element exists in the linear table, use e to return its value, return true,
// Otherwise, return false
{
if (position < 1 || position > Length())
{ // The position range is wrong
return false; // The element does not exist
}
else
{ // The position is legal
Node<ElemType> *tmpPtr;
tmpPtr = GetElemPtr(position); // Take out the pointer to the position node
e = tmpPtr->data; // Use e to return the value of the position element
return true;
}
}
template <class ElemType>
bool LinkList<ElemType>::SetElem(int position, const ElemType &e)
// Operation result: Assign the element at the position position of the linear table to e,
// The value range of position is 1≤position≤Length(),
// Return true when position is legal, otherwise return false
{
if (position < 1 || position > Length())
{ // The position range is wrong
return false;
}
else
{ // The position is legal
Node<ElemType> *tmpPtr;
tmpPtr = GetElemPtr(position); // Take out the pointer to the position node
tmpPtr->data = e; // Set the value of the position element
return true;
}
}
template <class ElemType>
bool LinkList<ElemType>::Delete(int position, ElemType &e)
// Operation result: Delete the element at the position position of the linear table, and use e to return its value, and the position value
// The range is 1≤position≤Length(). Return true when position is legal, otherwise return false
{
if (position < 1 || position > Length())
{ // The position range is wrong
return false;
}
else
{ // The position is legal
Node<ElemType> *tmpPtr;
tmpPtr = GetElemPtr(position - 1); // Take out the pointer to the position-1 node
Node<ElemType> *nextPtr = tmpPtr->next; // nextPtr is the successor of tmpPtr
tmpPtr->next = nextPtr->next; // Delete nodes
e = nextPtr->data; // Use e to return the value of the deleted node element
if (position == Length())
{ // Delete the tail node, the current node becomes the head node
curPosition = 0; // Set the current position number
curPtr = head; // Set pointer to the current position
}
else
{ // Delete non-tail nodes, the current node becomes the position node
curPosition = position; // Set the current position number
curPtr = tmpPtr->next; // Set pointer to the current position
}
count--; // The number of elements after successful deletion is reduced by 1
delete nextPtr; // Release the deleted nodes
return true;
}
}
template <class ElemType>
bool LinkList<ElemType>::Insert(int position, const ElemType &e)
// Operation result: Insert the value range of element e and position before the position position of the linear table
// It is 1≤position≤Length()+1. Return true when position is legal, otherwise return false
{
if (position < 1 || position > Length() + 1)
{ // The position range is wrong
return false; // Illegal location
}
else
{ // The position is legal
Node<ElemType> *tmpPtr;
tmpPtr = GetElemPtr(position - 1); // Take out the pointer to the position-1 node
Node<ElemType> *newPtr;
newPtr = new Node<ElemType>(e, tmpPtr->next); // Generate a new node and point the next pointer to the original next
tmpPtr->next = newPtr; // Insert tmpPtr into the linked list
curPosition = position; // Set the current position number
curPtr = newPtr; // Set pointer to the current position
count++; // Add 1 to the number of elements after insertion
return true;
}
}
template <class ElemType>
LinkList<ElemType>::LinkList(const LinkList<ElemType> ©)
// Operation result: Construct a new linear table from linear table copy - copy the constructor template
{
ElemType e;
head = new Node<ElemType>; // Construct the head pointer
curPtr = head;
curPosition = 0; // Initialize the current location
count = 0; // Initialize the number of elements
for (int pos = 1; pos <= copy.Length(); pos++)
{ // Copy data elements
copy.GetElem(pos, e); // Take out the posth element
Insert(Length() + 1, e); // Insert e to the current linear table
}
}
template <class ElemType>
LinkList<ElemType> &LinkList<ElemType>::operator=(const LinkList<ElemType> ©)
// Operation result: Assign the linear table copy to the current linear table - overload the assignment operator
{
if (© != this)
{
ElemType e;
Clear(); // Clear the current linear table
for (int pos = 1; pos <= copy.Length(); pos++)
{ // Copy data elements
copy.GetElem(pos, e); // Take out the posth element
Insert(Length() + 1, e); // Insert e to the current linear table
}
}
return *this;
}
/*
TODO: Complete the function of allocating linear table array allocation.
Function function: Use the library function pow evaluation to loop through the initial value, calculate the insertion position value, and call the function to insert the linear table.
Parameter description: lem-element array, n-element number, r-cardinality, d-keyword number, i-cyclic cardinality, list-linear table array
Return value description: None
*/
template <class ElemType>
void Distribute(ElemType elem[], int n, int r, int d, int i, LinkList<ElemType> list[])
// Initial conditions: r is the cardinality, d is the number of keyword bits, list[0.. r - 1] is the assigned linear table array
// Operation result: Perform i-th assignment
{
for (int power = pow(r, i - 1), j = 0; j < n; j++) // Is it useless to perform the i-th session? ?
{
int index = (elem[j] / power) % r;
list[index].Insert(list[index].Length() + 1, elem[j]);
}
}
/*
TODO: Complete the function of allocating linear table array collection.
Function function: Circular traversal to allocate, call the function to delete and reassign elements when the linear table is not empty.
Parameter description: lem-element array, n-element number, r-cardinality, d-keyword number, i-cyclic cardinality, list-linear table array
Return value description: None
*/
template <class ElemType>
void Colect(ElemType elem[], int n, int r, int d, int i, LinkList<ElemType> list[])
// Initial conditions: r is the cardinality, d is the number of keyword bits, list[0.. r - 1] is the assigned linear table array
// Operation results: Conduct i-way collection
{
for (int k = 0, j = 0; j < r; j++)
{ // Make the i-th time distribution
ElemType tmpElem;
while (!list[j].Empty())
{ // Collect list[j]
list[j].Delete(1, tmpElem);
elem[k] = tmpElem;
k++;
}
}
}
/*
TODO: Complete the function of sorting elems cardinality.
Function function: defines the array of linear tables to be stored and allocated corresponding space.
Looping through the calling function for allocation and collection, and finally free up the linear table space.
Parameter description: lem-element array, n-element number, r-base, d-keyword number
Return value description: None
*/
template <class ElemType>
void RadixSort(ElemType elem[], int n, int r, int d)
// Initial conditions: r is the cardinality, d is the number of keywords
// Operation result: Sort the elem cardinality
{
LinkList<ElemType> *list; // Used to store the allocated linear table array
list = new LinkList<ElemType>[r];
for (int i = 1; i <= d; i++)
{ // I-way distribution and collection
Distribute(elem, n, r, d, i, list); // distribute
Colect(elem, n, r, d, i, list); // collect
}
delete[] list;
}
template <class ElemType>
void Show(ElemType elem[], int n)
// Operation result: Display the values of each data element of the array elem
{
for (int i = 0; i < n; i++)
cout << elem[i] << " "; // Display array elem
cout << endl; // Line break
}
int main(void)
{
int a[6];
for (int i = 0; i < 6; i++)
{
cin >> a[i];
}
int n = 6, r = 10, d = 2;
cout << "Before sorting:";
// TODO: Call the function to display the array element values, and then sort the cardinality
Show(a, 6);
RadixSort(a, 6, r, d);
cout << "After sorting:";
// TODO: Calling the function to display the array element value
Show(a, 6);
system("pause");
return 0; // Return value 0, return to the operating system
}
