前言：在第5章的系列學(xué)習(xí)中，已經(jīng)實(shí)現(xiàn)了關(guān)于二叉搜索樹的相關(guān)操作，詳情查看第5章即可。在本節(jié)中著重學(xué)習(xí)使用底層是我們已經(jīng)封裝好的二叉搜索樹相關(guān)操作來(lái)實(shí)現(xiàn)一個(gè)基本的集合（set）這種數(shù)據(jù)結(jié)構(gòu)。
集合set的特性:
集合Set存儲(chǔ)的元素是無(wú)序的、不可重復(fù)的。為了能達(dá)到這種特性就需要尋找可以作為支撐的底層數(shù)據(jù)結(jié)構(gòu)。
這里選用之前自己實(shí)現(xiàn)的二叉搜索樹，這是由于該二叉樹是不能盛放重復(fù)元素的。因此我們可以使用二叉搜索樹這種底層來(lái)實(shí)現(xiàn)集合(set)。

1、集合set相關(guān)功能

功能點(diǎn).png

1.1 add()方法特性

二分搜索樹的添加操作add：不能盛放重復(fù)元素

2. set應(yīng)用

典型應(yīng)用：1.客戶統(tǒng)計(jì) 2.詞匯量統(tǒng)計(jì)

3.集合實(shí)現(xiàn)

3.1 Set接口定義

/**
 * 集合的接口
 */
public interface Set<E> {
    void add(E e);//添加  <——<不能添加重復(fù)元素
    void remove(E e);//移除
    int  getSize();//獲取大小
    boolean isEmpty();//是否為空
    boolean contains(E e);//是否包含元素
    
}

3.2 基于二分搜索樹實(shí)現(xiàn)集合Set

//基于BST二分搜索樹實(shí)現(xiàn)的集合Set
public class BSTSet<E extends Comparable<E>> implements Set<E> {//元素E必須滿足可比較的
 
    //基于BST類的對(duì)象
    private BST<E> bst;
 
    //構(gòu)造函數(shù)
    public BSTSet() {
        bst = new BST<>();
    }
 
    //返回集合大小
    @Override
    public int getSize() {
        return bst.size();
    }
 
    //返回集合是否為空
    @Override
    public boolean isEmpty() {
        return bst.isEmpty();
    }
 
    //Set添加元素
    @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);
    }
}

3.3測(cè)試：兩本名著的詞匯量 和不重復(fù)的詞匯量

public static void main(String[] args) {
 
        System.out.println("Pride and Prejudice");
        //新建一個(gè)ArrayList存放單詞
        ArrayList<String> words1=new ArrayList<>();
        //通過這個(gè)方法將書中所以單詞存入word1中
        FileOperation.readFile("pride-and-prejudice.txt",words1);
        System.out.println("Total words : "+words1.size());
 
        BSTSet<String> set1=new BSTSet<>();
        //增強(qiáng)for循環(huán)，定一個(gè)字符串word去遍歷words
        //底層的話會(huì)把ArrayList words1中的值一個(gè)一個(gè)的賦值給word
        for(String word:words1)
            set1.add(word);//不添加重復(fù)元素
        System.out.println("Total  different words : "+set1.getSize());
 
        System.out.println("-------------------");
        System.out.println("Pride and Prejudice");
        //新建一個(gè)ArrayList存放單詞
        ArrayList<String> words2=new ArrayList<>();
        //通過這個(gè)方法將書中所以單詞存入word1中
        FileOperation.readFile("a-tale-of-two-cities.txt",words2);
        System.out.println("Total words : "+words2.size());
 
        BSTSet<String> set2=new BSTSet<>();
        //增強(qiáng)for循環(huán)，定一個(gè)字符串word去遍歷words
        //底層的話會(huì)把ArrayList words1中的值一個(gè)一個(gè)的賦值給word
        for(String word:words2)
            set2.add(word);//不添加重復(fù)元素
        System.out.println("Total  different words : "+set2.getSize());
    }

結(jié)果：

image.png

這里需要說明一下就是關(guān)于我們統(tǒng)計(jì)的單詞數(shù)只考慮了每個(gè)單詞組成的不用，并沒有對(duì)單詞的特殊形式做區(qū)分。

在下一小節(jié)中繼續(xù)學(xué)習(xí)【集合和映射--集合Set->底層基于鏈表實(shí)現(xiàn)】。

點(diǎn)贊是最好的支持，關(guān)注是最大的鼓勵(lì)。親愛的朋友，很榮幸在簡(jiǎn)書遇到您。

源碼地址 https://github.com/FelixBin/dataStructure/tree/master/src/SetPart