词典的实现(3)--使用JAVA类库ArrayList实现Map数据结构

1，在词典的实现(2)-借助顺序表(数组)实现词典文章中使用了自定义的数组代替ArrayList，并实现了Map数据结构的基本功能。而借助JAVA类库ArrayList类的一些方法可以更加容易地实现Map。

2，实现思路如下

ArrayListDictionary.java 中定义了一个ArrayList的对象，该ArrayList对象用来存储Entry类的对象，而Entry类封装了(key，value)。这样，利用ArrayList类的一些方法来间接地操作(key,value)，从而实现各种词典的操作。

ArrayListDictionary.java 中部分代码解释如下：

public ArrayListDictionary(){

        listDictionary = new ArrayList<Entry>();

    }

在构造方法中初始化ArrayList对象。这样，每生成一个词典对象，就会有一个ArrayList对象。因为，每个词典对象都需要一个ArrayList对象来存储词典中的元素。

private class Entry{

        K key;

        V value;

私有内部类Entry用来封装(key,value)对，key 只有get方法没有set方法。因为对于词典而言，key是不能更改的。而value既有get方法又有set方法。

private class KeyIterator<S> implements Iterator<K>{

        Iterator<Entry> it = null;

        public KeyIterator(){

            it = listDictionary.iterator();

        }

        @Override

        public boolean hasNext() {

            return it.hasNext();

        }

        @Override

        public K next() {

            return  (K) it.next().getKey();

        }

        @Override

        public void remove() {

            throw new UnsupportedOperationException("can not remove a entry in iterator.unsupported");

        }

    }

私有内部类KeyIterator用来实现词典中键的迭代器。该迭代器的实现基于遍历Entry的迭代器，由于ArrayList存储Entry对象，因此可以借助ArrayList的iterator()方法很容易地得到遍历Entry的迭代器。在KeyIterator的构造方法中实例化遍历Entry对象的迭代器后，通过实现Iterator接口的三个方法来实现遍历词典的查找键的迭代器。

@Override

    public Iterator<K> getKeyIterator() {

        return new KeyIterator();

    }

ArrayListDictionary.java的getKeyIterator()方法返回一个遍历词典查找键的迭代器的对象。这样，ArrayListDictionary的对象就可以调用该方法来得到该迭代器了。

private int locateIndex(K key){

        int index = -1;

        Iterator<Entry> it = listDictionary.iterator();

        while(it.hasNext()){

            Entry e = it.next();//先获得每一个Map元素

            if(e.getKey().equals(key)){//依次与每一个Map元素的查找键比较

                index = listDictionary.indexOf(e);//获得给定的key匹配的Map元素在Arraylist中的位置

                break;

            }

        }

        return index;

    }

私有方法locateIndex(K key)，用来查找某个查找键在ArrayList数组中的哪个位置。由于ArrayList数组中存储的是Entry对象，因此先要通过遍历Entry的迭代器获得Entry对象，然后通过Entry类的getKey()方法来获得Entry对象的key属性。index 返回 –1 表示查找键key(所代表的Entry对象)不在ArrayList中。

public V remove(K key) {

        V  result = null;

        int index = locateIndex(key);

        if(index == -1){//key 不存在于ArrayList中

            result = null;

        }

        else{

            result = listDictionary.get(index).getValue();

            listDictionary.remove(index);

        }

        return result;

    }

remove()用来删除词典中的元素。其他的一些方法的功能可以参考DictionaryInterface.java中声明的方法解释。

整个完整的ArrayListDictionary.java实现如下

package dictionary;

import java.io.Serializable;

import java.util.ArrayList;

import java.util.Iterator;

public class ArrayListDictionary<K,V> implements DictionaryInterface<K, V>,Serializable {

    private static final long serialVersionUID = 1L;

    ArrayList<Entry> listDictionary = null;

    public ArrayListDictionary(){

        listDictionary = new ArrayList<Entry>();

    }

    private class Entry{

        K key;

        V value;

        private Entry(K key, V value){

            this.key = key;

            this.value = value;

        }

        public K getKey() {

            return key;

        }

        public V getValue() {

            return value;

        }

        public void setValue(V value) {

            this.value = value;

        }

    }

    private class KeyIterator<S> implements Iterator<K>{

        Iterator<Entry> it = null;

        public KeyIterator(){

            it = listDictionary.iterator();

        }

        @Override

        public boolean hasNext() {

            return it.hasNext();

        }

        @Override

        public K next() {

            return  (K) it.next().getKey();

        }

        @Override

        public void remove() {

            throw new UnsupportedOperationException("can not remove a entry in iterator.unsupported");

        }

    }

    private class ValueIterator<V> implements Iterator<V>{

        Iterator<Entry> it = null;

        public ValueIterator(){

            it = listDictionary.iterator();

        }

        @Override

        public boolean hasNext() {

            return it.hasNext();

        }

        @Override

        public V next() {

            return (V) it.next().getValue();

        }

        @Override

        public void remove() {

            throw new UnsupportedOperationException();

        }

    }

