外观
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
qc结点还在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); /* 第三步:还给系统 */