First Part Design and implement a class representing a doubly linked list. The c
ID: 3743783 • Letter: F
Question
First Part Design and implement a class representing a doubly linked list. The class must have the following requirements 1. The linked list and the nodes must be implemented as a C++ templates 1. The list must be generic - it should not implement arithmetic/logic functions 2. It must include a destructor, a copy constructor and the overloaded operator- 3. It must include methods to insert at the front and at the back of the list 4. It must include a method to return the length of the list 5. It must provide an iterator-based interface for the user from front to back 6. It must include an iterator-based interface for the user from back to front Second Part The implementation of the class LargeInt will use a dynamic physical structure to store the individual digits of an integer, and will provide some basic I'O and arithmetic operations that can be performed on integers In particular, the class should include 1) 2) A default constructor An operator function to overload the operator + 3) An operator function to overload the operator- 4) An operator function to overload the operator a) Since the Largelnt class does not contain pointers, there is no need for a copy constructor or a destructor b) You can assume huge integers are only positive (or 0) c) Your implementation of the huge integer type must be encapsulated as a C++ class, aggregating a list object for the internal representation of the huge integer value. The huge integer type is not a list, nor does it make sense for it to be derived from a list using inheritance d) Aside from list nodes used only within an encapsulating list template, all data members of classes and templates must be private or protected. Friend operators are permissible, but the huge integer type should absolutely not be declared a friend of the list.Explanation / Answer
//main.cpp
#include "LargeInt.hpp"
#include <string>
#include <iostream>
using namespace std;
int main()
{
LargeInt x, y, z;
cout << "Enter an integer of your choice : ";
cin >> x;
cout << "Enter an integer of your choice : ";
cin >> y;
z = x+ y;
cout <<"The Sum of " << x << " by " << y << " is : " << z << endl;
z = x /y;
cout <<"The product of " << x << " by " << y << " is : " << z << endl;
cout <<"The remainder of " << x << " by " << y << " is : " << z << endl;
return 0;
}
---------------------------------------------------------------------------------------------------
//LargeInt.cpp
#include "LargeInt.hpp"
#include <iostream>
#include <string>
using namespace std;
//overloaded operator << prints out an array of an object backwards
ostream& operator << (ostream& out, LargeInt &other)
{
other.list.setIteratorLast();
while (!other.list.didIteratorFinish())
{
out << other.list.getIteratorInfo();
other.list.setIteratorBack();
}
return out;
}
//overloaded operator >> first takes in input as a string
//whose length determines the length of an array
istream& operator >> (istream& in, LargeInt &other)
{
//take a string as input
string str;
in >> str;
int item;
for (int i = 0; i != str.length(); i++)
{
item = (str.at(i) - '0');
other.list.insertItemFront(item);
}
return in;
}
//default constructor
LargeInt::LargeInt()
{
}
//overloaded operator + returns an object of LargeInt which
//represents the sum of self and parameter
LargeInt LargeInt :: operator + (LargeInt other)
{
LargeInt temp;
temp.list.initializeList();
int smallerL;
int sumLength;
if (list.getLength() > other.list.getLength())
{
sumLength = list.getLength();
smallerL = other.list.getLength();
}
else
{
sumLength = other.list.getLength();
smallerL = list.getLength();
}
temp.list.setLength(sumLength);
int s = 0;
list.setIteratorFirst();
other.list.setIteratorFirst();
for (int i = 0; i < sumLength; i++)
{
if (i < smallerL)
{
s += list.getIteratorInfo() + other.list.getIteratorInfo();
if(!list.didIteratorFinish())
list.setIteratorNext();
if(!other.list.didIteratorFinish())
other.list.setIteratorNext();
}
else
{
if (sumLength == list.getLength())
{
s += list.getIteratorInfo();
if (!list.didIteratorFinish())
list.setIteratorNext();
}
else
{
s += other.list.getIteratorInfo();
if (!other.list.didIteratorFinish())
other.list.setIteratorNext();
}
}
if (s > 9)
{
s = s -10;
temp.list.insertItemBack(s);
s = 1;
}
else
{
temp.list.insertItemBack(s);
s = 0;
}
}
if (s == 1)
{
temp.list.insertItemBack(1);
temp.list.setLength(sumLength + 1);
}
return temp;
}
LargeInt LargeInt::operator-(LargeInt other)
{
LargeInt temp;
temp.list.initializeList();
int sumLength = list.getLength() >= other.list.getLength() ? list.getLength() : other.list.getLength();
temp.list.setLength(sumLength);
int sign =1;;
if(((*this).isNegative() && !other.isNegative()) || (!(*this).isNegative() && other.isNegative())){
sign=-1;
}
else{
sign=1;
}
int s = 0;
int carry = 0;
int num1 = 0;
int num2 = 0;
bool otherBigger = false;
if (other > *this)
otherBigger = true;
if (*this == other)
{
temp.list.insertItemFront(0);
}
else
{
list.setIteratorFirst();
other.list.setIteratorFirst();
for (int i = 0; i < sumLength; i++)
{
if (!list.didIteratorFinish())
{
num1 = list.getIteratorInfo();
list.setIteratorNext();
}
if (!other.list.didIteratorFinish())
{
num2 = other.list.getIteratorInfo();
other.list.setIteratorNext();
}
if (!otherBigger)
{
s = num1 - (num2 + carry);
if (s<0)
{
s = (num1 + 10) - (num2 + carry);
carry = 1;
}
else {
carry = 0;
}
}
if (otherBigger)
{
s = num2 - (num1 + carry);
if (s<0)
{
s = (num2 + 10) - (num1 + carry);
carry = 1;
}
else
{
carry = 0;
}
}
if(otherBigger && i == sumLength-1){
temp.list.insertItemBack(s*(-1));
}
else{
if (s==0 && list.didIteratorFinish()) {
}
else{
temp.list.insertItemBack(s);
}
}
num1 = 0;
num2 = 0;
if (s == 0 && other.list.didIteratorFinish() && otherBigger)
{
temp.list.deleteLast();
temp.list.setIteratorLast();
s = temp.list.getIteratorInfo();
temp.list.deleteLast();
temp.list.setIteratorLast();
temp.list.insertItemBack(s*-1);
}
}
}
if (carry>0) {
temp.list.insertItemBack(carry);
}
return temp;
}
LargeInt LargeInt::operator %(LargeInt other){
while(*this>other || *this==other){
*this=*this-other;
}
return *this;
}
LargeInt LargeInt::operator/( LargeInt other){
LargeInt temp,temp1;
list.setIteratorLast();
if (other>*this) {
temp1.list.insertItemBack(0);
}
else{
while(!list.didIteratorFinish()){
temp.list.insertItemFront(list.getIteratorInfo());
if (temp>other || temp==other) {
int count=0;
while (temp==other || temp>other) {
temp=temp-other;
count++;
}
temp1.list.insertItemFront(count);
}
cout<<temp<<endl;
list.setIteratorBack();
}
}
return temp1;
}
LargeInt LargeInt::multiply(LargeInt value, const int num)
{
LargeInt temp2;
int carry = 0;
for (value.list.setIteratorFirst(); !value.list.didIteratorFinish(); value.list.setIteratorNext())
{
int sum = num*value.list.getIteratorInfo() + carry;
carry = sum / 10;
sum %= 10;
temp2.list.insertItemBack(sum);
}
if (carry>0)
{
temp2.list.insertItemBack(carry);
}
return temp2;
}
LargeInt LargeInt::operator*(LargeInt other)
{
LargeInt product,temp;
int count = 0;
int power = 0;
product = *this;
for (other.list.setIteratorFirst(); !other.list.didIteratorFinish();other.list.setIteratorNext())
{
temp = (multiply(*this, other.list.getIteratorInfo()));
power = count;
if (power > 0)
{
while (power != 0)
{
temp.list.insertItemFront(0);
power--;
}
}
count++;
if (count == 1)
{
product = temp;
}
else
{
product = product + temp;
}
}
return product;
}
bool LargeInt::isNegative(){
list.setIteratorLast();
return (list.getIteratorInfo()< 0 )? true:false;
}
LargeInt LargeInt :: operator= (LargeInt other)
{
if (this != &other)
{
list.initializeList();
other.list.setIteratorFirst();
while (!other.list.didIteratorFinish())
{
list.insertItemBack(other.list.getIteratorInfo());
other.list.setIteratorNext();
}
return *this;
}
else
{
cout << " parameter is the same as the calling object: ";
return other;
}
}
//overload the == operator
bool LargeInt :: operator == (LargeInt other)
{
if (list.getLength() == other.list.getLength())
{
list.setIteratorFirst();
other.list.setIteratorFirst();
while (!list.didIteratorFinish())
{
if (list.getIteratorInfo() != other.list.getIteratorInfo())
return false;
list.setIteratorNext();
other.list.setIteratorNext();
}
return true;
}
else return false;
}
bool LargeInt :: operator < (LargeInt other)
{
if (list.getLength() > other.list.getLength())
return false;
else
{
if (list.getLength() < other.list.getLength())
return true;
else
{
list.setIteratorLast();
other.list.setIteratorLast();
if (list.getIteratorInfo() < other.list.getIteratorInfo())
return true;
else
return false;
}
}
}
bool LargeInt :: operator > (LargeInt other)
{
if (list.getLength() < other.list.getLength())
return false;
else
{
if (list.getLength() > other.list.getLength())
return true;
else
{
list.setIteratorLast();
other.list.setIteratorLast();
if (list.getIteratorInfo() > other.list.getIteratorInfo())
return true;
else
return false;
}
}
}
---------------------------------------------------------------------------
//LargeInt.hpp
#include <iostream>
#include "DoublyLinkedList.cpp"
using namespace std;
#ifndef LargeInt_hpp
#define LargeInt_hpp
#include <stdio.h>
class LargeInt
{
friend ostream& operator << (ostream&, LargeInt&);
friend istream& operator >> (istream&, LargeInt&);
public:
LargeInt();
LargeInt operator + (LargeInt other);
LargeInt operator = (LargeInt other);
LargeInt operator - (LargeInt other);
LargeInt operator * (LargeInt other);
LargeInt multiply(LargeInt value, const int num);
LargeInt operator / (LargeInt);
LargeInt operator %(LargeInt);
bool operator == (LargeInt);
bool operator < (LargeInt other);
bool operator > (LargeInt other);
bool isNegative();
private:
DoublyLinkedList<int> list;
};
#endif /* LargeInt_hpp */
--------------------------------------------------------------------
//DoublyLinkedList.cpp
#include "DoublyLinkedList.hpp"
#include <iostream>
#include <string>
using namespace std;
//overloaded operator <<
template <class Type>
ostream& operator << (ostream& out, const DoublyLinkedList<Type>& other)
{ nodeType<Type>* current=other.first;
while (current != NULL)
{
out << current->info << ' ';
current = current->next;
}
return out;
}
//overloaded operator >>
template <class Type>
istream& operator >> (istream& in, DoublyLinkedList<Type> &other)
{
string s;
in >> s[0];
return in;
}
template <class Type>
DoublyLinkedList<Type>::DoublyLinkedList()
{
first = NULL;
last = NULL;
iterator = NULL;
length = 0;
}
template <class Type>
DoublyLinkedList <Type>::~DoublyLinkedList()
{
nodeType<Type> *current;
while (first != NULL)
{
current = first;
first = first->next;
delete current;
}
}
template <class Type>
DoublyLinkedList<Type>::DoublyLinkedList(const DoublyLinkedList<Type> & other)
{
max = other.max;
length = other.length;
first = new nodeType<Type>;
nodeType<Type> *q = other.first;
nodeType<Type> *p = first;
while (q != NULL)
{
p->info = q->info;
q = q->next;
if (q != NULL)
{
p->next = new nodeType<Type>;
p = p->next;
}
else
{
p->next = NULL;
last = p;
}
}
}
template <class Type>
void DoublyLinkedList<Type>::initializeList()
{
first = NULL;
last = NULL;
iterator = NULL;
length = 0;
}
template <class Type>
DoublyLinkedList<Type> DoublyLinkedList<Type>::operator = (const DoublyLinkedList<Type>& other)
{
if (this != &other)
{
if (other.isEmpty())
{
first = last = NULL;
length = 0;
max = 100;
}
else
{
first = new nodeType<Type>;
nodeType<Type> *p;
p = first;
nodeType<Type> *q = other.fiirst;
}
}
}
template <class Type>
bool DoublyLinkedList <Type> ::isEmpty()
{
return (first == NULL);
}
template <class Type>
int DoublyLinkedList <Type> :: getLength()
{
return length;
}
template <class Type>
void DoublyLinkedList <Type> ::setLength(int n)
{
length = n;
}
template <class Type>
void DoublyLinkedList <Type> :: insertItemBack(const Type& insertItem)
{
nodeType <Type> *newNode;
newNode = new nodeType<Type>;
newNode->info = insertItem;
newNode->next = NULL;
newNode->back = NULL;
if (first == NULL)
{
first = last = newNode;
}
else
{
last->next = newNode;
newNode->back = last;
last = newNode;
}
length++;
}
template <class Type>
void DoublyLinkedList <Type> ::insertItemFront(const Type& insertItem)
{
nodeType <Type> *newNode;
newNode = new nodeType<Type>;
newNode->info = insertItem;
newNode->next = NULL;
newNode->back = NULL;
if (first == NULL)
{
first = last = newNode;
first->back = NULL;
first->next = NULL;
}
else
{
newNode->next = first;
first->back = newNode;
first = newNode;
}
length++;
}
template <class Type>
void DoublyLinkedList <Type> ::printForward()
{
nodeType<Type> *current;
current = first;
while(current != NULL)
{
cout << current->info << ' ';
current = current->next;
}
}
template <class Type>
void DoublyLinkedList <Type> ::printBackward()
{
nodeType<Type> *current;
current = last;
while (current != NULL)
{
cout << current->info << ' ';
current = current->back;
}
}
template <class Type>
void DoublyLinkedList <Type> ::printForwardCallRec()
{
printForwardRec(first);
}
template <class Type>
void DoublyLinkedList <Type> ::printForwardRec(nodeType<Type> *p)
{
if (p != NULL)
{
cout << p->info << ' ';
printForwardRec(p->next);
}
}
template <class Type>
void DoublyLinkedList <Type> ::printBackwardCallRec()
{
printBackwardRec(first);
}
template <class Type>
void DoublyLinkedList<Type>::printBackwardRec(nodeType<Type> *p)
{
if (p != NULL)
{
printBackwardRec(p->next);
cout << p->info << ' ';
}
}
template <class Type>
void DoublyLinkedList<Type>::deleteLast()
{
if (!isEmpty())
{
if (first == last)
{
delete first;
first = last = NULL;
}
else
{
nodeType<Type> *temp = last;
last = last->back;
last->next = NULL;
delete temp;
}
length--;
}
}
template <class Type>
void DoublyLinkedList<Type>::deleteFirst()
{
if (!isEmpty())
{
nodeType<Type> *current = first;
first = first->next;
delete current;
}
}
template <class Type>
int DoublyLinkedList<Type>::getNumOfItem(Type item)
{
if (!isEmpty())
{
nodeType<Type> *current = first;
int count = 0;
while (current != NULL)
{
if (current->info == item)
count++;
current = current->next;
}
return count;
}
return 0;
}
template <class Type>
void DoublyLinkedList<Type>::replace_item(Type olditem, Type newitem)
{
if (!isEmpty())
{
nodeType<Type> *current = first;
while (current != NULL)
{
if (current->info == olditem)
current->info = newitem;
current = current->next;
}
}
}
template <class Type>
void DoublyLinkedList<Type>::call_replace_itemR(Type olditem, Type newitem)
{
if (!isEmpty())
replace_itemR(olditem, newitem, first);
}
template <class Type>
void DoublyLinkedList<Type>::replace_itemR(Type olditem, Type newitem, nodeType<Type> *¤t)
{
if (current != NULL)
{
if (current->info == olditem)
current->info = newitem;
replace_itemR(olditem, newitem, current->next);
}
}
template <class Type>
void DoublyLinkedList<Type>::setIteratorFirst()
{
iterator = first;
}
template <class Type>
void DoublyLinkedList<Type>::setIteratorLast()
{
iterator = last;
}
template <class Type>
Type DoublyLinkedList<Type>::getIteratorInfo()
{
return iterator->info;
}
template <class Type>
void DoublyLinkedList<Type>::setIteratorNext()
{
iterator = iterator->next;
}
template <class Type>
void DoublyLinkedList<Type>::setIteratorBack()
{
iterator = iterator->back;
}
template <class Type>
bool DoublyLinkedList<Type>::didIteratorFinish()
{
return (iterator == NULL);
}
template <class Type>
bool DoublyLinkedList<Type>::isNextNull()
{
if (iterator->next == NULL)
return true;
else
return false;
}
-----------------------------------------------------------------------------------
//DoublyLinkedList.hpp
#include <iostream>
using namespace std;
#ifndef DoublyLinkedList_hpp
#define DoublyLinkedList_hpp
#include <stdio.h>
template <class Type>
struct nodeType
{
Type info;
nodeType <Type> *next;
nodeType <Type> *back;
};
template <class Type>
class DoublyLinkedList
{
friend ostream& operator << (ostream& out, const DoublyLinkedList<Type> & other);
friend istream& operator >> (istream& in, DoublyLinkedList<Type> &other);
public:
//Constructor
DoublyLinkedList();
//Destructor
~DoublyLinkedList();
//Copy constructor
DoublyLinkedList(const DoublyLinkedList<Type>& other);
//Assignment operator
DoublyLinkedList operator= (const DoublyLinkedList<Type> & other);
//Doubly Linked initializer
void initializeList();
//Method to check doubly linked list is empty
bool isEmpty() ;
//Get the lengh of doubly linked list
int getLength();
//Sets the size of doubly linked list
void setLength(int n);
//
void insertItemFront(const Type&insertItem);
void insertItemBack(const Type& insertItem);
bool isNextNull();
void setIteratorFirst();
void setIteratorLast();
void setIteratorNext();
void setIteratorBack();
bool didIteratorFinish();
Type getIteratorInfo();
void printForward();
void printForwardCallRec();
void printForwardRec(nodeType<Type> *p);
void printBackward();
void printBackwardCallRec();
void printBackwardRec(nodeType<Type> *p);
void deleteLast();
void deleteFirst();
int getNumOfItem(Type item);
void replace_item(Type olditem, Type newitem);
void call_replace_itemR(Type olditem, Type newitem);
void replace_itemR(Type olditem, Type newitem, nodeType<Type> *¤t);
protected:
int length, max;
nodeType <Type> *first; // pointer to the first node
nodeType <Type> *last; // pointer to the last node
nodeType <Type> *iterator;
};
#endif /* DoublyLinkedList_hpp */
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.