java实现数据结构06.01（集合详解代码之自定义基于二分搜索树的集合）

末蓝、 2023-06-23 03:54 23阅读 0赞

## 阅读此文章前请先阅读[java实现数据结构05（二分搜索树详解代码之自定义二分搜索树）][java_05] ##

## 自定义集合接口 ##

/**
     * @description: 集合接口
     * @author: liangrui
     * @create: 2019-12-17 10:56
     **/
    public interface Set<E> {
    
        /**
         * 添加元素
         * @param e 添加的元素
         */
        void add(E e);
    
        /**
         * 删除元素
         * @param e 删除的元素
         */
        void remove(E e);
    
        /**
         * 获取集合元素个数
         * @return 返回元素集合
         */
        int getSize();
    
        /**
         * 查询集合中是否存在某元素
         * @param e 查询的元素
         * @return 存在返回true，不存在返回false
         */
        boolean contains(E e);
    
        /**
         * 查看集合是否为空
         * @return 为空返回true，不为空返回false
         */
        boolean isEmpty();
    }

## 基于二分搜索树创建的集合 ##

/**
     * @description: 基于二分搜索树创建的集合
     * @author: liangrui
     * @create: 2019-12-17 11:01
     **/
    public class BSTSet<E extends Comparable<E>> implements Set<E> {
    
        private BinarySearchTree<E> binarySearchTree;
    
        public BSTSet(){
            binarySearchTree=new BinarySearchTree<>();
        }
    
        @Override
        public void add(E e) {
            binarySearchTree.add(e);
        }
    
        @Override
        public void remove(E e) {
            binarySearchTree.remove(e);
        }
    
        @Override
        public int getSize() {
            return binarySearchTree.getSize();
        }
    
        @Override
        public boolean contains(E e) {
            return binarySearchTree.contains(e);
        }
    
        @Override
        public boolean isEmpty() {
            return binarySearchTree.isEmpty();
        }
    }

## 自定义文件操作类： ##

自定义文件操作类，将txt文件中的单词存入自定义数组中，了解自定义数组可先阅读文章[java实现数据结构01(数组详解代码之自定义数组)][java_01]

import java.io.FileInputStream;
    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, Array<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;
            }
    
            // 简单分词
            // 这个分词方式相对简陋, 没有考虑很多文本处理中的特殊问题
            // 在这里只做demo展示用
            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.addLast(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 ++ ){
                //Character.isLetter()判断字符是否为字母
                if(Character.isLetter(s.charAt(i))){
                    return i;
                }
            }
            return s.length();
        }
    }

## main测试： ##

public class Main {
    
        public static void main(String[] args) {
            System.out.println("pride-and-prejudice");
            Array<String> array=new Array<>();
            FileOperation.readFile("pride-and-prejudice.txt",array);
            System.out.println("Total words:"+array.getSize());
    
            BSTSet<String> bstSet=new BSTSet<>();
            for (int i = 0; i < array.getSize(); i++) {
                bstSet.add(array.get(i));
            }
            System.out.println("Different words:"+bstSet.getSize());
        }
    }

## 测试结果： ##

> pride-and-prejudice  
> Total words:125901  
> Different words:6530

## pride-and-prejudice.txt文件（傲慢与偏见）随便一个txt文件都可以测试（必须为英文） ##

[java_05]: https://blog.csdn.net/liangruilz/article/details/103572142
[java_01]: https://blog.csdn.net/liangruilz/article/details/103430382