外观
2.15 用链表实现编辑器
编辑器能不能直接换成链表
2.6用顺序表做出了编辑器1.0,2.8换成动态数组,成了编辑器1.1。它们都跑在顺序表上。
2.11到2.14又做出了链表的六个操作:Init、Length、Get、Insert、Delete、Destroy。名字、参数、返回值,都和顺序表的一样。
现在想让编辑器跑在链表上。main和Show要不要重写一遍?
本节问题把编辑器的存储结构从顺序表换成链表,要改多少代码?
先预测:只改类型名
先不动手,想一想要改什么。
2.6写编辑器时守了一条规矩:main和Show只调用Init、Length、Get、Insert、Delete,2.8又加了Destroy,从来不直接碰L.data和L.length。编辑器只知道这几个操作"能做什么",不知道字符是怎么存的。
链表的六个操作,签名和顺序表的一模一样。2.14的Init也返回成功与否,和2.8的一致。
所以预测:只要把类型名SeqList换成LinkList,main和Show原样能用。要改的只有两处:
c
/* 原来 */ void Show(SeqList *L, int cursor) {
/* 现在 */ void Show(LinkList *L, int cursor) {
/* 原来 */ SeqList L;
/* 现在 */ LinkList L;Show和main的其余部分,一个字都不改,就是2.6、2.8里的样子。
编译时放在一起的是:链表的类型定义typedef struct Node {…} Node, *LinkList;,2.14末尾头结点版的六个操作,再加上Show和main。顺序表的代码,一行都不要。
验证:同一段会话
编译运行,输入2.6的那段会话:
text
i c c|
i a ca|
i t cat|
l ca|t
i x cax|t
d ca|t
r cat|
q输出和编辑器1.1逐行相同,预测成立。这就是编辑器2.0。
屏幕上一模一样,内存里却完全不同。比如敲完x、屏幕是cax|t的那一刻,编辑器1.1的内存里是一段连续的格子:
text
┌───┬───┬───┬───┬───┐
data │ c │ a │ x │ t │ │ length = 4
└───┴───┴───┴───┴───┘
0 1 2 3 4编辑器2.0的内存里,是一串散落在各处的结点:
text
L = 120
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ │ 100 │────►│ c │ 109 │────►│ a │ 102 │────►│ x │ 105 │────►│ t │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘ └───┴─────┘ └───┴─────┘
120 100 109 102 105两个编辑器的cursor都是3,Show都打印出cax|t。main不知道底下是格子还是结点,也不需要知道。
为什么能这样
这不是巧合,是从2.2到现在一路铺垫的结果。
抽象数据类型把"能做什么"和"怎么做到"分开了。编辑器只依赖"能做什么":插入一个字符、删除一个字符、取第i个、求长度。至于"怎么做到",是挪数组里的格子,还是改结点的地址格,编辑器不管。所以"怎么做到"可以整个换掉。
反过来想,如果2.6图省事,在main里写了L.data[cursor] = ch,现在就得重写整个main:链表根本没有data数组。
实际工程里怎么换实现
实际工程里,通常把线性表的实现放在单独的文件里,比如seqlist.c和linklist.c,编辑器只包含一个声明这六个操作的头文件。换实现,就是换一个文件。本书为了阅读方便,把代码写在一起,道理是一样的。
编辑器2.0能跑了。可是换链表的初衷,是解决2.7的问题:在行首附近打字慢。换了之后,到底快没快?下一节量一量。
练习1:换成链表,要改哪几处?
单选
把编辑器1.1换成跑在链表上,main和Show里要改的是什么?
A
只把两处
SeqList换成LinkListB
Insert、Delete的调用都要重写
链表的操作和顺序表的签名一样,调用一个字都不用改。
C
Show里取字符的循环要重写
Show只调用Length和Get,不碰存储结构,循环不用改。
D
要去掉main末尾的Destroy
链表版也有Destroy。结点都是malloc来的,更要释放。
main和Show只通过六个操作用这一行字,而两种实现的六个操作签名一样,所以只有写着类型名的地方要改。
练习2:Show直接顺着next走,会怎样?
单选
有人把编辑器2.0的Show改成直接顺着结点走,不调用Get:
c
void Show(LinkList *L, int cursor) {
int i = 0;
for (Node *p = (*L)->next; p != NULL; p = p->next, i++) {
if (i == cursor) printf("|");
printf("%c", p->data);
}
if (cursor == i) printf("|");
printf("\n");
}在链表上它照样能跑。以后再把存储结构换回顺序表,会怎样?
A
Show编译不过,要重写
B
只改类型名就能跑
顺序表没有结点,也没有next,(*L)->next这样的写法在顺序表上编译不过。
C
能编译,但输出不对
根本编译不过:SeqList里没有next。
这个Show直接碰了链表的存储结构,就和链表绑死了。只调用操作,才能换实现而不改代码。
到这里你有了跑在链表上的编辑器2.0,main和Show只改了类型名。下一步先猜一猜,在一千个字符的行首打字,编辑器1.1和2.0哪个快?下一节量一量。