Java Reference
In-Depth Information
9.
Figure 20-1b illustrates how you can use parallel arrays to represent the entries in a dictionary. Implement the
ADT dictionary by using this approach.
10.
Revise the class
Entry
given in Listing 20-1 of Segment 20.2 as a top-level class that implements the interface
Comparable
. You compare two
Entry
objects by comparing their search keys. Using this class and an
implementation of the ADT sorted list, write an implementation for a sorted dictionary. The classes, including
Entry
, should belong to the same package.
11.
Revise the class
Entry
, which is in Listing 20-1, to make it public. Implement a sorted dictionary by using an
array of
Entry
objects.
12.
Repeat the previous project, but instead use a chain of linked nodes that each reference an instance of
Entry
.
13.
Implement the interface
DictionaryInterface<String,
String>
to create a class of glossaries. A
glossary
is a
dictionary of specialized terms and their corresponding definitions. Represent the glossary as an array of 26 sorted
lists, one list for each letter of the alphabet. Each entry—which consists of a term and its definition—in a glossary
is stored in the sorted list corresponding to the term's first letter. Thoroughly test your class using a text file of
terms and definitions as data for your glossary.
A
NSWERS
TO
S
ELF
-T
EST
Q
UESTIONS
1.
The memory requirements for the search keys and the values are the same for each representation, so let's ignore
them. The memory requirement for the representation shown in Figure 20-1a uses three references for each entry
in the dictionary: one in the array and two in the
Entry
object. The parallel arrays in Figure 20-1b require only two
references for each dictionary entry. Thus, for
n
entries in the dictionary, the representation in Part
a
requires 3
n
references, but the representation in Part
b
requires only 2
n
references. However, if each array has a length of
m
,
where
m
is greater than
n
, Part
a
has
m
−
n
unused locations and Part
b
has twice that number.
2.
The initial search determines the insertion point when the dictionary is sorted, whereas the insertion point for an
unsorted dictionary is always right after the last entry in the array. Insertion into a sorted dictionary generally
requires shifting other entries in the array. No shifting is necessary for an unsorted dictionary.
3.
private int
locateIndex(K key)
{
return
binarySearch(0, numberOfEntries - 1, key);
}
// end locateIndex
private int
binarySearch(
int
first,
int
last, K key)
{
int
result;
if
(first > last)
result = first;
else
{
int
mid = first + (last - first) / 2;
K midKey = dictionary[mid].getKey();
if
(key.equals(midKey))
result = mid;
else if
(key.compareTo(midKey) < 0)
result = binarySearch(first, mid - 1, key);
else
result = binarySearch(mid + 1, last, key);
}
// end if
return
result;
}
// end binarySearch
