Skip to content
第2章

2.1 线性表 ​

什么是线性表 ​

这一行字可以看成一个线性表。

把字符换成任意一种元素,n个同类型的元素排成一列,就是线性表。n叫表的长度。元素的位置从0开始编号:第0个元素记作a₀,第1个记作a₁,最后一个是第n−1个,记作aₙ₋₁。整个表写成(a₀, a₁, …, aₙ₋₁)。

屏幕上的cat看成线性表,就是(c, a, t)。它的长度是3,第0个元素a₀是c,a₁是a,a₂是t。

这个定义里有四个要点,逐条看。

同类型。表里的元素都是同一种东西。cat里的c、a、t都是字符,这一行里不会混进一个整数,也不会混进一张图片。所以程序只需要准备一种格子,专门放字符。

一个接一个。元素之间有先后,而且是一个接一个。一个元素前面紧挨着的那个元素,叫它的前驱;后面紧挨着的那个元素,叫它的后继。一个接一个的意思是:除了第一个,每个元素恰好有一个前驱;除了最后一个,每个元素恰好有一个后继。在(c, a, t)里,a的前驱是c,后继是t;c没有前驱,t没有后继。

程序为什么要在乎先后?因为cat和act是两行不同的字。程序如果只记住"有c、a、t三个字符",就打印不出这一行。它还得记住谁在谁前面。

教材里常说线性表是"有序"的。这个"有序"指的是位置有先后,不是按大小排好了序。(c, a, t)没有按字母顺序排,照样是线性表。

个数有限。表的长度n是一个确定的数,可以是0。长度为0的表叫空表,记作()。编辑器刚启动时,屏幕上只有光标|,这一行就是空表。之后每敲一个字符,长度加1。程序任何时候都要知道现在有几个字符,否则就不知道显示到哪里为止。

可以重复。同一个元素可以出现在不同的位置。敲book时有两个o,两个都要记住,它们分别是第1个和第2个元素。

回到本章开头的第一个问题:程序要记住这一行字的什么?这一行字可以看成一个线性表,所以程序得记住三样东西:有哪些元素,它们的先后,现在有几个。

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