链接堆栈上浅拷贝的 J 单元测试失败

Question

我正在尝试为链接堆栈实现浅表复制，但我没有通过我的讲师提供的 J 单元测试。

我已经尝试实现一个 for 循环，它将从上到下循环遍历堆栈，并为每个节点创建一个对传递时新列表的引用。我添加了打印语句，数据引用似乎匹配，但我的测试仍然失败。

public class LinkedStack<E> implements Stack<E>{

private int size = 0;

// Unlike the book, we'll use an inner class for our Node.
// Its two data members can be accessed directly by the Stack
// code, so we don't need setters and getters.
protected class Node{

    E data; 
    Node next;
}

protected Node top; // not public, but can still be seen by other classes in the
                    // csci211 package.

/** Create an empty stack.
 * 
 */
public LinkedStack(){

    top = null;
}

@Override // see interface for comments.
public void push(E e){
    //TODO 75
    Node temp = new Node();
    temp.data = e;
    temp.next = top;
    top = temp;
}

@Override // see interface for comments.
public E pop(){
    if (top==null) {
        throw new NoSuchElementException("Cannout pop an Empty Stack.");
    }
    E topvar;
    topvar = top.data;
    top = top.next;
    return topvar;
}

@Override // see interface for comments.
public E peek() {
    if (top == null) {
        throw new NoSuchElementException("Cannout peek an Empty Stack.");
    }
    //E topvar;
    //topvar = top.data;
    return top.data;
}

/** Retrieve the number of elements on this stack.
 * 
 * @return an int containing the number of elements
 */ 
public int size() {

    return this.size;

}

/** An Iterator for our LinkedStack.
 * 
 * @author rhodes
 *
 */
 class LinkedStackIterator implements Iterator<E> {

    LinkedStack<E>.Node next;  // the book calls this "current"

    public LinkedStackIterator(LinkedStack<E> s){

        next = s.top;
    }

    @Override
    public boolean hasNext() {
        return top != null;
        //TODO 100
        //return false;
    }

    @Override
    public E next() {

        if (!hasNext()) throw new NoSuchElementException();
        E data = top.data;
        top = top.next; 
        return data;

        //TODO 100

        //return null;

    }


}


@Override
public void add(E element) {

    push(element);

}

@Override
public void clear() {

    this.top = null;
    this.size = 0;
}
@Override
public List<E> shallowCopy() {

     LinkedStack<E> newstack = new LinkedStack<E>();
     ArrayList<E> Alist = new ArrayList<E>();
    //Iterate through while we haven't hit the end of the stack
    Node newtest = top;
    while (newtest != null) {
        Alist.add(newtest.data);
        newtest = newtest.next;
    //TODO 85
    }
    for(int i = Alist.size()-1;i>=0;i--) {
        newstack.push(Alist.get(i));
    }
    return newstack;
}

@Override
public Iterator<E> iterator() {

    return new LinkedStackIterator(this);
}

}

这是我未通过的 Junit 测试

@Test
@SuppressWarnings("deprecation") // for Date.setHours(), Date.getHours()
public void shallowCopy1() {

    // let's use Date, since it's mutable.
    LinkedStack<Date> s = new LinkedStack<Date>();

    Date d = new Date();
    d.setHours(17);

    s.push(d);

    LinkedStack<Date> s2 =(LinkedStack<Date>) s.shallowCopy();

    Date d2=s2.pop();

    // The shallow copy should contain references to the same objects
    // as the original.
    assertTrue(d == d2);

    // So, we can change the Date in the original list using the Date that
    // came from the shallow copy.
    d2.setHours(14);
    assertTrue(d.getHours() == 14);
    // I don't usually put two asserts in one test, but this seems like 
    // an instructive example.
}

@Test(expected=NoSuchElementException.class)
public void shallowCopy2() {


    LinkedStack<Integer> s1 = new LinkedStack<Integer>();

    for(int i=0; i<10; i++) {

        s1.push(i);
    }       

    LinkedStack<Integer> s2 =(LinkedStack<Integer>) s1.shallowCopy();

    s2.push(10); // supposed to only affect s2
    s2.push(11); // supposed to only affect s2

    for(int i=0; i<10; i++) {

        s1.pop();
    }       

    int last = s1.pop(); // should throw

}


@Test
public void shallowCopy3() {

    LinkedStack<Integer> q1 = new LinkedStack<Integer>();

    for(int i=0; i<10; i++) {

        q1.push(i);
    }       

    LinkedStack<Integer> q2 =(LinkedStack<Integer>) q1.shallowCopy();

    //Let's check that the order of elements is correct in the copy.
    for(int i=0; i<10; i++) {

        int v1=q1.pop();
        int v2=q2.pop();

        assertEquals(v1, v2);
    }               
}

如果有人能指出正确的方向，我将不胜感激。 这是一道作业题。

Answer 1

浅拷贝尽可能少重复。集合的浅表副本是集合结构的副本，而不是元素。使用浅拷贝，两个集合现在共享单个元素。

深拷贝复制一切。集合的深拷贝是两个集合，其中原始集合中的所有元素都是重复的。

protected class Node{

    E data; 
    Node next;

    Node(Node node){
        this.next = node.next;
        this.data = node.data;
    }
}


@Override
public List<E> shallowCopy() {

    // LinkedStack<E> newStack = new LinkedStack<E>();
    //Iterate through while we haven't hit the end of the stack
    Node s = new Node(top);

     while (top.next != null) {
          s.next = new Node(top.next);
          top = top.next;
          s = s.next;
     }
     System.out.println("FINSHED!");
     return (List<E>) s;
 }


@Override
public List<E> shallowCopyWithoutUpdatingNodeClass() {

    // LinkedStack<E> newStack = new LinkedStack<E>();
    //Iterate through while we haven't hit the end of the stack
    Node s = new Node(top);

     while (top.next != null) {
          s.next = new Node();
          s.next.next = top.next;
          s.next.data = top.data;
          top = top.next;
          s = s.next;
     }
     System.out.println("FINSHED!");
     return (List<E>) s;
 }

答案受启发：- What is the difference between a deep copy and a shallow copy?

Answer 2

最初的问题是节点数据只是被覆盖而不是创建新节点。然后堆栈向后。最后我实现和数组来反转堆栈。

@Override
public List<E> shallowCopy() {

     LinkedStack<E> newstack = new LinkedStack<E>();
     ArrayList<E> Alist = new ArrayList<E>();
    //Iterate through while we haven't hit the end of the stack
    Node newtest = top;
    while (newtest != null) {
        Alist.add(newtest.data);
        newtest = newtest.next;
    //TODO 85
    }
    for(int i = Alist.size()-1;i>=0;i--) {
        newstack.push(Alist.get(i));
    }
    //System.out.println("FINSHED!");
    return newstack;
}

链接堆栈上浅拷贝的 J 单元测试失败

Failing J-unit test for Shallow Copy on a Linked Stack

java

shallow-copy