Skip to content
第2章

2.11 链表的初始化与读取 ​

初始化、求长度、取第i个元素 ​

2.10手工搭出了cat,又把它输出了一遍。那是专门为cat写的:多一个字符,就要多写几行。从这一节起,把链表上的事写成通用的操作。

本节问题
链表的初始化、求长度、取第i个元素,怎么写成C函数,而且参数、返回值和顺序表的一样?

签名和顺序表一样,编辑器才能原样搬过来。顺序表的操作,参数都是SeqList *L,SeqList这个名字代表整张表。链表也给"整个链表"起一个名字:把2.10类型定义的最后一行改成} Node, *LinkList;。

c
typedef struct Node {
    char         data;
    struct Node *next;
} Node, *LinkList;

LinkList就是Node *,用来代表整个链表。2.10的Node *L,以后写成LinkList L。

LinkList:就是Node *

最后一行} Node, *LinkList;一次定义了两个名字,相当于下面两句:

c
typedef struct Node Node;    /* Node 是结点类型 */
typedef Node *LinkList;      /* LinkList 就是 Node *,指向结点的指针 */

名字里看不出那个星号,要记住LinkList是一个指针。Node *p和LinkList p是同一个类型。习惯上,指一个结点时写Node *,代表整个链表时写LinkList。

链表的操作,参数都写成LinkList *L。main里照样写Init(&L)、Insert(&L, 2, 'x'),只是L的类型从SeqList换成了LinkList。

每个操作都当成一个问题来解,办法和2.10把cat存进链表一样:先画出要达到的样子;再一步一步做,每一步写一两行代码,对照图看它改了什么;最后把具体的换成一般的,写成函数。

初始化。编辑器刚启动,一个字符都没有,要先有一个空表。要达到的样子,就是2.10的第二步,头指针等于NULL:

text
L = NULL

只要一步:

c
L = NULL;

写成函数。L是main里的变量,函数要改它,参数就写成LinkList *L,函数里的*L就是main的L:

c
void Init(LinkList *L) {
    *L = NULL;
}

为什么写*L

Init要改的是main里的L。2.5讲过:要在函数里改main的变量,就传它的地址。所以main里调用Init(&L),参数的类型是LinkList *,也就是指向头指针的指针。

函数里的*L,就是main里的那个L。写成L = NULL,改的只是函数自己的参数,main的L不会变。

后面每个操作都这样:参数是LinkList *L,函数里用*L表示头指针。Length和Get不改头指针,参数也这样写,是为了和顺序表的签名一致。

求长度。显示这一行之前,要知道有几个字符。表里是cat时,要返回3:

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

2.10输出链表时,指针p从L出发,一个结点一个结点走到NULL。求长度走的是同一条路,只是把打印换成计数:

c
int n = 0;
for (Node *p = L; p != NULL; p = p->next)
    n++;                 /* 每到一个结点,计数加1 */

p依次是100、109、105,n数到3;再走一步,p成了NULL,停下。

写成函数。头指针换成*L,最后返回n:

c
int Length(LinkList *L) {
    int n = 0;
    for (Node *p = *L; p != NULL; p = p->next)
        n++;
    return n;
}

取第i个元素。显示时要把字符一个一个取出来。比如取第2个,也就是t:

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

第一步:从头出发。p等于L,到了100号,是第0个结点:

c
Node *p = L;             /* 100号,第0个 */

第二步:走两步。每走一步,p换成当前结点地址格里的数:

c
p = p->next;             /* 109号,第1个 */
p = p->next;             /* 105号,第2个 */

第三步:取数据。p指向t结点,取出它的数据:

c
char c = p->data;        /* t */

取第2个走了两步,取第i个就要走i步。位置越靠后,走得越远。这是链表的代价:顺序表取第i个,直接就能找到它所在的格子。

2.9讲得失时,已经看到过这一点。

写成函数。取第i个元素,就是从第0个结点出发走i步。走着走着p成了NULL,说明没有第i个;i是负数也不合法。这两种情况,和顺序表一样返回'\0':

c
char Get(LinkList *L, int i) {
    if (i < 0) return '\0';              /* 位置不合法 */
    Node *p = *L;                        /* 第一步:从头出发 */
    for (int k = 0; k < i && p != NULL; k++)
        p = p->next;                     /* 第二步:走i步 */
    if (p == NULL) return '\0';          /* 没有第i个 */
    return p->data;                      /* 第三步:取数据 */
}

带入Get(L, 5):走到105号之后再走一步,p成了NULL,循环停下,返回'\0'。顺序表拿i和长度比一下,就知道i合不合法;链表没有记长度,只能走着看。

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