在 Java 中检查两个链表之间的子集

Question

>我正在尝试编写一个布尔方法 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;
  }

Answer 1

首先，你的包含方法有一个小错误。条件cursor.getNext() != null;应cursor != null;。这样做可以防止搜索空集（这会导致代码崩溃），也可以防止搜索列表中的最后一个节点。如果您在status=true;后执行return status;，您的代码会运行得更快

isSubset 的结构与您创建的循环非常相似;循环如下所示：

for(cursor = head; cursor!=null; cursor.getNext()){
  if(setB.contain(cursor.getElement()) == false){
    return false;
  }
}

Answer 2

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

以这种方式做事的问题在于，如果列表很大，它会非常慢。我猜你是编程新手，可能从未听说过"大O"符号。这是一种描述算法性能如何随着输入数据大小的变化而变化的方法。您的subsetOf方法将是 O（n^2）。如果setB存储在哈希集中而不是链表中，它将是 O（n），这要好得多。

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