資料結構之Java實作底層Set

Set也是一種重要資料結構，其特點為不允許出現重複元素，不保證集合中的元素順序，可以有元素為null但隻允許出現一次。首先定義了一個Set接口，根據前面幾篇文章實作的連結清單和二分搜尋樹實作Set資料結構，下面是實作過程

Set接口

public interface Set<E> {

 void add(E e);   //添加一個元素

 void remove(E e);  //删除一個元素

 boolean contain(E e);//判斷是否包含元素

 int getSize();   //擷取集合大小

 boolean isEmpty();  //判斷是否為空

}

1.連結清單實作Set,可以保證元素的順序，主要注意避免重複元素

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 void add(E e){

        if(!list.contain(e))    //避免重複元素

            list.addFirst(e);

    }

    @Override

    public boolean contain(E e){

        return list.contain(e);

    }

    @Override

    public void remove(E e){

       list.removeElement(e);

    }

}

2.二分搜尋樹實作Set,可以保證元素的唯一性

public class BSTSet<E extends Comparable<E>> implements Set<E>{

 private BST<E> bst;

 public BSTSet() {

  bst = new BST<>();

 }

 @Override

 public void add(E e) {

  bst.add(e);

 }

 @Override

 public void remove(E e) {

  bst.remove(e);

 }

 @Override

 public boolean contain(E e) {

  return bst.contain(e);

 }

 @Override

 public int getSize() {

  return bst.size();

 }

 @Override

 public boolean isEmpty() {

  return bst.isEmpty();

 }

}

由于前面自己實作了連結清單(https://blog.csdn.net/zhangjun62/article/details/82758823)和二分搜尋樹(https://blog.csdn.net/zhangjun62/article/details/82766695)這兩個資料結構，是以實作Set集合比較容易.對于LinkedListSet 增、查、改時間複雜度都為O(n)， 對于BSTSet 增、查、改時間複雜度為O(h),其中h為樹的高度，二叉樹元素最多的情況是滿二叉樹, 滿二叉樹每一層元素個數為2 ^( h - 1)(h = 0, 1, 2,..., h), 根據等比數列求和可知總的元素個數n = 2 ^ h - 1, 是以h為以2底n + 1的對數，是以BST增、查、改時間複雜度O(h) = O(log n), 優于LinkedListSet.寫了一個測試用例，比較兩者耗時操作，下面是比較讀取檔案文本内容并統計詞彙量的耗時測試程式。首先實作讀取檔案的工具類

public class FileOperation {

    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;

    }

    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();

    }

}

下面是測試程式，文本是傲慢與偏見英文版

public class Main {

 private static double testSet(Set<String> set, String filename) {

  long startTime = System.nanoTime();

  System.out.println(filename);

  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 = "pride-and-prejudice.txt";

  BSTSet<String> bstSet = new BSTSet<>();

  double time1 = testSet(bstSet, filename);

  System.out.println("BST Set: " + time1 + " s");

  System.out.println();

  LinkedListSet<String> linkedListSet = new LinkedListSet<>();

  double time2 = testSet(linkedListSet, filename);

  System.out.println("Linked List Set: " + time2 + " s");

 }

}

每個人電腦組態和性能不一樣，時間會不同，但兩者差異還是會有展現的，以下是測試結果

這個結果表明二分搜尋樹實作的Set的時間複雜度确實優于連結清單實作的Set,以上整個過程就實作Set基本功能。