Dynamic Array and Linked List
Create a dynamic array ADT and a singly linked list ADT.
This project will include the following five files:
- h: declare a class VectorADT to manage a dynamic array of doubles
- cpp: implement VectorADT’s member and non-member functions as declared in VectorADT.h
- h: declare a class ListADT to manage a linked list of integers
- cpp: implement ListADT’s member and non-member functions as declared in ListADT.h
- cpp: test the above member and non-member functions.
VectorADT.hDeclare a class of the name VectorADT to manage a dynamic array of doubles. Specifically, include the following data members:double * array;
int size; //the number of doubles stored in array
int capacity; //the maximum number of doubles that can be stored in arrayThe definition of size and capacity are similar to those used in the vector STL. Refer to this page for more information about size. Refer to this page for more information about capacity .
- The interface of VectorADT is required to include the following functions:
- a default constructor to initialize the data members as follows: 0–>size, 10->capacity, and allocating a space of 10 doubles to array (of course). Don’t forget to initialize each element on array to 0.00.the “big-3”: destructor, copy constructor and overloaded assignment operatorvoid push_back(intval ); This member function inserts the value ‘val’ to the end of the dynamic arrayvoid resize(intnewSize); This member function Resizes the container so that it contains newSize elements. If newSize is smaller than the current container size, the content is reduced to its first newSize elements. You don’t have to reduce the capacity in this case. If newSize is greater than the current container size, the content is expanded by inserting at the end as many elements as needed to reach a size of newSize. You are required to initialize all the new elements to 0.00. If newSize is also greater than the current container capacity, make sure you increase the capacity to 2*newSize, i.e., double the value of newSize. For example, if the current value of capacity is 100 and newSize is 150, your program is going to reallocate memory to increase the capacity of array to 300.
- voidpop_back(); This member function deletes the last number from the array, i.e., it decreases the size of the container by 1.
- Overload the operator[ ] as a read-only member function to return the i-th element in array. Assume v1 is a VectorADT object, this operator allows one to retrieve the i-th element on array if i is valid using the statement v1[ i ];.
- Overload the addition operator (operator+) as a member function to add two VectorADT objects, say v1 and v2 if they are of the same size. This member function is not allowed to change either of its two operands. It returns a VectorADT object corresponding to the sum of v1 and v2. With this operator, one can add v1 and v2 as follows: v3 = v1+v2;
- Overload the put operator (i.e., operator<<) as a friend function to print out all the elements stored in a VectorADT object. For example, assume the VectorADT object v1 contains the following numbers 1.10, 21.12, -0.81. One can write cout<
3. ListADT.h
Declare a class of the name ListADT to manage a singly linked list of integers. Specifically, include the following data members:
class Node {
public:
Node(){ };
//implement this default constructor as an inline function using an initialization section. 0->value, nullptr->next
Node(intval) { } ;
//implement this constructor as an inline function using an initialization section. val->value, nullptr->next
int value;
Node *next
};
Node *head; //point to the first node on the linked list
int size; //number of nodes on the linked list
The interface of ListADT is required to include the following functions:
a default constructor to initialize the linked list: 0->size, nullptr->head
the “big-3”: destructor, copy constructor and overloaded assignment operator
voidpush_back(intval ); This member function inserts the value ‘val’ to the end of the linked list.
voidpush_front(intval); This member function inserts the value ‘val’ to the front of the linked list.
voidpop_back(); This member function deletes the last number from the linked list.
voidpop_front(); This member function deletes the first number from the linked list.
Overload the operator[ ] as a read-only member function to return the i-th element on the linked list. Assume list1 is a ListADT object, this operator allows one to retrieve the i-th element on the list if i is valid using the statement list1[ i ];. Note that this operator is not included in the STL list. We include it here to showcase how flexible operator overloading can be.
an overloaded put operator (i.e., operator<<) as a friend to print out all the data items on the linked list as a comma-separated list. For example, if a list l1 contains the following list of numbers 2->4->-1->10. The statement cout<
ListADT.cppThis program file implements the above list of functions declared in ListrADT.h5. testVectorList.cpp:Include the main() function in this program file to test all the functions you have implemented in this project.Solution
ListADT.cpp
/*
* ListADT.cpp
*
* Created on: Nov 18, 2017
* Author: Tan Nguyen
*/
#include “ListADT.h”
Node::Node()
{
value = 0;
next = NULL;
}
Node::Node(intval)
{
value = val;
next = NULL;
}
Node::Node(intval, Node* nextNode)
{
value = val;
next = nextNode;
}
Node::~Node()
{
}
ListADT::ListADT() :
size(0), head(NULL)
{
}
ListADT::ListADT(constListADT& that)
{
if (that.head == NULL)
{
head = NULL;
size = 0;
} else
{
head = new Node();
head->value = that.head->value;
Node *pNewNode = head;
Node *pOldNode = that.head->next;
while (pOldNode != NULL)
{
pNewNode->next = new Node();
pNewNode = pNewNode->next;
pNewNode->value = pOldNode->value;
pOldNode = pOldNode->next;
}
pNewNode->next = NULL;
size = that.size;
}
}
ListADT::~ListADT()
{
Node *p = head;
// Traverse the list deleting nodes
while (p != NULL)
{
head = head->next;
delete p;
p = head;
}
head = NULL;
size = 0;
}
intListADT::length() const
{
return size;
}
voidListADT::operator =(constListADT& that)
{
if (that.head == NULL)
{
head = NULL;
size = 0;
} else
{
head = new Node();
head->value = that.head->value;
Node *pNewNode = head;
Node *pOldNode = that.head->next;
while (pOldNode != NULL)
{
pNewNode->next = new Node();
pNewNode = pNewNode->next;
pNewNode->value = pOldNode->value;
pOldNode = pOldNode->next;
}
pNewNode->next = NULL;
size = that.size;
}
}
voidListADT::push_back(intval)
{
Node *newNode = new Node(val);
//Check if is empty
if (head == NULL)
{
head = newNode;
} else
{
Node* p = head;
// Move to end of list
while (p->next != NULL)
{
p = p->next;
}
p->next = newNode;
}
size++;
}
voidListADT::push_front(intval)
{
Node *newNode = new Node(val);
newNode->next = head;
head = newNode;
size++;
}
voidListADT::pop_back()
{
Node *p = head;
Node *previourNode;
if (head == NULL)
{
return;
} else
{
while (p->next != NULL)
{
previourNode = p;
p = p->next;
}
if (previourNode != NULL && p != NULL)
{
previourNode->next = NULL;
delete p;
size–;
}
}
}
voidListADT::pop_front()
{
Node *p = head;
if (head == NULL)
{
return;
} else
{
head = head->next;
delete p;
size–;
}
}
voidListADT::removeAll()
{
Node *p = head;
// Traverse the list deleting nodes
while (p != NULL)
{
head = head->next;
delete p;
p = head;
}
head = NULL;
size = 0;
}
intListADT::operator [](constint&index)
{
int count = 0;
Node *p = head;
if (index > size)
{
return -999; // Invalid value
} else
{
while (count != index && p != NULL)
{
p = p->next;
count++;
}
if (p != NULL)
return p->value;
else
return -9999; // Invalid value
}
}
std::ostream& operator<<(std::ostream& out, constListADT& that)
{
Node *p = that.head;
out<< “[“;
while (p != NULL)
{
cout<< p->value;
p = p->next;
if (p != NULL)
out<< “, “;
}
out << “]”;
return out;
}
ListADT.h
/*
* ListADT.h
*
* Created on: Nov 18, 2017
*/
#ifndef LISTADT_H_
#define LISTADT_H_
#include
using namespace std;
class Node
{
public:
Node();
//implement this default constructor as an inline function using an initialization section. 0->value, nullptr->next
Node(intval);
//implement this constructor as an inline function using an initialization section. val->value, nullptr->next
Node(intval, Node* nextNode);
int value;
Node *next;
~Node();
};
classListADT
{
public:
ListADT(); //default constructor
//big 3
ListADT(constListADT& that); // 1. copy constructor
void operator=(constListADT& that); // 2. copy assignment operator
~ListADT(); // 3. destructor
int length() const;
voidpush_back(intval); //This member function inserts the value ‘val’ to the end of the linked list.
voidpush_front(intval); //This member function inserts the value ‘val’ to the front of the linked list.
voidpop_back(); //This member function deletes the last number from the linked list.
voidpop_front(); //This member function deletes the first number from the linked list.
voidremoveAll(); // Remove all node
int operator[](constint& index); // Overload the operator[ ] as a read-only member function to return the i-th element on the linked list
friendstd::ostream& operator<<(std::ostream& out, constListADT& that);
private:
int size; //number of nodes on the linked list
Node *head; //point to the first node on the linked list
};
#endif /* LISTADT_H_ */
testVectorList.cpp
/*
* testVectorList.cpp
*
* Created on: Nov 18, 2017
*/
#include “VectorADT.h”
#include “ListADT.h”
#include
using namespace std;
int main()
{
cout<< “==============TEST VECTORADT===================” <
VectorADT a;
cout<< “printing empty vector” <
//test assignment overload
cout<< a <
//test isEmpty()
cout<< “testing if vector is empty” <
a.isEmpty();
//test push_back
cout<< “push_back” <
a.push_back(2);
a.push_back(27);
a.push_back(5);
a.push_back(4);
a.push_back(73);
a.push_back(6);
a.push_back(7);
a.push_back(73);
a.push_back(6);
a.push_back(7);
a.push_back(73);
a.push_back(6);
cout<< a <
cout<< “testing if vector is empty” <
a.isEmpty();
//test erase() for index
cout<< “a.erase(0, 0)” <
a.erase(0, 0);
cout<< a <
//test erase for range
cout<< “a.erase(2,4)” <
a.erase(2, 4);
cout<< a <
//test insert() at position
cout<< “a.insert(1,16)” <
a.insert(1, 16);
cout<< a <
//test pop_back()
cout<< “a.pop_back()” <
a.pop_back();
cout<< a <
//test shrink_to_fit()
cout<< “before shrink_to_fit the capacity is ” <
a.shrink_to_fit();
cout<< “after shrink_to_fit the capacity is ” <
//test relength()
a.resize(10);
cout<< “after a.resize(10); the capacity is ” <
VectorADT b, c, d;
b.push_back(3);
b.push_back(5);
b.push_back(7);
c.push_back(1);
c.push_back(2);
c.push_back(3);
cout<< “Vector b: ” <
cout<< b <
cout<< “Vector c: ” <
cout<< c <
d = b + c;
cout<< “Vector d = b + c” << ” capacity is: ” <
cout<< d <
cout<< “Test resize vectorADT.” <
cout<< “Current d vector size: ” <
cout<< d <
cout<< “Change size of d to 2” <
d.resize(2);
cout<< “Current d vector size: ” <
cout<< d <
cout<< “Change size of d to 15” <
d.resize(15);
cout<< “Current d vector size: ” <
cout<< d <
cout<< “===============TEST ListADT=====================” <
ListADT l;
cout<< “print empty list” <
cout<< l <
// Test push_back
l.push_back(4);
l.push_back(5);
cout<< “test push_back” <
cout<< l <
l.push_front(6);
l.push_front(7);
cout<< “test push_front” <
cout<< l <
l.pop_back();
cout<< “test pop_back” <
cout<< l <
l.pop_front();
cout<< “test pop_front” <
cout<< l <
cout<< “test operator[]. listADT[1] ” << l[1] <
return 0;
}
VectorADT.cpp
/*
* VectorADT.cpp
*
* Created on: Nov 18, 2017
*/
#include “VectorADT.h”
#include
using namespace std;
VectorADT::VectorADT() :
capacity(10), size(0)
{
array = new double[capacity];
for(int i = 0; i < capacity; ++i)
array[i] = 0;
}
//big 3
//1. copy constructor
VectorADT::VectorADT(constVectorADT& that) :
capacity(that.capacity), size(that.size)
{
array = new double[capacity];
for (int i = 0; i < size; i++)
array[i] = that.array[i];
}
//2. copy assignment operator
voidVectorADT::operator=(constVectorADT& that)
{
capacity = that.capacity;
size = that.size;
array = new double[capacity];
for (int i = 0; i < size; i++)
array[i] = that.array[i];
}
//3. destructor
VectorADT::~VectorADT()
{
if (array != NULL)
{
delete[] array;
array = NULL;
size = 0;
capacity = 0;
}
}
//the “capacity” function: Returns the number of elements that the vector could store without allocating more storage.
intVectorADT::curr_capacity() const
{
return capacity;
}
//the “empty” function: Tests if the vector container is empty.
boolVectorADT::isEmpty()
{
if (size == 0)
{
cout<< “the vector is empty\n\n”;
return true;
} else
{
cout<< “the vector is not empty\n\n”;
return false;
}
}
//the “erase” function: Removes an element or a range of elements in a vector from the specified positions.
voidVectorADT::erase(int first, int last)
{
double *temp = new double[capacity];
if (first == last)
{ //if range is only one element
//set elements of temp[] to ptr[]
for (int i = 0; i < first; i++)
temp[i] = array[i];
for (int i = first; i < size – 1; i++)
temp[i] = array[i + 1];
delete[] array;
array = temp;
size–;
} else
{ //handle range with multiple elements
//set elements of temp[] to ptr[]
for (int i = 0; i < first; i++)
temp[i] = array[i];
for (int i = first; i < size – last + first; i++)
temp[i] = array[i + last – first];
delete[] array;
array = temp;
size = size – last + first;
}
}
//the “insert” function: Inserts an element or a number of elements into the vector at a specified position.
voidVectorADT::insert(int first, double r)
{
double *temp;
if (capacity > size)
temp = new double[capacity];
else
{
temp = new double[capacity + 1];
capacity++;
}
for (int i = 0; i < first; i++) //first set elements of temp[] to ptr[]
temp[i] = array[i];
temp[first] = r;
for (int i = first; i < size; i++) //second set elements of temp[] to ptr[]
temp[i + 1] = array[i];
delete[] array;
array = temp;
size++;
}
//the “pop_back” function: Deletes the element at the end of the vector.
voidVectorADT::pop_back()
{
if (size > 0)
size–;
else
size = 0;
}
//the “push_back” function”: Adds an element to the end of the vector.
voidVectorADT::push_back(double r)
{
if (capacity == 0)
{
array = new double[1];
array[0] = r;
size++;
capacity++;
} else if (capacity > size)
{ //increase the size by one and add one more value to ptr[] if there is enough capacity
array[size] = r;
size++;
} else
{
double *temp = NULL;
try
{
temp = new double[capacity + 1];
} catch (bad_alloc& e)
{
cerr<< “VectorADTpush_back: ” <
}
for (int i = 0; i < size; i++)
temp[i] = array[i];
temp[size] = r;
delete[] array;
array = temp;
size++;
capacity++;
}
}
//the “resize” function: Specifies a new size for a vector. The new size can be smaller or larger than the old size.
voidVectorADT::resize(intnewSize)
{
if (newSize<= size)
size = newSize;
else
{
if (newSize<= capacity)
{
double *temp = new double[newSize];
for (int i = 0; i < size; i++)
temp[i] = array[i]; //set elements of temp[] to ptr[]
for (int i = size; i
temp[i] = 0;
delete[] array;
array = temp;
} else
{
capacity = 2 * newSize;
double *temp = new double[newSize];
for (int i = 0; i < size; i++)
temp[i] = array[i]; //set elements of temp[] to ptr[]
for (int i = size; i
temp[i] = 0;
delete[] array;
array = temp;
}
size = newSize;
}
}
//the “shrink_to_fit” function: Discards excess capacity.
voidVectorADT::shrink_to_fit()
{
if (capacity > size)
{
double *temp = new double[size];
for (int i = 0; i < size; i++)
temp[i] = array[i];
delete[] array;
array = temp;
capacity = size;
}
}
//the “size” function” Returns the number of elements stored in the vector.
intVectorADT::length() const
{
return size;
}
//the overloaded output operator (<<) to print out the elements in a vector.
ostream& operator<<(ostream& out, constVectorADT& that)
{
for (int i = 0; i
out<
return out;
}
double&VectorADT::operator[](constint& index)
{
return array[index];
}
VectorADTVectorADT::operator+(VectorADT v2)
{
VectorADT v3;
if (size == v2.length())
{
for (int i = 0; i < size; ++i)
v3.push_back(array[i] + v2[i]);
}
return v3;
}
VectorADT.h
/*
* VectorADT.h
*
* Created on: Nov 18, 2017
*/
#ifndef VECTORADT_H_
#define VECTORADT_H_
#include
//A Vector stores a list of elements:
classVectorADT
{
private:
int capacity; //the maximum number of doubles that can be stored in array
int size; //the number of doubles stored in array
double* array;
public:
VectorADT(); //default constructor
//big 3
VectorADT(constVectorADT& that); // 1. copy constructor
void operator=(constVectorADT& that); // 2. copy assignment operator
~VectorADT(); // 3. destructor
intcurr_capacity() const; //Returns the number of elements that the vector could store without allocating more storage.
boolisEmpty(); //the “empty” function: Tests if the vector container is empty.
void erase(int first, int last); //Removes element or range of elements in a vector from the specified positions.
void insert(int first, double r); //Inserts element or number of elements into the vector at a specified position.
voidpop_back(); //the “pop_back” function: Deletes the element at the end of the vector.
voidpush_back(double r); //the “push_back” function”: Adds an element to the end of the vector.
void resize(int size); //Specifies a new size for a vector. The new size can be smaller or larger than the old size.
voidshrink_to_fit(); //the “shrink_to_fit” function: Discards excess capacity.
int length() const; //the “size” function” Returns the number of elements stored in the vector.
double& operator[](constint& index);
VectorADT operator+(VectorADT v2);
friend std::ostream& operator<<(std::ostream& out, constVectorADT& that); //print out the elements in a vector.
};
#endif /* VECTORADT_H_ */
VectorADT.cppThis program file implements the above list of functions declared in VectorADT.h