数据结构之集合与映射(一)

本篇主要内容：集合及其应用

集合Set

数学上定义集合有最基本的三个性质：确定性、互异性和无序性。所谓确定性就是一个元素是否在这个集合中是确定的，互异性是一个集合中不能有相同的元素，无序性是打乱集合中元素的顺序集合还是这个集合。
在一般的数据结构教材中很少有讲解集合（Set）这种数据结构，不过理解集合这种数据结构是很必要的，它是一种高阶的数据结构，可以基于链表，二分搜索树等来实现。
在java语言中实现集合这种数据结构，首先写一个集合接口，集合可以由不同的方式实现：

'''Set.java'''
public interface Set<E> {
    void add(E e);
    void remove(E e);
    boolean contains(E e);
    int getSize();
    boolean isEmpty();
}

基于链表的实现
java提供的有链表类，不过为了加深对一些操作的理解，这里我们使用的是自己写的链表类，它能实现增删查改的基本功能，而且支持泛型：

'''LinkedList.java'''
public class LinkedList<E> {
    private class Node{
        //链表节点是链表内部类而且私有，用户不需知道底层如何,屏蔽实现细节
        public E e;
        public Node next;
        public Node(E e,Node next){
            this.e = e;
            this.next = next;
        }
        public Node(E e){
            this(e,null);
        }
        public Node(){
            this(null,null);
        }
        @Override
        public String toString(){
            return e.toString();
        }
    }

    private Node dummyhead;
    private int size;

    public LinkedList(){
        dummyhead = new Node(null,null);
        size = 0;
    }

    //获取链表中元素的个数
    public int getSize(){
        return size;
    }
    //返回链表是否为空
    public boolean isEmpty(){
        return size == 0;
    }
    //在链表的index(0-based)位置添加新的元素e
    //链表中不是常用操作，用作测试和练习
    public void add(int index, E e){
        if(index < 0||index > size)
            throw new IllegalArgumentException("Add failed, illegal index");
        else{
            Node prev =dummyhead;
            for(int i = 0;i<index;i++)
                prev = prev.next;

            Node node = new Node(e);
            node.next = prev.next;
            prev.next = node;
            //prev.next = new Node(e,prev.next);

            size ++;
        }
    }
    //链表头添加元素
    public void addFirst(E e){
        add(0,e);
    }
    //链表末尾添加元素e
    public void addLast(E e){
        add(size,e);
    }
    //链表中不是常用操作，用作测试和练习
    //获得链表的第index个元素
    public E get(int index){
        if(index < 0||index > size)
            throw new IllegalArgumentException("Add failed, illegal index");
        Node cur = dummyhead.next;
        for(int i=0;i<index;i++)
            cur = cur.next;
        return cur.e;
    }
    //获得链表的第一个元素
    public E getFirst(){
        return get(0);
    }
    //获得链表的最后一个元素
    public E getLast(){
        return get(size-1);
    }
    //修改index位置的元素为e
    //测试练习用
    public void set(int index,E e){
        //链表中不是常用操作，用作测试和练习
        if(index < 0||index > size)
            throw new IllegalArgumentException("Add failed, illegal index");
        Node cur = dummyhead.next;
        for(int i=0;i<index;i++)
            cur = cur.next;
        cur.e = e;
    }
    //查找链表是否存在元素e
    public boolean contains(E e){
        Node cur = dummyhead.next;
        while(cur != null){
            if(cur.e.equals(e))
                return true;
            cur = cur.next;
        }
        return false;
    }
    //删除index位置的元素,不常用，做练习和测试
    public E remove(int index){
        if(index < 0||index > size)
            throw new IllegalArgumentException("Add failed, illegal index");
        Node prev = dummyhead;
        for(int i=0;i<index;i++)
            prev = prev.next;
        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size --;

        return retNode.e;
    }
    //删除链表第一个元素
    public E removeFirst(){
        return remove(0);
    }
    //删除链表最后一个元素
    public E removeLast(){
        return remove(size-1);
    }
    //从链表中删除元素e
    public void removeElement(E e){
        Node prev = dummyhead;
        while(prev.next!=null){
            if(prev.next.e.equals(e))
                break;
            prev = prev.next;
        }
        if(prev.next!=null){
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size --;
        }
    }
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        Node cur = dummyhead.next;
        while(cur != null){
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL");
        return res.toString();
    }
}

然后基于链表实现我们的集合，集合支持泛型：

public class LinkedListSet<E> implements Set<E> {
    private LinkedList<E> list;
    public LinkedListSet(){
        list = new LinkedList<>();
    }
    @Override
    public int getSize(){
        return list.getSize();
    }
    @Override
    public boolean isEmpty(){
        return list.isEmpty();
    }
    @Override
    public boolean contains(E e){
        return list.contains(e);
    }
    @Override
    public void add(E e){
        if(!list.contains(e))
            list.addFirst(e);
    }
    @Override
    public void remove(E e){
        list.removeElement(e);
    }
}

可以发现在实现链表后，集合中的增删查操作只需调用它底层的链表相应操作就行。
基于BST的实现
BST的实现我们在《算法之美》系列文章递归的妙用中实现过了，这里不再重复，下面给出基于BST的Set：

public class BSTSet<E extends Comparable<E>> implements Set<E> {
    private BST<E> bst;
    public BSTSet(){
        bst = new BST<>();
    }
    @Override
    public int getSize(){
        return bst.size();
    }
    @Override
    public boolean isEmpty(){
        return bst.isEmpty();
    }
    @Override
    public void add(E e){
        bst.add(e);
    }
    @Override
    public boolean contains(E e){
        return bst.contains(e);
    }
    @Override
    public void remove(E e){
        bst.remove(e);
    }
}

