Main.cpp

ArrayList.h (Lab3)

#ifndef ARRAYLISTT_H_

#define ARRAYLISTT_H_

#include

using namespace std;

template

class ArrayList{

public:

ArrayList(const unsigned int=1);

bool isEmpty() const; //Checks if list is empty

bool isFull() const; // Checks if list is full

unsigned int listSize() const; // Returns the size of the list

unsigned int maxListSize() const; // Returns the maximum possible size of the list

void print() const; // Prints the elements of the list on the console

bool isItemAtEqual(const unsigned int, const elemType &) const; // Checks if the item at position matches the 2nd parameter

void insertAt(const unsigned int, const elemType &); // Inserts 2nd parameter at position

void insertEnd(const elemType&); // Inserts object to end of the list

void removeAt(const unsigned int); // Removes object at position

elemType retreiveAt(const unsigned int) const; // Retrieves object at position

void replaceAt(const unsigned int, const elemType &); // Replaces object at position with 2nd parameter

void clearList(); // Empties the list

ArrayList &operator=(const ArrayList &);

virtual ~ArrayList();

private:

unsigned int size;

unsigned int maxSize;

elemType* myList;

};

template

ArrayList::ArrayList(const unsigned int maxSize) {

this->maxSize = maxSize;

this->size = 0;

this->myList = new elemType[maxSize];

}

//This function is O(1)

template

bool ArrayList::isEmpty() const {

if(size == 0)

return true;

return false;

}

C++

//This function is O(1)

template

bool ArrayList::isFull() const {

if(size == maxSize)

return true;

return false;

}

//This function is O(1)

template

unsigned int ArrayList::listSize() const {

return size;

}

//This function is O(1)

template

unsigned int ArrayList::maxListSize() const {

return maxSize;

}

//This function is O(n)

template

void ArrayList::print() const {

for(unsigned int i = 0; i

cout

}

cout

}

//This function is O(1)

template

bool ArrayList::isItemAtEqual(const unsigned int position, const elemType &element) const {

if(position > size){

throw "Out of bounds.";

}

if(element == myList[position-1])

return true;

return false;

}

//This function is O(n)

template

void ArrayList::insertAt(const unsigned int position, const elemType &element) {

if (this->isFull()){

throw "List if full";

}

if(position > size+1){

throw "Inserting out of bounds.";

}

for(unsigned int i = size; i > position-1; i--){

myList[i] = myList[i-1];

}

myList[position-1] = element;

size++;

}

//This function is O(1)

template

void ArrayList::insertEnd(const elemType &element) {

if (this->isFull()){

throw "List if full";

}

myList[size] = element;

size++;

}

//This function is O(n)

template

void ArrayList::removeAt(const unsigned int position) {

if(position > size){

throw "Removing out of bounds.";

}

for(unsigned int i = position-1; i

myList[i] = myList[i+1];

}

size--;

}

//This function is O(1)

template

elemType ArrayList::retreiveAt(const unsigned int position) const{

if(position > size){

throw "Retrieving out of bounds.";

}

return myList[position-1];

}

//This function is O(1)

template

void ArrayList::replaceAt(const unsigned int position, const elemType &element) {

if(position > size){

throw "Retrieving out of bounds.";

}

myList[position-1] = element;

}

//This function is O(1)

template

void ArrayList::clearList() {

size = 0;

}

//This function is O(n)

template

ArrayList& ArrayList::operator =(const ArrayList& constArrayList) {

if (constArrayList.maxListSize() > maxSize){

throw "Array too big to copy";

}

for(unsigned int i = 0; i

myList[i] = constArrayList.retreiveAt(i+1);

}

size = constArrayList.listSize();

return *this;

}

//This function is O(1)

template

inline ArrayList::~ArrayList() {

delete[] myList;

}

#endif /* ARRAYLISTT_H_ */

linkedListList.h(lab4)

* linkedListList.h

#ifndef LINKEDLISTLIST_H_

#define LINKEDLISTLIST_H_

#include

#include

using namespace std;

template

