c++ programming Data structures and algorithm
Assg 03: Pointers and Dynamic Memory
COSC 2336 Data Structures
Objectives
• Practice using pointers and dynamically allocating memory
• Practice writing an Abstract Data Type using a class
Description
In C++ the largest int value is 2147483647. So, an integer larger than this cannot be stored and processed as an integer. Similarly if the sum or product of two positive integers is greater than 2147483647, the result will be incorrect.
One way to store and manipulate large integers is to store each individual digit of the number in an array. In this assignment, you will design a class named LargeInteger such that an object of this class can store an integer of any number of digits. Your abstract data type LargeInteger will support member functions to add() two LargeInteger objects together and return a new resulting LargeInteger object. You will only implement an unsigned integer, we will not worry about handling negative large integers in this as- signment. Likewise, subtraction and especially multiplication are a bit more complicated, and we will leave those operations for later. But in addition to the add() member function, you will implement several other member functions and constructors, that will be useful to implementing addition of the LargeInteger values.
For this assignment you need to perform the following tasks. You will be given 3 template files, and some of the LargeInteger class will already have been implemented for you (I will give you a simple constructor and the class destructor). You should implement the member functions, in this order, and uncomment the test code incrementally to test your functions as you implement them.
1
1. Implement a tostring() member function. This function will return a string representation of the LargeInteger. You should probably used <sstream> string streams to implement this function. Note that the digits of the large integer are stored in reverse of their display order, e.g. the 1’s place (100) is in index 0 of digits, the 10’s place (101) is in index 1, etc.
2. Implement a second constructor for the LargeInteger. This construc- tor will be used to construct a large integer from an array of digits. This constructor takes an int, which is the size of the array of digits, and an integer array as the second parameter. You will need to dy- namically allocate the space for the digitis in your constructor (see the given constructor for an example).
3. Implement a member function named maxDigits(). This function will take a reference to a LargeInteger as its only parameter. This function should return the number of digits in the larger LargeInteger comparing the passed in object to this object.
4. Implement a member function named digitAtPlace(). This function returns the digit of this large integer object at a particular digit in- dex. So this function takes an integer index as its input parameter, and returns an integer as its result. Again, if you ask for the digi- tAtPlace() index 0, this should return the 1’s place 100 digit of the integer. If asked for the digit at place 1, this should return the 10’s place 101 digit. If you ask for a digit place that is larger than the number of digits in the integer the member function should return 0. For example, if the integer represents 345, and you ask for the digit at place 3, then the function will return a 0. Likewise, if a negative index is given to this function, it should also return 0.
5. Implement a member function named appendDigit(). This functions takes an int digit as its only parameter. This will be a void function as it does not return any value result from calling it. The function is not something a normal user of the LargeInteger type is likely to need to do to an integer, but it will be very useful for our add function. This function appends the digit to become the new most significant digit of the LargeInteger object. For example, if the large integer object represents the value 345 and we ask it to appendDigit(7), then the new value of the object will be 7345. This function needs to manage memory to perform its task. You need to perform the following steps
2
1) allocate a new array of digits of numDigits+1 (e.g. enough space to hold one more digit). 2) copy the old digits to the new array of digits you created. 3) append the new passed in digit to the end of the array. Then 4) free up the old original array of digits, and make sure you class now uses the new array of allocated digits. Also, you might want to have this function ignore the append of a ’0’ digit (e.g. do not grow the large integer if trying to append a 0, as this does not need to be represented by the LargeInteger).
6. And finally, implement the add() member function. This function takes a reference to another LargeInteger object, and adds the digits of the other object to this object together.
Lets discuss the algorithm for the add() member function in more detail. This function will simply take a reference parameter of type LargeInteger as its one and only parameter. You need to perform the following steps in your add() member function:
1. Dynamically allocate a new array to hold the resulting sum of this and the other LargeInteger. Use the maxDigits() member function to determine the size needed for this new array. The size of the resulting sum will either be equal to the number of digits of the larger of the 2 numbers, or this value + 1 if there is a carry on the most significat sum. We handle needing to grow the result in the last step of the algorithm. For example if this large ineteger has the value 4537 (4 digits) and the other has the value of 23 (2 digits), the result will fit in 4 digits, which is what maxDigits() should return. Only if we have a carry would we need an extra digit. For example if this is 4537 and the other is 7242 the result of adding them together would be 11779, which needs 5 digits. But as mentioned, we will grow to accomodate a final carry in the last step of the algorithm.
2. Perform the addition, from least significant digit to most significant digit, handling carry as needed. Use the digitAtPlace() member function here, as this will determine if each number has a digit, or will return a 0 if you are beyond the size of each number. The resulting digits should be stored in the new array you allocated in step 1. Also make sure you keep track of the carry, and at the end, you should know if a 0 or 1 was carried from the addition of the last most significant digits.
3
3. Dynamically allocate a new LargeInteger() object, using the con- structor you created that takes an array as its parameter. You will pass in the array of new digits you summed up in step 2 and its size that you determined and dynamically allocated in step 1.
4. If there was a carry on the last most significant digit, use the append- Digit() member function to add the carry value as the new most sig- nificant digit to the new LargeInteger() you created in step 3. As mentioned above, you could also just have your appendDigit() func- tion ignore a request to append a ’0’ digit, thus in your add() you could always just call appendDigit() with the final carray, and the append would append or ignore as appropriate.
5. Finally the add() function should return a reference to the new LargeInteger() that contains the calculated sum you just computed and assigned to it.
In this assignment, you will be given 3 starting template files, named assg- 03.cpp, LargeInteger.cpp and LargeInteger.hpp. This is our first example of breaking code up into multiple files. You should add the function prototypes to the class declaration in the LargeInteger.hpp file, and implement the class member functions asked for in the LargeInteger.cpp file. You should not add any code to the assg-03.cpp file, only remove the comments to perform the tests shown on your functions (though make sure you add your name and information to the top of all 3 files in the file headers). The assg-03.cpp tests are designed to be implemented incrementally. You should first uncomment the first tests to test out your tostring() implementation. Once you have that working, move on to creating the asked for constructor, etc. If you perform all of the above tasks correctly, the tests given to you in the starting template will produce the following correct output:
Testing Constructors, tostring() and destructor: ------------------------------------------------------------- li1 = 3483 li2 = 2147483648 li3 = 193839 <LargeInteger::~LargeInteger> destructor entered, freeing my digits
id = 3 value=193839
Testing maxDigits() member function
4
------------------------------------------------------------- The maximum digits between l1 and l2 is: 10 li4 = 398298312 and li5 = 65939674215124133 The maximum digits between l5 and l4 is: 17
Testing digitAtPlace() member function ------------------------------------------------------------- li5[0] == 3 li5[16] == 6 li5[17] == 0 li5[4] == 2 li5[10] == 7 li5[25] == 0 li5[-1] == 0
li4[0] == 2 li4[8] == 3 li4[9] == 0 li4[2] == 3 li4[33] == 0 li4[-5] == 0
Testing appending digits appendDigit() member function ------------------------------------------------------------- li5 after appendDigit(1) = 165939674215124133 li5 after appendDigit(0) = 165939674215124133 li4 after appendDigit(7) = 7398298312 li4 after appendDigit(0) = 7398298312
Testing LargeInteger addition add() member function ------------------------------------------------------------- Addition of li4 + li5 = 165939681613422445 Addition of li5 + li4 = 165939681613422445
999999999 + 999999999 ------------
1999999998
<LargeInteger::~LargeInteger> destructor entered, freeing my digits id = 10
5
value=1999999998 <LargeInteger::~LargeInteger> destructor entered, freeing my digits
id = 9 value=999999999
<LargeInteger::~LargeInteger> destructor entered, freeing my digits id = 8 value=999999999
<LargeInteger::~LargeInteger> destructor entered, freeing my digits id = 7 value=165939681613422445
<LargeInteger::~LargeInteger> destructor entered, freeing my digits id = 6 value=165939681613422445
<LargeInteger::~LargeInteger> destructor entered, freeing my digits id = 5 value=165939674215124133
<LargeInteger::~LargeInteger> destructor entered, freeing my digits id = 4 value=7398298312
<LargeInteger::~LargeInteger> destructor entered, freeing my digits id = 2 value=2147483648
<LargeInteger::~LargeInteger> destructor entered, freeing my digits id = 1 value=3483
Assignment Submission
A MyLeoOnline submission folder has been created for this assignment. You should attach and upload your completed .cpp and .hpp source files to the submission folder to complete this assignment. You really do not need to give me the assg-03.cpp file again, as I will have my own file with additional tests of your functions. However, please leave the names of the other two files as LargeInteger.hpp and LargeInteger.cpp when you submit them.
6
Requirements and Grading Rubrics
Program Execution, Output and Functional Requirements
1. Your program must compile, run and produce some sort of output to be graded. 0 if not satisfied.
2. 10 pts. Correctly implement the tostring() member function.
3. 15 pts. Correctly implement the asked for constructor. Constructor uses dynamic allocation to allocate memory as asked for.
4. 10 pts. maxDigits() implementation is correct.
5. 10 pts. digitsAtPlace() implementation is correct. Function returns 0 for a negative digit or for a digit greater than number of places in the object.
6. 15 pts. appendDigit() implemented correctly. Correctly allocat- ing dynamic memory. Correctly freeing up the old memory after not needed.
7. 30 pts. add() implemented correctly.
8. 5 pts. All output is correct and matches the correct example output.
9. 5 pts. Followed class style guidelines, especially those mentioned below.
Program Style
Your programs must conform to the style and formatting guidelines given for this class. The following is a list of the guidelines that are required for the assignment to be submitted this week.
1. Most importantly, make sure you figure out how to set your indentation settings correctly. All programs must use 2 spaces for all indentation levels, and all indentation levels must be correctly indented. Also all tabs must be removed from files, and only 2 spaces used for indentation.
2. A function header must be present for member functions you define. You must give a short description of the function, and document all of the input parameters to the function, as well as the return value and data type of the function if it returns a value for the member functions, just like for regular functions. However, setter and getter methods do not require function headers.
7
3. You should have a document header for your class. The class header document should give a description of the class. Also you should doc- ument all private member variables that the class manages in the class document header.
4. Do not include any statements (such as system("pause") or inputting a key from the user to continue) that are meant to keep the terminal from going away. Do not include any code that is specific to a single operating system, such as the system("pause") which is Microsoft Windows specific.
8