Java Reference
In-Depth Information
list according to the
equals
method. The
boolean
valued method
sameContents
has one parameter of type
IntTree
and returns
true
if the calling object and the
argument tree contain exactly the same numbers, and returns
false
otherwise.
Note that
equals
and
sameContents
are not the same. Also, write a suitable
test program.
6. Write an
addSorted
method for the generic linked list from Display 15.8 such
that the method adds a new node in the correct location so that the list remains
in sorted order. Note that this will require that the type parameter
T
extend the
Comparable
interface. Write a suitable test program.
7. Add a
remove
method and an iterator for the
Set
class in Display 15.37 . Write a
suitable test program.
8. The hash table from Display 15.34 hashed a string to an integer and stored the
same string in the hash table. Modify the program so that instead of storing strings,
it stores
Employee
objects as defined in Display 7.2 . Use the
name
instance variable
as the input to the hash function. The modification will require changes to the
linked list, because the
LinkedList2
class created only linked lists of strings. For
the most generality, modify the hash table so that it uses the generic
LinkedList3
class defined in Display 15.8. You will also need to add a
get
method that returns
the
Employee
object stored in the hash table that corresponds to the input name.
Test your program by adding and retrieving several names, including names that
hash to the same slot in the hash table.
9. Display 15.34 and 15.35 provide the beginnings of a spell-checker. Refine the pro-
gram to make it more useful. The modified program should read in a text file, parse
each word, see if it is in the hash table, and, if not, output the line number and
word of the potentially misspelled word. Discard any punctuation in the original
text file. Use the
words.txt
file as the basis for the hash table dictionary. This file
can be found on the topic's website. The file contains 87,314 words in the English
language. Test your spell-checker on a short text document.
10. Change the
Set<T>
class of Display 15.37 so that internally it uses a hash table
to store its data instead of a linked list. The headers of the public methods should
remain the same so that a program such as the demonstration in Display 15.38
should still work without requiring any changes. Add a constructor that allows the
user of the new
Set<T>
class to specify the size of the hash table array.
For an additional challenge, implement the set using both a hash table and a
linked list. Items added to the set should be stored using both data structures. Any
operation requiring lookup of an item should use the hash table, and any operation
requiring iteration through the items should use the linked list.
