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