外观
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 1052.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合不合法;链表没有记长度,只能走着看。