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;
  }

链表

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

2 回答 2

0

您检查集合 A 是否是集合 B 的子集的逻辑是正确的。您问“如何提取每个元素”，但您的代码contain表明您已经知道如何遍历链表。因此，只需以相同的方式遍历集合 A，并调用setB.contain(cursor)您遍历的每个元素。如果对任何元素返回 false，则立即返回 false。

这样做的问题是如果列表很大，它会很慢。我猜您是编程新手，可能从未听说过“大 O”表示法。这是一种描述算法性能如何随着输入数据大小的变化而变化的方式。您的subsetOf方法将是 O(n^2)。如果setB存储在散列集而不是链表中，它将是 O(n)，这要好得多。

您可以在以下网址了解有关此主题的更多信息：http ://en.wikipedia.org/wiki/Time_complexity 。

于 2013-01-27T23:28:55.560 回答
0

首先，您的包含方法中有一个小错误。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 回答