表的定义和性质
一、表的定义
表是由n(n≥0)个同一类型的元素（结点）a1,a2,…,an组成的有限序列。其中，元素的个数n定义为表的长度。当n=0时称为空表。当n≥l时，我们说元素ai位于该表的第i个位置，或称ai是表中第i个元素，i=1,2,…，n。根据各元素在表中的不同位置可以定义它们在表中的前后次序。我们称元素ai在元素ai+1之前或ai是ai+1的前驱(i=1,2,…,n-1)。同时，我们也称元素ai+1在元素ai之后，或ai+1是ai的后继。另外，称a1为表头(head)，an为表尾(tail)。
由于表的元素具有线性性质，所以又称为线性表。
表是程序设计中使用得最频繁的一种ADT，也是实现其他许多ADT的基础。
二、表的性质
从表的定义不难看出表具有以下数学性质：除了表头和表尾外，表中的每一个元素有且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。
注意：表和数组的区别
从概念上来看，表是一种抽象数据类型；数组是一种具体的数据结构。
从数学性质上来看，表是一个二元关系R，<x,y>∈R
当且仅当x是y的前驱；如果将该二元关系用关系图（将每一个元素用一个点来表示，若x与y有关系则从x到y连一条有向线段）来表示，则得到的是一条单链a1→a2→…→an
，因此表也可以看成是特殊的图或特殊的树（每个节点有且仅有一个子节点）；而数组是从1..n的自然数集合到数组元素集合的一一映射，其中n是数组的长度，1..n中每一个自然数唯一地对应着一个数组元素，反之亦然。所以数组可以用来实现映射。
从物理性质来看，数组中相邻的元素是连续地存储在内存中的，或者对于程序员来说可以认为它们是连续地存储在内存中的，数组的存取对程序员来说是透明的；表只是一个抽象的数学结构，并不具有具体的物理形式，表需要通过其它有具体物理形式的数据结构来实现。在表的具体实现中，表中相邻的元素不一定存储在连续的内存空间中，除非表是用数组来实现的。对于数组，可以利用其下标在一个操作内随机存取任意位置上的元素；对于表，只能根据当前元素找到其前驱或后继，因此要存取第i个位置上的元素，一般不能在一个操作内实现，除非表是用数组实现的。在实现表时需要提供足够的信息以便能够通过表中元素的位置p来存取表中的元素。表中元素的位置p是指示表中元素位置的信息，通过对p进行处理（可能是从事某种函数运算计算出该元素在内存中的位置，也可能从表头开始，依次寻找当前元素的后继，重复i次找到第i个位置的元素）可以得到表中元素在内存中的物理位置，因此不能简单地将位置p理解为类似数组下标的自然数，实际上p可以是各种类型的变量，在数学上可将p定义为一个偏序集上的变量。在具体实现表及其运算时，应区分p与p所表示的位置，以及该位置上的元素三者之间的不同含义。