外观
2.2 线性表的操作
线性表的基本操作
2.1节说的是线性表"是什么"。要用它,还得规定能对它做什么。1.3节说过,逻辑关系加上一组操作,就是抽象数据类型。这一节给线性表定下这组操作。
线性表常用的操作有很多,不同的程序用到的不一样,没有哪一组适合所有用途。这里取最基本的五个,编辑器正好都要用。下面把表记作L,位置记作i,要插入的元素记作x。
Init(L):建立一个空表。编辑器刚启动时,这一行一个字符都没有。程序先要有一个空表,之后才能往里放字符。
Length(L):返回表的长度n。程序每一步都要把整行重新显示出来,它得知道一共有几个字符,显示到哪里为止。这就是上一节说的"现在有几个",Length就是用来问这个数的。
Get(L, i):返回第i个元素,也叫按位查找。知道了有几个,还要一个一个拿出来显示。显示cat,就是依次取第0个、第1个、第2个元素:c、a、t。i必须是已有元素的位置,也就是在0到n−1之间。
Insert(L, i, x):在第i个位置插入x。原来第i个及之后的元素,位置都加1。表(a₀, …, aₙ₋₁)变成(a₀, …, aᵢ₋₁, x, aᵢ, …, aₙ₋₁),长度加1。
屏幕是ca|t时敲x,x落在a和t之间,也就是第2个位置;原来在第2个的t变成第3个。这一步就是Insert(L, 2, x),表从(c, a, t)变成(c, a, x, t):
text
0 1 2 0 1 2 3
┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐
│c│ │a│ │t│ ──► │c│ │a│ │x│ │t│
└─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘i可以等于n。在cat|的末尾敲一个s,就是Insert(L, 3, s),s追加到最后。所以Insert的i在0到n之间。
Delete(L, i):删除第i个元素。之后的元素,位置都减1。表(a₀, …, aₙ₋₁)变成(a₀, …, aᵢ₋₁, aᵢ₊₁, …, aₙ₋₁),长度减1。
屏幕是cax|t时按退格,删掉的是x。x在第2个位置,这一步就是Delete(L, 2)。表从(c, a, x, t)回到(c, a, t),t又回到第2个位置:
text
0 1 2 3 0 1 2
┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐
│c│ │a│ │x│ │t│ ──► │c│ │a│ │t│
└─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘Delete的i不能等于n。第n个位置上没有元素,没有东西可删。所以Delete的i在0到n−1之间。
左右移动光标不改这一行字,表不变,所以不需要操作。
插在第几个、删第几个,由光标的位置决定。光标怎么用一个数记下来、怎么算出i,是编辑器自己的事。这一点留到2.6做编辑器时再讲。
五个操作汇总如下:
| 操作 | 含义 | i的范围 |
|---|---|---|
| Init(L) | 建立一个空表 | |
| Length(L) | 返回表的长度n | |
| Get(L, i) | 返回第i个元素 | 0 ≤ i ≤ n−1 |
| Insert(L, i, x) | 在第i个位置插入x,原来第i个及之后的元素位置都加1 | 0 ≤ i ≤ n |
| Delete(L, i) | 删除第i个元素,之后的元素位置都减1 | 0 ≤ i ≤ n−1 |
常见的还有按值查找、判空、销毁等操作,用到时再加。比如2.8节会加一个销毁操作。
编辑器的敲字、退格、显示,都能用这五个操作做到。这就回答了本章开头的第二个问题:要对这一行字做哪些事。