/* * Instructions: * * 1. Only complete the functions specified below. Do not create any additional function. * 2. Use Visual Studio 2019 to build, test and run your code. * 3. Do not include any additional header or library. * 4. This is an exercise of linked list operations. Do not copy linked lists to arrays for manipulation. * */

#include #include #include #include

#define MAX_LENGTH 1000 // the max allowed input length

using namespace std;

/* Linked list node */ struct node { int data; node* next; };

//-------------------------- functions to be implemented by you

/* * Given a non-negative integer as a c-string (number), build a linked list that each node stores one digit of * the number starting from the least significant digit. * * The function returns a pointer to the head node (LSD) of the list. * * Precondition: number of digits > 0 * * Example: * Given number: 123 * Output list: [3]-> [2]-> [1]-> NULL * */ node* buildReverseList(char* number) { }

/* * Given two linked lists representing two non-negative integers in reverse order, add the two integers and store * the sum in a new linked list. * * The function returns a linked list (in reverse order) of the sum. * * Precondition: num1 and num2 are non-empty. * * Post-condition: num1 and num2 are unaltered. * * Space and Time Complexity Requirement: O(n) * * Example: * Given number 1: 123 * Given number 2: 456 * Output list: [9]-> [7]-> [5]-> NULL * */ node* addNumbers(node* num1, node* num2) {

}

//-------------------------- functions prepared for you

/* * Helper functions for linked list. */ class ListHelper { public:

//print nodes in a given linked list static void printList(node* list) { while (list != NULL) { printf("[%d]-> ", list->data); list = list->next; } cout << "NULL" << endl; }

//delete nodes in a given linked list static void deleteList(node* list) { node* temp; while (list != NULL) { temp = list; list = list->next; delete temp; } } };

/* * Driver program * * Read the test cases from the input file and use them to test * your functions' implementation. * */ int main() {

char number[MAX_LENGTH]; // buffer

ifstream fin("tut04_input.txt"); if (!fin) { cout << "Input file not found."; exit(1); }

int testcase; fin >> testcase;

for (int i = 0; i < testcase; i++) {

cout << "Case " << i + 1 << endl;

fin >> number; node* num1 = buildReverseList(number); fin >> number; node* num2 = buildReverseList(number);

cout << "Num 1:\t"; ListHelper::printList(num1); cout << "Num 2:\t"; ListHelper::printList(num2); cout << "Sum:\t"; node* sum = addNumbers(num1, num2); ListHelper::printList(sum); cout << endl;

ListHelper::deleteList(num1); ListHelper::deleteList(num2); ListHelper::deleteList(sum); }

return 0; }

Please write the code in C++.

--------------------------------------------

Contents of txt file given below.

--------------------------------------------

5 123 456 111 111111 222222 222 0 10 999 111

================================================================================ Below is the description of the input format and expected output. ================================================================================

Input: The first line of input contains an integer T denoting the number of test cases. Each following test case contains two integer numbers, each on a single line.

Output: Case 1 Num 1: [3]-> [2]-> [1]-> NULL Num 2: [6]-> [5]-> [4]-> NULL Sum: [9]-> [7]-> [5]-> NULL

Case 2 Num 1: [1]-> [1]-> [1]-> NULL Num 2: [1]-> [1]-> [1]-> [1]-> [1]-> [1]-> NULL Sum: [2]-> [2]-> [2]-> [1]-> [1]-> [1]-> NULL

Case 3 Num 1: [2]-> [2]-> [2]-> [2]-> [2]-> [2]-> NULL Num 2: [2]-> [2]-> [2]-> NULL Sum: [4]-> [4]-> [4]-> [2]-> [2]-> [2]-> NULL

Case 4 Num 1: [0]-> NULL Num 2: [0]-> [1]-> NULL Sum: [0]-> [1]-> NULL

Case 5 Num 1: [9]-> [9]-> [9]-> NULL Num 2: [1]-> [1]-> [1]-> NULL Sum: [0]-> [1]-> [1]-> [1]-> NULL