Question: 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
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
this->maxSize = maxSize;
this->size = 0;
this->myList = new elemType[maxSize];
}
//This function is O(1)
template
bool ArrayList
if(size == 0)
return true;
return false;
}
C++
//This function is O(1)
template
bool ArrayList
if(size == maxSize)
return true;
return false;
}
//This function is O(1)
template
unsigned int ArrayList
return size;
}
//This function is O(1)
template
unsigned int ArrayList
return maxSize;
}
//This function is O(n)
template
void ArrayList
for(unsigned int i = 0; i
cout
}
cout
}
//This function is O(1)
template
bool ArrayList
if(position > size){
throw "Out of bounds.";
}
if(element == myList[position-1])
return true;
return false;
}
//This function is O(n)
template
void ArrayList
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
if (this->isFull()){
throw "List if full";
}
myList[size] = element;
size++;
}
//This function is O(n)
template
void ArrayList
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
if(position > size){
throw "Retrieving out of bounds.";
}
return myList[position-1];
}
//This function is O(1)
template
void ArrayList
if(position > size){
throw "Retrieving out of bounds.";
}
myList[position-1] = element;
}
//This function is O(1)
template
void ArrayList
size = 0;
}
//This function is O(n)
template
ArrayList
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
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
Node
};
//This function is O(1)
template
LinkedListList
myListHead = NULL;
size = 0;
}
//This function is O(1)
template
bool LinkedListList
if(size == 0)
return true;
return false;
}
//This function is O(1)
template
bool LinkedListList
return false;
}
//This function is O(1)
template
unsigned int LinkedListList
return size;
}
//This function is O(1)
template
unsigned int LinkedListList
return __INT_MAX__;
}
//This function is O(n)
template
void LinkedListList
Node
while(temp){
cout element
temp = temp->next;
}
cout
}
//This function is O(n)
template
bool LinkedListList
if(position > size){
throw "Out of bounds.";
}
Node
if(node->element == element)
return true;
return false;
}
//This function is O(n)
template
void LinkedListList
if (this->isFull()){
throw "List if full";
}
if(position > size+1){
throw "Inserting out of bounds.";
}
Node
newNode->element = element;
if(size > 1){
if(position == 1){
newNode->next = myListHead;
myListHead = newNode;
}
else{
Node
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
if (this->isFull()){
throw "List if full";
}
Node
newNode->element = element;
newNode->next = NULL;
if(size > 0){
Node
node->next = newNode;
}
else{
myListHead = newNode;
}
size++;
}
//This function is O(n)
template
void LinkedListList
if(position > size){
throw "Removing out of bounds.";
}
Node
Node
node->next = elemToDel->next;
delete elemToDel;
size--;
}
//This function is O(n)
template
elemType LinkedListList
if(position > size){
throw "Retrieving out of bounds.";
}
Node
return node->element;
}
//This function is O(n)
template
void LinkedListList
if(position > size){
throw "Retrieving out of bounds.";
}
Node
node->element = element;
}
//This function is O(n)
template
void LinkedListList
Node
while(temp){
Node
temp = temp->next;
delete elemToDel;
}
myListHead = NULL;
size = 0;
}
//This function is O(n)
template
LinkedListList
clearList();
Node
Node
while(temp){
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
clearList();
}
//This function is O(n)
template
Node
unsigned int i = 1;
Node
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
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help