由一道代码填空题目引发的小思考

由数据结构的一道期中考题的引发的思考

其实在有限的时空内思考别人的思考方式并实现，是个有十分有意思的事情，并且也是代码能力的一种体现。

如有发现证明出错，务必指出，谢谢！

题面

要求在/*===i===*/中补全代码实现链表排序。

/*
    Programming Language: cpp
    已知节点类的定义如下:
    struct NODE {
        int val;
        struct NODE* next;
        NODE() {}
        NODE(int val,NODE* next):val(val),next(next) {}
    };
    typedef NODE* LinkList;
*/

void InsertSort(LinkList& L) {
    LinkList p,q,r,u;
    p = L->next;
    /*===1===*/
    while(/*===2===*/) {
        r = L;
        q = L->next;
        while( /*===3===*/ && q->data <= p->data ) {
            r = q;
            q = q->next;
        }
        u = p->next;
        /*===4===*/
        /*===5===*/
        p = u;
        break;
    }
}

思考

参考答案

首先思考标准答案的正确性，标准答案如下:

位置	语句
/*==1==*/	L = nullptr;
/*==2==*/	p != nullptr;
/*==3==*/	q != nullptr;
/*==4==*/	r->next = p;
/*==5==*/	p->next = q;

毫无疑问，这是正确的。这段代码的含义是，普通的链表插入排序法。

---

插入排序思想如下:

1. 需要新构造一个空表
2. 将每次选择原表中的第一个元素(q)，删除(q)在原链表中的位置(头删)
3. 按照顺序将元素(u)插入到新的空表中。
4. 重复(2)-(3)直到原表为空，即是排序完毕，排序的结果就是空表。

---

L就是上述中的空表，所以初始为空(就是位置1操作)，而u是原表的第一个元素位置。

由于原来的链表无头节点，所以在阅读上，会有些许不适。

引发的小思考

关于 L=nullptr 是否必要的小思考，假设我们去除L=nullptr，我们就是在原来的表中进行插入和删除操作，由于选择元素是不断向后的，我们只要保证现在将要插入的元素插入到它之前的位置是正确的即可。

可能上面的说法有点绕，直观解释如图:

1

即，只要保证data4插入到红色区域时不会影响红色区域的正确性即可，假设红色区域为有序，这个是显然的，因为假设红色区域有序，这就是链表的插入排序。

2

因此只要证明红色区域有序即可。

• 由于第一步操作不会影响正确性，故略去。
• 从第二步开始思考
  • 假设第第二个节点(u)被移动，此u必定会被移动到后面，即图中的灰色区域 (即待排序区域)，不会影响正确性。
  • 假设未被移动，即正常排序，由于只有一个元素，所以排序之后必定有序

由于寻找中要求了严格小于，所以避免了p,q相等的情况,但是这边也有个小陷阱

3

因此，由[1][2]和数学归纳法可得，去掉L=nullptr不影响正确性。

一个小陷阱

陷阱是出现在不写L=nullptr的情况下的。

这边就有个疑问了，那是不是题面中的(4)，(5)的顺序是不是可以乱填了呢？

当然是不能的!

假设

位置	语句
…	…
/*==4==*/	p->next = q;
/*==5==*/	r->next = p;

由于代码只保证了p和q不相等，并没有保证p和r不相等，所以当出现p = r的时候，按照上面的写法会在 (5)执行结束后在 p 处 形成自环，代码错误。

而原来的写法，就相等于覆盖了自环的赋值，所以避免了形成自环，代码正确。

对于答案的思考

答案一：

4,5位置可以互换

位置	语句
/*==1==*/	L = nullptr;
/*==2==*/	p != nullptr;
/*==3==*/	q != nullptr;
/*==4==*/	r->next = p;
/*==5==*/	p->next = q;

答案二：

4,5位置不可以互换

位置	语句
/*==1==*/	随意
/*==2==*/	p != nullptr;
/*==3==*/	q != nullptr;
/*==4==*/	r->next = p;
/*==5==*/	p->next = q;

结论

虽然证明了乱填第一空，也可以使代码正确。但是，在本着代码编写是首先是给人看的，其次才是运行正确，所以在实际编写中，不推荐第二种写法。
我第二种,进入思维盲区，发现r=p找了一下午，真的笋干爆炸