Rationale: You must successfully complete individual assignments 1 and 2, before you can join a team

Rationale: You must successfully complete individual assignments 1 and 2, before you can join a team for assignment 3. Teams must be formed in time to complete the design in week 3.
Therefore, if you are not able to successfully complete both assignments 1 and 2
within one day of the due dates, you will not be allowed to move forward in this course.
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
© 2014, Regis University
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
© 2014, Regis University
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.
Sample Empty Lists:
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
© 2014, Regis University
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.
Sample Filled Linked Lists:
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
© 2014, Regis University
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.
Sample Output 1
Say that:
The first input file, listnums.txt, contains 35 integers, but 2 are duplicates.
The second input file, findthem.txt, contains 5 integers, of which 2 are in the odd list and 1 of which is in the even list.
The results might be:
Doubly Linked List Program
Reading input
111 is a duplicate and will be ignored.
28 is a duplicate and will be ignored.
Lists created using input file listnums.txt
9 integers inserted into Odd list:
7 11 33 55 77 99 111 555 999
24 integers inserted into Even list:
4 12 22 28 36 42 68 84 88 92
222 234 236 244 266 432 444 456 666 678
766 828 864 888
Search results for input file findthem.txt:
403 not found in odd list
11 found 2 numbers down in the odd list
766 found 21 numbers down in the even list
33 found 3 numbers down in the odd list
162 not found in even list
© 2014, Regis University
Sample Output 2
Say that:
The first input file, listnums2.txt, contains 5 odd integers only with one duplicate
The second input file, findthem2.txt, contains 2 integers, one even and one odd.
The results might be:
Part 2: Items Due
Submit:
Your program code
All input data files used to test your code
to the Programming Assignment 2 folder in the Dropbox area of the online course by midnight, Sunday.
All necessary files should be attached to one dropbox submission.
WARNING:
Programs that do not compile, are not modular, use ANY global variables, or are submitted more than 1 day late, will NOT be accepted.
Before submitting your program and data files, name them as follows:
Lastname-assn2-prog.cpp
Lastname-assn2-data1.txt
Lastname-assn2-data2.txt
If you have multiple test data files, append a letter on the end of each filename (A is the first input data file, and B is the second input data file that will be run against A’s list).
Examples: Smith-assn2-prog.cpp
Smith-assn2-data1A.txt
Smith-assn2-data1B.txt
Smith-assn2-data2A.txt
Smith-assn2-data2B.txt
Doubly Linked List Program
Reading input
13 is a duplicate and will be ignored.
Lists created using input file listnums2.txt
4 integers inserted into Odd list:
13 255 411 611
0 integers inserted into Even list
Search results for input file findthem2.txt:
16 not found – even list empty
611 found 4 numbers down in odd list
© 2014, Regis University
Part 3: Grading
The grading rubric that will be used for this assignment is included on the next pages.
© 2014, Regis University
CS 372 Advanced Programming and Algorithms
Individual Programming Assignment #2 Grading Rubric
Rating
Exemplary
Proficient
Basic (needs work)
Not Demonstrated
Rating Category Documentation
Documentation clearly explains what code does. Includes complete and accurate file and function headers, as detailed in the CS372 coding standards, along with additional in-line comments at appropriate locations.
Documentation includes all required headers, but lacks clarity or details in some places, OR violated minor details of the CS372 coding standards for comments, OR code is completely over commented.
Documentation is incomplete and/or incorrect and/or formatted incorrectly. Missed significant details of the CS372 coding standards for comments or did not document the underlying program intent.
Only a few (or no) comments in program. Data Storage
Constants used for fixed values. Correct data types used for all variables, including double linked list structure. All definitions within the correct program scope. Follows all CS372 coding standards for data storage.
A few minor errors in constant usage, data declaration scope, data typing or assignment, OR violated some minor details of the CS372 coding standards for data storage.
Multiple minor errors or at least one major error in constant usage, declaration scope, data typing, or assignment AND/OR violated of significant details of CS372 coding standards for data storage.
Did not follow any of the CS372 coding standards for data storage. File Usage
Passes filename(s) in via command line argument. Checks if correct number of arguments passed in. Checks if file(s) exist before trying to read from them. If not passed or non-existent, prompts for valid filename(s). File(s) closed immediately after all data is read.
Passes filename(s) in via command line argument, but only one check performed, OR both checks performed but still did not read in valid filenames when error occurred OR file(s) not closed immediately after use.
Passes filename(s) in via command line argument, but neither check performed, OR filename(s) not passed (simply read from user) but checks still performed.
Filename not passed (hardcoded or read from user) AND no checks performed. Program Input (Reading and Processing)
Reads data from input file correctly and identifies list to insert into. Checks if data already in that list. Recognizes end of file correctly, whether the file contains a newline on the last line or not.
Incorrectly identifies list to insert to for some data OR read count is off by one due to incorrect reading of file OR does not always recognize end of file correctly.
Does not check to see if integer is already in proper list OR has problems completing more than one of the other required tasks.
Fails to read any file input. Program Processing: Linked List Creation
Correctly implements doubly linked lists and initializes all lists correctly to NULL. Verifies memory allocation before using it. Inserts data into correct list in correct order, if not already there. There are no memory leaks.
Minor problem with list implementation, OR initialization (inserts dummy nodes), OR allocation verification, OR not ordered insertion, OR inserts duplicate integers.
Major problem with list implementation, OR initialization, OR allocation verification, OR inserted integers into incorrect locations OR inserted duplicate integers OR minor problems with more than one of the above items.
Fails completely. Double linked integer lists not created at all or lists created incorrectly. Program Processing: Linked List Usage
Uses forward links to search. Uses backward links for determining location in list.
Traversal, integer counts or displays have minor errors.
Uses forward links for everything (no backward link usage) OR traversal counts/displays have other major errors.
Integer lists not traversed correctly in either direction.
© 2014, Regis University
Display Output
Displays correct unique counts and both created lists. Displays correct positions for data found. Correctly identifies data not in either list.
Does not satisfy one of the requirements.
Does not satisfy multiple requirements.
Produces no display output. Modularity (functional breakdown)
Program is efficient, modular in design, and logically organized. Each module performs one well-defined task and is defined, prototyped, and called correctly. main function minimal – does little more than call other functions. All required ADT functions were implemented correctly, and no other functions directly accessed the doubly linked lists.
Program is mostly efficient, modular and logically organized. Program may include one unnecessary function, a function that performs too many tasks, and/or a function that is incorrectly defined or called. A required function may have been defined incorrectly, or another function may have directly accessed the doubly linked lists.
Program is only somewhat modular (missing necessary functional breakdown), AND/OR multiple modules perform too many tasks, AND/OR multiple parts of the program are not efficient or logically organized, AND/OR multiple problems with module definitions/calls or incorrectly accessing the doubly linked lists.
Program contains very little modularity (too many tasks performed from main function), but does contain at least two prototyped functions, AND/OR contains adequate number of functions, but none are implemented efficiently. C++ Constructs / Parameter Passing/ Readability / Miscellaneous
Demonstrates understanding of program, control, and file structures. Appropriate use of language with only necessary parameter passing. Code is well organized, easy to follow, and adheres to all CS372 coding standards for code usage (e.g. no use of break/return to exit loop).
A parameter or two was passed incorrectly (value vs. reference), OR an unnecessary parameter(s) was passed, OR there was minor improper control or data structure usage, AND/OR had occasional spacing, indentation, and/or other minor organizational issues.
Many problems with control/data structure usage or parameter definitions and usage, AND/OR one other major error or coding standard violation, AND/OR substantial spacing, indentation, and/or organizational issues.
Demonstrates minimal understanding of control/data structures or proper parameter passing AND/OR has major coding standard violations, AND/OR code is poorly organized and difficult to read AND/OR has other major construct issues. Unacceptable
Is late OR does not compile OR is not modular OR uses one or more global variables OR is submitted more than 1 day late.