经典的数据结构作业，实现Dictionary ADT的接口，完成Latin Dictionary.

The Program

This program is an example of an application that uses a very common interface, the DictionaryADT. A dictionary is a structure that accepts key=value pairs. The keys are used to order the structure and to lookup values. Keys must be distinct; no duplicates are allowed. There may, however, be duplicate values. For this dictionary application, the key is a latin word, and the value is its definition. The application program consists of the java class LatinDictionary, which has the following methods:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import java.util.Iterator;
import data_structures.*;

public class LatinDictionary {
    private DictionaryADT<String,String> dictionary;

    // constructor takes no arguments. Size depends on the datafile.
    // creates an instance of the DictionaryADT. Use your HashTable 
    // implementation in this class (though all four should work).
    // Methods that make modifications to the dictionary modify the
    // DictionaryADT object, not the datafile.
    public LatinDictionary() {
        }

    // reads the key=value pairs from the datafile and builds a dictionary structure 
    public void loadDictionary(String fileName) {
        }

    // inserts a new Latin word and its definition
    public boolean insertWord(String word, String definition) {
        }

    // removes the key value pair that is identified by the key from the dictionary
    public boolean deleteWord(String word) {
        }

    // looks up the definition of the Latin word
    public String getDefinition(String word) {
        }

    // returns true if the Latin word is already in the dictionary
    public boolean containsWord(String word) {
        }
    
    // returns all of the keys in the dictionary within the range start .. finish
    // inclusive, in sorted order. Neither value 'start' or 'finish' need be in the
    // dictionary. Returns null if there are no keys in the range specified.
    public String[] getRange(String start, String finish) {
        }
            
    // returns an Iterator of the latin words (the keys) in the dictionary,
    // in sorted order.
    public Iterator<String> words() {
        }

    // returns the definitions in the dictionary, in exactly the same order
    // as the words() Iterator
    public Iterator<String> definitions() {
        }
}

To assist you in developing the application, you will be provided with two helper classes, and a sample driver program:

• DictionaryReader.java This class has the static method public static DictionaryEntry[] getDictionaryArray(String fileName) This method reads a datafile with latin words and their definitions. The datafile was provided by the Internet Dictionary Project and is in the public domain. The method creates an array of type DictionaryEntry (also provided) and returns it.
• DictionaryEntry.java This class is a wrapper class that has two String fields, the KEY and VALUE. These are the latin word, and its definition. This is for convenience in getting the data into your dictionary structure. Note that you must extract the key and value from a DictionaryEntry object to insert them into your dictionary.
• DictionaryDriver.java This is a sample driver program you may use to test your LatinDictionary class.

Here are links to the three Java files and the Latin.txt datafile:

• DictionaryReader.java
• DictionaryEntry.java
• DictionaryDriver.java
• DictionaryADT.java
• Latin.txt

You do not have to open or parse the Latin.txt file. Use the DictionaryReader method getDictionaryArray(filename) to load the latin words and definitions into an array for the load(filename) in your LatinDictionary class.

To get an array of DictionaryEntry containing all the words in the dictionary:

1

DictionaryEntry [] entries = DictionaryReader.getDictionaryArray(fileName);

The DictionaryADT

As with previous assignments, all data structures must be in package data_structures. The DictionaryADT is an interface defined as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

package data_structures;

import java.util.Iterator;
import java.util.NoSuchElementException;

public interface DictionaryADT<K extends Comparable<K>,V> {

// Returns true if the dictionary has an object identified by
// key in it, otherwise false.
public boolean contains(K key);

// Adds the given key/value pair to the dictionary. Returns 
// false if the dictionary is full, or if the key is a duplicate.
// Returns true if addition succeeded.
public boolean add(K key, V value);

// Deletes the key/value pair identified by the key parameter.
// Returns true if the key/value pair was found and removed,
// otherwise false.
public boolean delete(K key);

// Returns the value associated with the parameter key. Returns
// null if the key is not found or the dictionary is empty.
public V getValue(K key);

// Returns the key associated with the parameter value. Returns
// null if the value is not found in the dictionary. If more 
// than one key exists that matches the given value, returns the
// first one found. 
public K getKey(V value);

// Returns the number of key/value pairs currently stored 
// in the dictionary
public int size();

// Returns true if the dictionary is at max capacity
public boolean isFull();

// Returns true if the dictionary is empty
public boolean isEmpty();

// Returns the Dictionary object to an empty state.
public void clear();

// Returns an Iterator of the keys in the dictionary, in ascending
// sorted order. The iterator must be fail-fast.
public Iterator<K> keys();

// Returns an Iterator of the values in the dictionary. The
// order of the values must match the order of the keys. 
// The iterator must be fail-fast. 
public Iterator<V> values();

}

The DictionaryADT must be implemented in four ways:

• Binary Search Tree
• HashTable with chaining
• Ordered Array
• Red/Black Tree

For the first three implementations, you must write your own code. For the fourth implementation, the RedBlackTree, you will use the Java API class java.util.TreeMap, which is an implementation using a Red/Black tree. For the fourth implementation only, you may use any class in the Java API.

In your LatinDictionary class, you will instantiate an instance of DictionaryADT and hardcode your HashTable class:

1
2
3
4

DictionaryADT<String,String> dictionary;

    ...
    dictionary = new HashTable<String,String>(maxSize); // in the constructor

Although you are hardcoding the HashTable in your LatinDictionary class, all four implementations should work identically with the application. Your DictionaryADT and your implementations must be in a package named data_structures.

Project Files

Your project will consist of the following files. You must use exactly these filenames.

• LatinDictionary.java The application program.
• Latin.txt The datafile, a text file containing Latin words and their definitions. The words do not occur in sorted order in the datafile. (provided)
• DictionaryReader.java Helper class to read the datafile. (provided)
• DictionaryEntry.java Helper class, a wrapper class to provide a single array that has both keys and values. (provided)
• DictionaryADT.java The dictionary interface. (provided)
• BinarySearchTree.java The binary search tree implementation of the DictionaryADT.
• HashTable.java The hash table implementation of the DictionaryADT. You must using chaining.
• UnorderedList.java A standard unordered linked list used for your hash table implementation. (Use your list class from project #2).
• OrderedArrayDictionary.java An ordered array implementations of the DictionaryADT.
• RedBlackTree.java The red/black tree implementation of the DictionaryADT. Use the Java TreeMap class.

The files DictionaryADT.java, BinarySearchTree.java, HashTable.java, UnorderedList.java, OrderedArrayDictionary.java, and RedBlackTree.java must be in a package named data_structures.

Project Submission

As with the previous assignments, you must place all of the files for your project that were not supplied in your handin/prog3 subdirectory. Please remember that the names of your files must match the specifications here.

Do not make a data_structures folder in your handin subdirectory.

IMPORTANT: As the due date falls at the end of the semester, there will be no opportunity for resubmission of your project. Please be certain that you have created and submitted your files correctly. If you have questions, please seek help from me.

Submit printed copy of your report only. Do NOT submit printouts of your Java source code files.