虽然两种方式都能实现Set这种数据结构，但是两者的性能存在巨大差异，基于链表实现的Set性能要远远低于基于BST实现的Set，这是为什么呢？这涉及到链表和BST的时间复杂度分析：

操作\方式	链表Set	BSTSet
增	O(n)	O(h)
删	O(n)	O(h)
查	O(n)	O(h)

对于我们实现的链表Set来说，不难得出它的增删查时间复杂度都是O(n)，这里要说明的是本来链表的添加操作在头部时间复杂度仅为O(1)，不过集合要求互异性，所以添加元素时还要检查该元素是否已经存在，故最终添加操作的时间复杂度是O(n)。而对于BSTSet，它的时间复杂度和BST的深度有关，最坏的情况下BST会退化为链表，时间复杂度也会是O(n)，不过平均下来，BST的高度是，故BSTSet的平均时间复杂度是，这是远远优于O(n)的。如果Set是基于平衡二叉树来实现，则最坏情况复杂度也是，这实际上就是java中Set的实现方式。

---

集合的应用

文本词数统计

文本词数统计有很广泛的应用，比如词数统计可以用于书的难度分级，一本有10000个不同单词的书和一本有3000个不同单词的书显然不是一个难度级别。
现在我们就基于集合来实现一个txt英文小说词数统计的小程序。首先编写一个文件读取类，这个类用于做分词，将txt文本中英文单词提取出来并全部转为小写保存到String数组中：

import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Locale;
import java.io.File;
import java.io.BufferedInputStream;
import java.io.IOException;
public class FileOperation {

    // 读取filename中的内容，并将其中包含的所有词语放进words中
    public static boolean readFile(String filename, ArrayList<String> words){

        if (filename == null || words == null){
            System.out.println("filename is null or words is null");
            return false;
        }
        // 文件读取
        Scanner scanner;
        try {
            File file = new File(filename);
            if(file.exists()){
                FileInputStream fis = new FileInputStream(file);
                scanner = new Scanner(new BufferedInputStream(fis), "UTF-8");
                scanner.useLocale(Locale.ENGLISH);
            }
            else
                return false;
        }
        catch(IOException ioe){
            System.out.println("Cannot open " + filename);
            return false;
        }

        // 简单分词
        if (scanner.hasNextLine()) {

            String contents = scanner.useDelimiter("\\A").next();

            int start = firstCharacterIndex(contents, 0);
            for (int i = start + 1; i <= contents.length(); )
                if (i == contents.length() || !Character.isLetter(contents.charAt(i))) {
                    String word = contents.substring(start, i).toLowerCase();
                    words.add(word);
                    start = firstCharacterIndex(contents, i);
                    i = start + 1;
                } else
                    i++;
        }

        return true;
    }
    // 寻找字符串s中，从start的位置开始的第一个字母字符的位置
    private static int firstCharacterIndex(String s, int start){

        for( int i = start ; i < s.length() ; i ++ )
            if( Character.isLetter(s.charAt(i)) )
                return i;
        return s.length();
    }
}

这只是一个简单的分词过程，全部转换为小写后单词不同就算不同。有学过自然语言处理的可以更加细化一下分词过程，比如将名词的单复数算为一个单词，动词的原型ing、ed、第三人称单数算作一个单词......不过这就比较麻烦了，本文不再进行这样的处理。接下来使用我们的集合对Little Prince这部童话的英文版进行词数统计：

'''Main.java'''
import java.util.ArrayList;
//BST比链表实现的集合更加高效
public class Main {
    private static double testSet(Set<String> set,String filename){
        long startTime = System.nanoTime();
        System.out.println("Little Prince");
        ArrayList<String> words = new ArrayList<>();
        if ((FileOperation.readFile(filename, words))) {
            System.out.println("Total words: " + words.size());
            for (String word : words)
                set.add(word);
            System.out.println("Total different words: " + set.getSize());
        }
        long endTime = System.nanoTime();
        return (endTime - startTime)/1000000000.0;
    }
    public static void main(String[] args) {
        String filename = "little-prince.txt";
        LinkedListSet<String> linkedListSet = new LinkedListSet<>();
        double time2 = testSet(linkedListSet,filename);
        System.out.println(time2+"\n");

        BSTSet<String> bstSet = new BSTSet<>();
        double time1 = testSet(bstSet,filename);
        System.out.println(time1+"\n");

        }
}

在上面的代码中，我们用链表Set和BSTSet都进行了词数统计任务，并对它们的过程计时，运行结果如下：

词数统计

可以看到两种方式都给出了正确的词数统计，而且BSTSet方式明显用时更少。

LeetCode804——唯一摩尔斯密码词

接下来用集合来解决一道LeetCode上的题目，题目描述如下：

LeetCode804-1 LeetCode804-2

这里我们不再用自己的Set，而是用java中提供的TreeSet(底层是平衡二叉树，性能更好)来实现我们的Solution：

import java.util.TreeSet;

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] codes = {".-","-...","-.-.","-..",".","..-.","--.",
                "....","..",".---","-.-",".-..","--","-.","---",".--.",
                "--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        TreeSet<String> set = new TreeSet<>();
        for(String word:words){
            StringBuilder res = new StringBuilder();
            for(int i=0;i<word.length();i++)
                res.append(codes[word.charAt(i)-'a']);//当前字符对应的摩斯码存入res
            set.add(res.toString());
        }
        return set.size();
    }
}

提交，获得通过！