辅导 program、讲解 R编程语言
HOMEWORK 9
This project is individual work. Each student must complete this assignment
independently.
User Request:
“Create a simple system to read, store, merge, purge, sort, search, and write data
using a complete array library, a linked list library, error checking, user
interaction, and providing fast lookup by suitable values.”
Objectives:
1 Use Java file IO to read and write files while using Java standard I/O (in and out) for
user interaction, using appropriate exception handling and giving appropriate error
messages.
5 points
2 Encapsulate primitive arrays inside a generic class that provides controlled access to
the array data, retains information on array capacity and use, and can be used to store
data of any class or primitive type. Integrate appropriate exception handling into the
MUarray class.
5 points
3 Efficiently sort and search the data based on the field specified by the user (using a
comparator).
5 points
4 Store data in a linked list maintained in order, sorted by RecordIDs. Add and remove
entries from the linked list while maintaining its order. Integrate appropriate exception
handling into classes that implement linked lists.
5 points
5 Create and use a hash table with RecordIDs as keys for efficient insertion and
retrieval of data based on RecordIDs. This hash table must store data within an array
and resize appropriately to maintain efficiency.
25 points
6 Encapsulate hash tables inside a generic class that provides controlled access to the
hash table data, retains information on hash table capacity and load factor, and can be
used to store data of any class or primitive type.
10 points
7 Handle collisions in the hash table using separate chaining implemented using your
OrderedMULinkedListclass.
10 points
8 Integrate appropriate exception handling into the generic hash table class. 5 points
9 Provide a design document explaining and justifying alternative implementation
choices for a hash table.
10 points
10 Develop and use an appropriate design. 10 points
11 Use proper documentation and formatting. 10 points
Description:
For this homework, you will revise and improve EV 2.0 from Homework 8 in one important way.
You are encouraged to reuse and build on your code from Homework 8. EV 3.0 will have the same basic
functionality as EV 2.0, but it will have one major change “under the hood”– because it is believed
that users will most often want to search for data by RecordID values, the list of RecordID values will be
used as keys to a hash table that stores pointers to the associated data. This will allow for data to be
looked up by RecordIDs in constant time, that is, in Θ(1) time, unless the hash table becomes too full or
the data are extremely skewed in some unlikely way. Of course, your table should resize if it becomes too
full. (Note that EV 3.0 will still store the list of data using linked list data structures during initial
reading, merging, and purging and will still store the list of data using your generic array for sorting and
searching using fields besides RecordIDs.)
Operational Issues:
From a user interface perspective, EV 3.0 will behave as described for EV 2.0, except that there will be
one additional data saving/display option, as follows.
“Enter (o)utput, (s)ort, (f)ind, (e)fficiency, (m)erge, (p)urge, (r)ecords,
(h)ash table, or (q)uit: ”
If the user enters ‘h’ for hash table display, EV 3.0 will list the data with RecordIDs in the order they are
stored in the hash table, each prepended with the bucket number (hash code) where it is stored, followed
by a colon. If a bucket is empty, the bucket number and colon should be skipped. If a bucket overflows,
the overflow items should be prepended with “OVERFLOW:” and be displayed in their overflow order
before proceeding to the next bucket. There should also be a blank line displayed between buckets. All
of this will be followed by a blank line, then a line giving some data about the hash table, namely, its
“base capacity” (the size of the array, not counting any overflow), its “total capacity” (the size of the
array plus any separate chaining links used for overflow), and its load factor. This is immediately
followed by the usual line stating the number of data lines read, etc. As with the other data
saving/displaying options, if the user enters ‘h’ for hash display, EV 3.0 will prompt for an output
filename and send the output to the standard out console if no file name is provided. Note that this is
thought of as a debug display as it is unlikely to be of use to an end user but may help you to debug your
project.
Implementation Issues:
In most areas, EV 3.0 will be implemented just as EV 2.0. This includes how EV reads files and
prints data, carries out user interaction via standard in and standard out, encapsulates arrays, how
exception handling is implemented for arrays and similar classes, and how the list of records is
stored in a linked list when data is initially read in and when it is being merged and purged. The big
implementation change will be the data structure used in the code to find data based on RecordID values.
For EV 3.0, you are no longer allowed to sort and search by RecordIDs using the array, you need to use a
hash table instead. This hash table will use an array of OrderedMULinkedLists to hold the data and
resolve collisions through separate chaining. For this hash table, we will keep the hash function simple
by using RecordIDs and wrapping RecordIDs that are too large for the array using modulus table
capacity. However, to avoid too many collisions for likely data subsampling, we will make the table
capacity always a prime number, following a predefined resizing schedule. The table will resize to the
next larger size in the schedule when it exceeds its maximum load factor (which will have a default value
of 90% but should be able to be set to other values via a constructor), and resize down to the next smaller
size in the schedule when it falls below its minimum load factor (which will have a default value of 40%
but should be able to be set to other values via the same constructor).
Of course, many alternatives could be selected for hash table implementations. For this reason, you
should include a design document with your submission. Please make this a PDF file and name it “EV 3
Design.pdf” in your submission. In this document, you should describe one alternative hash function
you could have chosen and one alternative collision resolution strategy that you could have chosen,
along with a brief analysis of how these alternatives would influence the complexity and efficiency
of your code.
Note that when you first create your hash table in EV, you will know the amount of data it is to contain.
This is because you will wait to create it until you have read the first file of data. Similarly, when you
merge or purge data, you will use your adjusted list to create a new hash table for the adjusted amount of
data. This means that when EV creates a new hash table, it should specify this value. However, your
member function for adding entries to the hash table should be capable of automatic resizing if the table
exceeds the maximum load factor or falls below the minimum load factor.
Be sure to use all developed code, use efficient mutator methods (e.g., don’t make new arrays
unless doubling or halving the array), and check whether memory is available on the stack when using
new in your MUArray, OrderedMULinkedList, and MUHashTable classes and throw
OutOfMemoryError if no space is available.
Be sure to use a good object-oriented design in this project. That includes the appropriate use of
encapsulation, inheritance, overloading, overriding, accessibility modifiers, etc.
Be sure to use good code documentation. This includes header comments for all classes and methods,
explanatory comments for each code section, meaningful variable and method names, consistent
indentation, etc.
You may write your program from scratch or start from programs for which the source code is freely
available on the web or through other sources (such as friends or student organizations). If you do not
start from scratch, you must give a complete and accurate accounting of where your code came from
and indicate which parts are original or changed and which you got from which other source. Failure to
give credit where credit is due is academic fraud and will be dealt with accordingly.
Submission:
You must submit an electronic copy of your code to the appropriate homework submission link
over the blackboard. You must also submit the Homework Summary Document CS 210.docx with
your submission.
Submission Process for All Assignments: 1) Make sure that the file path for reading and writing is given by
the user as input by using Scanner etc. (should not be hardcoded in your code). 2) Before submission, make
sure that your code is working from the command line by compiling and running without issues as you type
"javac" to compile and "java" to run the compiled file. If your code does not run from the command line or
compile, you will get 0. Running JUnit test source code from the command line can be tricky. You do not
need to run JUnit source files from command lines.