定义结点类型
2.9用格子图和箭头图讲清了链式存储。它能不能真的把编辑器里的这一行存下来?
下面以cat为例。要达到的样子,就是2.9的箭头图:
textL = 100
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ c │ 109 │────►│ a │ 105 │────►│ t │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘
100 109 105
一个结点有两格:数据格放一个字符,地址格放下一个结点的地址。
第一步:定义类型。要用C语言把它实现出来,先得有结点。结点用2.3学过的结构体表示:
ctypedef struct Node {
char data; /* 数据格 */
struct Node *next; /* 地址格:下一个结点的地址 */
} Node;
图里的每个方框,就是一个Node。数据格是data,地址格是next。next存的是地址,所以它是一个指针,从方框伸出去的箭头就是它。
图里的头指针,在C语言里是一个变量,习惯上叫L。它存的也是一个结点的地址,所以它和next是同一种类型:Node *。
next:指向自己这种结构体的指针
这里有一处第一次见到的写法:结构体里有一个指向自己这种结构体的指针。下一个结点也是Node,所以next的类型是"指向Node的指针"。
struct Node写了两遍,是因为定义next那一行时typedef还没完成,Node这个简写还不存在,只能用完整的struct Node *。定义结束后,其他地方都可以用Node。
类型有了,可图里的三个结点还不存在。它们怎么一个个申请、接起来?
第二步:空链表。还没有任何字符时,链表一个结点都没有。头指针不指向任何结点,就是NULL:
cNode *L = NULL; /* 头指针:现在是空链表 */
链表不需要像顺序表那样记长度和容量。结点是一个一个申请的,用多少申请多少,没有"容量";要知道有几个结点,从L出发数一遍就行。
搭出cat
第三步:第一个结点。存c需要一个结点。链表的结点是零散的,多一个元素才需要一个结点,所以每个结点单独用2.8讲过的malloc申请。
假设申请到100号,用p1记住它。数据格填c;后面还没有结点,地址格填NULL,也就是结束标记0。最后让头指针指向它:
cNode *p1 = (Node *)malloc(sizeof(Node)); /* 申请一个结点 */
p1->data = 'c';
p1->next = NULL;
L = p1; /* 头指针指向它 */
sizeof(Node)是一个结点占的字节数。最后一行让L等于100,链表就有了第一个结点:
textL = 100
│
▼
┌───┬─────┐
│ c │ 0 │
└───┴─────┘
100
第四步:第二个结点。同样申请一个结点存a,假设申请到109号,用p2记住它:
cNode *p2 = (Node *)malloc(sizeof(Node));
p2->data = 'a';
p2->next = NULL;
textL = 100
│
▼
┌───┬─────┐ ┌───┬─────┐
│ c │ 0 │ │ a │ 0 │
└───┴─────┘ └───┴─────┘
100 109
这时a结点已经有了,但还没接上:c结点的地址格还是0,从L出发走不到它。
要把a接到c后面,就是把c结点的地址格从0改成109。c结点是p1,109存在p2里:
cp1->next = p2; /* c 结点指向 a 结点 */
textL = 100
│
▼
┌───┬─────┐ ┌───┬─────┐
│ c │ 109 │────►│ a │ 0 │
└───┴─────┘ └───┴─────┘
100 109
第五步:同理,第三个结点。申请一个结点存t,假设在105号,再把它接到a后面,也就是把a结点的地址格从0改成105:
cNode *p3 = (Node *)malloc(sizeof(Node));
p3->data = 't';
p3->next = NULL;
p2->next = p3; /* a 结点指向 t 结点 */
textL = 100
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ c │ 109 │────►│ a │ 105 │────►│ t │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘
100 109 105
和开头要达到的样子一模一样,cat存进链表了。
输出链表
存进去了,还要能读出来,编辑器才能显示这一行。要做的是按顺序打印c、a、t:
textL = 100
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ c │ 109 │────►│ a │ 105 │────►│ t │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘
100 109 105
用一个指针p记住读到了哪个结点。
- 从头出发:p等于L,是100。打印100号的数据c。
- 走到下一个:100号的地址格是109,p变成109,打印a。109号的地址格是105,p变成105,打印t。
- 走到头停下:105号的地址格是0,p变成NULL,后面没有结点了,停下。
p一路往后走,L一直是100。要是拿L来走,走完就找不到第一个结点了。
一般地,p从L开始;每次打印p->data,再用p = p->next走到下一个结点;p为NULL就停下。写成循环:
cfor (Node *p = L; p != NULL; p = p->next)
printf("%c", p->data);
printf("\n");
也可以写成while
很多教材把这个循环写成while,两种写法完全等价:
cNode *p = L;
while (p != NULL) {
printf("%c", p->data);
p = p->next;
}
本书用for,是因为"从哪开始、走到哪停、怎么走一步"三件事挤在一行,一眼就能认出这是在遍历链表。两种写法都要能认出来。
把这一节的代码放在一起,就是一个完整的程序:
c#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
char data;
struct Node *next;
} Node;
int main(void) {
Node *L = NULL; /* 空链表 */
Node *p1 = (Node *)malloc(sizeof(Node)); /* c 结点 */
p1->data = 'c';
p1->next = NULL;
L = p1;
Node *p2 = (Node *)malloc(sizeof(Node)); /* a 结点,接在 c 后面 */
p2->data = 'a';
p2->next = NULL;
p1->next = p2;
Node *p3 = (Node *)malloc(sizeof(Node)); /* t 结点,接在 a 后面 */
p3->data = 't';
p3->next = NULL;
p2->next = p3;
for (Node *p = L; p != NULL; p = p->next) /* 输出 */
printf("%c", p->data);
printf("\n"); /* 输出 cat */
return 0;
}
运行,输出cat。三个字符在内存里散着放,读出来的顺序没错,靠的就是next。
为了看清结构,这个程序省掉了两件事:没有检查malloc是不是申请成功,结束前也没有把结点还给系统。
这种写法只能演示:多一个字符,就要多一个指针、多写几行。把取元素、插入、删除写成通用的操作,是下一节的事。