1
算法与数据结构  C语言版
1.4.1.1 2.1.1 线性表的定义
2.1.1 线性表的定义

线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系,数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的,或者说线性表是由同一类型的数据元素构成的线性结构。在实际问题中线性表的例子是很多的,如学生情况信息表是一个线性表,表中数据元素的类型为学生类型;一个字符串也是一个线性表:表中数据元素的类型为字符型,等等。

综上所述,线性表定义如下:

线性表是具有相同数据类型的n(n≥0)个类型相同的数据元素组成的有限序列。至于每个数据元素的具体含义,在不同的情况下各不相同,它可以是一个数或一个符号,也可以是一页书,甚至其他更复杂的信息。

线性表通常记为:(a1,…,ai1,,ai,ai+1,,…,an),其中n为表长,n=0时称为空表。

表中相邻元素之间存在着顺序关系,ai1领先于ai,ai领先于ai+1,称ai1是ai的直接前驱元素,ai+1是ai的直接后继元素。当i=1,2,…,n-1时,ai有且仅有一个直接后继;当i=2,3,…,n时,ai有且仅有一个直接前驱ai1;当i=1,2,…,n-1时,有且仅有一个直接后继ai+1,而a1是表中第一个元素,它没有前趋,an是最后一个元素,无后继。

线性表是一个相当灵活的数据结构,它的长度可以根据需要增长或缩短,即对线性表的数据元素不仅可以进行访问,还可以进行插入和删除等。