Java方法等于循环列表

Question

这是我的 Element 的代码类:

public class Element<T> {
    Element<T> next;
    Element<T> previous;
    T info;
}

... 和 CircularList :

public class CircularList<T> {
    Element<T> first=null;

    public void add(Element<T> e){
        if (first==null){
            first=e;
            e.next=e;
            e.previous=e;
        } 
        else { //add to the end;
            first.previous.next=e;
            e.previous = first.previous;
            first.previous=e;
            e.next=first;
        }
    }

    public boolean equals(Object o){
        // TODO
    }
}

我不知道如何为一个循环列表创建一个equals方法...

只检查是否o instanceof CircularList<T> ？？ (如果!返回 false else true？)嗯..不知道该怎么做:(

我(从学校)知道我必须检查 3 个条件:

if this == o return true
if o == null return false
if !o instanceof CircularList<T> return false

...

我现在不知道是否必须检查 list1 中的元素至 o , 与 while ...帮帮我 :)

是一项大学测试，我无法修改或向元素类添加方法。我只需要实现 equals来自 CircularList<T> 的方法上课!

Answer 1

我认为关键点在于列表是循环。因此，我假设列表

A, B, C, D, E 
   B, C, D, E, A

应该被视为相等。因为他们是。当你旋转一个圆时，它仍然是一个圆。

所以我猜诀窍是检查另一个列表的每个元素，并在从这个元素开始时查看列表是否相等。在上面的例子中，一个人会测试

• 是列表B, C, D, E, A等于A, B, C, D, E ？没有
• 是列表C, D, E, A, B等于A, B, C, D, E ？没有
• 是列表D, E, A, B, C等于A, B, C, D, E ？没有
• 是列表E, A, B, C, D等于A, B, C, D, E ？没有
• 是列表A, B, C, D, E等于A, B, C, D, E ？是的。最后。

通过一些测试用例快速实现，我希望涵盖最重要的用例:

public class CircularListEquality {
    public static void main(String[] args) {

        CircularList<String> c0 = createList("A", "B", "C", "D", "E");
        CircularList<String> c1 = createList("A", "B", "C", "D");
        CircularList<String> c2 = createList(     "B", "C", "D", "E");
        CircularList<String> c3 = createList(     "B", "C", "D", "E", "A");

        CircularList<String> c4 = createList("A", "B", "C", "A", "B", "C");
        CircularList<String> c5 = createList("A", "B", "C");

        CircularList<String> c6 = createList("A");
        CircularList<String> c7 = createList("A", "A", "B", "C");

        test(c0, c1, false);
        test(c0, c2, false);
        test(c1, c2, false);
        test(c0, c3, true);
        test(c3, c0, true);
        test(c4, c5, false);
        test(c5, c4, false);
        test(c6, c7, false);
    }

    private static <T> void test(
        CircularList<T> c0, CircularList<T> c1, boolean expected) {
        boolean actual = c0.equals(c1);
        if (actual == expected) {
            System.out.print("PASSED");
        } else {
            System.out.print("FAILED");
        }
        System.out.println(" for " + toString(c0) + " and " + toString(c1));
    }

    private static <T> String toString(CircularList<T> c) {
        StringBuilder sb = new StringBuilder();
        Element<T> current = c.first;
        while (true) {
            sb.append(String.valueOf(current.info));
            current = current.next;
            if (current == c.first) {
                break;
            } else {
                sb.append(", ");
            }
        }
        return sb.toString();
    }

    private static CircularList<String> createList(String... elements) {
        CircularList<String> c = new CircularList<String>();
        for (String e : elements) {
            c.add(createElement(e));
        }
        return c;
    }

    private static <T> Element<T> createElement(T t) {
        Element<T> e = new Element<T>();
        e.info = t;
        return e;
    }
}

class Element<T> {
    Element<T> next;
    Element<T> previous;
    T info;
}

class CircularList<T> {
    Element<T> first = null;

    public void add(Element<T> e) {
        if (first == null) {
            first = e;
            e.next = e;
            e.previous = e;
        } else { // add to the end;
            first.previous.next = e;
            e.previous = first.previous;
            first.previous = e;
            e.next = first;
        }
    }

    public boolean equals(Object object) {
        if (this == object)
        {
            return true;
        }
        if (object == null)
        {
            return false;
        }
        if (!(object instanceof CircularList<?>))
        {
            return false;
        }
        CircularList<?> that = (CircularList<?>) object;

        Element<?> first0 = first;
        Element<?> current0 = first0;
        Element<?> first1 = that.first;
        Element<?> current1 = first1;
        while (true) {
            if (equalSequence(current0, current0, current1, current1)) {
                return true;
            }
            current1 = current1.next;
            if (current1 == first1) {
                return false;
            }
        }
    }

    private static boolean equalSequence(
        Element<?> first0, Element<?> current0,
        Element<?> first1, Element<?> current1) {
        while (true) {
            if (!equalElements(current0, current1)) {
                return false;
            }
            current0 = current0.next;
            current1 = current1.next;
            if (current0 == first0 && current1 == first1) {
                return true;
            }
            if (current0 == first0) {
                return false;
            }
            if (current1 == first1) {
                return false;
            }
        }
    }

    private static boolean equalElements(Element<?> t0, Element<?> t1) {
        if (t0 == null) {
            return t1 == null;
        }
        return equal(t0.info, t1.info);
    }

    private static <T> boolean equal(T t0, T t1) {
        if (t0 == null) {
            return t1 == null;
        }
        return t0.equals(t1);
    }
}

(编辑:添加了另一个测试用例)