0

ブール値メソッド isSubset を作成しようとしています (セット A のすべての要素がセット B にある場合はブール値を返し、それ以外の場合は false を返します)。メソッド呼び出しはこのように記述できますsetA.subsetOf(setB)。私の考えは、setA の各要素を抽出し、それを setB と比較することです。setA の最初の要素が setB のいずれかと一致する場合は、setA の次の要素に進んで確認します。setA のすべての要素が setB のいずれかの要素と一致する場合、メソッドは true を返します。そうでない場合 (setA のすべての要素が setB にあるとは限りません)、false を返します。次のように、リンクされたリストに要素が含まれているかどうかを確認するメソッドを既に作成しました。

  public boolean contain (Object target) {
      boolean status = false;
      Node cursor;
      for (cursor = head; cursor.getNext() != null; cursor = cursor.getNext()) {
          if (target.equals(cursor.getElement())) 
              status = true;
      }   
      return status;
  }

リンクされたリスト操作の構文についてまだ混乱しているので、私の質問は、各要素を抽出して残りを行う方法です。どんな助けでも大歓迎です。ノードが宣言されています

  public Node(Object o, Node n) {
    element = o;
    next = n;
  }

SLinkedList

  public SLinkedList() {
    head = new Node(null, null); // create a dummy head
    size = 0;
  }
4

2 に答える 2

0

まず、containメソッドには小さなバグがあります。for条件は。であるcursor.getNext() != null;必要がありますcursor != null;。そうすることで、空のセットの検索（コードがクラッシュする原因となる）を防ぎ、リストの最後のノードを検索できるようにします。return status;後に実行した場合、コードはより高速に実行されますstatus=true;

isSubsetの構造は、作成したループと非常によく似ています。ループは次のようになります。

for(cursor = head; cursor!=null; cursor.getNext()){
  if(setB.contain(cursor.getElement()) == false){
    return false;
  }
}
于 2013-01-28T00:17:22.653 に答える
0

セット A がセット B のサブセットであるかどうかをチェックするロジックは正しいです。「各要素を抽出する方法」を尋ねましたが、コードはcontain、リンクされたリストをトラバースする方法を既に知っていることを示しています。したがって、同じ方法でセット A をsetB.contain(cursor)トラバースし、トラバースする各要素を呼び出すだけです。いずれかの要素に対して false を返す場合は、すぐに false を返します。

この方法の問題点は、リストが大きい場合に非常に遅くなることです。あなたはプログラミングが初めてで、「big O」表記について聞いたことがないかもしれません。これは、入力データのサイズが変化したときにアルゴリズムのパフォーマンスがどのように変化するかを説明する方法です。メソッドsubsetOfは O(n^2) になります。setBリンクされたリストではなくハッシュセットに格納されている場合は、O(n) になり、はるかに優れています。

このトピックの詳細については、http: //en.wikipedia.org/wiki/Time_complexityを参照してください。

于 2013-01-27T23:28:55.560 に答える