3

我有一个链接列表，我希望能够看到前面的两个节点。我需要检查前两个节点是否有整数，如果有，并且第三个节点说 ADD，那么我需要将该信息压缩到一个节点中并释放其他两个节点。

我对我的while循环应该做什么感到困惑。我检查第三个节点是否指向 null，但不知何故，这并没有给我正确的输出。我也不知道我是否正确处理了我的 node.next。其中一些现在是伪代码。

while(node1.next.next.next != NULL){
    if((node1.data.isInteger() && (node2.data.isInteger()){
        if(node3.data.equals('add')){
            node1.data = node1.data + node2.data;
        } else {
            //ERROR
        }
        garbage_ptr1 = node2;
        garbage_ptr2 = node3;
        node1.next = node3.next;
        free(garbage_ptr1);
        free(garbage_ptr2);
        node2.next = node1.next.next;
        node3.next = node2.next.next;
   } else {
        node1.next = node1.next.next;
        node2.next = node1.next.next;
        node3.next = node2.next.next;
   }
4

1 回答 1

0

我发现更简单的一种方法是维护一个充当列表窗口的小数组，并在数组上查找匹配项。如果将空检查移到实用程序方法中，代码也会变得更简洁。通过做这些事情，列表上的循环只需要检查窗口的最后一个元素即可终止。

Java中的草图：

/* small utility methods to avoid null checks everywhere */
public static Node getNext(Node n) { return n != null ? n.next : null; }

public static boolean isInteger(Node n) {
  return (n != null) && (n.data != null) && (n.data instanceof Integer);
}
public static boolean isAdd(Node n) { 
  return (n != null) && (n.data != null) && n.data.equals("add");
}

/* checks for a match in the 3-node window */
public boolean isMatch(Node[] w) {
  return isInteger(w[0]) && isInteger(w[1]) && isAdd(w[2]);
}

/* Loads the 3-node window with 'n' and the next two nodes on the list */
public void loadWindow(Node[] w, Node n) { 
  w[0] = n; w[1] = getNext(w[0]); w[2] = getNext(w[1]);
}

/* shifts the window down by one node */
public void shiftWindow(Node[] w) { loadWindow(w, w[1]); }

...
Node[] window = new Node[3];
loadWindow( window, node1 );
while (window[2] != null) {
  if (isMatch(window)) { 
    window[0].data = stack[0].data + stack[1].data;
    window[0].next = window[2].next;
    loadWindow(window, window[0]);  // reload the stack after eliminating two nodes
  } else {
    shiftWindow( window );
  }
}
于 2013-03-08T16:53:51.380 回答