0
public class LinkedList {

 Object contents;
 LinkedList next = null;

public boolean equals(Object item) {
   return (this == item) || ((item instanceof LinkedList) &&  this.equals((LinkedList)item)); 
  }

 public boolean equals(LinkedList item) { 
   return myUtil.equals(this.contents, item.contents) && myUtil.equals(this.next, item.next); 
 }

} 

public class myUtil{
  public static boolean equals(Object x, Object y) {
    return (x == y) || (x != null && x.equals(y));
 }
}

main(){
 LinkedList myList = new LinkedList();
 myList.next = new LinkedList();
 LinkedList head = myList.next;
 myList.next = head;
}

我想我在这里创建了一个循环链表。所以我所做的是覆盖equals方法以确保处理循环引用:

由于某种原因 LinkedList.equals 似乎没有返回......是因为我的循环链表,还是我错过了一些条件?

4

5 回答 5

2

此代码的主要问题是您的比较不会在循环引用时终止,并且如果所有内容字段都相等,则将永远循环。它将一直持续到下一个比较,并且由于下一个项目始终存在(因为它是一个圆圈),这将永远持续下去。

myUtil.equals(this.contents, item.contents) && myUtil.equals(this.next, item.next);

要解决此问题,最简单的方法是为每个列表项添加一个布尔私有“已访问”字段。比较时,对比较后的每一项设置visited。如果两者都没有访问过并且相同,则继续。如果只访问一个,则您的列表不相同。如果两者都被访问,则您已经比较了整个列表的可达性。通常,在列表中包含循环是一个坏主意,并且存在专门用于检测它们的算法。这可能是一个令人困惑的话题。这是循环检测的覆盖范围,可以帮助您进一步了解问题。请记住,如果您使用访问字段,则必须在 equals() 中使用另一个循环取消设置所有这些字段,以使其再次运行。

另一方面,您没有为测试初始化​​列表节点的内容字段。这在这里没问题,因为它们被初始化为 null,但通常最好显式初始化所有字段。

一般来说,您也不需要equals(Object item)覆盖。尝试

public boolean equals(LinkedList item){
  if (this == item){
     return true; // It's the same object
  }

  // Add some null checks here, I'm lazy

  if (this.visited && item.visited && this.contents.equals(item.contents){
     this.visited = false; //Unset
     item.visited = false;
     return true;
  }
  if (this.visited && !item.visited){
      this.visited = false;
      return false;
  }
  if (!this.visited && item.visited){
      item.visited = false;
      return false;
  }
  if (!this.visited && !item.visited && this.visited.contents.equals(item.contents){
      this.visited = true;
      item.visited = true;
      boolean ret = this.next.equals(item.next);
      this.visited = false;
      item.visited = false;
      return ret;
  }

  // Contents not equal
  return false;
}

这会通过一些基本的递归来回溯和取消设置。我显然没有编译这个,但我认为这就是它的要点(我希望没有太多错误)

于 2012-06-20T14:18:39.833 回答
1

两个问题,首先你没有循环链表。以下代码创建 2 个列表,list1.next = list2,list2.next = null。没有创建圈子。

LinkedList myList = new LinkedList();
myList.next = new LinkedList();
LinkedList head = myList.next;
myList.next = head;

其次,如果你有一个循环链表,下面会产生一个无限循环,因为没有达到结束条件,这是因为在循环链接中,next不应该是null.

public boolean equals(Object item) {
  return (this == item) || ((item instanceof LinkedList) &&       
    this.equals((LinkedList)item)); 
}

public boolean equals(LinkedList item) { 
   return myUtil.equals(this.contents, item.contents) && myUtil.equals(this.next, item.next); 
}

为了有效地做到这一点,您需要提供一些机制来以非循环方式迭代列表,即使该机制是私有的并且不向其他用户公开。一种方法是将单个节点标记为“根”。

于 2012-06-20T14:16:50.087 回答
0
return myUtil.equals(this.contents, item.contents) 
&& myUtil.equals(this.next, item.next); 

我想这是您怀疑的问题,当您执行 && 的第二个表达式时,即myUtil.equals(this.next, item.next);输入执行此行的 myUtil.equals 方法:

return (x == y) || (x != null && x.equals(y));

它又使用x's .equals() 方法,它会重复它的过程item.next,依此类推,因为你有一个循环链表。

于 2012-06-20T14:10:18.703 回答
0

这将导致无限循环,这是因为在代码中:

public static boolean equals(Object x, Object y) {
        return (x == y) || (x != null && x.equals(y));
    }

x.equals(y)再次调用:

public boolean equals(LinkedList item) {
        return myUtil.equals(this.contents, item.contents)
                && myUtil.equals(this.next, item.next);
    }

但是如果你正在执行myList1.equals(myList1),你不会得到一个无限循环,因为(x==y)inmyUtils.equals()会返回true,所以如果你比较相同的对象,就不会发生无限循环。

但是,当您比较不同的对象时,您将进入无限循环。

这不是循环列表问题,这是因为您选择的代码设计。

于 2012-06-20T14:26:40.890 回答
0

终于完成了我的equals方法实现。为此,我不得不自己使用额外的检查工具。我不能说它是否有效,但检查了一些异常状态。

public boolean equals(Object o)
{
    if(!(o instanceof CircularlyLinkedList))
        return false;

    CircularlyLinkedList<E> list=(CircularlyLinkedList<E>)o;

    if(this==list)
        return true;

    if(size()!=list.size())
        return false;
    //tail element of this object
    Node<E> thisTail=tail;

    //tail element of list passing as parameter
    Node<E> listTail=list.tail;

    //checking if tail elements of both lists are the same or not. If not rotate list till equatation is provided for tails
    if(!thisTail.equals(listTail))
    {
        listTail = equate(list);
        if(listTail==null)
            return false;
    }

    //Each element checking
    for(int i=0; i<size(); i++)
    {
        thisTail=thisTail.next;
        listTail=listTail.next;

        if(!thisTail.equals(listTail))
        {
            listTail = equate(list);
            listTail=tail;
            i=0;
            if(listTail==null)
                return false;
        }
    }

    return true;
}

等价方法:

private Node<E> equate(CircularlyLinkedList<E> list)
{

    Node<E> thisTail=tail;
    Node<E> listTail;
    for(int i=0; i<list.size(); i++)
    {
        list.rotate();
        listTail=list.tail;

        //If full rotation completes then returns null
        if(list.getRotation()==0)
        {
            return null;
        }
        if(thisTail.equals(listTail))
        {
            return nodeList;
        }
    }

    return null;
}

getRotation方法返回旋转操作的计数并在 0 和size-1之间变化。我希望它会变得有用。

于 2020-04-13T16:36:55.363 回答