《算法》第四版笔记 创建对象 和 为对象赋值区别

Stack(debug版本) - github

问题起因

在算法1.2 下压堆栈链表实现过程出, 出现了下面一个问题, 又牵扯出一些新旧问题.

测试函数中的foreach语句不能遍历

for (String t : s) {
  System.out.println(t);
}

在StackIterator类中, 测试hasNext()方法, print出 “in hasNext() false”, 也就是说迭代不会开始

public boolean hasNext() {
  System.out.println("in hasNext()" + (current != null));
  return current != null;
}

在main函数中, 测试isEmpty(), 这个函数会判断 链表中first指针, 是否为null, 结果打印出 true

Stack<String> s = new Stack<String>();
System.out.println(s.isEmpty());
s.push("Truing");
s.push("Dijkstra");
s.push("Kruthun");
System.out.println(s.isEmpty());

找到问题是出在push()函数

public void push(Item elem) {
  // 向栈中添加元素
  Node oldFirst = first;
  // Node first = new Node();           // 这样写的逻辑更直观
  first = new Node();                   // debug: why? 与上一行的区别
  first.next = oldFirst;
  first.item = elem;
  ++N;
}

疑惑, 构造一个对象时, 下面两行代码的区别?

public void push(Item elem) {
  // 向栈中添加元素
  Node oldFirst = first;
  // Node first = new Node();           // bug
  first = new Node();                   // ok: why? 与上一行的区别
  first.next = oldFirst;
  first.item = elem;
  ++N;
}

上一行导致, first对象指向null, 而下一行的first != null

---

重新在push方法种进行debug后

public void push(Item elem) {
  // 向栈中添加元素
  Node oldFirst = first;
  // Node first = new Node();
  first = new Node();                   // debug: why? 与上一行的区别
  System.out.println("first ?= null : " + (first == null));
  System.out.println("oldFirst ?= null : " + (oldFirst == null));
  first.next = oldFirst;
  first.item = elem;
  ++N;
}

空链表push两次:

$ java Stack
first ?= null : false
oldFirst ?= null : true
first ?= null : false
oldFirst ?= null : false

public void push(Item elem) {
  // 向栈中添加元素
  Node oldFirst = first;
  Node first = new Node();
  // first = new Node();                   // debug: why? 与上一行的区别
  System.out.println("first ?= null : " + (first == null));
  System.out.println("oldFirst ?= null : " + (oldFirst == null));
  first.next = oldFirst;
  first.item = elem;
  ++N;
}

空链表push两次:

$ java Stack
first ?= null : false
oldFirst ?= null : true
first ?= null : false
oldFirst ?= null : true

---

问题更进一步

因此, 这两种写法的区别就在于:

Node oldFirst = first;       // oldFirst指向first对象的引用
Node first = new Node();     // first对象被重新构造, oldFirst指向null
first.next = oldFirst;

此时, 如果oldFirst指向null的话, 将oldFirst作为first的后继, 是不符合我的原意的。

正确的写法是:

Node oldFirst = first;     // 只是用来保存first对象的引用
first = new Node();        // first指向新的引用对象
first.next = oldFirst;     // first.next结点对象指向oldFirst的引用

但为什么既然
oldFirst -> 原来的first对象引用
first->新的对象
oldFirst ?-> 新的结点对象 // why?

如何oldFirst指向新的结点对象的话, 那么对first赋值新的后继, 是永远只能赋值给它自己本身的。。