Question
Sorting Study in C++ Requires 2 headers (arrayListType.h and linkedQueueType.h) and one driver file (main.cpp) Please give example output through a terminal Declare an array
Sorting Study in C++
Requires 2 headers (arrayListType.h and linkedQueueType.h) and one driver file (main.cpp)
Please give example output through a terminal
Declare an array using arrayListType.h to hold 50 integers. Load the array with data from the file num.dat. Sort the array using the selection sort (which you will define in arrayListType.h) and count the number of loop iterations and the number of record moves. Print the sorted array, the number of loop iterations, and the number of record moves to the screen.
Do the same thing with the insertion and quick sort.
Note: You must start with the original unsorted array each time.
Next, add the merge sort algorithm to the class defined in the linkedQueueType.h file. Insert the same data from num.dat to your list object. In the same driver file where you tested the array-based sorting algorithms, now test your linked list sort function. You will again print the sorted list, the number of loop iterations, and the number of record moves. Refer to the textbooks description of merge sort to see what values you should get for the number of data elements stored in the list.
Make sure your program is properly documented and good programming standards are followed.
---------------------------------------------arrayListType.h------------------------------------------------------------
#ifndef H_arrayListType
#define H_arrayListType
//***********************************************************
// Author: D.S. Malik
//
// This class specifies the members to implement the basic
// properties of array-based lists.
//***********************************************************
#include
#include
using namespace std;
template
class arrayListType
{
public:
const arrayListType
(const arrayListType
//Overloads the assignment operator
bool isEmpty() const;
//Function to determine whether the list is empty
//Postcondition: Returns true if the list is empty;
// otherwise, returns false.
bool isFull() const;
//Function to determine whether the list is full.
//Postcondition: Returns true if the list is full;
// otherwise, returns false.
int listSize() const;
//Function to determine the number of elements in the list
//Postcondition: Returns the value of length.
int maxListSize() const;
//Function to determine the size of the list.
//Postcondition: Returns the value of maxSize.
void print() const;
//Function to output the elements of the list
//Postcondition: Elements of the list are output on the
// standard output device.
void clearList();
//Function to remove all the elements from the list.
//After this operation, the size of the list is zero.
//Postcondition: length = 0;
int seqSearch(const elemType& item) const;
//Function to search the list for a given item.
//Postcondition: If the item is found, returns the location
// in the array where the item is found; otherwise,
// returns -1.
void insert(const elemType& insertItem);
//Function to insert the item specified by the parameter
//insertItem at the end of the list. However, first the
//list is searched to see whether the item to be inserted
//is already in the list.
//Postcondition: list[length] = insertItem and length++
// If the item is already in the list or the list
// is full, an appropriate message is displayed.
arrayListType(int size = 100);
//constructor
//Creates an array of the size specified by the
//parameter size. The default array size is 100.
//Postcondition: The list points to the array, length = 0,
// and maxSize = size
arrayListType(const arrayListType
//copy constructor
~arrayListType();
//destructor
//Deallocates the memory occupied by the array.
private:
protected:
elemType *list; //array to hold the list elements
int length; //to store the length of the list
int maxSize; //to store the maximum size of the list
};
template
bool arrayListType
{
return (length == 0);
}
template
bool arrayListType
{
return (length == maxSize);
}
template
int arrayListType
{
return length;
}
template
int arrayListType
{
return maxSize;
}
template
void arrayListType
{
for (int i = 0; i < length; i++)
cout << list[i] << " ";
cout << endl;
}
template
void arrayListType
{
length = 0;
}
template
int arrayListType
{
int loc;
bool found = false;
for (loc = 0; loc < length; loc++)
if (list[loc] == item)
{
found = true;
break;
}
if (found)
return loc;
else
return -1;
} //end seqSearch
template
void arrayListType
{
int loc;
if (length == 0) //list is empty
list[length++] = insertItem; //insert the item and increment the length
else if (length == maxSize)
cerr << "Cannot insert in a full list." << endl;
else
{
loc = seqSearch(insertItem);
if (loc == -1) //the item to be inserted does not exist in the list
list[length++] = insertItem;
else
cerr << "the item to be inserted is already in "
<< "the list. No duplicates are allowed." << endl;
}
} //end insert
template
arrayListType
{
if (size < 0)
{
cerr << "The array size must be positive. Creating "
<< "an array of size 100. " << endl;
maxSize = 100;
}
else
maxSize = size;
length = 0;
list = new elemType[maxSize];
assert(list != NULL);
}
template
arrayListType
{
delete [] list;
}
//copy constructor
template
arrayListType
(const arrayListType
{
maxSize = otherList.maxSize;
length = otherList.length;
list = new elemType[maxSize]; //create the array
assert(list != NULL); //terminate if unable to allocate memory space
for (int j = 0; j < length; j++) //copy otherList
list [j] = otherList.list[j];
}
// overloading assignment operator (equals sign)
template
const arrayListType
(const arrayListType
{
if (this != &otherList) //avoid self-assignment
{
delete [] list;
list = new elemType[maxSize]; //create the array
assert(list != NULL); //if unable to allocate memory space, terminate the program
for (int i = 0; i < length; i++)
list[i] = otherList.list[i];
}
return *this;
}
#endif
---------------------------------------------------------------linkedQueueType.h------------------------------------------------------
//Header file linkedQueue.h
#ifndef NodeType
#define NodeType
//Definition of the node
template
struct nodeType
{
Type info;
nodeType
};
#endif
#ifndef H_linkedQueue
#define H_linkedQueue
#include
#include
using namespace std;
//*************************************************************
// Author: D.S. Malik
//
// This class specifies the basic operations on a queue as a
// linked list.
//*************************************************************
template
class linkedQueueType
{
public:
const linkedQueueType
(const linkedQueueType
//Overload the assignment operator.
bool isEmptyQueue() const;
//Function to determine whether the queue is empty.
//Postcondition: Returns true if the queue is empty,
// otherwise returns false.
bool isFullQueue() const;
//Function to determine whether the queue is full.
//Postcondition: Returns true if the queue is full,
// otherwise returns false.
void initializeQueue();
//Function to initialize the queue to an empty state.
//Postcondition: queueFront = NULL; queueRear = NULL
Type front() const;
//Function to return the first element of the queue.
//Precondition: The queue exists and is not empty.
//Postcondition: If the queue is empty, the program
// terminates; otherwise, the first element of the
// queue is returned.
Type back() const;
//Function to return the last element of the queue.
//Precondition: The queue exists and is not empty.
//Postcondition: If the queue is empty, the program
// terminates; otherwise, the last element of the
// queue is returned.
void addQueue(const Type& queueElement);
//Function to add queueElement to the queue.
//Precondition: The queue exists and is not full.
//Postcondition: The queue is changed and queueElement is
// added to the queue.
void deleteQueue();
//Function to remove the first element of the queue.
//Precondition: The queue exists and is not empty.
//Postcondition: The queue is changed and the first element
// is removed from the queue.
void copyQueue(const linkedQueueType
void printQueue() const;
// Output the content of the queue to the screen
linkedQueueType();
//Default constructor
linkedQueueType(const linkedQueueType
//Copy constructor
~linkedQueueType();
//Destructor
private:
nodeType
nodeType
};
//Default constructor
template
linkedQueueType
{
queueFront = NULL; //set front to null
queueRear = NULL; //set rear to null
} //end default constructor
template
bool linkedQueueType
{
return(queueFront == NULL);
} //end isEmptyQueue
template
bool linkedQueueType
{
return false;
} //end isFullQueue
template
void linkedQueueType
{
nodeType
//while there are elements left in the queue
while (queueFront != NULL)
{
//set temp to point to the current node
temp = queueFront;
//advance first to the next node
queueFront = queueFront->link;
//deallocate memory occupied by temp
delete temp;
}
queueRear = NULL; //set rear to NULL
} //end initializeQueue
template
void linkedQueueType
{
nodeType
newNode = new nodeType
newNode->info = newElement; //store the info
newNode->link = NULL; //initialize the link field to NULL
if (queueFront == NULL) //if initially the queue is empty
{
queueFront = newNode;
queueRear = newNode;
}
else //add newNode at the end
{
queueRear->link = newNode;
queueRear = queueRear->link;
}
}//end addQueue
template
Type linkedQueueType
{
assert(queueFront != NULL);
return queueFront->info;
} //end front
template
Type linkedQueueType
{
assert(queueRear!= NULL);
return queueRear->info;
} //end back
template
void linkedQueueType
{
nodeType
if (!isEmptyQueue())
{
temp = queueFront; //make temp point to the first node
queueFront = queueFront->link; //advance queueFront
delete temp; //delete the first node
if (queueFront == NULL) //if after deletion the queue is empty
queueRear = NULL; //set queueRear to NULL
}
else
cout << "Cannot remove from an empty queue" << endl;
}//end deleteQueue
//Destructor
template
linkedQueueType
{
initializeQueue();
} //end destructor
template
void linkedQueueType
{
nodeType
if (queueFront != NULL) //if queue is nonempty, make it empty
initializeQueue();
if (otherQueue.queueFront == NULL)
queueFront = NULL;
else
{
//set current to point to the queue to be copied
current = otherQueue.queueFront;
queueFront = new nodeType
queueFront->info = current->info; //copy the info
queueFront->link = NULL; //set the link field of the node to NULL
last = queueFront; //set last to point to the node
current = current->link; //set current to point to the next node
//copy the remaining queue
while (current != NULL) {
newNode = new nodeType
newNode->info = current->info;
newNode->link = NULL;
last->link = newNode;
last = newNode;
current = current->link;
}//end while
queueRear = last;
}//end else
}
template
void linkedQueueType
nodeType
temp = queueFront;
while(temp != NULL) {
cout << temp->info << " ";
temp = temp->link;
}
}
template
const linkedQueueType
(const linkedQueueType
{
if (this != &otherQueue) //avoid self-copy
copyQueue(otherQueue);
return *this;
} //end assignment operator
//copy constructor
template
linkedQueueType
{
queueFront = NULL;
copyQueue(otherQueue);
} //end copy constructor
#endif
----------------------------------------------------num.dat----------------------------------------------------------------------------
735 341 646 229 842 620 741 222 165 182 943 150 250 350 228 344 828 110 987 777 191 545 878 900 351 291 854 404 607 305 199 395 809 504 841 149 492 613 386 929 481 853 729 205 482 774 338 194 743 108
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
Database Support For Data Mining Applications Discovering Knowledge With Inductive Queries Lnai 2682
Authors: Rosa Meo ,Pier L. Lanzi ,Mika Klemettinen
2004th Edition
3540224793, 978-3540224792
