线性表是最基本、最简单、也是最常用的一种数据结构。线性，是说数据在逻辑结构上具有线性关系。线性关系指的是数据一个挨着一个，总体呈线性分布。就好比我们小时候玩“老鹰捉小鸡”游戏中，小朋友们全都手拉着手，它们之间的关系就可以称为线性关系。将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。

1、线性表的定义

线性表是具有相同数据类型的n（n ≥ 0）个数据元素的有限序列，其中n为表的长度，当n = 0 时，线性表是一个空表，若用L命名线性表，则其一般表达式为：L = （a1,a2,a3,···,an）

图1：线性表

上图中，a1是唯一的“第一个”数据元素，又称为表头元素；an是唯一的“最后”一个元素，又称为表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且只有一个直接后继。

对于线性表中的数据来说，位于当前数据之前的数据统称为“前趋元素”，前边紧挨着的数据称为“直接前趋”；同样，后边的数据统称为“后继元素”，后边紧挨着的数据称为“直接后继”。除非在线性表中插入或者删除数据元素，否则数据之间的关系不会改变。

图2：当前数据的前趋和后继

线性表只对数据的逻辑结构有要求，根据实际存储的物理结构的不同，逻辑结构上相邻的数据在实际的物理存储中有两种形式：集中存储和分散存储。

数据元素在内存中集中存储，采用顺序表示结构，简称“顺序存储”；数据元素在内存中分散存储，采用链式表示结构，简称“链式存储”。

2、线性表的顺序存储结构

线性表的顺序存储结构，指的是用一段地址连续的存储单元一次存储线性表的数据结构。线性表的顺序存储示意图如下：

图三：线性表的顺序结构

也就是说逻辑结构上呈线性分布的数据元素在实际的物理存储结构中也同样相互之间紧挨着，按照前后的次序全部存储在一整块连续的内存空间中，之间不存在空隙，这种存储结构称为线性表的顺序存储结构。线性表的顺序存储又称顺序表。它是用一组连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第一个元素存储在线性表的起始位置，第 i 个元素的存储位置后面紧挨着存储的第 i+1 个元素，称 i 为元素ai在线性表中位序。

使用顺序存储结构存储的数据，第一个元素所在的地址就是这块存储空间的首地址。通过首地址，可以轻松访问到存储的所有的数据，只要首地址不变，数据永远都能找着。而使用线性表的顺序存储结构生成的表，称为顺序表。如下图所示：

图4：顺序表

3、顺序存储结构的操作

线性表中元素的位序是从 1 开始的，而数组中元素的下标是从0开始的。

假定线性表的元素类型为ElemType, 则线性表的顺序存储类型描述为：

#define MaxSize 50			   /*定义线性表的最大长度*/Typedef int ElemTypetypedef struct{	 ElemType data[MaxSize];    /*数组存储数据元素，最大值为MaxSize*/			 int length;				   /*顺序表的长度*/}SqList;					       /*顺序表的类型定义*/

这里，顺序存储结构需要三个属性：

存储空间的起始位置：数组data,它的存储位置就是存储空间的存储位置；线性表的最大存储容量：数组长度MaxSize;线性表的当前长度：length。

一维数组可以是静态分配也可以是动态分配，静态分配时，数组的大小和空间事先定好了，一旦空间占满，再加入新的数据将会产生溢出，进而导致程序崩溃，故可采用动态分配的方法。

#define InitSize 100		    //表长度的定义typedef struct{					  ElemType *data;			//指示动态分配数组的指针	  int MaxSize, length;	   //数组的最大容量和当前个数}SeqList;					   //动态分配数组顺序表的类型定义初始化顺序表

（1）初始化顺序表

void Init_SeqList(SeqList& L){     L.elem = (ElemType*)malloc(List_INIT_SIZE * sizeof(ElemType) );    L.length = 0;    L.listsize = List_INIT_SIZE; }  

（2）插入操作

线性表的插入运算是指在表的第 i (1≤i≤n+1)个位置前插入一个新元素 e，使长度为n的线性表 (，…,，，…，) 变成长度为 n+1 的线性表（，…,，M，，…，）（其中 n 为 L 的表长度）。

用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将原表中位置 n，n-1，…，i 上的结点，依次后移到位置 n+1，n，…，i+1 上，空出第 i 个位置，然后在该位置上插入新结点 e。当 i=n+1 时，是指在线性表的末尾插入结点，所以无需移动结点，直接将 e 插入表的末尾即可。

图5：顺序表插入元素

bool ListInsert(SqList &L, int i, ElemType e){	   if( i < 1 || i > L.length + 1)			//判断 i 的范围是否有效	  	return false;									    if(L.length >= MaxSize)					//当前存储已满，不能插入		  return false;    	for(int j = L.length; j >= i; j--)	//将第i个元素及后面的元素后移		  L.data[j] = L.data[j - 1];    	L.data[i - 1] = e;						//将位置 i 放入e	    L.length++;						   //线性表的长度加1	    return ture;}

最好情况：在表尾插入(即 i = n +1)，元素后移不执行，时间复杂度为O(1);

最坏情况：在表头插入(即 i = 1)，元素后移将执行 n 次，时间复杂度为 O(n);

线性表插入算法的平均时间复杂度为O(n)。

（3）删除操作

线性表的删除运算是指将表的第 i(1≤i≤n)个元素删去，使长度为n的线性表 (，…,，(M)，，…，)，变成长度为 n-1 的线性表(，…,，，…，)。

用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此当需要删除第 i 个元素时，必须将原表中位置在 i+1,i+2，…，n-1，n 上的结点，依次前移到位置 i,i+1, …n-1。（其中n为 L 的表长度）。

图6：顺序表删除元素

bool ListDelete(SqList &L, int i, ElemType &e){   	if(i < 1 || i > L.length)			//判断 i 的范围是否有效		return false;							  	e = L.data[i - 1];					//将删除元素的值赋给e	  for(int j = i; j < L.length; j++)	//将第 i 个位置后的元素前移		L.data[j - 1] = L.data[j];	  L.length--;							//线性表的长度减 1  	return true;}

最好情况：在表尾删除(即 i = n)，无需移动元素，时间复杂度为O(1);

最坏情况：在表头删除(即 i = 1)，需移动除第一个元素外的所有元素，时间复杂度为 O(n);

线性表删除算法的平均时间复杂度为O(n)。

（4）按值查找

在顺序表 L 中查找第一个元素等于 e 的元素，并返回其位序。

int LocateElem(SqList L, ElemType e){int i;	for(i = 0; i < L.length; i++){		   if(L.data[i] == e)			  return i+1;	 //下表为 i 的元素等于 e, 返回其位序 i + 1； 	     }	     return 0;				 //退出循环，说明查找失败}

最好情况：查找的元素就在表头，仅需要比较一次，时间复杂度为O(1);

最坏情况：查找的元素在表尾（或不存在）时，需要比较 n 次，时间复杂度为 O(n);

线性表按值查找的平均时间复杂度为O(n)。

4、线性表顺序存储结构的优缺点

（1）优点： 无须为顺序表中元素之间的逻辑关系而增加额外的存储空间；可以快速地存取表中任一位置的元素。

（2）缺点：插入或者删除元素不方便，需要移动大量元素；存储空间利用率低，预先分配内存可能会造成浪费。

【参考文献】数据结构(C语言版）、大话数据结构、算法导论、算法设计与分析基础.