进一步优化squish()方法

Question

这个问题的第二部分说：

填写squish()类中的SList方法，使其按照注释中的指示执行。您的解决方案不应该使用数组，也不应该使用您的smoosh()方法。不要更改SList构造函数或insertEnd方法的原型；我们的测试软件将调用它们。

下面是在squish()方法中作为解决方案编写的代码。对该方法进行了模块化测试。

public class SList {

  private SListNode head;
  private int size;

  /**
   *  SList() constructs an empty list.
   **/

  public SList() {
    size = 0;
    head = null;
  }

  /**
   *  isEmpty() indicates whether the list is empty.
   *  @return true if the list is empty, false otherwise.
   **/

  public boolean isEmpty() {
    return size == 0;
  }

  /**
   *  length() returns the length of this list.
   *  @return the length of this list.
   **/

  public int length() {
    return size;
  }

  /**
   *  insertFront() inserts item "obj" at the beginning of this list.
   *  @param obj the item to be inserted.
   **/

  public void insertFront(Object obj) {
    head = new SListNode(obj, head);
    size++;
  }

  /**
   *  insertEnd() inserts item "obj" at the end of this list.
   *  @param obj the item to be inserted.
   **/

  public void insertEnd(Object obj) {
    if (head == null) {
      head = new SListNode(obj);
    } else {
      SListNode node = head;
      while (node.next != null) {
        node = node.next;
      }
      node.next = new SListNode(obj);
    }
    size++;
  }


  /**
   *  squish() takes this list and, wherever two or more consecutive items are
   *  equal(), it removes duplicate nodes so that only one consecutive copy
   *  remains.  Hence, no two consecutive items in this list are equal() upon
   *  completion of the procedure.
   *
   *  After squish() executes, the list may well be shorter than when squish()
   *  began.  No extra items are added to make up for those removed.
   *
   *  For example, if the input list is [ 0 0 0 0 1 1 0 0 0 3 3 3 1 1 0 ], the
   *  output list is [ 0 1 0 3 1 0 ].
   *
   *  IMPORTANT:  Be sure you use the equals() method, and not the "=="
   *  operator, to compare items.
   **/

  public void squish() {
      // Fill in your solution here. (Ours is eleven lines long.)
      SListNode prevNode = null;
      SListNode curNode = null;
      int size = this.length();
      if(size >= 2){
          prevNode = this.head;
          curNode = this.head.next;  
      }
      if(!this.isEmpty()){
        while(size >= 2){
            if(prevNode.item.toString().equals(curNode.item.toString())){
                prevNode.next = curNode.next;
                size--;
                if(size >= 2){
                    curNode = curNode.next;
                }
            }else{
                size--;
                if(curNode.next != null){
                    prevNode = curNode;
                    curNode = curNode.next;

                }
            }
        }
    }
  }
  public String toString() {
    int i;
    Object obj;
    String result = "[  ";

    SListNode cur = head;

    while (cur != null) {
      obj = cur.item;
      result = result + obj.toString() + "  ";
      cur = cur.next;
    }
    result = result + "]";
    return result;
  }