    //返回指定的查找键所代表的元素在arraylist中的位置

    private int locateIndex(K key){

        int index = -1;

        Iterator<Entry> it = listDictionary.iterator();

        while(it.hasNext()){

            Entry e = it.next();//先获得每一个Map元素

            if(e.getKey().equals(key)){//依次与每一个Map元素的查找键比较

                index = listDictionary.indexOf(e);//获得给定的key匹配的Map元素在Arraylist中的位置

                break;

            }

        }

        return index;

    }

    @Override

    public V add(K key, V value) {

        V result = null;

        int index = locateIndex(key);

        if(index == -1){//key 不在ArrayList中

            listDictionary.add(new Entry(key, value));

        }

        else{

            //这里index不会为-1，所以 get(index)不会抛出IndexOutOfBoundsException

            result = listDictionary.get(index).getValue();

            listDictionary.get(index).setValue(value);//调用Entry内部类中的setValue方法更新Entry的Value

        }

        return result;

    }

    @Override

    public V remove(K key) {

        V  result = null;

        int index = locateIndex(key);

        if(index == -1){//key 不存在于ArrayList中

            result = null;

        }

        else{

            result = listDictionary.get(index).getValue();

            listDictionary.remove(index);

        }

        return result;

    }

    @Override

    public V getValue(K key) {

        V result = null;

        int index = locateIndex(key);

        try{

            result = listDictionary.get(index).getValue();//当index=-1时，表示key不存在

        }catch(IndexOutOfBoundsException e){//index = -1时抛出异常

            result = null;

        }

        return result;

    }

    @Override

    public boolean contains(K key) {

        boolean result = false;

        Iterator<Entry> it = listDictionary.iterator();

        while(it.hasNext()){

            Entry e = it.next();

            if(e.getKey().equals(key)){

                result = true;

                break;

            }

        }

        return result;

    }

    @Override

    public Iterator<K> getKeyIterator() {

        return new KeyIterator();

    }

    @Override

    public Iterator<V> getValueIterator() {

        return new ValueIterator();

    }

    @Override

    public boolean isEmpty() {

        return listDictionary.isEmpty();

    }

    @Override

    public boolean isFull() {

        return false;

    }

    @Override

    public int getSize() {

        return listDictionary.size();

    }

    @Override

    public void clear() {

        listDictionary.clear();

    }

}

在实现完词典后，以下写了个测试程序借且词典来统计单词的个数。思路如下：

文本文件word.txt中存放待统计的单词，词典客户端程序PrintWordsFrequency.java 提供word.txt，然后查看每个单词出现的次数。

词典表FrequencyCounterDictionary.java负责统计word.txt中的单词并将结果存储到Map词典中，并实现对词典的遍历(display())。

PrintWordsFrequency.java 代码如下：

package dictionary.common;

package dictionary.client;

import java.io.File;

import java.io.FileNotFoundException;

import java.io.IOException;

import java.util.Scanner;

import dictionary.common.FrequencyCounterDictionary;

public class PrintWordsFrequency {

    public static void main(String[] args) {

        FrequencyCounterDictionary wordCounter = new FrequencyCounterDictionary();

        String fileName = "word.txt";//存放单词的文本文件，统计其中的单词出现次数

        try{

            Scanner data = new Scanner(new File(fileName));

            wordCounter.readFile(data);

        }catch(FileNotFoundException e){

            System.out.println("File not found: " + e.getMessage());

        }catch(IOException e){

            System.out.println("I/O error" + e.getMessage());

        }

        wordCounter.display();

        System.out.println("Bye");

    }

}

FrequencyCounterDictionary.java代码如下：

package dictionary.common;

import java.util.Iterator;

import java.util.Scanner;

import dictionary.ArrayListDictionary;

import dictionary.DictionaryInterface;

public class FrequencyCounterDictionary {

    private DictionaryInterface<String, Integer> wordTable;

    public FrequencyCounterDictionary(){

        wordTable = new ArrayListDictionary<String, Integer>();

    }

    public void readFile(Scanner data){

        data.useDelimiter("\\W+");

        while(data.hasNext()){

            String nextWord = data.next();//从Scanner打开的输入流中读取单词

            nextWord.toLowerCase();

            Integer frequency = wordTable.getValue(nextWord);//判断该单词在词典中已出现的次数

            if(frequency == null){//单词从未出现过

                wordTable.add(nextWord, new Integer(1));//将其出现次数置 1

            }

            else//单词已经在词典中

            {

                frequency++;//出现次数增 1

                wordTable.add(nextWord, frequency);

            }

        }//end while

        data.close();

    }

    public void display(){

        Iterator<String> keyIterator = wordTable.getKeyIterator();

        Iterator<Integer> valueIterator = wordTable.getValueIterator();

        while(keyIterator.hasNext()){

            System.out.println(keyIterator.next() + " : " + valueIterator.next());

    }

    }

}

运行结果

文本文件内容如下：

巴特西

词典的实现(3)--使用JAVA类库ArrayList实现Map数据结构

最新文章

热门文章