Question

8.9 Coding lab #5: create a dynamic array ADT and a singly linked list ADT.

Honor Code

Your answers to this homework must be your own work.You are not allowed to share your solutions.You may not engage in any other activities that will dishonestly improve your results or dishonestly improve or damage the results of others.

Plagiarism

Plagiarism is when you copy words, ideas, or any other materials from another source without giving credit. Plagiarism is unacceptable in any academic environment.

The main goal of this coding project is to practice on and then fully grasp the following knowledge points in the context of ADT implementation: (This project will be graded for a total of 80 points.)

use separate files to separate a class's declaration from its implementationfully understand the necessity of including the big-3 member functions if a class includes a pointer-based dynamic data structurelearn to implement the big-3learn to overload different operatorslearn to implement read-only accessors and mutators for a classlearn to manipulate a singly linked list at both the node-level and list-level

This project will include the following five files:

VectorADT.h: declare a class VectorADT to manage a dynamic array of doublesVectorADT.cpp: implement VectorADT's member and non-member functions as declared in VectorADT.hListADT.h: declare a class ListADT to manage a linked list of integersListADT.cpp: implement ListADT's member and non-member functions as declared in ListADT.htestVectorList.cpp: test the above member and non-member functions.

1. VectorADT.h

Declare 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 array

The 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 (i.e., the public section) 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(double val ); This member function inserts the value 'val' to the end of the dynamic arrayvoid resize(int newSize); 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 capacityin 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.void pop_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 VectorADTobject, 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<<v1; to print out a comma-separated list of these three numbers on the screen.int length() const; This read-only member function returns the current size of the array (i.e., the number of doubles in the container).int curr_capacity() const; This read-only member function returns the current capacity of the array (i.e., the maximum number of doubles that can be stored in the container).

2. VectorADT.cpp

This program file implements the above list of functions declared in VectorADT.h

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(int val) { } ; //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->headthe "big-3": destructor, copy constructor and overloaded assignment operatorvoid push_back(int val ); This member function inserts the value 'val' to the end of the linked list.void push_front(int val); This member function inserts the value 'val' to the front of the linked list.void pop_back(); This member function deletes the last number from the linked list.void pop_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<<l1; will produce 2,4,-1,10 on the standard output.int length() const; This read-only member function returns the current size of the list container (i.e., the number of integers in the container).

4. ListADT.cpp

This program file implements the above list of functions declared in ListrADT.h

5. testVectorList.cpp:

Include the main() function in this program file to test all the functions you have implemented in this project.

Answer 1

Please let me know if you have any doubts or you want me to modify the code. And if you find this code useful then don't forget to rate my answer as thumps up. Thank you! :)

//main.cpp

#include "VectorADT.h"
#include "ListADT.h"
using namespace std;

int main()
{
    VectorADT emptyVector;

    cout << emptyVector;
    cout << "the capacity is " << emptyVector.curr_capacity() << "." << endl;

    emptyVector.push_back(5.6);
    cout << "the capacity is " << emptyVector.curr_capacity() << "." << endl;

    cout << emptyVector;
    ListADT emptyList;
    cout << emptyList;
    cout << "the capacity is " << emptyVector.curr_capacity() << "." << endl;
    emptyList.push_back(1);
    cout << "the capacity is " << emptyVector.curr_capacity() << "." << endl;
    emptyList.push_front(4);
    emptyList.push_front(2);
    cout << "the capacity is " << emptyVector.curr_capacity() << "." << endl;
    emptyList.pop_back();
    cout << "the capacity is " << emptyVector.curr_capacity() << "." << endl;
    emptyList.push_back(8);
    emptyList.pop_front();
    cout << "the capacity is " << emptyVector.curr_capacity() << "." << endl;

    return 0;
}
------------------------------------------------------------------------------------------------------------------------
//VectorADT.cpp
#include "VectorADT.h"

VectorADT::~VectorADT()
{
    delete[] array;
    array = nullptr;
}

VectorADT::VectorADT()
{
    size = 0;
    capacity = 0;
    this->resize(5);
    size = 0;
}

VectorADT::VectorADT(const int size, const int capacity)
{
    array = new double[capacity];
    if (array)
    {
        this->size = size;
        this->capacity = capacity;

        for (int i = 0; i < capacity; i++) {
            array[i] = 0.0;
        }
    }
}
VectorADT& VectorADT::operator= (const VectorADT & clone)
{
    array = new double[clone.capacity];
    if (array)
    {
        this->size = clone.size;
        this->capacity = clone.capacity;

        for (int i = 0; i < capacity; i++) {
            array[i] = clone.array[i];
        }
    }
    return *this;
}

VectorADT::VectorADT(const VectorADT & clone)
{
    array = new double[clone.capacity];
    if (array)
    {
        this->size = clone.size;
        this->capacity = clone.capacity;

        for (int i = 0; i < capacity; i++) {
            array[i] = clone.array[i];
        }
    }
}

void VectorADT::push_back(double val)
{
    if (size >= capacity)
    {
        resize(size + 1);
        array[size - 1] = val;
    }
    else
    {
        array[size++] = val;
    }
}

void VectorADT::resize(int newSize)
{
    if (newSize > capacity)
    {
        capacity = 2 * newSize;
        double *newarray = new double[capacity];
        if (newarray)
        {
            if (size)
            {
                for (int i = 0; i < size; i++)
                {
                    newarray[i] = array[i];
                }
                delete[] array;
            }
            for (int i = size; i < capacity; i++)
            {
                newarray[i] = 0.0;
            }
            array = newarray;
        }
    }
    size = newSize;
}

void VectorADT::pop_back()
{
    if (size > 0) {
        size--;
    }

}

