Java Reference
In-Depth Information
structor should each produce a deep copy that is equal to the original 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, since the
LinkedList2
class only created 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 corre-
sponds 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
program 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 dic-
tionary. This file can be found on the CD accompanying the textbook and also
on the topic's website. The file contains 45,407 common words and names in
the English language. Note that some words are capitalized. 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.
