Part 1: The Program Write a program to analyze all integers contained in two text files. Both text data input files will contain an unknown number of integers (in the range 1 - 999), separated by whitespace. There may be duplicate integers in the files. The program will: - Read and organize all of the integers from the first data input file into two doubly linked lists, based on whether the integer is odd or even. - Search for all the integers in the second data input file, to determine which list they are in and what their location is within that list. The program must be modular and use correct parameter passing. Use of global variables will NOT be allowed. And object-oriented constructs (classes, objects, templates, STL, etc) may NOT be used. Although we will not be using objects yet, we will begin introducing object-oriented concepts, via Abstract Data Type data definitions and functions. Therefore, you will be required to implement the following doubly linked list data structure and functions. Data Structure Overview This program will maintain a doubly linked list for odd integers, and a second doubly linked list for even integers. The individual nodes in each list should contain one integer and two pointers (one pointer pointing forward to the next node and one pointer pointing backwards to the previous node) only. Sample Node: To create the doubly linked lists, first define a struct type that contains fields for the node data as described above (integer, pointer forward, and pointer backwards). integer forward pointer backward pointer The nodes in each list should contain integers and pointers only. Do not store any other additional information. Also define a second struct type for a doubly linked list. There should be a field for the length of the list (i.e. a count of nodes in the list) and a field for a pointer to a node, which will point to the top node in the list. You must implement the linked list data structures from scratch (no use of templates from the STL allowed). Initially, the lists should not contain any nodes (i.e. the top pointers will be NULL, and the length will be 0). After the lists are built, the backwards pointing pointer of the first node in each list will be NULL, and the forward pointing pointer of the last node in each list will be NULL. Function Overview You will be required to implement the following functions to operate on your doubly linked list data structure: InitializeList - takes a doubly linked list as input, initializes the fields (sets the length/count to 0 and the list top pointer to NULL), and passes back the initialized structure. EmptyList - takes a doubly linked list as input, and returns true if the list is empty (false otherwise). NumInList - takes a doubly linked list and an integer as inputs. Searches for an integer value within the list. If the value is found, returns a pointer to the node containing the value. If the value is not found, or the list is empty, returns NULL. OrderedListInsertIon - takes a doubly linked list and an integer as inputs. Inserts a new node (containing the passed in integer) into the doubly linked list, in ascending numeric order. Returns true if allocation and insertion of the new node was successful, false otherwise. ListLength - takes a doubly linked list as input, and returns the length of the list. PositionInList - takes a doubly linked list and an integer as inputs. Calls NumInList to determine if the integer is in the list. If it is, uses the backward pointers to determine the position of the node within the list. Returns an integer, representing the node position in the list, or 0 if the integer is not in the list. DisplayList - takes a doubly linked list as input. Traverses the list, neatly displaying all integers in the list. DestroyList - takes a doubly linked list as input, and frees the list memory by de-allocating all nodes in the list. length top Only the listed functions will be allowed to access the fields within the list data structure. All other code must use these functions to access the list. Implementation Details Your code must also follow all required coding standards from Content section 1.8. Part 1: Both input data filenames will be given as command line arguments to the program. The program should validate that exactly two filename arguments were given on the command line, and that both the filenames are valid (i.e. the files exist and can be opened), before trying to read data from either of them. If either (or both) filename argument is missing, or one of the files does not exist, the program should prompt the user for the necessary information, until two valid (existing) filenames are obtained. After validating that both data input files exist, the program should initialize both the lists to be empty. Odds 0 Evens 0 Then the program will process the first input data file, as follows: Read one integer at a time from the input file (integers will be separated by whitespace). For each integer the program reads, it should: 1) Determine which doubly linked list the integer belongs in (odd or even). 2) If the integer is unique, insert it into the list (no duplicates). This means you must first search to see if the integer is already in the doubly linked list. a) If the integer is already in the list, issue a message saying so. b) If the integer is not yet in the list, the program should insert the integer into the appropriate doubly linked list in ascending numeric order. NOTE: Your linked list program in CS362 and the first stack/queue assignment in CS372 were implemented by inserting nodes at the beginning (top) or end (bottome) of a linked list. This specification requires you to demonstrate the ability to code a different implementation, by inserting the data into the list in numeric order. NOTE: means the pointer is NULL Be sure to check that memory could be allocated for each new node before using it. c) As you insert numbers into the lists, increment the length to keep track of how many unique integers were inserted into each list. OddList 3 EvenList 2 If memory allocation fails while reading the first input data file, the program should immediately stop reading the file, issue an error message saying that not all numbers were inserted into the lists, and proceed directly to the second part of the program. Part 2: After all of the integers in the first data input file have been read and all unique integers have been inserted into the proper lists (or there was a memory allocation error), display: The filename processed The count of unique numbers inserted into each list The actual numbers in each list (10 numbers per line, formatted neatly in columns) Then process the second input data file to find numbers in the lists. 1) Display the filename of the file containing the numbers to search for. 2) Read one integer at a time from the second input file. Use the forward-pointing links in the doubly linked list, to search for each integer in the appropriate list. NOTE: Do not count nodes as you search in the forward direction! a) If the integer is not found, issue a message saying so. Also state specifically if it was not found because the list was empty. b) If the integer is found, the program should then use the backward-pointing links in the doubly linked list to count how far down in the list the integer was found, and display the results. NOTE: Previously you have traversed lists using forward pointing links to walk down the list. This specification requires you to demonstrate a different ability, using the backwards pointing links to walk up the list. After processing all integers in the second input file, the program should free up all nodes in the doubly linked lists, and exit. 812 413 41 88 339 Program Implementation Notes 1. Your program must conform to the CS372 Coding Standards. The program should include a file header comment block at the top of the program, and each function should include a function header comment block. 2. This program should be of modular design with proper parameter passing. - The breakdown of the code into functions must be logical, not arbitrary! - The main function should do little more than call other functions. - The other functions should each perform ONE well-defined task.