Transcript Chapter17

Dictionaries
Chapter 17
Chapter Contents
Specifications for the ADT Dictionary
• A Java Interface
• Iterators
Using the ADT Dictionary
• A Directory of Telephone Numbers
• The Frequency of Words
• A Concordance of Words
Java Class Library: the Interface Map
2
Specifications for the ADT Dictionary
Contains entries that each have two parts
• A key word or search key
• A value associated with the key
Fig. 17-1 An English
dictionary.
3
Specifications for the ADT Dictionary
Data
• Pairs of objects (key, value)
• Number of pairs in the collection
Operations
• add
• isEmpty
• remove
• isFull
• getValue
• getSize
• contains
• clear
• getKeyIterator
4
Iterators
Note that getKeyIterator and
getValueIterator return iterators
• Create iterators for a dictionary myTable with
Iterator keyIterator = myTable.getKeyIterator();
Iterator valueIterator = myTable.getValueIterator();
An iteration of a dictionary's values
• Corresponds to an iteration of the search keys
5
Iterators
Fig. 17-2 Two iterators that traverse a
dictionary's keys and values in parallel.
6
Using the ADT Dictionary
A directory of telephone numbers
Fig 17-3 A class diagram for a telephone directory.
7
A Directory of Telephone Numbers
The beginning of the implementation of the
class TelephoneDirectory
import java.io.*;
import java.util.*;
public class TelephoneDirectory
{ private DictionaryInterface phoneBook;
private static final String DELIMITERS = " \n\r\t";
public TelephoneDirectory()
{
phoneBook = new SortedDictionary();
} // end default constructor
...
8
A Directory of Telephone Numbers
Other methods may include:
/** Task: Reads a text file of names and telephone numbers.
* @param dataFile a text file that is open for input */
public void readFile(BufferedReader dataFile) throws IOException
public String getPhoneNumber(String firstName, String lastName)
public String getPhoneNumber(Name personName)
/** Task: Finds the telephone number of the person whose name is
* given by the user.
* @return the desired phone number as a string, or
* null if no phone number is found, or|
* the string "quit" if the user enters quit instead of a name */
public String getPhoneNumber()
9
The Frequency of Words
We seek an ADT that will enable us to
count each occurrence of a word as it is
read from a text file
To determine the frequency of a word
• The word must be the search key
• The data field will be of the class
FrequenceyCounter
• Read a word from the file
• If not in dictionary, add it, initialize word count = 1
• If it is in the dictionary, increment the word count
10
A Concordance of Words
Provide an index for finding a word in a file
• Index would give the page number
• A concordance would give the line number of a
word (in a smaller file of words)
A word may appear multiple times in the
file
• Appears once in index/concordance
• The associated data is a list of page/line
numbers
11
Java Class Library: The Interface Map
A list of method signatures in Map
• Note similarity to methods developed in this
chapter
public Object put(Object key, Object value);
public Object remove(Object key);
public Object get(Object key);
public boolean containsKey(Object key);
public boolean containsValue(Object value);
public Set keySet();
public Collection values();
public boolean isEmpty();
public int size();
public void clear();
12