Skip to content
第2章

2.10 链表的C语言实现 ​

定义结点类型 ​

2.9用格子图和箭头图讲清了链式存储。它能不能真的把编辑器里的这一行存下来?

下面以cat为例。要达到的样子,就是2.9的箭头图:

text
L = 100
  │
  ▼
┌───┬─────┐     ┌───┬─────┐     ┌───┬─────┐
│ c │ 109 │────►│ a │ 105 │────►│ t │  0  │
└───┴─────┘     └───┴─────┘     └───┴─────┘
    100             109             105

一个结点有两格:数据格放一个字符,地址格放下一个结点的地址。

本节问题
怎样用C语言把这张箭头图做出来?

第一步:定义类型。要用C语言把它实现出来,先得有结点。结点用2.3学过的结构体表示:

c
typedef 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:

c
Node *L = NULL;    /* 头指针:现在是空链表 */
text
L = NULL

链表不需要像顺序表那样记长度和容量。结点是一个一个申请的,用多少申请多少,没有"容量";要知道有几个结点,从L出发数一遍就行。

选中正文里的任意文字,就可以针对它发表评论