每次都从头找
2.15做出了编辑器2.0,留下一个问题:换成链表之后,到底快没快?
用2.7的方法量一量。2.9说过,链表插入、删除不用挪动,步数全花在从头走到要改的结点上。编辑器2.0的每条指令,都按光标的位置去找结点。设这一行有n个字符:
- 敲字符、退格:调用Insert、Delete,要从头结点走到光标处。光标在行首,一步不走;在行尾,走n步。最坏O(n)。
- 右移:先要调用Length看是不是到了行尾。链表没有记长度,Length要从头数一遍,O(n)。
- 左移:只改cursor,O(1)。
- 显示:Show调用n次Get,每次Get都从头走,合起来是n×n步,O(n²)。顺序表的Show是O(n),换成链表,显示慢了一个量级。
求长度也可以是O(1)
给链表多加一个变量记长度,求长度就是O(1),不用每次从头数一遍。代价是插入、删除时,要记得把它加1、减1。多花一个变量的空间,省下数一遍的时间,这是常用的"空间换时间"。
行首打字确实快了:顺序表要挪n个字符,链表一步不用走。可在行尾打字,反而是顺序表快:顺序表一个都不挪,链表要走n步。编辑器2.0并没有整体变快,步数只是从挪动搬到了走路。
最慢的是行尾。看一个例子:屏幕是cats|,再敲一个e。
敲e,调用的是Insert(L, 4, 'e')。链表要先找到第3个结点s,才能把e接在它后面。可链表没有格子可算,只能从头结点出发,一个一个往后走:
textL = 120
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ │ 100 │────►│ c │ 109 │────►│ a │ 105 │────►│ t │ 116 │────►│ s │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘ └───┴─────┘ └───┴─────┘
120 100 109 105 116
头结点 prev
走了4步,才走到s结点。可s结点就是上一次刚接上去的,光标也一直停在它后面。
一行有一千个字符时,每敲一个字,都要从头走一千步。光标明明一直停在那里,程序却每次都从头找一遍。
本节问题光标一直停在同一个地方。能不能不再每次从头找?
给定结点,在它后面插入
从头找,是因为光标只记了"第几个"。那就换个记法:光标直接记住它左边那个字符的结点。屏幕是cats|时,光标记s结点。光标在行首时,左边没有字符,就记头结点。
插入时,把这个结点交给操作,不再交"第几个"。2.14的插入有四步,看看怎么变:
- 找到前一个结点。原来要从头结点走i步。现在不用走,交进来的结点就是前一个结点。
- 申请新结点。不变。
- 新结点指向后一个。不变。
- 前一个指向新结点。不变。
只有第一步没了。敲e时,光标记着s结点,e直接接在它后面:
text ┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
... ───►│ t │ 116 │────►│ s │ 124 │────►│ e │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘
105 116 124
p q
像这样直接给出一个结点,在它后面插入,叫按结点操作,教材里常说"指定结点的插入、删除"。原来的操作给的是"第几个",教材里把这个"第几个"叫位序,那种操作叫按位序操作。
写成函数,叫InsertAfter:在结点p后面插入x。和2.14的Insert比,去掉了开头走i步的循环和位置检查,prev换成了p:
cint InsertAfter(LinkList *L, Node *p, char x) {
Node *q = (Node *)malloc(sizeof(Node)); /* 申请新结点 */
if (q == NULL) return 0;
q->data = x;
q->next = p->next; /* 新结点指向后一个 */
p->next = q; /* p指向新结点 */
return 1;
}
不管表有多长,都是固定几步,O(1)。参数L在这里用不到,照样写上,是为了和其他操作一样,说清"对哪个表做"。
其他操作怎么改
从按位序换成按结点,2.14里凡是用到"第几个"的地方,都要换一种说法。逐个看。
删除:Delete(L, i)换成DeleteAfter(L, p)。和插入一样,去掉第一步走路,删p后面那个结点。p后面没有结点时,没有东西可删,返回0:
cint DeleteAfter(LinkList *L, Node *p) {
if (p->next == NULL) return 0; /* p后面没有结点 */
Node *q = p->next; /* 记下要删的结点 */
p->next = q->next; /* 越过它 */
free(q); /* 还给系统 */
return 1;
}
取元素:Get(L, i)换成Data(p)。不用走,直接读p的数据格。
行首:位置0换成Head(L)。按结点说,行首就是头结点。
往后一个:i+1换成Next(p)。顺着p的地址格走一步。
这三个各只有一行:
cNode *Head(LinkList *L) { return *L; }
Node *Next(Node *p) { return p->next; }
char Data(Node *p) { return p->data; }
只有一行,也写成操作,是守2.15立下的规矩:编辑器只调用操作,不碰存储结构。下一节换存法时,这条规矩还会派上用场。
往前一个:i−1换成Prev(L, p)。这一个变不简单。单链表的结点只记后一个结点的地址。站在p上,往后一步就到;往前,却没有任何记录。唯一的办法是从头结点出发往后走,走到"下一个就是p"的那个结点为止。
比如屏幕是cat|,光标在t结点上,要找它的前一个:
text┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ │ 100 │────►│ c │ 109 │────►│ a │ 105 │────►│ t │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘ └───┴─────┘
120 100 109 105
q 走0步 q 走1步 q 走2步 p
下一个是p
q从头结点出发,走2步到a结点,它的下一个就是p。Prev返回a结点:
cNode *Prev(LinkList *L, Node *p) {
Node *q = *L; /* 从头结点出发 */
while (q != NULL && q->next != p) /* 走到下一个是p为止 */
q = q->next;
return q; /* p是头结点时,走到NULL */
}
p是第i个结点时,要走i步,Prev是O(n)。
q != NULL不能省
p是头结点时,没有哪个结点的下一个是它。q会一直走过最后一个结点,走到NULL。这时如果不先判断,就会去读NULL的next,程序崩溃。有了这个判断,Prev走到头就返回NULL,正好表示"头结点没有前一个"。
初始化、求长度、销毁。它们不涉及位置,不用改。
汇总如下:
| 原来按位序 | 现在按结点 | 单链表上 |
|---|
| Insert(L, i, x) | InsertAfter(L, p, x):在p后面插入x | O(1) |
| Delete(L, i) | DeleteAfter(L, p):删除p后面的结点 | O(1) |
| Get(L, i) | Data(p):返回p的字符 | O(1) |
| 位置0 | Head(L):返回头结点 | O(1) |
| i+1 | Next(p):返回p后面的结点,没有时返回NULL | O(1) |
| i−1 | Prev(L, p):返回p前面的结点,p是头结点时返回NULL | O(n) |
只有往前一步要从头走,其余都是O(1)。
编辑器2.1
光标改成一个结点:Node *cursor,一开始指向头结点。显示从头结点后面的第一个结点走起,走到光标结点时,在它后面打|;光标是头结点时,|打在最前面:
cvoid Show(LinkList *L, Node *cursor) {
if (cursor == Head(L)) printf("|");
for (Node *p = Next(Head(L)); p != NULL; p = Next(p)) {
printf("%c", Data(p));
if (p == cursor) printf("|");
}
printf("\n");
}
敲字符用InsertAfter,右移用Next,左移用Prev。退格删的是光标结点本身,也就是它前一个结点后面的那个:先用Prev找到前一个,再DeleteAfter:
cint main(void) {
LinkList L;
Node *cursor;
char cmd, ch;
if (!Init(&L)) return 1;
cursor = Head(&L); /* 行首 */
while (scanf(" %c", &cmd) == 1 && cmd != 'q') {
switch (cmd) {
case 'i':
scanf(" %c", &ch);
if (ch == '_') ch = ' ';
if (InsertAfter(&L, cursor, ch)) cursor = Next(cursor);
else printf("插入失败\n");
break;
case 'd':
if (cursor != Head(&L)) {
Node *prev = Prev(&L, cursor);
DeleteAfter(&L, prev);
cursor = prev;
}
break;
case 'l':
if (cursor != Head(&L)) cursor = Prev(&L, cursor);
break;
case 'r':
if (Next(cursor) != NULL) cursor = Next(cursor);
break;
}
Show(&L, cursor);
}
Destroy(&L);
return 0;
}
退格的三行,顺序不能乱
DeleteAfter删掉的,正是光标指着的那个结点。所以要先用Prev找到前一个,删完再把光标移过去。如果删完不改cursor,它就指着一个已经还给系统的结点,后面的显示和操作都不可靠。
编译时放在一起的是:结点类型的定义,2.14末尾的Init和Destroy,这一节的六个操作,再加上Show和main。输入2.6的那段会话:
texti c c|
i a ca|
i t cat|
l ca|t
i x cax|t
d ca|t
r cat|
q
输出和编辑器2.0逐行相同。这就是编辑器2.1。每条指令的时间复杂度,套用上一页的表就能得出:
| 指令 | 编辑器2.0 | 编辑器2.1 |
|---|
| 敲字符 | O(n) | O(1) |
| 右移 | O(n) | O(1) |
| 显示 | O(n²) | O(n) |
| 左移 | O(1) | O(n) |
| 退格 | O(n) | O(n) |
往后的都快了,用到Prev的左移和退格还是O(n)。
链表没换,结点还是那些结点,只是从按位序换成了按结点,敲字符就从O(n)变成了O(1)。顺序表凭位序一步就能找到格子,链表凭结点一步就能找到地方。操作用什么指出位置,决定了实现能有多快。
实际工程里的按结点操作
C++标准库的链表用"迭代器"指出位置,Weiss的《数据结构与算法分析》用Position,说的都是这一节的按结点操作。它的单链表forward_list,提供的正是insert_after和erase_after,和这一节的InsertAfter、DeleteAfter一样。它也没有"往前一步"的操作,原因和单链表的Prev一样。