外观
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; /* 第三步:头指针指向新结点 */