struct Node{

elemType element;

Node* next;

Node(){

next = NULL;

}

};

template

class LinkedListList{

public:

LinkedListList();

bool isEmpty() const; //Checks if list is empty

bool isFull() const; // Checks if list is full

unsigned int listSize() const; // Returns the size of the list

unsigned int maxListSize() const; // Returns the maximum possible size of the list

void print() const; // Prints the elements of the list on the console

bool isItemAtEqual(const unsigned int, const elemType &) const; // Checks if the item at position matches the 2nd parameter

void insertAt(const unsigned int, const elemType &); // Inserts 2nd parameter at position

void insertEnd(const elemType&); // Inserts object to end of the list

void removeAt(const unsigned int); // Removes object at position

elemType retreiveAt(const unsigned int) const; // Retrieves object at position

void replaceAt(const unsigned int, const elemType &); // Replaces object at position with 2nd parameter

void clearList(); // Empties the list

LinkedListList &operator=(const LinkedListList &);

virtual ~LinkedListList();

private:

unsigned int size;

Node* myListHead;

Node *getNodeAt(const unsigned int) const;

};

//This function is O(1)

template

LinkedListList::LinkedListList() {

myListHead = NULL;

size = 0;

}

//This function is O(1)

template

bool LinkedListList::isEmpty() const {

if(size == 0)

return true;

return false;

}

//This function is O(1)

template

bool LinkedListList::isFull() const {

return false;

}

//This function is O(1)

template

unsigned int LinkedListList::listSize() const {

return size;

}

//This function is O(1)

template

unsigned int LinkedListList::maxListSize() const {

return __INT_MAX__;

}

//This function is O(n)

template

void LinkedListList::print() const {

Node *temp = myListHead;

while(temp){

cout element

temp = temp->next;

}

cout

}

//This function is O(n)

template

bool LinkedListList::isItemAtEqual(const unsigned int position, const elemType &element) const {

if(position > size){

throw "Out of bounds.";

}

Node *node = getNodeAt(position);

if(node->element == element)

return true;

return false;

}

//This function is O(n)

template

void LinkedListList::insertAt(const unsigned int position, const elemType &element) {

if (this->isFull()){

throw "List if full";

}

if(position > size+1){

throw "Inserting out of bounds.";

}

Node *newNode = new Node;

newNode->element = element;

if(size > 1){

if(position == 1){

newNode->next = myListHead;

myListHead = newNode;

}

else{

Node *node = getNodeAt(position-1);

newNode->next = node->next;

node->next = newNode;

}

}

else{

myListHead = newNode;

}

size++;

}

//This function is O(n). Can be O(1) if tail is stored.

template

void LinkedListList::insertEnd(const elemType &element) {

if (this->isFull()){

throw "List if full";

}

Node *newNode = new Node;

newNode->element = element;

newNode->next = NULL;

if(size > 0){

Node *node = getNodeAt(size);

node->next = newNode;

}

else{

myListHead = newNode;

}

size++;

}

//This function is O(n)

template

void LinkedListList::removeAt(const unsigned int position) {

if(position > size){

throw "Removing out of bounds.";

}

Node *node = getNodeAt(position-1);

Node *elemToDel = node->next;

node->next = elemToDel->next;

delete elemToDel;

size--;

}

//This function is O(n)

template

elemType LinkedListList::retreiveAt(const unsigned int position) const{

if(position > size){

throw "Retrieving out of bounds.";

}

Node *node = getNodeAt(position);

return node->element;

}

//This function is O(n)

template

void LinkedListList::replaceAt(const unsigned int position, const elemType &element) {

if(position > size){

throw "Retrieving out of bounds.";

}

Node *node = getNodeAt(position);

node->element = element;

}

//This function is O(n)

template

void LinkedListList::clearList() {

Node *temp = myListHead;

while(temp){

Node *elemToDel = temp;

temp = temp->next;

delete elemToDel;

}

myListHead = NULL;

size = 0;

}

//This function is O(n)

template

