Fraser International College CMPT XXXXXXXXXXAssignment 2 Dr. Yonas T. Weldeselassie Page 1
FIC - CMPT XXXXXXXXXXAssignment 2
Due Date and Time: Tuesday 15 March 2022 at 11:55PM PST
Instructor: Dr. Yonas T. Weldeselassie (Ph.D.)
In this assignment, we will be working with C++ classes to represent nodes of linked lists and linked list data
structure and then use the linked list class in order to store numeric information representation in unsigned
inary, sign and magnitude binary, and twos complement binary representations. For a detailed description of
the linked list data structure, please refer to the supplementary material posted on Moodle together with this
assignment.
Representing Linked Lists with C++ class
We may design a C++ class in order to represent a linked list. From our discussion in the supplementary
material, we observe that a linked list class requires only one member variable which is the head pointer and
then we could implement all the functions discussed in the supplementary material as member functions.
You are provided the following Node class declaration and definition as well as LinkedList class declaration.
The definitions of the member and friend functions of the LinkedList class are almost identical to the non
member functions discussed in the supplementary material. The only difference is that the head pointer
parameter of the non member functions discussed in the supplementary material is removed from these
member and friend functions because the head pointer is a member variable of the class and therefore each
of these member and friend functions has access to it and doesn't need it as a parameter.
#include
using namespace std;
class Node
{
typedef Node* NodePtr;
private:
int data;
NodePtr link;
public:
Node();
Node(const int &);
Node(const Node &);
int getData() const;
NodePtr getLink() const;
void setData(const int &);
void setLink(const NodePtr &);
friend ostream& operator
(ostream &, const Node &);
};
typedef Node* NodePtr;
Node::Node() : data(0), link(nullptr) {}
Node::Node(const int &d) : data(d), link(nullptr){}
Node::Node(const Node &n) : data(n.data), link(n.link){}
int Node::getData() const { return data; }
NodePtr Node::getLink() const { return link; }
void Node::setData(const int &d) { data = d; }
void Node::setLink(const NodePtr &p) { link = p; }
ostream& operator
(ostream& out, const Node& n)
{
out
n.data;
return out;
}
typedef Node* NodePtr;
Fraser International College CMPT XXXXXXXXXXAssignment 2 Dr. Yonas T. Weldeselassie Page 2
class LinkedList
{
private:
NodePtr head;
public:
LinkedList();
LinkedList(const LinkedList &);
copy constructor (deep copy)
~LinkedList();
destructor (must delete all the nodes from the heap)
LinkedList& operator= (const LinkedList &);
Assignment operator (deep copy)
int getLength() const;
eturn the number of nodes in the linked list
void head_insert(const int &);
NodePtr search_node(const int &) const;
void insert_after(const NodePtr &, const int &) const;
void remove_node(const NodePtr &);
void remove_node(const int &);
void remove_all(const int &);
void tail_insert(const int &);
void insert_before(const NodePtr &, const int &);
friend ostream& operator
(ostream&, const LinkedList &);
Assignment specific member functions
void flipBits() const;
void reverseBits() const;
LinkedList operator + (const LinkedList &) const;
void addOne() const;
int twosComplementToDecimal() const;
};
You are required to implement the LinkedList class as described in the supplementary material.
Restrictions and Requirements
ï‚· You are not allowed to add or remove any include directive, namespace, member function, or friend
function to the provided Node and LinkedList classes.
ï‚· You are not allowed to declare, define, or use any container variables (objects) such as static a
ays,
dynamic a
ays, or any STL container such as vectors in your LinkedList class definition.
ï‚· You are not allowed to use any STL algorithm in your LinkedList class definition.
The flipBits, reverseBits, operator +, addOne, and twosComplementToDecimal member functions
of the LinkedList class should be implemented as follows:
ï‚· flipBits:- A member function to flip the bits in the nodes of the calling object. Assume each node
data is a bit (0 or 1).
ï‚· reverseBits:- A member function to reverse the bits in the nodes of the calling object. Please note
that this is a constant function because it only needs to modify the data of each node without
modifying any member variable. Example: reverse of 11100 is 00111.
ï‚· operator +:- A member function to add the bits in the nodes of the calling object and the argument
object and return a LinkedList object whose nodes store the sum.
ï‚· addOne:- A member function to add 1 to the bits in the nodes of the calling object.
ï‚· twosComplementToDecimal:- A member function to compute and return the decimal value of the
its in the nodes of the calling object assuming twos complement representation.
Fraser International College CMPT XXXXXXXXXXAssignment 2 Dr. Yonas T. Weldeselassie Page 3
Information Representation using Linked Lists
Now consider the following test program that makes use of the LinkedList class in order to represent numeric
information in unsigned binary, sign and magnitude binary, and twos complement binary representations.
int selectComputation()
{
cout
"Select your computation"
endl;
cout
" 1. Unsigned Binary Representation Computation"
endl;
cout
" 2. Sign and Magnitude Representation Computation"
endl;
cout
" 3. Two's Complement Representation Computation"
endl;
cout
" 4. Exit Program"
endl;
int selection;
cout
"Enter your selection (1, 2, 3, or 4): ";
cin
selection;
while (selection != 1 && selection != 2 && selection != 3 && selection != 4)
{
cout
"Please enter a co
ect choice: ";
cin
selection;
}
return selection;
}
int main()
{
cout
"This program demonstrates the Linked List Data Structure in C++"
endl;
cout
"Linked Lists will be used for numeric information representation using"
endl;
cout
" *** Unsigned Binary Representation"
endl;
cout
" *** Sign and Magnitude Binary Representation"
endl;
cout
" *** Two's Complement Binary Representation"
endl
endl;
cout
"In addition, the program demonstrates"
endl;
cout
" *** Two's complement binary addition, and"
endl;
cout
" *** Conversion from two's complement to decimal."
endl
endl;
do
{
int selection = selectComputation();
if (selection == 1)
{
int bit_pattern_size, num;
cout
endl
"Enter a positive integer for the bit pattern size: ";
cin
bit_pattern_size;
while (bit_pattern_size <= 0)
{
cout
"You must enter a positive integer. Enter again please: ";
cin
bit_pattern_size;
}
cout
"Enter a non-negative integer: ";
cin
num;
while (num < 0)
{
cout
"You must enter a non-negative integer. Enter again please: ";
cin
num;
}
LinkedList LL = computeUnsignedBinary(num, bit_pattern_size);
cout
"The unsigned binary representation of "
num
" in "
it_pattern_size
" bit is "
LL
endl;
cout
endl;
}
else if (selection == 2)
{
int bit_pattern_size, num;
cout
endl
"Enter a positive integer for the bit pattern size: ";
cin
bit_pattern_size;
while (bit_pattern_size <= 0)
{
Fraser International College CMPT XXXXXXXXXXAssignment 2 Dr. Yonas T. Weldeselassie Page 4
cout
"You must enter a positive integer. Enter again please: ";
cin
bit_pattern_size;
}
cout
"Enter an integer: ";
cin
num;
LinkedList LL = computeSignAndMagnitudeBinary(num, bit_pattern_size);
cout
"The sign and magnitude binary representation of "
num
" in "
it_pattern_size
" bit is "
LL
endl;
cout
endl;
}
else if (selection == 3)
{
int bit_pattern_size, num1, num2;
cout
endl
"Enter a positive integer for the bit pattern size: ";
cin
bit_pattern_size;
while (bit_pattern_size <= 0)
{
cout
"You must enter a positive integer. Enter again please: ";
cin
bit_pattern_size;
}
cout
"Enter an integer: ";
cin
num1;
LinkedList LL1 = computeTwosComplementBinary(num1, bit_pattern_size);
cout
"The two's complement binary representation of "
num1
" in "
it_pattern_size
" bit is "
LL1
endl;
cout
endl;
cout
"Enter a second integer: ";
cin
num2;
LinkedList LL2 = computeTwosComplementBinary(num2, bit_pattern_size);
cout
"The two's complement binary representation of "
num2
" in "
it_pattern_size
" bit is "
LL2
endl;
cout
endl;
LinkedList LL3 = LL1 + LL2;
cout
"The binary sum of "
LL1
" and "
LL2
" is "
LL3
endl;
int sum = LL3.twosComplementToDecimal();
cout
"The integer value of the binary sum is "
sum
endl;
if (sum == num1 + num2)
cout
"This is a co
ect result."
endl;
else