线性表

线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中：
　① 存在一个唯一的被称为“第一个”的数据元素；
　② 存在一个唯一的被称为“最后一个”的数据元素；
　③ 除第一个元素外，每个元素均有唯一一个直接前驱；
　④ 除最后一个元素外，每个元素均有唯一一个直接后继。

线性表的定义

线性表(Linear List) ：是由n(n≧0)个数据元素(结点)a1，a2， …an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。

• 当n=0时，称为空表。
• 当n>0时，将非空的线性表记作： (a1，a2，…an)
• a1称为线性表的第一个(首)结点，an称为线性表的最后一个(尾)结点。
• a1，a2，…ai-1都是ai(2≦i≦n)的前驱，其中ai-1是ai的直接前驱;
• ai+1，ai+2，…an都是ai(1≦i ≦n-1)的后继，其中ai+1是ai的直接后继。

线性表的顺序存储结构

顺序存储 ：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。
顺序存储的线性表的特点：

• 线性表的逻辑顺序与物理顺序一致;
• 数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。

设有非空的线性表：(a1，a2，…an) 。顺序存储如下图1-1所示。
设线性表的每个元素需占用l个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：
LOC(ai+1)=LOC(ai)+l
线性表的第i个数据元素ai的存储位置为：
LOC(ai)=LOC(a1)+(i-1)*l

图1-1.png

线性表的链式存储结构

__链式存储 __：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。
　　存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。
　　链表中结点的逻辑顺序和物理顺序不一定相同。

为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置），称为指针或链(link）

链表的结点结构
┌───┬───┐
│data │next │
└───┴───┘
data域--存放结点值的数据域
next域--存放结点的直接后继的地址（位置）的指针域（链域）
注意：
①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。
②每个结点只有一个链域的链表称为单链表（Single Linked List）