data structure lab 1

profileahmeddxn7
CSC240_Radix_Sort.zip
Home>Computer Science homework help>data structure lab 1

CSC240_Radix_Sort/CSC240_Radix_Sort.cpp

CSC240_Radix_Sort/CSC240_Radix_Sort.cpp

//============================================================================
// Name        : CSC240_Radix_Sort.cpp
// Author      : Ivan Temesvari
// Version     : 4/24/2019
// Description : Test the Radix Sort using a LinkedQueue
//============================================================================
#include   < fstream >
#include   < iostream >
#include   < cstdlib >
#include   "QueType.h"
#include   "RadixSort.h"
const   int  SIZE  =   50 ;
const   int  NUM_POSITIONS  =   3 ;   //3-digit integers
const   int  RADIX  =   10 ;   //an integer has 10 possible values for each position (place-value)
using   namespace  std ;

// SIZE should be a multiple of 10.

void   Print ( ofstream & ,   int []);     // Prints array
void   InitValues ( int []);           // Creates random array
void   CopyValues ( int [],   int []);    // Makes a copy of random array

template   < class   ItemType >
void   Swap ( ItemType &  item1 ,   ItemType &  item2 );

int  main ()
{
  ofstream outFile ;        // file containing output
  string outFileName ;      // output file external name
  string outputLabel ;
  string command ;          // operation to be executed
   int  values [ SIZE ];
   int  copyValues [ SIZE ];

  cout  <<   "Enter name of output file; press return."   <<  endl ;
  cin   >>  outFileName ;
  outFile . open ( outFileName . c_str ());

  cout  <<   "Enter name of test run; press return."   <<  endl ;
  cin   >>  outputLabel ;
  outFile  <<  outputLabel  <<  endl ;


   //Initialize the array of values to be sorted.
   InitValues ( values );
   CopyValues ( values ,  copyValues );
  outFile  <<   "Initial values***************"   <<  endl ;
   Print ( outFile ,  values );

   //Call the Radix Sort
   RadixSort ( copyValues ,  SIZE ,  NUM_POSITIONS ,  RADIX );

  cout  <<   "Testing completed."    <<  endl ;
  outFile  <<   "Sorted values***************"   <<  endl ;
   Print ( outFile ,  copyValues );
  outFile . close ();
   return   0 ;
}

void   InitValues ( int  values [])
// initializes the values array with random integers from 0 to 999
{
   for   ( int  index  =   0 ;  index  <  SIZE ;  index ++ )
    values [ index ]   =   ( std :: rand ()   %   1000 );
}

void   Print ( ofstream &  outFile ,   int  values [])
{
   using   namespace  std ;
   for   ( int  count  =   0 ;  count  <  SIZE ;  count =  count + 10 )
    outFile  <<  values [ count ]    <<   ", "   <<  values [ count + 1 ]   <<   ", "   <<  values [ count + 2 ]   <<   ", "
     <<  values [ count + 3 ]   <<   ", "   <<  values [ count + 4 ]   <<   ", "   <<  values [ count + 5 ]   <<   ", "
     <<  values [ count + 6 ]   <<   ", "   <<  values [ count  +   7 ]   <<   ", "   <<  values [ count  +   8 ]
     <<   ", "   <<  values [ count + 9 ]   <<  endl  <<  endl ;

}

template   < class   ItemType >
void   Swap ( ItemType &  item1 ,   ItemType &  item2 )
// Post: Contents of item1 and item2 have been swapped.
{
   ItemType  tempItem ;
  tempItem  =  item1 ;
  item1  =  item2 ;
  item2  =  tempItem ;
}

void   CopyValues ( int  inData [],   int  outData [])
{
   for   ( int  count  =   0 ;  count  <  SIZE ;  count ++ )
    outData [ count ]   =  inData [ count ];
}

CSC240_Radix_Sort/QueType.h

