线性表
基本概念
线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。这些元素也可称为结点或表目.
在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。
逻辑结构
用二元组(K,R)来表示线性表,则有:
1 | K={k0,k1,k2,...,kn-1} |
当n=0时，线性表不包含任何数据元素，称为空表
当n>0时，线性表称为非空表
用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱.
线性表的关系r具有反对称性和传递性.
举例说明:
设R为非空集合A上的二元关系
反对称性: ((x,y)∈R∧(y,x)∈R→x=y )
传递性: ((x,y)∈R∧(y,z)∈R→(x,z)∈R)
假设R为“小于等于”（前驱/后继关系），则
反对称性：x<=y and y<=x => x=y
传递性：x<=y and y<=z => x<=z
存储结构
线性表主要由顺序表示或链式表示。在实际应用中，常以栈、队列、字符串等特殊形式使用。
顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构或顺序映像（sequential mapping）。它以“物理位置相邻”来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。
链式表示指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。
在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素的存储映像，称为结点（node）。它包括两个域；存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链.
