Java程序辅导

DCS128 Algorithms and Data Structures       27 March 2006
Exercise 10: Using and building a String collection class
The files for this exercise can be found in the directory
http://www.dcs.qmul.ac.uk/~mmh/DCS128/exercises/words
You will need to make use of the Java code in the files WordGen.java, WordTest0.java,
WordTest1.java, WordTest2.java, WordTest3.java and WordTest4.java from this
directory. There is a missing file, WordStore.java. Without this file, you can compile and run
the code in WordTest0.java, which uses the code in WordGen.java, but not the other files.
You need to supply the missing file, with correct code to make the other programs work. You will
not need make modifications to any of the other files.
The code in WordGen.java generates random words. The zero-argument static method make in
this class returns a String with a new word. There is no guarantee that a word returned by a
previous call of make will not be returned again. The static method initialise which takes an
integer argument, the "seed", sets up a particular series of words which is always given for any
particular seed, so you can test the code several times knowing each time the same words will be
generated. There is no test that the words generated have any meaning in English, most won't, but
the rules which generate them ensure they are pronounceable using standard English spelling and
phonetics convention, with shorter words being generated more often than longer words, and the
chance of a particular letter being used being roughly as it is in English. So some words are more
likely to be generated than others. All words generated consist of lower case alphabetic characters
only.
The program in WordTest0.java just generates and displays some words, so you can see the
sort of data you are dealing with. The program in WordTest1.java enables you to generate
some words (which are not displayed, so you can generate more of them than you could
reasonably display on the screen) and then enter your own words to see how many times each of
them was generated. It requires that objects of type WordStore have methods add and count.
Both methods take a String as an argument, the first adding it to the collection held in the
WordStore object, the second returning an integer saying how many times the String argument
is stored in the collection. So the collection class you write as WordStore must have the concept
of a word being stored in the objects it describes a particular number of times.
The programs in WordTest2.java, WordTest3.java and WordTest4.java are designed to
test the efficiency of the operations count, add and remove respectively. So for WordTest4 you
need to write an additional method, remove, for WordStore which takes a String as an
argument and removes one occurrence of that String from the collection (not all occurrences).
The code in these programs generates a collection of words, then generates a second set of words
stored in an array and applies the operation on the collection with each word from the second set.
It measures and displays the time taken to apply the operation repeatedly.
You should first attempt this exercise making use of appropriate classes from Java’s Collections
Framework to implement WordStore. You should then test your ability to write your own
collection classes by writing an implementation of WordStore which does not use any class from
Java’s code library apart from String. For an efficient implementation, you may need to research
algorithms and data structures not covered in the course notes, particularly trees and hash tables,
but a good approach would be to start by building a simple but possibly inefficient
implementation.