数据结构——线性结构之线性表

线性结构是一种基本的数据结构，主要用于对具有单一前驱和后继的数据关系进行描述。它的特点是数据元素之间呈现一种线性关系，即是元素”一个接一个排列“。

线性表是最简单、基本和常用的一种线性结构。

一个线性表是n个元素的有限序列，通常表示为(a1, a2, ... , an)，非空线性表的特点如下：

存在唯一的一个”第一个“的元素。

存在唯一的一个”最后一个“的元素。

除第一个元素外，序列中的每个元素均只有一个直接前驱。

除最后一个元素外，序列中的每个元素均只有一个直接后继。

线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

 线性表的链式存储是通过指针链接起来的结点来存储数据元素，基本的结点结构如下所示：

数据域

指针域

存储各元素的结点地址并不要求是连续的，因此存储数据元素的同时必须存储元素之间的逻辑关系。同时，结点空间只有在需要的时候才申请，无须事先分配（顺序存储必须事先分配好空间大小）。

根据结点的指针域的设置方式，还有其他的几种链表结构。

双向链表。每个结点包含两个指针：一个指向前驱，一个指向后继。其特点是从表中任意的结点出发，都可以从两个方向遍历链表。

循环链表。在单向链表（或双向链表）的基础上增加了表尾的指针指向链表的第一个结点，构成循环链表。其特点是从表中任意结点都可以遍历链表。

静态链表。借助数组来描述线性表的链式存储结构，用数组元素的下标表示元素所在结点的指针。