  public static void main (String[] args) {
   String result;
   int i;
   System.out.println("\nLet's squish linked lists!\n");

    int[] test5 = {3, 7, 7, 7, 4, 5, 5, 2, 0, 8, 8, 8, 8, 5};
    SList list5 = new SList();
    for (i = 0; i < test5.length; i++) {
      list5.insertEnd(new Integer(test5[i]));
    }
    System.out.println("squishing " + list5.toString() + ":");
    list5.squish();
    result = list5.toString();
    System.out.println(result);
    TestHelper.verify(result.equals("[  3  7  4  5  2  0  8  5  ]"),
                      "BAD SQUISH!!!  No biscuit.");

    int[] test6 = {6, 6, 6, 6, 6, 3, 6, 3, 6, 3, 3, 3, 3, 3, 3};
    SList list6 = new SList();
    for (i = 0; i < test6.length; i++) {
      list6.insertEnd(new Integer(test6[i]));
    }
    System.out.println("squishing " + list6.toString() + ":");
    list6.squish();
    result = list6.toString();
    System.out.println(result);
    TestHelper.verify(result.equals("[  6  3  6  3  6  3  ]"),
                      "BAD SQUISH!!!  No biscuit.");

    int[] test7 = {4, 4, 4, 4, 4};
    SList list7 = new SList();
    for (i = 0; i < test7.length; i++) {
      list7.insertEnd(new Integer(test7[i]));
    }
    System.out.println("squishing " + list7.toString() + ":");
    list7.squish();
    result = list7.toString();
    System.out.println(result);
    TestHelper.verify(result.equals("[  4  ]"),
                      "BAD SQUISH!!!  No biscuit.");

    int[] test8 = {0, 1, 2, 3, 4, 5, 6};
    SList list8 = new SList();
    for (i = 0; i < test8.length; i++) {
      list8.insertEnd(new Integer(test8[i]));
    }
    System.out.println("squishing " + list8.toString() + ":");
    list8.squish();
    result = list8.toString();
    System.out.println(result);
    TestHelper.verify(result.equals("[  0  1  2  3  4  5  6  ]"),
                      "BAD SQUISH!!!  No biscuit.");

    SList list9 = new SList();
    System.out.println("squishing " + list9.toString() + ":");
    list9.squish();
    result = list9.toString();
    System.out.println(result);
    TestHelper.verify(result.equals("[  ]"),
                      "BAD SQUISH!!!  No biscuit.");
  }
}

SListNode

class SListNode {
  Object item;
  SListNode next;


  /**
   *  SListNode() (with two parameters) constructs a list node referencing the
   *  item "obj", whose next list node is to be "next".
   */

  SListNode(Object obj, SListNode next) {
    item = obj;
    this.next = next;
  }

  /**
   *  SListNode() (with one parameter) constructs a list node referencing the
   *  item "obj".
   */

  SListNode(Object obj) {
    this(obj, null);
  }
}

TestHelper

public class TestHelper {

  /**
   *  verify() checks an invariant and prints an error message if it fails.
   *  If invariant is true, this method does nothing.  If invariant is false,
   *  the message is printed, followed by a dump of the program call stack.
   *
   *  @param invariant  the condition to be verified
   *  @param message  the error message to be printed if the invariant fails to
   *                  hold true.
   **/

  static void verify(boolean invariant, String message) {
    if (!invariant) {
      System.out.println("*** ERROR:  " + message);
      Thread.dumpStack();
    }
  }
}

测试输出：

我们来压缩链接列表吧！压缩7 7 4 5 2 0 8 8 8 5：3 7 4 5 2 0 8 5压缩6 6 6 3 3：6 3 6 3 6 3压缩4 4 4：4.压缩0 1 2 3 4 5 6：0 1 2 3 4 5 6压缩undefined：undefined

请评论squish()方法的可读性方面。

你能指导我把这段代码压缩到11行吗？

注意:此代码不打算遵循OOP原则。

Answer 1

我不会太担心电话号码的。在我看来，任务并不是说你必须保持在11条线以下，而只是说他们的解决方案是11条线，这样你就可以大致知道一个解决方案可能要多长时间(所以，如果你在50条线以下，你就知道你偏离了轨道)。

尺寸

您的本地size变量名很差，因为它并不表示列表的大小，而只是一个迭代器变量。

而且，如果size删除了一个节点，那么squish字段将包含错误的值。

早期返回和简化大小检查

您可以将大小检查组合在一起：

    if (size < 2) {
        return;
    }

然后您可以像这样分配prevNode和curNode：

    SListNode prevNode = this.head;
    SListNode curNode = this.head.next;

这是更易读和节省您的行。

零值与toString

节点的值现在可以是null，因为insert不检查这个值。但是squish方法不能处理空值。

=与toString

