C++ linklist supercard

CMPS 1063 – Data Structures & ADTs Spring 2018 Program Assignment 5 100 points DUE: Wednesday, April 18, 2018

Purpose: To learn how to use dynamic memory allocation and a doubly-linked list.

Problem: In this assignment, you are to process super cardinals, that is big numbers. You will test methods

of the Supercard class, and then will find the 10’s complement of a number, sum two super cardinal

numbers, and print them out.

Method: Very large integer numbers cannot be stored in variables of type in or even long int. Certainly one

cannot perform arithmetic, e.g. addition, multiplication, etc., on very large numbers. For example, one

cannot compute 500! For this assignment, you will implement a class and methods to access the digits

in a super cardinal. Suppose the Supercard S = 81234. In your representation of S, the digits of S will

be stored in a doubly-linked list with the least significant digit first; that is, in reverse order. This is

pictured as follows:

Note the digits are stored backwards to make it easier to perform addition.

In addition to representing the digits of S, the representation will also keep track of four other pieces of

data.

 head, a pointer to the front of the list (the least significant digit of the number; remember the

digits are stored in reverse in the list)

 cursor, a pointer to some digit in the list

 length, which represents the number of digits in S.

 currentIndex, which is described as follows:

Let S = dndn-1..d2d1 where di is the ith digit of S. For example if S = 81234, then d1 = 4, d2 =3,

d3= 2, d4 =1, and d5 = 8. In the conceptual view of the double-linked list S could be

represented as 4 3 ↓ 2 1 8 with the cursor currently indicating 2, which is d3. In this case the

current index is 3. Current index is used to improve the efficiency of the implementation of the

getDigit and setDigit methods in the Supercard class. The need for this information arises from

the fact that getDigit and setDigit are conceptually “random access” operations for Supercard,

but the implementation of supercard, a double-linked list, is not a random access structure like

an array.

The type declaration for the representation of Supercard shown above are:

class Supercard

{ private:

int length; int currentIndex;

Node * head; Node * cursor; }

where Node is declared as a class inside Supercard as:

class Node

{ friend Supercard; int item; Node * prev;

4 3 2 1 8

length 5

index 3

head

cursor

Node *next; };

You will find a zipped project on D2L for this assignment. Unzip it. In the project, there are 3 files:

Supercard.h, Supercard.cpp, and TestSupercard.cpp (the main file). Print out the Supercard.h file and

study it – it specifies a list of methods for Supercard. There are also comments and some code in the

other files. You are to complete the implementation of Supercard and complete the implementation of

three functions in main: printSupercard, complement and addSupercards.

Keep the following ideas in mind when your implement the Supercard methods:

 The digits of Supercard are stored in a double-linked list, which means you can go forward and

backwards in the list. Use the cursor and current index to figure out which way to move

current index to get to the desired position. For example, if you need the 95th digit of a 100

digit number, you do not want to start with the 1st digit if the cursor is at the 85th digit. Likewise

you can retreat from the 100th digit to get to the 95th digit. You will be gaded on efficiency.

 A Supercard always has at least one node in it – it may be just 0.

 Comment out parts of the main program until you can the constructor, getLength and getDigits

and setDigits working.

 Then get printSuperCard to work.

 Get the methods swap and the destructor to work.

Finally, you must implement two other NON-MEMBER functions: tensComplement and

addSupercards.

The 10’s complement is easy, replace each digit with 10 – digit, so the 10’s complement of 84321 is

26789.

Adding two Supercards is done by adding corresponding digits starting with the least significant digits

with proper carry from previous digits. Think about how you added big numbers in the 3rd grade using

the usual paper-and-pencil method. The result of the addition is stored in another Supercard. The

function must accept as parameters two Supercards and it returns a Supercard with the digits for the

sum. Upon returning from the function, the program should print the result.

Input: None, you are running a test driver.

Output: Output is to a file.

Extra Credit (10 points)

Write the non-member function in the main program to print or addSupercards using recursion. (5

points each.)

Turn in: Printouts of all .h and .cpp files (3 of them)

Printout of the output file – turn this in EVEN if your output is incorrect!

Storage media containing all .h, .cpp files AND project files.

Everything in a big envelope

Academic misconduct statement.