我正在尝试使用双向链表编写撤消和重做函数,该双向链表在调用 doAction() 时在 list_1 前面添加操作(节点),在调用 undo() 时将操作存储在 list_2 中,并在调用 redo() 时将操作添加回 list_1。两个列表中的所有元素都添加到列表的前面(堆栈)。 我不允许导入任何其他 Java 包。
公共(public)类 StringDoublyLinkedList {
/**
* A private class to represent a link in the linked list.
*/
private class Node {
String value;
Node next;
Node prev;
Node(String value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
private int size = 0;
private Node head = null;
private Node tail = null;
private Node head_2 = null;
/**
* Add a String to the end of the list.
*
* @param value The String to add.
*/
public void add(String value) {
Node newNode = new Node(value);
if (this.size == 0) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.size += 1;
}
/**
* Get the number of elements in the list.
*
* @return The number of elements in the list.
*/
public int size() {
return this.size;
}
public String get(int index) {
return this.getNode(index).value;
}
public void remove(int index) {
Node curr = this.head;
if (index == 0) {
this.head = curr.next;
} else {
Node node = this.getNode(index - 1);
node.next = node.next.next;
if (node.next == tail) {
this.tail = node;
}
}
this.size -= 1;
}
private Node getNode(int index) {
Node curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
return curr;
}
public boolean undo() {
Node curr = this.head;
if (this.size > 0) {
curr.next.prev = null;
this.head = curr.next;
this.head_2 = curr;
} else if (this.size == 0) {
return false;
}
this.size -= 1;
return true;
}
public boolean redo() {
Node curr = this.head;
Node curr_2 = this.head_2;
if (this.size > 0) {
curr_2.next.prev = null;
this.head_2 = curr_2.next;
curr.next = this.head;
this.head.prev = curr;
this.head = curr;
} if (this.size == 0) {
return false;
}
this.size += 1;
return false;
}
/**
* Record an action.
*
* @param action The action to record.
*/
public void doAction(String action) {
Node newNode = new Node(action);
if (this.size == 0) {
this.head = newNode;
this.tail = newNode;
} else {
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
}
this.size += 1;
}
/**
* Get the number of actions recorded. Does *not* include actions that were undone.
*
* @return The number of actions recorded.
*/
public int getNumActions() { //FIXME
int count = 1;
int i;
for (int i = getNumActions() - 1; i >=0 ; i--) { // second option you have provided
count++;
}
return count;
}
/**
* Get the action at the specified index.
*
* Assumes the index < this.getNumActions().
*
* @param index The index of the desired action.
* @return The action (String).
*/
public String getAction(int index) { //FIXME
int i;
for (i = 0; i < this.size(); i++) {
index = this.size() - index - 1;
}
String Actions = this.get(index);
return Actions;
}
public void print() {
Node curr = this.head;
while (curr != null) {
System.out.print(curr.value);
System.out.print(", ");
curr = curr.next;
}
System.out.println();
}
}
这是测试用例:
public static void main(String[] args) {
StringDoublyLinkedList actions = new StringDoublyLinkedList();
actions.doAction("create outline");
actions.doAction("write introduction paragraph");
actions.doAction("write paragraph 1a");
actions.undo();
actions.doAction("write paragraph 1b");
actions.doAction("write paragraph 2a");
actions.undo();
actions.undo();
actions.redo();
actions.doAction("write paragraph 2b");
actions.doAction("write paragraph 3");
actions.doAction("write paragraph 4");
actions.undo();
actions.doAction("write conclusion paragraph");
actions.doAction("add expletive about how long this assignment took");
actions.undo();
String[] correctActions = {
"create outline",
"write introduction paragraph",
/*"write paragraph 1a",
"write paragraph 2b",
"write paragraph 3",
"write conclusion paragraph" */
};
// create a variable for overall correctness
boolean allCorrect;
// check the number of actions
System.out.println(
"Expected " + Integer.toString(correctActions.length) + " actions " +
"and found " + Integer.toString(actions.getNumActions())
);
allCorrect = (actions.getNumActions() == correctActions.length);
// if the number of actions is correct, check each action
if (allCorrect) {
for (int i = 0; i < correctActions.length; i++) {
// get the expected and action actions
String expectedAction = correctActions[i];
String actualAction = actions.getAction(i);
// compare them
boolean correct = (expectedAction == actualAction);
// print them out
System.out.println(
"(" + (correct ? "correct" : "incorrect") + ") " +
"Action " + Integer.toString(i) + " should be \"" + correctActions[i] + "\" " +
"and got \"" + actions.getAction(i) + "\"."
);
// update the overall correctness
allCorrect = (allCorrect && correct);
}
}
// give a summary correct/incorrect judgment
if (allCorrect) {
System.out.println("CORRECT!");
} else {
System.out.println("INCORRECT!");
}
}
}
我在 getAction() 中编写的代码返回从列表的索引[0]开始的操作,但我希望它向后返回操作(从列表的末尾开始)。
以我的测试用例为例:
(不正确)操作 0 应该是“创建大纲”并得到“编写介绍段落”。
(不正确)操作 1 应该是“编写介绍段落”并得到“创建大纲”。
public int getNumActions() { //FIXME
int count = 1;
int i;
for (int i = getNumActions() - 1; i >=0 ; i--) { // error
count++;
}
return count;
}
public String getAction(int index) { //FIXME
int i;
for (i = 0; i < this.size(); i++) {
index = this.size() - index - 1;
}
String Actions = this.get(index);
return Actions;
}
最佳答案
这可能是题外话,但我认为使用递归来计算LinkedList
中的元素是一个相当复杂的解决方案。
我认为你应该首先在程序中拆分两个逻辑对象:
LinkedList
实现,具有getSize()
、add(String)
和remove(String)
等基本方法;ActionManager
实现,具有doAction(Stirng)
、undo(String)
和redo(String)
等方法。
在这种情况下,您的程序质量会更好并且没有错误。
<小时/>public final class LinkedList {
private Node head;
private int size;
public int getSize() {
return size;
}
public void add(String value) {
Node node = new Node(value);
if (size == 0)
head = node;
else {
Node tail = getTail();
tail.next = node;
node.prev = tail;
}
size++;
}
public String remove() {
if (size == 0)
throw new IllegalArgumentException();
String value;
if (size == 1) {
value = head.value;
head = null;
} else {
Node tail = getTail();
value = tail.value;
tail.prev.next = null;
tail.prev = null;
}
size--;
return value;
}
private Node getTail() {
Node node = head;
while (node != null && node.next != null)
node = node.next;
return node;
}
private static final class Node {
private final String value;
private Node next;
private Node prev;
public Node(String value) {
this.value = value;
}
@Override
public String toString() {
return value;
}
}
}
<小时/>
public final class ActionManager {
private final LinkedList actions = new LinkedList();
private final LinkedList undoActions = new LinkedList();
public int getTotalActions() {
return actions.getSize();
}
public void doAction(String action) {
actions.add(action);
}
public void undo() {
if (actions.getSize() == 0)
throw new IllegalArgumentException();
undoActions.add(actions.remove());
}
public void redo() {
if (undoActions.getSize() == 0)
throw new IllegalArgumentException();
actions.add(undoActions.remove());
}
@Override
public String toString() {
return "total: " + actions.getSize() + ", undo: " + undoActions.getSize();
}
}
关于java - 返回从末尾开始(向后)的双向链表的索引,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58044985/