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

作者: Ice_spring | 来源:发表于2019-07-31 21:57 被阅读10次

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

集合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的高度是log_2n,故BSTSet的平均时间复杂度是O(log_2n),这是远远优于O(n)的。如果Set是基于平衡二叉树来实现,则最坏情况复杂度也是O(log_2n),这实际上就是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();
    }
}

提交,获得通过!

相关文章

  • Tourist with Data Structure Thir

    探索哈希表 概念 哈希集合:哈希集合是集合数据结构的实现之一,用于存储非重复值。哈希映射 :哈希映射是映射数据结构...

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

    本篇主要内容:集合及其应用 集合Set 数学上定义集合有最基本的三个性质:确定性、互异性和无序性。所谓确定性就是一...

  • 复习

    数据结构 数据结构 集合常见数据结构:集合,链表,队列,数组,栈,映射java中:List列表,Set集合,Map...

  • 映射、元组、集合

    映射 元组 集合 集合之seq 集合之set 集合之map

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

    本篇主要内容:映射Map及其实现,Map的应用,Map与Set的对比 映射Map 数据结构里的所谓映射是键值对的数...

  • Map、WeakMap、Set、WeakSet

    ES6引入了四种新的数据结构:映射(Map)、集合(Set)、弱集合(WeakSet)和弱映射(WeakMap) ...

  • 数据结构之集合和映射

    基于二分搜索树的集合实现 集合(Set)的基础概念: 数据结构中的集合概念与数学中的集合概念是一样的,集合中的元素...

  • 非线程安全集合浅谈

    Java 的集合框架大体分为四种数据结构——线性表、映射表、集合、队列。 集合框架分析 Collection 接口...

  • Java集合干货系列-集合总体大纲

    前言 Java集合是java提供的工具包,包含了常用的数据结构:集合、链表、队列、栈、数组、映射等。Java集合工...

  • Vector

    Java集合 Java集合是java提供的工具包,包含了常用的数据结构:集合、链表、队列、栈、数组、映射等。Jav...

网友评论

    本文标题:数据结构之集合与映射(一)

    本文链接:https://www.haomeiwen.com/subject/xgdxdctx.html