Skip to content
第2章

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个及之后的元素位置都加10 ≤ i ≤ n
Delete(L, i)删除第i个元素,之后的元素位置都减10 ≤ i ≤ n−1

常见的还有按值查找、判空、销毁等操作,用到时再加。比如2.8节会加一个销毁操作。

编辑器的敲字、退格、显示,都能用这五个操作做到。这就回答了本章开头的第二个问题:要对这一行字做哪些事。

选中正文里的任意文字,就可以针对它发表评论