LinkedListList& LinkedListList::operator =(const LinkedListList& constLLList) {

clearList();

Node* temp = constLLList.myListHead;

Node* temp_this = NULL;

while(temp){

Node* newNode = new Node;

newNode->element = temp->element;

if(temp_this == NULL){

myListHead = newNode;

}

else{

temp_this->next = newNode;

}

temp_this = newNode;

temp = temp->next;

}

size = constLLList.listSize();

return *this;

}

//This function is O(n)

template

LinkedListList::~LinkedListList() {

clearList();

}

//This function is O(n)

template

Node *LinkedListList::getNodeAt(const unsigned int position) const{

unsigned int i = 1;

Node *temp = myListHead;

while(i

assert(temp != NULL);

temp = temp->next;

i++;

}

return temp;

}

#endif /* LINKEDLISTLIST_H_ */

The main file Lab+10+-+Searching The user interface for your searching algorithms is provided in a file called main.cpp. The user selects what searching algorithm needs to be run and on what data structure. Your task in this lab is to be able to implement the searching algorithms. The data structures required for this assignment are arrays, sorted arrays, and linked lists. You may use arrays and linked lists from your previous assignments or use the solution to labs 3 and 4 that will be released on 11/06. Searching algorithms on unsorted arrays Implement sequential search on the arrayList data structure from Lab 3 as a member function called unsigned int seqSearchIter (elemType element) and unsigned int seqSearchRec (elenType element) that returns the index at which the element is present using iteration and recursion respectively Searching algorithms on sorted arrays Create a new template called sortedarrayList in a file called sortedarrayList.h with the functionalities as follows: Function bool isEmpty() const bool isFull() const int listSize() const int maxListize() const void print() bool insert(elenType) void remove(elentype) void clearList() Decide if you need to use any parameters Especially required if you use Checks if list is Checks if list is full Returns the size of the Returns the maximum possible size of the list Prints the elements of the list on the console Inserts an element into the sorted list Removes element from the Empties the list Implement binary search on the sortedarrayList data structure as a member function called unsigned int binarySearchlter (elemType element) and unsigned int binarySearchRec (elemType element) that returns the index at which the element is present using iteration and recursion respectively. Searching algorithms on linked lists Implement sequential search on the 1inkedListlist data structure from Lab 4 as a member function called bool seqSearchIter (elemType elenent) and bool seqSearchRec (elemType element) that returns true if the element is present in the array and false otherwise, using iteration and recursion respectively. The main file Lab+10+-+Searching The user interface for your searching algorithms is provided in a file called main.cpp. The user selects what searching algorithm needs to be run and on what data structure. Your task in this lab is to be able to implement the searching algorithms. The data structures required for this assignment are arrays, sorted arrays, and linked lists. You may use arrays and linked lists from your previous assignments or use the solution to labs 3 and 4 that will be released on 11/06. Searching algorithms on unsorted arrays Implement sequential search on the arrayList data structure from Lab 3 as a member function called unsigned int seqSearchIter (elemType element) and unsigned int seqSearchRec (elenType element) that returns the index at which the element is present using iteration and recursion respectively Searching algorithms on sorted arrays Create a new template called sortedarrayList in a file called sortedarrayList.h with the functionalities as follows: Function bool isEmpty() const bool isFull() const int listSize() const int maxListize() const void print() bool insert(elenType) void remove(elentype) void clearList() Decide if you need to use any parameters Especially required if you use Checks if list is Checks if list is full Returns the size of the Returns the maximum possible size of the list Prints the elements of the list on the console Inserts an element into the sorted list Removes element from the Empties the list Implement binary search on the sortedarrayList data structure as a member function called unsigned int binarySearchlter (elemType element) and unsigned int binarySearchRec (elemType element) that returns the index at which the element is present using iteration and recursion respectively. Searching algorithms on linked lists Implement sequential search on the 1inkedListlist data structure from Lab 4 as a member function called bool seqSearchIter (elemType elenent) and bool seqSearchRec (elemType element) that returns true if the element is present in the array and false otherwise, using iteration and recursion respectively