Java Reference
In-Depth Information
2.
Begin two linked implementations of the ADT dictionary according to the two data structures illustrated in Parts
a
and
b
of Figure 20-6. Declare the data fields, define the constructors, and define the method
add
for unsorted data.
3.
In the sorted, vector-based implementation of a dictionary, replace the sequential search performed by the method
locateIndex
with a binary search. (See Segment 20.19.)
4.
For a sorted linked implementation of a dictionary, write iterative versions of the methods
remove
and
getValue
.
5.
For a sorted linked implementation of a dictionary, write recursive versions of the methods
add
,
remove
, and
getValue
.
6.
Segment 20.25 defines the class
KeyIterator
. An instance of this class is an iterator that traverses the search
keys in the dictionary. In a similar fashion, define a class
ValueIterator
to provide a way to traverse the
dictionary's values.
7.
Define an iterator for the ADT dictionary that returns entries containing both a search key and a value. Describe
the class of these entries. Implement a method
getEntryIterator
that returns such an iterator.
8.
Consider adding operations to the ADT dictionary to form the union and intersection of two given dictionaries.
Each operation returns a new dictionary. The union should combine the entries in both dictionaries into a third
dictionary. The intersection should be a dictionary of the entries common to both of the two dictionaries.
Within each given dictionary, search keys are not repeated. However, an entry in one dictionary could have the
same search key as an entry in the second dictionary. Propose and discuss ways to specify these two operations for
this case.
9.
Implement the union and intersection operations that Exercise 8 describes for an unsorted array-based dictionary.
10.
Repeat Exercise 9 for a sorted array-based dictionary.
11.
Repeat Exercise 9 for a sorted linked dictionary.
P
ROJECTS
1.
Implement an unsorted array-based dictionary. Allow the array to expand as necessary during execution.
2.
Repeat the previous project, but maintain the search keys in sorted order.
3.
Implement an unsorted dictionary by using an instance of
Vector
or
ArrayList
.
4.
Repeat the previous project, but maintain the search keys in sorted order.
5.
Implement an unsorted dictionary by using a chain of linked nodes.
6.
Implement a sorted dictionary by using a chain of linked nodes.
7.
In this chapter, the ADT dictionary has distinct search keys. Implement a dictionary that removes this restriction.
Choose one of the following possibilities:
•
The method
add
adds an entry whose search key is already in the dictionary but whose value is not.
The method
remove
deletes all occurrences of the search key. The method
getValue
retrieves all
values associated with a search key.
•
The methods behave as just described, but a secondary search key enables
remove
and
getValue
to
delete or retrieve a single entry.
8.
Segment 19.7 of the previous chapter began a discussion of a telephone directory. Use your dictionary
implementation from Project 7 in a revision of the telephone directory that allows duplicate names.
