Skip to content
第2章

2.12 链表的插入 ​

在第0个位置插入结点 ​

本节问题
在链表里插入一个字符,怎么写成函数?插入的位置不同,做法一样吗?

插入分两种情形:插在第0个,和插在某个结点后面。先看简单的。

光标在行首|cat,敲b,要变成b|cat。b成为第0个字符,是Insert(L, 0, 'b')。操作前是cat:

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

要达到的样子,假设b结点放在112号:

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

对照两张图,变了两处:多了b结点,它的地址格写着100;头指针从100变成了112。c、a、t一个没动。

第一步:申请b结点。和2.10造结点一样,用malloc申请一个结点,假设得到112号,用q记住它:

c
Node *q = (Node *)malloc(sizeof(Node));   /* 112号 */
q->data = 'b';
q->next = NULL;
text
L = 100
  │
  ▼
┌───┬─────┐     ┌───┬─────┐     ┌───┬─────┐
│ c │ 109 │────►│ a │ 105 │────►│ t │  0  │
└───┴─────┘     └───┴─────┘     └───┴─────┘
    100             109             105

┌───┬─────┐
│ b │  0  │
└───┴─────┘
    112
     q

第二步:让b结点指向c结点。b的下一个是原来的第一个结点c。c的地址100正记在头指针里,抄给b结点:

c
q->next = L;                              /* b 结点的地址格写 100 */
text
L = 100
  │
  ▼
┌───┬─────┐     ┌───┬─────┐     ┌───┬─────┐
│ c │ 109 │────►│ a │ 105 │────►│ t │  0  │
└───┴─────┘     └───┴─────┘     └───┴─────┘
    100 ▲           109             105
        │
┌───┬───┴─┐
│ b │ 100 │
└───┴─────┘
    112
     q

第三步:让头指针指向b结点。头指针从100改成112:

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

从头出发:112、100、109、105,读出bcat。

第二步和第三步的顺序不能反。c的地址100只记在头指针里。要是先做第三步,把头指针改成112,100就没人记着了,c、a、t三个结点都再也找不到。

先让新结点指向后一个,再让前一个指向新结点。这里的"前一个"是头指针;下一页插在中间时,"前一个"是一个结点,顺序还是这个顺序。

空表也是这种情形。头指针是NULL,第二步b结点的地址格得到NULL,正好是结束标记;第三步头指针改成112,表里就有了一个结点。2.10搭cat的第三步,做的就是这件事。

写成代码。'b'换成要插的字符x,L换成*L;malloc申请不到时,插入失败,返回0:

c
Node *q = (Node *)malloc(sizeof(Node));   /* 第一步:申请新结点 */
if (q == NULL) return 0;
q->data = x;
q->next = *L;                             /* 第二步:新结点指向原来的第一个 */
*L = q;                                   /* 第三步:头指针指向新结点 */
选中正文里的任意文字,就可以针对它发表评论