CS19 Spring 2016
Assignment 5 (Looking Out for Number One)
The natural world is full of hidden and beautiful mathematics. The whorls of a conch shell hide the Fibonacci sequence and its Golden Ratio, plants grow in fractal patterns, and comets trace hyperbolic patterns through the solar system. All those beautiful patterns hide in the grungy data of human observation. So, what patterns are the populations of every town in California and the number of friends by the members of Facebook hiding from you?
Define a class called DigitAnalyzer that implements a Linked List (by serving as a List class as described in class) that can store integers and perform some analysis on them. Your Linknode class may (at your preference) store your integer data in the linking node object itself for your convenience. Your DigitAnalyzer class must support, at a minimum, the following functions:
- A constructor that initializes the list to empty
- A destructor that correctly deallocates all the objects in the list
- A public function named getSize() that returns the length of the list.
- A public function named getStartingDigits() that returns an integer array of size 10 that contains the number of values from the List that begin with that initial digit (zero through nine.)
- A public function named int countAndRemoveMatches(int) that removes from the list all entries that match the parameter and returns a count of the nodes removed.
- A public function that allows you to insert an integer into the list.
- a public function named printAll() that sends each integer in the list in order, starting from the first, to STDOUT, with one entry per line.
- Other member functions as you deem appropriate.
- Remember that list traversals take time—do your best to minimize the number of traversals needed in your functions/program!
Main and program data files
Write a main function that reads an unspecified number of lines of text from a regular text file by getting the filename from the command line. If no filename is provided on the command line, your program should instead read its input (not a filename) from STDIN. Your program should exit on an invalid text file (name.) You may assume that no line of text will consist of more than 255 characters. Every line will contain, at most, one comment and, at most, one integer. Some lines may be blank. Comments will be contained within specific start "(*" and end "*)" delimeters, and both the start and end delimeters will always occur on the same line. Integer data may come before, or after comments if the line has both. Read each integer and store it in your linked list. Your list must store the full integer value. Once you have completed all input, use the functions you have written to display (in a table) the total number of entries, the number of entries that begin with each digit, and what percentage (formatted as a percentage with one decimal place example: 7.5%) of the total input that digit accounts for. Seperate the columns with a single tab character. Call your countAndRemoveMatches function with a value of zero, and if any entries were removed, then display how many zeroes were removed and print the table a second time. Your main function may use helper functions.
What to "Turn-In"
Since this is a multi-file project, I will collect the directory 19-5 and all of its contents. You are required to ensure that only the necessary .h and .cpp files, a working makefile, and a readme.txt file are present. This directory should not contain any files not part of your project, and it should not contain any subdirectories. I will collect all of the files from this directory. The binary program resulting from compiling your project should be called "p5". You will loose points if any other files are present, unless you have a 'make clean' option that removes them.
Write up any observations that you make about these data sets in a readme.txt file. Your discoveries are worth up to five additional points. You may earn an additional five extra credit points if you send me a data file that I can use for future versions of this assignment. Only correct programs can earn extra credit.
Sample Data Files
- Cabrillo: Student Ages
- Cabrillo: Student Degree Aplicable Units
- Cabrillo: Student Transferable Units
- Cabrillo: Student Units
- Sunspot Activity
- Libraries: Collection Sizes
- Social Networking Website: Daily New Users
- MBARI windspeed
[steveh@pengo CS19]$ ./p5 randomValues.txt Leading Digit Analysis Sample Solution digit count % 0s 0 0.0% 1s 625 10.2% 2s 674 11.0% 3s 696 11.4% 4s 698 11.4% 5s 715 11.7% 6s 696 11.4% 7s 688 11.3% 8s 624 10.2% 9s 684 11.2% 6100 entries total [steveh@pengo CS19]$
[steveh@pengo CS19]$ ./p5 < randomValues.txt Leading Digit Analysis Sample Solution digit count % 0s 0 0.0% 1s 625 10.2% 2s 674 11.0% 3s 696 11.4% 4s 698 11.4% 5s 715 11.7% 6s 696 11.4% 7s 688 11.3% 8s 624 10.2% 9s 684 11.2% 6100 entries total [steveh@pengo CS19]$
[steveh@pengo CS19]$ ./p5 cc-units.txt Leading Digit Analysis Sample Solution digit count % 0s 1242 14.3% 1s 1856 21.4% 2s 982 11.3% 3s 1135 13.1% 4s 922 10.6% 5s 675 7.8% 6s 716 8.3% 7s 522 6.0% 8s 378 4.4% 9s 240 2.8% 8668 entries total Removing 1242 zero entries. digit count % 0s 0 0.0% 1s 1856 25.0% 2s 982 13.2% 3s 1135 15.3% 4s 922 12.4% 5s 675 9.1% 6s 716 9.6% 7s 522 7.0% 8s 378 5.1% 9s 240 3.2% 7426 entries total [steveh@pengo CS19]$