double VectorADT::operator[](const int index) const
{
    double retVal = -1;
    if (index < size && index >= 0)
    {
        retVal = array[index];
    }
    return retVal;
}

VectorADT operator+(const VectorADT &rhs, const VectorADT &lhs)
{
    VectorADT sum;
    if (rhs.length() == lhs.length())
    {
        for (int i = 0; i < rhs.length(); i++)
        {
            double val1 = rhs[i];
            double val2 = lhs[i];
            sum.push_back(val1 + val2);
        }
    }
    return sum;

}

std::ostream& operator<< (std::ostream& stream, const VectorADT& rhs)
{
    if (rhs.length() == 0)
    {
        stream << "no values found " << endl;
    }
    else
    {
        for (int i = 0; i < rhs.length(); i++)
        {
            double val = rhs[i];
            if (i == rhs.length() - 1)
            {
                stream << val << '.' << endl;
            }
            else
            {
                stream << val << ', ';
            }
        }
    }
    return stream;
}

int VectorADT::length() const
{
    return size;
}

int VectorADT::curr_capacity() const
{
    return capacity;
}
--------------------------------------------------------------------------------------------------------------------------------
//VectorADT.h

#pragma once
#include <iostream>
#include <vector>
using namespace std;

class VectorADT
{
private:
    double * array;
    int size;
    int capacity;

public:
    ~VectorADT();
    VectorADT();
    VectorADT( const int size, const int capacity);
    VectorADT(const VectorADT & clone);
    VectorADT& operator= (const VectorADT & clone);

    void push_back(double val);

    void resize(int newSize);

    void pop_back();

    double operator[]( const int index) const;

    friend VectorADT operator+ ( const VectorADT &rhs, const VectorADT &lhs);

    friend std::ostream& operator<< (std::ostream& stream, const VectorADT& rhs);

    int length() const;

    int curr_capacity() const;

};
-----------------------------------------------------------------------------------------------------------------------------------

//ListADT.cpp

#include "ListADT.h"

ListADT::ListADT()
{
    size = 0;
    head = nullptr;
}

ListADT::ListADT(int val)
{
    head = new Node;
    head->data = val;
    head->next = nullptr;
    size = 1;
}

ListADT::ListADT(const ListADT& clone)
{
    size = 0;
    head = nullptr;
    if (clone.head)
    {
        Node *currentnode = clone.head;
        while (currentnode != nullptr)
        {
            push_back(currentnode->data);
            currentnode = currentnode->next;
        }
    }
}

ListADT& ListADT::operator= (const ListADT & clone)
{
    size = 0;
    head = nullptr;
    if (clone.head)
    {
        Node *currentnode = clone.head;
        while (currentnode != nullptr)
        {
            push_back(currentnode->data);
            currentnode = currentnode->next;
        }
    }
    return *this;
}

ListADT::~ListADT()
{
    struct Node* tempNode;
    while (head != NULL)
    {
        tempNode = head->next;
        delete head;
        head = tempNode;
    }
}

void ListADT::push_back(int val)
{
    Node *newNode = new Node;
    if (nullptr == newNode)
    {
        return;
    }
    newNode->data = val;
    newNode->next = nullptr;

    if (head == nullptr)
    {
        head = newNode;
    }
    else
    {
        Node *last = head;
        while (last->next != nullptr)
        {
            last = last->next;
        }
        last->next = newNode;
    }
    size++;
}

void ListADT::push_front(int val)
{
    Node *newNode = new Node;
    if (nullptr == newNode)
    {
        return;
    }
    newNode->data = val;
    newNode->next = nullptr;

    if (head == nullptr)
    {
        head = newNode;
    }
    else
    {
        newNode->next = head;
        head = newNode;
    }
    size++;
}

void ListADT::pop_back()
{
    if (head) {
        if (head->next == nullptr) {
            delete head;
            head = nullptr;
        }
        else
        {
            Node* prevnode = head;
            Node *currentnode = head->next;
            while (currentnode->next != nullptr)
            {
                prevnode = currentnode;
                currentnode = currentnode->next;
            }
            delete currentnode;
            prevnode->next = nullptr;
        }
        size--;
    }
}

void ListADT::pop_front()
{
    Node * toPop = head;
    if (head != nullptr)
    {
        head = head->next;
    }
    if (toPop)
    {
        delete toPop;
    }
    size--;
}

int ListADT::operator[](const int index)
{
    int retVal = -1;
    if (index < size && head)
    {
        Node *currentNode = head;
        for (int i = 0; i < index; i++)
        {
            currentNode = currentNode->next;
        }
        retVal = currentNode->data;
    }
    return retVal;
}

void ListADT::print(std::ostream& stream)
{
    if (head == nullptr)
    {
        stream << "The list is empty" << endl;
    }
    Node *currentNode = head;
    while (currentNode != nullptr)
    {
        if (currentNode != head)
        {
            stream << ',';
        }
        stream << currentNode->data << endl;
        currentNode = currentNode->next;
    }
    stream << endl;

}

std::ostream& operator << (std::ostream& stream, ListADT& list)
{
    list.print(stream);
    return stream;
}

int ListADT::length() const
{
    return size;
}
-----------------------------------------------------------------------------------------------------------------------
//ListADT.h
#pragma once
#include <iostream>
using namespace std;

class ListADT
{
private:
    struct Node
    {
        int data;
        Node* next;
    };
    int size;
    Node* head;

public:
    ~ListADT();

    ListADT();
    ListADT(const ListADT & clone);
    ListADT& operator= (const ListADT & clone);

    ListADT(int val);

    void push_back(int val);

    void push_front(int val);

    void pop_back();

    void pop_front();

    int operator[](const int index);

    void print(std::ostream& stream);
    friend std::ostream& operator<< (std::ostream& stream, ListADT& list);

    int length() const;
};