#ifndef QUETYPE_H #define QUETYPE_H // Header file for Queue ADT. #include <new> #include <cstddef> #include <iostream> using namespace std; class FullQueue {}; class EmptyQueue {}; template <class ItemType> struct NodeType; template <class ItemType> class QueType { public: QueType(); // Class constructor. // Because there is a default constructor, the precondition // that the queue has been initialized is omitted. ~QueType(); // Class destructor. QueType(const QueType& anotherQue); // Copy constructor void MakeEmpty(); // Function: Initializes the queue to an empty state. // Post: Queue is empty. bool IsEmpty() const; // Function: Determines whether the queue is empty. // Post: Function value = (queue is empty) bool IsFull() const; // Function: Determines whether the queue is full. // Post: Function value = (queue is full) void Enqueue(ItemType newItem); // Function: Adds newItem to the rear of the queue. // Post: If (queue is full) FullQueue exception is thrown // else newItem is at rear of queue. void Dequeue(ItemType& item); // Function: Removes front item from the queue and returns it in item. // Post: If (queue is empty) EmptyQueue exception is thrown // and item is undefined // else front element has been removed from queue and // item is a copy of removed element. void Print(); //Print function private: NodeType<ItemType>* front; NodeType<ItemType>* rear; }; template <class ItemType> struct NodeType { ItemType info; NodeType* next; }; template <class ItemType> QueType<ItemType>::QueType() // Class constructor. // Post: front and rear are set to NULL. { front = NULL; rear = NULL; } template <class ItemType> void QueType<ItemType>::MakeEmpty() // Post: Queue is empty; all elements have been deallocated. { NodeType<ItemType>* tempPtr; while (front != NULL) { tempPtr = front; front = front->next; delete tempPtr; } rear = NULL; } // Class destructor. template <class ItemType> QueType<ItemType>::~QueType() { MakeEmpty(); } template <class ItemType> bool QueType<ItemType>::IsFull() const // Returns true if there is no room for another ItemType // on the free store; false otherwise. { NodeType<ItemType>* location; try { location = new NodeType<ItemType>; delete location; return false; } catch(std::bad_alloc) { return true; } } template <class ItemType> bool QueType<ItemType>::IsEmpty() const // Returns true if there are no elements on the queue; false otherwise. { return (front == NULL); } template <class ItemType> void QueType<ItemType>::Enqueue(ItemType newItem) // Adds newItem to the rear of the queue. // Pre: Queue has been initialized. // Post: If (queue is not full) newItem is at the rear of the queue; // otherwise a FullQueue exception is thrown. { if (IsFull()) throw FullQueue(); else { NodeType<ItemType>* newNode; newNode = new NodeType<ItemType>; newNode->info = newItem; newNode->next = NULL; if (rear == NULL) front = newNode; else rear->next = newNode; rear = newNode; } } template <class ItemType> void QueType<ItemType>::Dequeue(ItemType& item) // Removes front item from the queue and returns it in item. // Pre: Queue has been initialized and is not empty. // Post: If (queue is not empty) the front of the queue has been // removed and a copy returned in item; // othersiwe a EmptyQueue exception has been thrown. { if (IsEmpty()) throw EmptyQueue(); else { NodeType<ItemType>* tempPtr; tempPtr = front; item = front->info; front = front->next; if (front == NULL) rear = NULL; delete tempPtr; } } template <class ItemType> QueType<ItemType>::QueType (const QueType<ItemType>& anotherQue) { NodeType<ItemType>* ptr1; NodeType<ItemType>* ptr2; if (anotherQue.front == NULL) front = NULL; else { front = new NodeType<ItemType>; front->info = anotherQue.front->info; ptr1 = anotherQue.front->next; ptr2 = front; while (ptr1 != NULL) { ptr2->next = new NodeType<ItemType>; ptr2 = ptr2->next; ptr2->info = ptr1->info; ptr1 = ptr1->next; } ptr2->next = NULL; rear = ptr2; } } template <class ItemType> void QueType<ItemType>::Print(){ NodeType<ItemType>* node = front; while(node != rear->next){ cout << node->info << " "; node = node->next; } cout << endl; } #endif

CSC240_Radix_Sort/RadixSort.h

// This file contains the functions for Radix Sort. // In the RadixSort function, the parameters have these meanings: // // values is the array to be sorted // numValues is the size of the array to be sorted // numPositions is the size of the key measured in digits, characters etc.. // If keys have 3 digits, this has the value 3, // If 10 digit keys, this has the value 10. // If word keys, then this is the number of characters in // the longest word. // radix is the radix of the key, 10 in the case of decimal digit keys // 26 for case-insensitive letters, 52 if case-sensitive letters. // Modified SubKey -- IT 4/24/2019 #include "QueType.h" #include <math.h> int SubKey(int value, int position){ return (value / (int)pow(10,position-1)) % 10; } template<class ItemType> void RadixSort(ItemType values, int numValues, int numPositions, int radix) // Post: Elements in values are in order by key. { QueType<int> queues[10]; // With default constructor, each queue size is 500 int whichQueue; for (int position = 1; position <= numPositions; position++) { for (int counter = 0; counter < numValues; counter++) { whichQueue = SubKey(values[counter], position); queues[whichQueue].Enqueue(values[counter]); } CollectQueues(values, queues, radix); } } template<class ItemType> void CollectQueues(ItemType values[], QueType<ItemType> queues[], int radix) // Post: queues are concatanated with queue[0]'s on top and // queue[9]'s on the bottom and copied into values. { int index = 0; ItemType item; for (int counter = 0; counter < radix; counter++) { while (!queues[counter].IsEmpty()) { queues[counter].Dequeue(item); values[index] = item; index++; } } }