Question
C++: Write a program that attempts to make the Radix Sort more practical: make it sort strings of a maximum length of 15. Have an
C++: Write a program that attempts to make the Radix Sort more practical: make it sort strings of a maximum length of 15. Have an array of strings. Then in the Radix Sort, create an array of LinkedQueue with 95 queues (95 are the printable characters starting with space). Those queues will be used to separate the data then combine them (i.e. bins). Randomly generate 10,000 strings with lengths from 1 to 15 (during the sort and with strings less than 15, treat all positions at the end that are not there as space). When generating random characters, have only 10% be digits, 10% special characters, and the rest, 80%, alphabetic characters, upper and lowercase. Before the sort, print out the first 10 strings, print out the middle 10 strings, and print last 10 strings. Then do the radix sort then print out the first 10 strings, print out the middle 10 strings, and print last 10 strings
@file LinkedQueue.h */
#ifndef LINKED_QUEUE_
#define LINKED_QUEUE_
#include
#include
#include "QueueInterface.h"
#include "Node.h"
#include "PrecondViolatedExcep.h"
template
class LinkedQueue : public QueueInterface
{
private:
// The queue is implemented as a chain of linked nodes that has
// two external pointers, a head pointer for front of the queue and
// a tail pointer for the back of the queue.
std::shared_ptr> backPtr;
std::shared_ptr> frontPtr;
public:
LinkedQueue();
LinkedQueue (const LinkedQueue& aQueue);
~LinkedQueue();
bool isEmpty() const;
bool enqueue(const ItemType& newEntry);
bool dequeue();
/** @throw PrecondViolatedExcep if the queue is empty */
ItemType peekFront() const throw(PrecondViolatedExcep);
void LastFirst();
int LineRemove(char letter);
}; // end LinkedQueue
#include "LinkedQueue.cpp"
#endif
/** @file LinkedQueue.cpp */
#ifndef LINKED_QUEUE_CPP
#define LINKED_QUEUE_CPP
#include "LinkedQueue.h"
#include
#include
template
LinkedQueue::LinkedQueue()
{ } // end default constructor
template
LinkedQueue::LinkedQueue(const LinkedQueue& aQueue)
{ // Implementation left as an exercise (Exercise 1).
auto origChainPtr = aQueue.frontPtr; // Points to nodes in original chain
// Using shared pointers initializes frontPtr/backPtr to nullPtr
if (origChainPtr != nullptr)
{
// Copy first node
frontPtr = std::make_shared>();
frontPtr->setItem(origChainPtr->getItem());
// Advance original-chain pointer
origChainPtr = origChainPtr->getNext();
// Copy remaining nodes
auto newChainTailPtr = frontPtr; // Points to last node in new chain
while (origChainPtr != nullptr)
{
// Get next item from original chain
ItemType nextItem = origChainPtr->getItem();
// Create a new node containing the next item
auto newNodePtr = std::make_shared>(nextItem);
// Link new node to end of new chain
newChainTailPtr->setNext(newNodePtr);
// Advance pointers
newChainTailPtr = newChainTailPtr->getNext();
origChainPtr = origChainPtr->getNext();
} // end while
newChainTailPtr->setNext(nullptr); // Flag end of chain
backPtr = newChainTailPtr;
} // end if
} // end copy constructor
template
LinkedQueue::~LinkedQueue()
{
//smart pointers will clean-up
backPtr == nullptr;
frontPtr == nullptr;
} // end destructor
template
bool LinkedQueue::isEmpty() const
{
return backPtr == nullptr;
} // end isEmpty
template
bool LinkedQueue::enqueue(const ItemType& newEntry)
{
auto newNodePtr = std::make_shared>(newEntry);
// Insert the new node
if (isEmpty())
frontPtr = newNodePtr; // Insertion into empty queue
else
backPtr->setNext(newNodePtr); // Insertion into nonempty queue
backPtr = newNodePtr; // New node is at back
return true;
} // end enqueue
template
bool LinkedQueue::dequeue()
{
bool result = false;
if (!isEmpty())
{
// Queue is not empty; delete front
auto nodeToDeletePtr = frontPtr;
if (frontPtr == backPtr)
{ // Special case: one node in queue
backPtr = nullptr;
frontPtr = nullptr;
}
else
{
frontPtr = frontPtr->getNext();
}
result = true;
} // end if
return result;
} // end dequeue
template
ItemType LinkedQueue::peekFront() const throw(PrecondViolatedExcep)
{
if (isEmpty())
throw PrecondViolatedExcep("getFront() called with empty queue.");
// Queue is not empty; return front
return frontPtr->getItem();
} // end peekFront
template
void LinkedQueue::LastFirst()
{
string name;
int length, x;
auto curPtr = frontPtr;
while (curPtr != nullptr)
{
while (curPtr != nullptr)
{
name = curPtr->getItem();
x = name.find(' ');
length = name.length();
if (x > 0)
{
name = name.substr(x+1, length) + ", " + name.substr(0, x);
curPtr->setItem(name);
}
curPtr = curPtr->getNext();
}
}
}
// End of implementation file.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started