外观
2.6 用顺序表实现编辑器
编辑器要做什么
前五节把顺序表和它的五个操作做出来了。这一节用它们实现2.1开头的那个单行编辑器。
为了把程序写得简单,我们用一行指令代替一次按键。用户能做的事只有五件:
| 指令 | 相当于 | 效果 |
|---|---|---|
i c | 敲字符c | c插入到光标处,光标移到它后面 |
d | 按退格键 | 删掉光标前面那个字符,光标跟着前移 |
l | 按左方向键 | 光标左移一格,已在行首则不动 |
r | 按右方向键 | 光标右移一格,已在行尾则不动 |
q | 退出 |
每处理一条指令,程序都把整行打印出来,光标位置用|标出。编辑器只管一行文字,字符只有英文字母和空格,空格用_输入。
把敲出cat、在a和t之间插入x再删掉这一串动作换成指令,就是下面这段会话。左边是输入的指令,右边是程序的输出:
text
i c c|
i a ca|
i t cat|
l ca|t
i x cax|t
d ca|t
r cat|
q本节问题用顺序表和它的五个操作,怎么把这个编辑器做出来?
编辑器的初始化
编辑器要记两样东西:这一行字,和光标的位置。
这一行字用一个顺序表L记。编辑器刚启动时一个字符都没有,所以先调用Init,得到一个空表。
光标用一个整数cursor记。它的意思是:光标左边有几个字符。刚启动时,光标左边一个字符都没有,所以cursor是0:
text
┌───┬───┬───┬───┬───┐
data │ ? │ ? │ ? │ ? │ ? │ length = 0
└───┴───┴───┴───┴───┘
0 1 2 3 4
▲
cursor = 0光标总是夹在两个字符之间,所以图里把它画在格子之间的竖线下面。
再看一个有字符的例子。屏幕是ca|t时,光标左边有c、a两个字符,cursor是2:
text
┌───┬───┬───┬───┬───┐
data │ c │ a │ t │ │ │ length = 3
└───┴───┴───┴───┴───┘
0 1 2 3 4
▲
cursor = 2行尾也一样。屏幕是cat|时,光标左边有3个字符,cursor是3,正好等于长度。
光标是编辑器自己的东西,线性表里没有它。表只管存字符,光标由编辑器另外记着。
写成代码:定义一个顺序表L和一个整数cursor,cursor一开始是0;再调用Init,把L变成空表。
c
SeqList L;
int cursor = 0;
Init(&L);敲字符和退格
五条指令里,只有敲字符和退格会改这一行字,先看这两条。每条指令要回答两件事:对表做什么操作,光标怎么变。想清楚之后,再写成代码。下面都从屏幕ca|t开始,这时cursor是2。
敲字符:i c。在ca|t里敲x,x要出现在光标的位置。光标左边有2个字符,所以x成为第2个字符,也就是调用Insert(L, 2, x),原来的t被挤到第3个:
text
┌───┬───┬───┬───┬───┐
data │ c │ a │ x │ t │ │ length = 4
└───┴───┴───┴───┴───┘
0 1 2 3 4
▲
cursor = 3x插在了光标左边,光标左边多了一个字符,所以cursor加1,变成3。屏幕是cax|t。
一般地,敲字符就是Insert(L, cursor, c),然后cursor加1。
写成代码:敲进来的字符记在ch里,先把_换成空格。Insert可能失败,比如表满了,所以看它的返回值,成功才把cursor加1。
c
if (ch == '_') ch = ' '; /* 空格用_输入 */
if (Insert(&L, cursor, ch)) cursor++;
else printf("插入失败\n");退格:d。在cax|t里按退格,删的是光标左边紧挨着的那个字符x。光标左边有3个字符,紧挨着的那个是第2个,也就是调用Delete(L, 2):
text
┌───┬───┬───┬───┬───┐
data │ c │ a │ t │ t │ │ length = 3
└───┴───┴───┴───┴───┘
0 1 2 3 4
▲
cursor = 2光标左边少了一个字符,cursor减1,变成2,屏幕回到ca|t。data[3]里留下的t不用管,长度说了算。
一般地,退格就是Delete(L, cursor−1),然后cursor减1。cursor为0时,光标左边没有字符,什么都不做。
写成代码:
c
if (cursor > 0) {
Delete(&L, cursor - 1);
cursor--;
}移动光标、退出和显示
剩下的三条指令都不改这一行字。再加上每条指令之后都要做的显示。
左移、右移:l和r。移动光标不改这一行字,所以不调用任何操作,只改cursor。左移减1,到0就不再动;右移加1,到长度就不再动。
写成代码,各是一行:
c
if (cursor > 0) cursor--; /* l:左移 */
if (cursor < Length(&L)) cursor++; /* r:右移 */退出:q。结束程序。它不改表也不改光标,在下一页读指令的循环里处理:读到q就不再往下读。
显示。显示不是一条指令,但每条指令之后都要做。从第0个到第Length−1个字符,逐个用Get取出来打印;走到第cursor个字符之前,先打一个|。光标在行尾时,cursor等于长度,循环里碰不到它,循环结束后要补一个|。
显示要在每条指令之后反复用,所以写成一个函数Show:
c
void Show(SeqList *L, int cursor) {
int n = Length(L);
for (int i = 0; i < n; i++) {
if (i == cursor) printf("|");
printf("%c", Get(L, i));
}
if (cursor == n) printf("|");
printf("\n");
}把指令合在一起:编辑器1.0
前三页的代码已经齐了:初始化、每条指令的代码、显示用的Show。剩下的是把它们装进一个循环。
编辑器从启动到退出,做的就是这个循环:读一条指令,执行它,把整行显示出来,再读下一条,直到q。
读指令。每条指令是一个字母,用scanf(" %c", &cmd)读。格式串开头的空格不能省:它让scanf跳过上一条指令留下的换行,否则换行会被当成一条指令。读到q就结束循环。i后面还跟一个字符,在i的分支里再读一次。
执行。按读到的字母选一段代码执行,用switch。每个分支就是前两页里对应指令的那几行代码,原样放进去。
显示。每轮循环的末尾调用一次Show。
合起来就是main:
c
int main(void) {
SeqList L;
int cursor = 0;
char cmd, ch;
Init(&L);
while (scanf(" %c", &cmd) == 1 && cmd != 'q') { /* 读指令 */
switch (cmd) { /* 执行 */
case 'i':
scanf(" %c", &ch);
if (ch == '_') ch = ' ';
if (Insert(&L, cursor, ch)) cursor++;
else printf("插入失败\n");
break;
case 'd':
if (cursor > 0) { Delete(&L, cursor - 1); cursor--; }
break;
case 'l':
if (cursor > 0) cursor--;
break;
case 'r':
if (cursor < Length(&L)) cursor++;
break;
}
Show(&L, cursor); /* 显示 */
}
return 0;
}写进文件时,Show要放在main前面,因为C语言要求函数先定义后使用。
编译运行,逐条输入第1页的会话:
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.0。
再看一眼main和Show:它们只调用了Init、Length、Get、Insert、Delete,从头到尾没有直接读写L.data和L.length。编辑器不知道、也不需要知道字符是怎么存的。这正是2.2节说的抽象数据类型的好处,也是2.5坚持传地址、不用全局变量的目的之一。后面把存储结构换掉时,这段main会原样保留。
练习1:光标一步步怎么变?
填空
屏幕是cat|,cursor是3。依次执行下面四条指令。
l之后,cursor是- 再
l之后,cursor是 i b之后,cursor是d之后,cursor是
屏幕依次是ca|t、c|at、cb|at、c|at。左移一次减1;敲b插在光标处,cursor加1;退格删掉刚敲的b,cursor减1。
练习2:退格调用哪个操作?
单选
屏幕是ca|t,按一次退格。
A
Delete(L, 1)
B
Delete(L, 2)
第2个字符是t,在光标右边。退格删的是光标左边紧挨着的那个。
C
Delete(L, 3)
表里只有第0到第2个字符,没有第3个。
cursor是2,光标左边紧挨着的是第cursor−1个,也就是第1个字符a。
练习3:加一条指令h,要调用哪个操作?
单选
想加一条指令h,把光标移到行首。
A
不需要调用任何操作,只把cursor设为0
B
Delete
移动光标不删字符。
C
Insert
移动光标不加字符。
光标是编辑器自己记的,线性表里没有它。移动光标只改cursor,表不变。
到这里你有了能运行的编辑器1.0:用顺序表记这一行字,用cursor记光标左边有几个字符,main只通过五个操作访问数据。下一步量一量编辑器1.0的效率,找出两个问题。