2012-08-02 117 views
3

我正在做一些家庭作业问题,并且我陷入了对夫妇的困境。我很难理解交换列表中数据的最佳方法。使用虚假列表类

我应该使该方法reverse(),它使用LinkedIntList类(下面)。这是一个有限的列表类,所以我只能使用那里的东西。

的点是取项目的列表

[1,2,3,4,5] 和反向他们 [5,4,3,2,1]

我想我的伪代码将是

采取第一条数据并将其附加到列表中。 在原始大小上循环(因为发生变化) 并取出0 处的棋子,然后将当前棋子添加到末尾0,1位置。

对于这样的输入: [1,8,19,4,17]
预期是这样的: 前 - > [17] - > [4] - > [19] - > [8] - > [1]/
我的代码获取此: 前 - > [19] - > [4] - > [17] - > [8] - > [19] - > [1]/

不知道我做错了什么。

public void reverse(){ 
    int x = this.size(); 
    this.add(front.data); 

    for (int i = 0; i < x; i++){ 
       this.remove(0); 
     this.add(this.size()-1, front.data); 
    } 
} 

// A LinkedIntList object can be used to store a list of integers. 
public class LinkedIntList { 
    private ListNode front; // node holding first value in list (null if empty) 
    private String name = "front"; // string to print for front of list 

    // Constructs an empty list. 
    public LinkedIntList() { 
     front = null; 
    } 

    // Constructs a list containing the given elements. 
    // For quick initialization via Practice-It test cases. 
    public LinkedIntList(int... elements) { 
     this("front", elements); 
    } 

    public LinkedIntList(String name, int... elements) { 
     this.name = name; 
     if (elements.length > 0) { 
      front = new ListNode(elements[0]); 
      ListNode current = front; 
      for (int i = 1; i < elements.length; i++) { 
       current.next = new ListNode(elements[i]); 
       current = current.next; 
      } 
     } 
    } 

    // Constructs a list containing the given front node. 
    // For quick initialization via Practice-It ListNode test cases. 
    private LinkedIntList(String name, ListNode front) { 
     this.name = name; 
     this.front = front; 
    } 

    // Appends the given value to the end of the list. 
    public void add(int value) { 
     if (front == null) { 
      front = new ListNode(value, front); 
     } else { 
      ListNode current = front; 
      while (current.next != null) { 
       current = current.next; 
      } 
      current.next = new ListNode(value); 
     } 
    } 

    // Inserts the given value at the given index in the list. 
    // Precondition: 0 <= index <= size 
    public void add(int index, int value) { 
     if (index == 0) { 
      front = new ListNode(value, front); 
     } else { 
      ListNode current = front; 
      for (int i = 0; i < index - 1; i++) { 
       current = current.next; 
      } 
      current.next = new ListNode(value, current.next); 
     } 
    } 

    public boolean equals(Object o) { 
     if (o instanceof LinkedIntList) { 
      LinkedIntList other = (LinkedIntList) o; 
      return toString().equals(other.toString()); // hackish 
     } else { 
      return false; 
     } 
    } 

    // Returns the integer at the given index in the list. 
    // Precondition: 0 <= index < size 
    public int get(int index) { 
     ListNode current = front; 
     for (int i = 0; i < index; i++) { 
      current = current.next; 
     } 
     return current.data; 
    } 

    // Removes the value at the given index from the list. 
    // Precondition: 0 <= index < size 
    public void remove(int index) { 
     if (index == 0) { 
      front = front.next; 
     } else { 
      ListNode current = front; 
      for (int i = 0; i < index - 1; i++) { 
       current = current.next; 
      } 
      current.next = current.next.next; 
     } 
    } 

    // Returns the number of elements in the list. 
    public int size() { 
     int count = 0; 
     ListNode current = front; 
     while (current != null) { 
      count++; 
      current = current.next; 
     } 
     return count; 
    } 

    // Returns a text representation of the list, giving 
    // indications as to the nodes and link structure of the list. 
    // Detects student bugs where the student has inserted a cycle 
    // into the list. 
    public String toFormattedString() { 
     ListNode.clearCycleData(); 

     String result = this.name; 

     ListNode current = front; 
     boolean cycle = false; 
     while (current != null) { 
      result += " -> [" + current.data + "]"; 
      if (current.cycle) { 
       result += " (cycle!)"; 
       cycle = true; 
       break; 
      } 
      current = current.__gotoNext(); 
     } 

     if (!cycle) { 
      result += " /"; 
     } 

     return result; 
    } 

    // Returns a text representation of the list. 
    public String toString() { 
     return toFormattedString(); 
    } 

    // Returns a shorter, more "java.util.LinkedList"-like text representation of the list. 
    public String toStringShort() { 
     ListNode.clearCycleData(); 

     String result = "["; 

     ListNode current = front; 
     boolean cycle = false; 
     while (current != null) { 
      if (result.length() > 1) { 
       result += ", "; 
      } 
      result += current.data; 
      if (current.cycle) { 
       result += " (cycle!)"; 
       cycle = true; 
       break; 
      } 
      current = current.__gotoNext(); 
     } 

     if (!cycle) { 
      result += "]"; 
     } 

     return result; 
    } 


