Skip to content
第2章

2.13 链表的删除 ​

删除第0个结点 ​

本节问题
从链表里删掉一个字符,怎么写成函数?删掉的结点去哪了?

和插入一样,删除也分两种情形:删第0个,和删某个结点后面的那个。先看简单的。

屏幕上是c|at,按退格,删掉c,是Delete(L, 0)。操作前是cat,要达到的样子:

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

对照两张图,变了两处:头指针从100变成了109;c结点不见了,100号的两个格子还给了系统。

第一步:记下要删的c结点。c结点的地址100在头指针里,用q记下来:

c
Node *q = L;                              /* 100号,c 结点 */
text
L = 100
  │
  ▼
┌───┬─────┐     ┌───┬─────┐     ┌───┬─────┐
│ c │ 109 │────►│ a │ 105 │────►│ t │  0  │
└───┴─────┘     └───┴─────┘     └───┴─────┘
    100             109             105
     q

第二步:让头指针越过c结点。c的下一个是a,c结点的地址格是109,抄给头指针:

c
L = q->next;                              /* 头指针改成 109 */
text
L = 109
  │
  └──────────────┐
                 ▼
┌───┬─────┐     ┌───┬─────┐     ┌───┬─────┐
│ c │ 109 │────►│ a │ 105 │────►│ t │  0  │
└───┴─────┘     └───┴─────┘     └───┴─────┘
    100             109             105
     q

c结点还在100号,只是从头出发再也走不到它了。

第三步:把c结点还给系统。和2.8一样,malloc申请来的空间,不用了要用free还回去:

c
free(q);                                  /* 100号还给系统 */

这就得到了要达到的样子:at。

第一步不能省。第二步一改,头指针就不再记着100了;不先用q记下来,就没法释放c结点。

第三步必须放在最后。释放之后,100号就不归我们了,再读它的地址格是错的。

空表没有第0个:L是NULL,删不了,返回0。写成代码:

c
Node *q = *L;                             /* 第一步:记下要删的结点 */
if (q == NULL) return 0;                  /* 空表,没有第0个 */
*L = q->next;                             /* 第二步:头指针越过它 */
free(q);                                  /* 第三步:还给系统 */
选中正文里的任意文字,就可以针对它发表评论