4.1.1 线性表的特性

线性表是一种最基本、最简单、最常用的数据结构。在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。因为这些特殊线性表都有自己的特性，所以掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率是至关重要的。

线性表是一种线性结构，是一个含有n≥0个节点的有限序列。在节点中，有且仅有一个开始节点没有前趋节点并且有一个后继节点，有且仅有一个终端节点没有后继节点并且有一个前趋节点，其他节点都有且仅有一个前趋节点和一个后继节点。通常可以把线性表表示成线性序列：k1，k2，…，kn，其中k1是开始节点，kn是终端节点。

1．线性结构的特征

在编程领域中，线性结构具有如下两个基本特征。

（1）集合中必须存在唯一的“第一元素”和“最后元素”。

（2）除最后元素外，均有唯一的后继元素；除第一元素外，均有唯一的前趋元素。

由n(n≥0)个数据元素（节点）a1，a2，…，an组成的有限序列，数据元素的个数n定义为表的长度。当n=0时称为空表，通常将非空的线性表（n＞0）记作：（a1，a2，…，an）。数据元素ai(1≤i≤n)没有特殊含义，不必“追根问底”地研究，它只是一个抽象的符号，其具体含义在不同的情况下可以不同。

2．线性表的基本操作过程

线性表虽然只是一对一关系，但是其操作功能非常强大，具备很多操作技能。线性表的基本操作如下。

（1）Setnull(L)：置空表。

（2）Length(L)：求表的长度和表中各元素的个数。

（3）Get(L,i)：获取表中的第i个元素（1≤i≤n）。

（4）Prior(L,i)：获取i的前趋元素。

（5）Next(L,i)：获取i的后继元素。

（6）Locate（L,x)：返回指定元素在表中的位置。

（7）Insert(L,i,x)：插入新元素。

（8）Delete(L,x)：删除已有元素。

（9）Empty(L)：判断表是否为空。

3．线性表的结构特点

线性表具有如下结构特点。

（1）均匀性：虽然不同数据表的数据元素各种各样，但同一线性表的各数据元素必须有相同的类型和长度。

（2）有序性：各数据元素在线性表中的位置只取决于它们的序号。数据元素之前的相对位置是线性的，即存在唯一的“第一个”和“最后一个”数据元素，除了第一个和最后一个元素外，其他元素的前面只有一个数据元素直接前趋，后面只有一个数据元素直接后继。