最近正在重读《编程珠玑》，对于以前忽略的细节，现在也有了更深的了解。
这是13章课后习题中的第4题，向有序单链表中插入新结点。linus曾经谈到过使用二级指针删除结点的问题，具体请见“酷壳网”。
作者介绍了两种方法，并在链表中创建了哨兵结点，第一种是我们常用的一级指针，我将它改成了C语言版本（其实没改什么东西），如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void insert(int t)
{
node * p;
if(head->val == t)
return ;
if(head->val > t)
{
head = newNode(t ,head);
return ;
}
for(p = head; p->next->val < t; p = p->next)
;
if(p->next->val == t)
return ;
p->next = newNode(t, p->next);
}
|
这是我们常用的方法，也是老师讲过的标准方法，需要对head结点单独进行讨论，这个方法不难理解。
下面我们主要讨论作者介绍的第二种方法，使用二级指针来插入新结点，代码如下：
1
2
3
4
5
6
7
8
9
10
11
|
void insert(int t)
{
node **p;
for(p = &head; (*p)->val < t; p = &((*p)->next))
;
if ((*p)->val == t)
return;
*p = newNode(t, *p);
}
|
使用二级指针就可以不用将头结点单独讨论，插入第一个结点时， p = &head，*p = newNode(t, *p)，相当于第一中方法中的 head = newNode(t ,head), 这样第二种方法就将第一种方法中的两种情况(头结点和非头结点)都包含了。
对于非头结点的情况，即当前结点有前驱结点(设为prev结点)，此时*p 的值等于prev->next，即 *p = newNode(t, *p) 相当于 prev->next = newNode(t, prev->next)。
为了加深理解，我用gdb追踪各指针。 初始化链表后，head和sentinel都指向哨兵结点。
当我们使用二级指针向链表中插入1时：
insert函数的for循环结束后：
此时p指针指向的是head指针，p等于head。 执行完 p = newNode(t, p); 之后：
此时p指针仍然指向head指针，但是head指针的指向了新插入的结点。 向链表中插入2，执行完insert函数中的for循环：
将存储1的结点命名为prev，0x602038其实是prev-next的地址，即此时p存储的是prev->next的地址，p指向的是哨兵结点。 执行 p = newNode(t, p); 相当于执行 prev->next = newNode(t, prev->next)。 执行完之后:
此时p仍然指向prev->next,但是prev的next保存的地址变成了新生成的结点的内存地址，这样就完成了新结点的插入。
下面附上完整代码，方便需要的人运行，调试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int val;
struct node *next;
}node;
node *head, *sentinel;
node* newNode(int val, node *n)
{
node *temp = (node*)malloc(sizeof(node));
temp->val = val;
temp->next = n;
return temp;
}
void initList(int maxval)
{
sentinel = head = newNode(maxval, 0);
}
void insert(int t)
{
node **p;
for(p = &head; (*p)->val < t; p = &((*p)->next))
;
if ((*p)->val == t)
return;
*p = newNode(t, *p);
}
int main(int argc, char *argv[])
{
initList(50);
int a[5] = {1, 2};
int i;
for (i = 0; i < 2; ++i)
insert(a[i]);
node *iterator;
for(iterator = head; iterator != sentinel; iterator = iterator->next)
printf ("%d\n", iterator->val);
return 0;
}
|
(结束)