2

假设我有对象 A、B、C、D。它们可以包含对彼此的引用，例如，A 可能引用 B 和 C，而 C 可能引用 A。我想创建段但不想创建两次，所以我不想要段 AC 和段 CA，只是其中 1 个。所以我想保留一个已创建段的列表，例如：AC，并检查我是否已经有一个 AC 或 CA，如果有则跳过它。

有没有可以做到这一点的数据结构？

谢谢

if(list.contains(a,b)
{
   //dont add
}
4

5 回答 5

2

你可以介绍类似的东西

class PairKey<T extends Comparable<T>> { 
  final T fst, snd;
  public PairKey(T a, T b) {
    if (a.compareTo(b) <=0 ) {
      fst = a;
      snd = b;
    } else {
      fst = b;
      snd = a;
    }
  }

  @Override
  public int hashCode() {
    return a.hashCode() & 37 & b.hashCode();
  }

  @Override
  public boolean equals(Object other) {
    if (other == this) return true;
    if (!(other instanceOf PairKey)) return false;
    PairKey<T> obj = (PairKey<T>) other;
    return (obj.fst.equals(fst) && obj.snd.equals(snd));
  }
}

那么您可以将边缘放入 HashSet < PairKey < ？extends Comparable> > 然后检查给定的对是否已经存在。

您需要使您的顶点具有可比性，因此可以将 PairKey(A,B) 视为等于 PairKey(B,A)

然后 HashSet 将为您完成剩下的工作，例如您将能够查询

pairs.contains(new PairKey(A,B));

如果对包含 PairKey(A,B) 或 PairKey(B,A) - 它将返回 true。

hashCode 实现可能略有不同，可能是 IDE 会生成更复杂的东西。

希望有帮助。

于 2012-10-07T17:31:40.150 回答
1

我会使用一个Pair看起来像这样的对象： 

class Pair  
{  
    Node start;  
    Node end;  

    public Pair(Node start, Node end)  
    { 
      this.start=start;
      this.end=end;  
    }  

   public Pair reverse()  
   {  
       return new Pair(end,start);  
   }  
}

现在您可以执行以下操作： 

if(pairs.contains(currentPair) || pairs.contains(currentPair.reverse())  
{  
    continue;
}  else{  
     pairs.add(currentPair);  
}

正如评论中所指出的，您将需要实现 equals 和 hashcode。但是，在纯 OO 中进行检查以使其与段的反转相匹配是一种不好的做法，因为。通过以注释中描述的方式实现 equals ，只会将 Pair 绑定到您的应用程序并删除它的可移植性。

于 2012-10-07T17:23:01.070 回答
0

您可以使用一组对象集。

Set<Set<MyObjectType>> segments = new HashSet<Set<MyObjectType>>();

然后您可以添加表示成对的二元素集MyObject。由于集合是无序的，如果segments包含具有 A 和 B 的集合，尝试添加包含 B 和 A 的集合会将其视为已存在于segments.

Set<MyObjectType> segment = new HashSet<MyObjectType>();
segment.add(A); // A and B are instances of MyObjectType
segment.add(B);
segments.add(segment);
segment = new HashSet<MyObjectType>();
segment.add(B);
segment.add(A);
segments.add(segment);
System.out.println("Number of segments: " + segments.size()); // prints 1
于 2012-10-07T17:21:26.240 回答
0

使用java.util.Set/java.util.HashSet并继续添加您找到的参考文献，例如

   Set set1 = new HashSet();
   set1.add(A), set1.Add(C), set1.Add(C)

您可以将此发现添加到外部集中，如finalSet.add(set1)

  Set<Set> finalSet = new HashSet<Set>();
  finalSet.add(set1);

这将自动过滤掉重复项，最后，您将只剩A & C下。

于 2012-10-07T17:22:15.800 回答
0

您的问题与图论有关。

您可以尝试删除该内部列表并创建一个所有对象共享的事件矩阵。

最终解决方案主要取决于任务目标和可用结构。因此，很难根据您提供的描述为您的问题选择最佳解决方案。

于 2012-10-07T17:34:05.803 回答