线性表

来自计算思维百科
跳转至: 导航搜索

线性表(Linear List)是零个或多个数据元素的有穷序列。通常可表示成

a1,a2,…,an (n≥0)

式中:n称为表的长度。若n=0,则线性表为空表。当n≥1时,a1称为第1个元素,an称为最后一个元素,称ai是ai+1的前驱,ai+1是ai的后继,i为ai的序号(或叫索引)。

线性表的逻辑结构是线性结构。在线性结构中所有结点按“一个接一个排列”的方式相互关联,从而组成一个整体。线性结构的基本特征是:若至少含有一个结点,则除起始结点没有直接前驱外,其他结点有且仅有一个直接前驱;除终端结点没有直接后继外,其他结点有且仅有一个直接后继。直接前驱和直接后继从不同的角度刻画了同一种关系,即结点间的逻辑关系(邻接关系)。在线性结构中,这种邻接关系是一对一的,也就是说每个结点至多只有一个直接前驱且至多只有一个直接后继。而所有结点按一对一的邻接关系构成的整体就是线性结构。 

线性结构中的一个结点代表一个数据元素,其含义可以是各种各样的,但同一线性表中的元素必定具有相同特性。

例如,一个星期中的七天表示为(Sun, Mon, Tue, Wed, Thu, Fri, Sat),它是一个线性表,表中的数据元素是一周中每一天的名称。

一个学校的学生健康情况登记表如图1所示,它也是一个线性表,表中的数据元素是一条条记录,每个记录由姓名、学号、性别、年龄、班级和健康状况等数据项组成。

3.2.9.png

图1学生健康情况登记表