C和指针 （pointers on C）――第十二章：使用结构和指针
C和指针 （pointers on C）――第十二章：使用结构和指针 篇1
这章就是链表，先单链表，后双向链表。
总结：
单链表是一种使用指针来存储值的数据结构。链表中的每个节点包含一个字段，用于指向链表的下一个节点。
有一个独立的根指针指向链表的第1个节点。单链表只能从一个方向遍历。
如何insert单链表：1、新节点的link字段必须设置为指向它的后面节点。2、前一个节点的link字段必须指向这个新节点。
为了防止可能会插入链表的起始位置这种情况，在C中，可以保存一个指向必须进行修改的link字段的指针，而不是保存一个指向前一个节点的指针。
双链表中的每个节点包含两个link字段：其中一个指向链表的下一个node，另一个指向前一个node。
双链表有两个根指针，一个指向第一个node，另一个指向最后一个node。因此遍历的过程中可以从任何一端开始，而且在遍历过程中够可以改变方向。
为了把一个新节点插入到双链表中，我们必须修改4个指针。新节点的前向和后向link字段必需被设置，前一个节点的fwd和后一个节点的bwd也要修改，指向新节点。
警告：
1、落到链表尾部的后面。
2、使用指针时应该格外小心，因为C并没有对他们的使用提供安全网。
3、从if语句中提炼语句可能会改变测试结果。
编程提示：
1、消除特殊情况使代码更易于维护。
2、不要轻易的进行提炼语句，这样会使你的语句更难维护。
编程实例：(本章就不再弄习题了，关于数据结构这块会有大量代码进行训练)
1、提炼后的单链表插入操作
?
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
#include “stdlib.h”
typedef struct NODE
{
struct NODE *link;
intvalue;
} Node;
int sll_int(register Node **linkp, int new_value)
{
register Node *current;//指向当前节点
register Node *new_node;//指向插入节点
/*
** 寻找正确插入位置，按顺序访问链表，直到有个值大于或等于新值
*/
while ((current = current->link) != NULL && current->value < new_value)
{
linkp = ¤t->link; //移动linkp指向下一个Node的link
}
/* 分配新的内存，并存到新节点去 */
new_node = (NODE *) malloc (sizeof(NODE));
if (new_node == NULL)
{
return 0;
}
new_node->value = new_value;
/* 插入新节点 */
new_node->link = current;
*linkp = new_node;
return 1;
}
2、双链表插入操作
?
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
75
76
77
78
79
80
#include “stdlib.h”
typedef struct NODE
{
struct NODE *fwd;
struct NODE *bwd;
int value;
}Node;
int dll_insert(Node *rootp, int value)
{
/* 把一个值插入到一个双向链表中，rootp是一个指向根节点的指针
value 是插入的新值
返回值：如果已经存在链表中，返回0
如果内存不足导致无法插入，返回-1，成功返回1;
*/
Node *this_node;
Node *next_node;
Node *new_node;
for (this_node = rootp; next_node != NULL; this_node = next_node )
{
if (next_node->value == value)
return 0;
if (next_node->value < value)
break;
next_node = next_node->fwd;
}
/* 为新节点申请内存空间*/
new_node = (Node *) malloc (sizeof(Node));
if (new_node == NULL)
return -1;
new_node->value = value;
/*
插入节点
if 不在链表尾部 then 不在链表起始位置 or 位于链表起始位置
else 在链表尾部 then 不在链表起始位置 or 位于链表起始位置(空链表)
*/
if (next_node->fwd != NULL)
{
/*不在链表尾部*/
if (this_node != rootp)
{
/* 不在链表的头部 */
this_node->fwd = new_node;
next_node->bwd = new_node;
new_node->bwd = this_node;
new_node->fwd = next_node;
}
else
{
/* 在链表的头部*/
rootp->fwd = new_node;
next_node->bwd = new_node;
new_node->bwd = rootp;
new_node->fwd = next_node;
}
}
else
{
/*在链表尾部*/
if (this_node->bwd != rootp)
{
/* 不在链表的头部 */
new_node->fwd = NULL;
new_node->bwd = this_node;
this_node->fwd = new_node;
rootp->bwd = new_node;
}
else
{
/* 在链表的头部*/
new_node->fwd = NULL;
new_node->bwd = NULL;
rootp->bwd = new_node;
rootp->fwd = new_node;
}
}
}