24-集合

一、用链表实现集合

Set类

package com.weyan.set;

public interface Set<E> {
    int size();
    boolean isEmpty();
    void clear();
    boolean contains(E element);
    void add(E element);
    void remove(E element);
    //遍历
    void traversal(Visitor<E> visitor);
    
    public static abstract class Visitor<E> {
        boolean stop;
        public abstract boolean visit(E element);
    }
}

---

ListSet类

package com.weyan.set;

import com.weyan.list.LinkedList;
import com.weyan.list.List;

public class ListSet<E> implements Set<E> {
    private List<E> list = new LinkedList<>();
    
    @Override
    public int size() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public boolean contains(E element) {
        return list.contains(element);
    }

    @Override
    //集合的性质：不添加重复的元素
    public void add(E element) {
//      if (list.contains(element)) return;
//      list.add(element);
        
        int index = list.indexOf(element);
        if (index != List.ELEMENT_NOT_FOUND) {//存在就覆盖
            list.set(index, element);
        }else {//不存在就添加
            list.add(element);
        }
    }
    
    @Override
    public void remove(E element) {
        int index = list.indexOf(element);
        if (index != List.ELEMENT_NOT_FOUND) {
            list.remove(index);
        }
    }

    @Override
    public void traversal(Visitor<E> visitor) {
        if (visitor == null) return;
        int size = list.size();
        for (int i = 0; i < size; i++) {
            if (visitor.visit(list.get(i))) return;
        }
    }

}

---

二、用红黑树实现集合

TreeSet类

package com.weyan.set;

import com.weyan.tree.RBTree;

public class TreeSet<E> implements Set<E> {
    private RBTree<E> tree = new RBTree<>();
    
    @Override
    public int size() {
        return tree.size();
    }

    @Override
    public boolean isEmpty() {
        return tree.isEmpty();
    }

    @Override
    public void clear() {
        tree.clear();
    }

    @Override
    public boolean contains(E element) {
        return tree.contains(element);
    }

    @Override
    public void add(E element) {
        tree.add(element);
    }

    @Override
    public void remove(E element) {
        tree.remove(element);
    }

    @Override
    public void traversal(Visitor<E> visitor) {
        tree.inorderTraversal();
    }

}

用红黑树实现集合(TreeSet)的局限性:

• 红黑树也是二叉搜索树，传入的元素要具备可比较性

---

三、查找文件当中代码的行树和单词的个数（不包括重复的单词）

工具类：FileInfo

package com.weyan.file;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileFilter;
import java.io.FileReader;
import java.io.IOException;

public class Files {
    
    /**
     * 读取文件内容
     * @param file
     * @return
     */
    public static FileInfo read(String file) {
        if (file == null) return null;
        FileInfo info = new FileInfo();
        StringBuilder sb = new StringBuilder();
        try (FileReader reader = new FileReader(file);
                BufferedReader br = new BufferedReader(reader)) {
            String line;
            while ((line = br.readLine()) != null) {
                sb.append(line).append("\n");
                info.setLines(info.getLines() + 1);
            }
            int len = sb.length();
            if (len > 0) {
                sb.deleteCharAt(len - 1);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        info.setFiles(info.getFiles() + 1);
        info.setContent(sb.toString());
        return info;
    }
    
    /**
     * 读取文件夹下面的文件内容
     * @param dir
     * @param extensions
     * @return
     */
    public static FileInfo read(String dir, String[] extensions) {
        if (dir == null) return null;
        
        File dirFile = new File(dir);
        if (!dirFile.exists()) return null;

        FileInfo info = new FileInfo();
        dirFile.listFiles(new FileFilter() {
            public boolean accept(File subFile) {
                String subFilepath = subFile.getAbsolutePath();
                if (subFile.isDirectory()) {
                    info.append(read(subFilepath, extensions));
                } else if (extensions != null && extensions.length > 0) {
                    for (String extension : extensions) {
                        if (subFilepath.endsWith("." + extension)) {
                            info.append(read(subFilepath));
                            break;
                        }
                    }
                } else {
                    info.append(read(subFilepath));
                }
                return false;
            }
        });
        return info;
    }
}

工具类：Files

package com.weyan.file;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileFilter;
import java.io.FileReader;
import java.io.IOException;

public class Files {
    
    /**
     * 读取文件内容
     * @param file
     * @return
     */
    public static FileInfo read(String file) {
        if (file == null) return null;
        FileInfo info = new FileInfo();
        StringBuilder sb = new StringBuilder();
        try (FileReader reader = new FileReader(file);
                BufferedReader br = new BufferedReader(reader)) {
            String line;
            while ((line = br.readLine()) != null) {
                sb.append(line).append("\n");
                info.setLines(info.getLines() + 1);
            }
            int len = sb.length();
            if (len > 0) {
                sb.deleteCharAt(len - 1);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        info.setFiles(info.getFiles() + 1);
        info.setContent(sb.toString());
        return info;
    }
    
    /**
     * 读取文件夹下面的文件内容
     * @param dir
     * @param extensions
     * @return
     */
    public static FileInfo read(String dir, String[] extensions) {
        if (dir == null) return null;
        
        File dirFile = new File(dir);
        if (!dirFile.exists()) return null;

        FileInfo info = new FileInfo();
        dirFile.listFiles(new FileFilter() {
            public boolean accept(File subFile) {
                String subFilepath = subFile.getAbsolutePath();
                if (subFile.isDirectory()) {
                    info.append(read(subFilepath, extensions));
                } else if (extensions != null && extensions.length > 0) {
                    for (String extension : extensions) {
                        if (subFilepath.endsWith("." + extension)) {
                            info.append(read(subFilepath));
                            break;
                        }
                    }
                } else {
                    info.append(read(subFilepath));
                }
                return false;
            }
        });
        return info;
    }
}

---

验证