    // ListNode is a class for storing a single node of a linked list. This 
    // node class is for a list of integer values. 
    // Most of the icky code is related to the task of figuring out 
    // if the student has accidentally created a cycle by pointing a later part of the list back to an earlier part. 

    public static class ListNode { 
     private static final List<ListNode> ALL_NODES = new ArrayList<ListNode>(); 

     public static void clearCycleData() { 
      for (ListNode node : ALL_NODES) { 
       node.visited = false; 
       node.cycle = false; 
      } 
     } 

     public int data;   // data stored in this node 
     public ListNode next;  // link to next node in the list 
     public boolean visited; // has this node been seen yet? 
     public boolean cycle;  // is there a cycle at this node? 

     // post: constructs a node with data 0 and null link 
     public ListNode() { 
      this(0, null); 
     } 

     // post: constructs a node with given data and null link 
     public ListNode(int data) { 
      this(data, null); 
     } 

     // post: constructs a node with given data and given link 
     public ListNode(int data, ListNode next) { 
      ALL_NODES.add(this); 
      this.data = data; 
      this.next = next; 
      this.visited = false; 
      this.cycle = false; 
     } 

     public ListNode __gotoNext() { 
      return __gotoNext(true); 
     } 

     public ListNode __gotoNext(boolean checkForCycle) { 
      if (checkForCycle) { 
       visited = true; 

       if (next != null) { 
        if (next.visited) { 
         // throw new IllegalStateException("cycle detected in list"); 
         next.cycle = true; 
        } 
        next.visited = true; 
       } 
      } 
      return next; 
     } 
    } 

// YOUR CODE GOES HERE 

} 
+3

您是否正在使用一个IDE来让您逐步进行调试?它可以帮助你查看你的列表正在发生什么。或者,在你的'for'循环中添加一个print语句('System.out.println(toFormattedString())')来观察列表的变化。 – 2012-08-02 07:02:22

+0

它在练习网站上,所以我不能插入打印语句。这是我最大的抱怨,没有调试代码。 – hobbes131 2012-08-02 07:09:25

+1

但是你知道代码的细节,你刚刚发布了它。如果你能抓住一个Java IDE(比如说[Eclipse](http://www.eclipse.org/downloads/)),那么把它放在一个新项目中并且玩一下就是一个简单的任务。如果你挣扎,我们可以帮助你做到这一点。 – 2012-08-02 07:11:15

回答

2

这里是你的代码的打印语句:

public void reverse() { 
    System.out.println(toFormattedString()); 

    int x = this.size(); 
    this.add(front.data); 
    System.out.println(toFormattedString()); 

    for (int i = 0; i < x; i++) { 
    this.remove(0); 
    System.out.println(toFormattedString()); 
    this.add(this.size() - 1, front.data); 
    System.out.println(toFormattedString()); 
    } 
} 

输出:

front -> [1] -> [2] -> [3] -> [4] -> [5]/
front -> [1] -> [2] -> [3] -> [4] -> [5] -> [1]/
front -> [2] -> [3] -> [4] -> [5] -> [1]/
front -> [2] -> [3] -> [4] -> [5] -> [2] -> [1]/
front -> [3] -> [4] -> [5] -> [2] -> [1]/
front -> [3] -> [4] -> [5] -> [2] -> [3] -> [1]/
front -> [4] -> [5] -> [2] -> [3] -> [1]/
front -> [4] -> [5] -> [2] -> [3] -> [4] -> [1]/
front -> [5] -> [2] -> [3] -> [4] -> [1]/
front -> [5] -> [2] -> [3] -> [4] -> [5] -> [1]/
front -> [2] -> [3] -> [4] -> [5] -> [1]/
front -> [2] -> [3] -> [4] -> [5] -> [2] -> [1]/

希望这有助于。

+0

是的,我当然可以看到,我的代码不按照计划。让我试着将它插入eclipse中,看看我能否把它整理出来。谢谢! – hobbes131 2012-08-02 19:41:44

+0

HAHA!明白了,看着这个在行动中发生的事情是巨大的。伟大的电话格式化的字符串的东西。 – hobbes131 2012-08-02 20:45:27

+0

@ hobbes131很高兴你很开心:-) – 2012-08-02 20:49:03

1

嗨,你总是把数据size()-1可能要做到这一点,而不是

this.add(this.size()-i-1, front.data); 

,然后删除第一个元素另一次。

不要犹豫,逐步调试你的代码,看看它是怎么回事。


成为某网站上不应该使用IDE阻止你,但a piece of paper将做的工作也是如此。

+0

谢谢!当我将它与下面的回复结合起来时,这是一个很大的帮助。我从你的反馈开始,并努力解决问题。 – hobbes131 2012-08-02 20:44:54

1

首先,您应该将第一个元素添加到(x-i)的索引中。然后删除第一个元素。我的意思是你的循环应该是;

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

    this.add(this.size()-i, front.data); 
    this.remove(0); 
} 

你也可以删除;

this.add(front.data); 

我认为这有助于。

+0

当我想通了,我回去调整并保存了几行不必要的代码。谢谢一堆! – hobbes131 2012-08-02 20:46:07