Transcript Ch17v2.0
Dictionaries
Chapter 17
Slides by Steve Armstrong
LeTourneau University
Longview, TX
2007, Prentice Hall
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
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Specifications for the ADT Dictionary 1
• 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.
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Specifications for the ADT Dictionary
Fig. 17-2 An instance of an ADT dictionary has pairs of
search keys and corresponding values
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Specifications for the ADT Dictionary 2
• Data
Pairs of objects (key, value)
Number of pairs in the collection
• Operations
• add
• traverse values
• remove
• isFull
• retrieve
• get number of entries
• contains
• remove all entries
• traverse keys
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Specifications for the ADT Dictionary 3
• Additional refinement possibilities
Distinct search keys vs.
Duplicate search keys
Secondary search keys
• View Java source code for interface
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Iterators 6
• Note that getKeyIterator and getValueIterator
return iterators
Create iterators for a dictionary dataBase with
• Possible to traverse
All search keys in dictionary without traversing values
All values without traversing search keys
All search keys and values in parallel
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Iterators
Fig. 17-3 Two iterators that traverse a
dictionary's keys and values in parallel.
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Using the ADT Dictionary 7
• A directory of telephone numbers
Fig 17-4 A class diagram for a telephone directory.
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
A Directory of Telephone Numbers
• Consider a client of the class
TelephoneDirectory as specified
in Fig. 17-4
View source code
Note output
• View source code of
class TelephoneDirectory
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
The Frequency of Words 12
• We seek an ADT that will enable us to
count each occurrence of a word as it is
read from a text file
• View client program which uses
FrequenceyCounter
Note output
• View class FrequencyCounter used by
the client
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
A Concordance of Words 18
• 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
• View class Concordance
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Java Class Library: The Interface Map 22
• Package java.util contains interface
Map <K, V>
Similar to our ADT dictionary
• View list of method headers
Note similarity to methods developed in this
chapter
Differences from our methods are highlighted
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X