Java最下位実装チェーンテーブルと二分探索ツリーに基づくSet集合

セット
チェーンテーブルと二分探索ツリーに基づく
文書ディレクトリ

1、集合とは何か

2、集合クラスの実現——チェーンテーブル

に基づく

2.1、インタフェース関数実現

2.2、基本操作関数

2.3、増加元素

2.4、削除要素

2.5、クエリー要素

3、集合クラスの実装-二分探索ツリー

に基づく

3.1、基本操作関数

3.2、増加元素

3.3、削除要素

3.4、クエリー要素

4、時間複雑度分析

最後の

1、集合とは何か
数学的には、1つ以上の決定された要素からなる全体として定義される.しかし、コンピュータの分野では、集合は1つ以上の異なる要素からなる全体として定義される.すなわち,1つの集合の中の要素はすべて異なる.
これはこのような特性のためであり,比較的古典的なのは言語統計に用いられる.1つの文章にどれだけの語彙が使われているかを調べ,ユーザの読解難易度係数を判断する.
2、集合クラスの実現——チェーンテーブルに基づく
スタックやキューと同様に、他のデータ構造に基づいてクラスをカプセル化します.集合に関するインタフェースが必要ですチェーンテーブルの下部をカプセル化したため,具体的な関数法はLinkedListチェーンテーブルという文章を見ることができる.
2.1、インタフェース関数の実現
具体的な関数法は依然として4つの操作を追加削除して調べる.ここでは、インデックスの概念に関連していないため、操作を変更することはできません.インタフェース関数の実装:

public interface Set<E> {
    void add(E e);
    void remove(E e);
    boolean contains(E e);
    int getSize();
    boolean isEmpty();
}

2.2、基本操作関数
  以前にチェーンテーブルの下部をカプセル化したため、具体的な関数方法はLinkedListチェーンテーブルという文章を見ることができます.
プログラム実装:

@Override
public int getSize() {
    return linkedList.getSize();
}

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

2.3、元素を増加する
プログラム実装:

@Override
public void add(E e) {
    if (!linkedList.contains(e))   //        
        linkedList.addFirst(e);  //               
}

2.4、要素の削除
プログラム実装:

@Override
public void remove(E e) {
    linkedList.removeElement(e);
}

2.5、クエリー要素
プログラム実装:

@Override
public boolean contains(E e) {
    return linkedList.contains(e);
}

@Override
public int getSize() {
    return linkedList.getSize();
}

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

3、集合クラスの実現——二分探索ツリーに基づく
  我々は以前にチェーンテーブルの下部をカプセル化したので,具体的な関数法はBST二分探索ツリーという文章を見ることができる.
3.1、基本操作関数

@Override
public int getSize() {
    return bst.getSize();
}

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

3.2、元素を増やす
プログラム実装:

@Override
public void add(E e) {
    bst.add(e);
}

3.3、要素の削除
プログラム実装:

@Override
public void remove(E e) {
    bst.remove(e);
}

3.4、クエリー要素
プログラム実装:

@Override
public boolean contains(E e) {
    return bst.contains(e);
}

4、時間複雑度分析
私たちは上から見ることができて、私たちのこれらの方法はすべてとても紹介して、これも私たちの底のパッケージが良いためです.
要素を追加
要素の削除
クエリー要素
チェーンテーブル
O(N)
O(N)
O(N)
にぶんたんさくじゅ
O(log(N))
O(log(N))
O(log(N))
ここでは、チェーンテーブルに要素を追加するのはO(1)の複雑さではないかと聞くことができますが、実はそうではありません.それは、集合というデータ構造の中で、要素が重複しないことを保証する必要があります.まずチェーンテーブルを遍歴する必要があるので、複雑度はO(N)レベルです.
したがって,下位層の二分探索ツリーの性能はチェーンテーブルの実現よりはるかに高いことが表で分かる.
最後に
総じてこのようなデータ構造の集合は比較的簡単である.
もっとすばらしい内容、みんなは私のホームページに回ることができます:曲怪曲怪のホームページ
あるいは私の微信の公衆番号に注目します:TeaUrn
ソースアドレス:公衆番号内でデータ構造とアルゴリズムのソースコードを返信することができます.