删除对toString的调用，这没有多大意义，可能会返回错误的结果，这取决于equals实现。

检查下一个节点是否为空

您正在不一致地处理这个问题:第一次使用if (size >= 2)检查curNode.next是否为空，第二次使用if (curNode.next != null)。在这两种情况下，您应该使用相同的检查。

而且，实际上只需要检查一次:在执行if语句时，可以将其移出if语句。

我觉得你甚至不需要那张支票。如果大小小于2，则while循环无论如何都会停止。

码

如果您遵循所有建议，您的代码将如下所示：

// NOTE: size field might be wrong after calling this method, and it doesn't work with null values in nodes
public void squish() {
    // Fill in your solution here. (Ours is eleven lines long.)
    if (size < 2) {
        return;
    }

    SListNode prevNode = this.head;
    SListNode curNode = this.head.next;
    while (size >= 2) {
        if (prevNode.item.equals(curNode.item)) {
            prevNode.next = curNode.next;
        } else {
            prevNode = curNode;
        }
        curNode = curNode.next;
        size--;
    }
}

已经有点短了。我不会再减少线，它只会降低可读性。

但是，如果您真的想要删除curNode，则可以删除它，因此也可以删除以下检查：

public void squish() {
    SListNode prevNode = this.head;
    while (size >= 2) {
        if (prevNode.item.equals(prevNode.next.item)) {
            prevNode.next = prevNode.next.next;
        } else {
            prevNode = prevNode.next;
        }
        size--;
    }
}

这还会给您留出两行代码，这甚至足以正确维护size字段：

// maintains size field, but still doesn't handle null values in nodes
public void squish() {
    SListNode prevNode = this.head;
    for (int i = this.size; i >=2; i--) {
        if (prevNode.item.equals(prevNode.next.item)) {
            prevNode.next = prevNode.next.next;
            this.size--;
        } else {
            prevNode = prevNode.next;
        }
    }
}

Answer 2

在单链接列表中，检查后续节点比保存以前节点的信息更容易。很难担心head可能是null；必须担心两个节点可能是null，这就增加了许多复杂性。

size变量在squish()中被错误地命名:它实际上计算要考虑的剩余节点数，而不是列表的大小。更糟糕的是，它隐藏了名为size的实例变量。结果，列表变得不一致，在压缩后报告错误的长度.实际上，squish()方法没有理由需要知道列表的大小。它应该能够进行可视操作，根据它在当前节点附近所看到的操作。

使用if(!this.isEmpty()) { … }检查while(size >= 2) { … }是多余的。最内部的if(size >= 2)与while(size >= 2)也是冗余的；无条件地执行curNode = curNode.next是安全的。类似地，if(curNode.next != null)看起来像是一个多余的检查。拥有这些冗余条件的害处不在于有更多的代码行。相反，越多的条件意味着不变量越少，或者违反了不变量，这就很难分析代码。

不应该通过比较节点项的字符串表示形式来比较它们。检查prevNode.item.equals(curNode.item)会更合适。(这假设节点从来不包含空item。)

提出了squish()

的解决方案

public void squish() {
    for (SListNode cur = head; cur != null; cur = cur.next) {
        // Seek the next node with a different value
        SListNode seek;
        for (seek = cur.next; seek != null; seek = seek.next) {
            if ((cur.item == null) != (seek.item == null)) break;
            if (cur.item != null && !cur.item.equals(seek.item)) break;
            this.size--;
        }
        cur.next = seek;
    }
}

if ((cur.item == null) != (seek.item == null)) break;是出于偏执，如果节点可以包含null项的话。

测试

insertEnd()是一个比insertFront()低效率的操作。通过操纵头部来建立你的列表。

int[] test5 = {3, 7, 7, 7, 4, 5, 5, 2, 0, 8, 8, 8, 8, 5};
SList list5 = new SList();
for (i = test5.length - 1; i >= 0; i--) {
  list5.insertFront(new Integer(test5[i]));
}