- The Largest Integer That Can Be Stored Using A 32 Bit Int Data Type Is 2 147 483 647 In This Question You Are Going To 1 (55.48 KiB) Viewed 49 times
- The Largest Integer That Can Be Stored Using A 32 Bit Int Data Type Is 2 147 483 647 In This Question You Are Going To 2 (63.73 KiB) Viewed 49 times
- The Largest Integer That Can Be Stored Using A 32 Bit Int Data Type Is 2 147 483 647 In This Question You Are Going To 3 (92.96 KiB) Viewed 49 times
- The Largest Integer That Can Be Stored Using A 32 Bit Int Data Type Is 2 147 483 647 In This Question You Are Going To 4 (34.79 KiB) Viewed 49 times
- The Largest Integer That Can Be Stored Using A 32 Bit Int Data Type Is 2 147 483 647 In This Question You Are Going To 5 (32.44 KiB) Viewed 49 times
#include <iostream>
#include <iomanip>
#include <string>
#include <cctype>
#include <cstdlib>
using namespace std;
struct Node
{
int value;
Node * next;
};
// output the linked list
void print_list(Node * head)
{
Node * current = head;
while (current != NULL)
{
// process the current node, e.g., print the content
cout << current->value << " -> ";
current = current->next;
}
cout << "NULL\n";
}
// output the large number stored in the linked list
void print_num(Node * head)
{
Node * current = head;
while (current != NULL)
{
if (current == head)
cout << current->value;
else
cout << setw(5) << setfill('0') <<
current->value;
current = current->next;
}
}
// insert a value as a node to the head of a linked list
void head_insert(Node * & head, int v)
{
Node * p = new Node;
p->value = v;
p->next = head;
head = p;
}
// delete the head node from a linked list
void delete_head( Node * & head)
{
if (head != NULL) {
Node * p = head;
head = head->next;
delete p;
}
}
// free an entire linked list
void delete_list(Node * & head)
{
while ( head != NULL )
{
delete_head(head);
}
}
// double the capacity of an array
// array: input array
// size: original size of array, updated to new size of
array
void grow_array( char * & array, int & size )
{
if (array == NULL)
return;
int newSize = size * 2;
// doubled the size of the array;
char * tmp = new char [ newSize ];
// copy original contents
for (int i = 0; i < size; ++i)
tmp = array;
delete [] array;
array = tmp;
size = newSize;
}
// get a number from a user
// by reading character by character until a space is hit
// use dynamic array to store the digits
// digits: character array that stores the digits of the
number
// numDigits: number of digits read from input
void input_num(char * & digits, int & numDigits)
{
int arraysize = 32;
digits = new char [arraysize];
char c;
int numRead = 0;
// read each digit as a character until a white space is hit
c = cin.get();
while (!isspace(c))
{
if (numRead >= arraysize)
grow_array( digits, arraysize );
digits[numRead] = c;
numRead++;
c = cin.get();
}
numDigits = numRead;
}
// get a large integer from user input
// and store in a linked list of Node
// each node stores the value of a chunk of 5 digits taken from
the large integer
// e.g., if the input is 43323000089500012, the linked list
is
// 43 -> 32300 -> 895 -> 12 -> NULL
//
Node * create_num_list()
{
// TASK 1a: declare a pointer pointing to the head of the link
list
Node * head = NULL;
string str;
char * digits = NULL; // a dynamic array for storing an input
number
int numDigits;
int val;
// get a number from the user
input_num( digits, numDigits);
// scan the digits in reverse, and create a list of nodes
for
// the value of every 5 digits
str.clear();
for (int i = numDigits-1; i >=0; --i) {
str = digits + str;
if (str.length()==5) {
val = atoi(str.c_str());
// TASK 1b: insert a value as a node to the head of the linked
list
head_insert(head, val);
str.clear();
}
}
// the digits array is scanned and there are still digits
// stored in str that are not inserted into the list yet
if (!str.empty()) {
val = atoi(str.c_str());
// TASK 1c: insert a value as a node to the head of the linked
list
head_insert(head, val);
}
if (digits != NULL) {
delete [] digits;
}
// TASK 1d: return the pointer to the linked list
return head;
}
// return the length of a linked list
int list_length(Node * head)
{
// TASK 3: Modify this print function to one that
// count the number of nodes in a linked list
int num = 0;
Node * current = head;
while (current != NULL)
{
// process the current node, e.g., print the content
++num;
current = current->next;
}
return num;
}
// return if the number n1 is larger than n2
bool larger(Node * n1, Node * n2)
{
int len1 = list_length(n1);
int len2 = list_length(n2);
// TASK 4a: handle the case
// when the list lengths are different
if (len1 > len2)
return true;
else if (len1 < len2)
return false;
// the two lists are of equal length
Node * curr1 = n1, * curr2 = n2;
while (curr1 != NULL) {
if (curr1->value > curr2->value)
return true;
else if (curr1->value < curr2->value)
return false;
// TASK 4b: advance curr1, curr2
// to point to the next nodes
curr1 = curr1->next;
curr2 = curr2->next;
}
return false;
}
int main()
{
Node * n1, * n2;
cout << "expr> ";
n1 = create_num_list();
cin.get(); // skip the '>' sign
cin.get(); // the space after the '>' sign
n2 = create_num_list();
// TASK 2: call print_list() on n1 and n2 for checking
print_list(n1);
print_list(n2);
if (larger(n1, n2)) {
cout << "Yes, ";
print_num(n1);
cout << " is larger." << endl;
}
else {
cout << "No, ";
print_num(n1);
cout << " is not larger." << endl;
}
// TASK 5: free the linked lists
delete_list(n1);
delete_list(n2);
return 0;
}
The largest integer that can be stored using a 32-bit int data type is 2,147,483,647. In this question, you are going to implement addition of two arbitrarily large numbers using linked lists. A large integer is to be stored in your program as follows. Starting from the least significant digit, an integer n is segmented into chunks of 3 digits. The value of the chunk with the least significant digits is stored in the first node and that of the most significant digits is stored in the last node, so that the linked list in reverse will give the original integer n. Here are some examples:
12345678 678 345 12 1009 9 1 不 21474000083647 647 83 0 474 1 21 Input: • Your program should accept an expression a + b from the user, which is an addition of two large numbers a and b. Output: • First two lines of output print the linked list storing the two input large numbers to be added. • The third line of output prints the linked linked list storing the sum of the two numbers. • The fourth line of output prints the sum in its conventional form.
Requirements: . • You should assume that the input integers are of arbitrarily number of digits. In other words, you cannot simply store the input numbers in any integer or string types. • You should start with the solution program largenum.cpp of the tutorial problem and modify the code from there. Then the use of dynamic array to handle the arbitrary long input would have been done for you. • Remember to name your submission as 1.cpp . Modify the code so it first creates two linked lists for the input numbers, then performs the addition which creates a third linked list storing the sum. Addition is done by adding the values stored in the nodes of the two linked lists that correspond to the same decimal places, and propagating the carry digit (if there is any) to the addition of the next nodes storing the value of the more significant digits. You are not allowed to use STL containers (e.g., vectors) or other external libraries.
• You may add your own functions wherever appropriate for better program modularity. • You are allowed to reuse/modify functions in the sample programs build_list_forward.cpp, build_list_backward.cpp, build_list_sorted.cpp, build_list_reverse.cpp and largenum.cpp of Module 8.3 whenever appropriate.
Sample Test Cases User inputs are shown in blue. 1_1 12345678 + 1009 678 -> 345 -> 12 -> NULL 9 -> 1 => NULL 687 -> 346 -> 12 -> NULL 12346687 1_2 999999999 + 99 999 -> 999 -> 999 -> NULL 99 -> NULL 98 -> 0 => 0 -> 1 -> NULL 1000000098 1_3 12345678 + 21474000083647 678 -> 345 -> 12 -> NULL 647 -> 83 -> -> 474 -> 21 -> NULL 325 -> 429 -> 12 -> 474 -> 21 -> NULL 21474012429325