1、线性表的定义：有零个或多个数据元素组成的有序数列。
线性表是一种常用的数据结构。在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。
线性表是一个线性结构，它是一个含有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有且仅有一个直接前驱。
所以线性表元素的个数n(n ≥ 0)定义为线性表长度，当n=0时，称为空表。
在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。
2、线性表的抽象数据类型
数据类型 : 是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
例如很多编程语言的整型、浮点型、字符型这些指的就是数据类型。
抽象：是指抽取出事物具有的普遍性的本质。它要求抽出问题的特征而忽略非本质的细节，是对具体事物的一个概括。抽象是一种思考问题的方式，它隐藏了繁杂的细节。
我们对已有的数据类型进行抽象，就有了抽象数据类型。
抽象数据类型(Abstract Data Type,ADT) 是指一个数据模型及定义在该模型上的一组操作。
抽象数据类型的定义仅取决于它的一组逻辑性，而与其在计算机内部如何表示和实现无关。
线性表的抽象数据类型定义如下：
ADT 抽象数据类型名
Data 数据元素之间逻辑关系的名称
Operation 操作
endADT
ADT 线性表(List)
Data
线性表的数据对象集合为{a1,a2,....,an},每个元素的类型均为DataType。其中除了，第一个元素a1外，每一个元素有且只有一个直接前驱元素，除最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
InitList(*L):初始化操作，建立一个空的线性表。
ListEmpty(L):若线性表为空，返回true，否则返回false。
ClearList(\*L):线性表清空。
GetElem(L,i,\*e):将线性表L中第i个位置元素返回给e。
LocateElem(L,e):在线性表L中查找与给定值e相等的元素，如果
查找成功,返回该元素在表中的序列号；否则，返回0表示失败。
ListInsert(\*L,i,e):在线性表的第i个位置插入元素e。
ListDelete(\*L,i,\*e):删除线性表L中的第i个元素，并用e返回其值
ListLength(L):返回线性表L的元素个数。<br>
endADT
对于不同的应用，线性表的操作时不同的，上述操作时最基本的，问题中设计的关于线性表的更复杂操作，完全可以用这些基本操作的组合来实现。
比如，要实现两个线性表集合A和B的并集操作。即要使得集合A = A ∪ B，说白了，就是把存在集合B中但并不存在中的数据元素插到A中即可。
假设我们La表示集合A，Lb表示集合B
示例如下：
//将所有的在线性表Lb中但不在La中的元素插入到La中
void unionL(List *La , List Lb)
{
int La_len,Lb_len,i;
ElemType e;
La_len = ListLength(*La);
Lb_len = ListLength(*Lb);
for(i = 0 ;i ≤ Lb;i++)
{
GetElem(Lb,i,*e);//取出Lb中第i个数据元素赋给e
if(!LocateElem(*La,e))//La中不存在和e元素相同的数据元素
{
ListInsert(La,++La_len,e);//插入
}
}
}
3、线性表的顺序存储结构
线性表有两种物理存储结构：顺序存储结构和链式存储结构。
3.1、顺序存储结构定义
线性表的顺序存储结构，指定的是用一段地址连续的存储单元一次存储线性表的数据元素。
3.2、顺序存储结构方式
线性表的顺序存储方式，说白了，就是在内存中找了一块地方，把一定内存空间占了，然后把相同数据类型的数据元素一次存在在里面。既然线性表的数据元素的类型都相同，所以用C语言的一维数组来实现顺序存储结构，即把第一个数据元素存储到数组下表为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。
为了建立一个线性表，要在内存中找一块地，于是这块地的第一个位置就非常关键，它是存储空间的起始位置。
线性表中，我们估算这个线性表的最大存储容量，建立一个数组，数组的长度就是最大存储容量。
我们已经有了起始位置，也有了最大的容量，于是我们可以在里面增加数据了。随着数据的插入，我们线性表的长度开始变大，不过线性表的当前长度不能超过存储容量，即数组的长度。
接下来看线性表顺序存储的结构代码：
#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int length; //线性表当前长度
}SqList;
顺序存储结构封装需要三个属性：
- 存储空间的起始位置，数组data，它的存储位置就是线性表存储空间的存储位置。
- 线性表的中最大存储容量，数组的长度MaxSize。
- 线性表的当前长度:length。
注意，数组的长度与线性表的当前长度需要区分一下：数组的长度是存放线性表的存储区间的总长度，一般初始化后不变。而线性表的当前长度是线性表中元素的个数，是会变化的。
3.3、数组长度与线性表长度区别
数组长度是存放线性表的存储空间的长度，存储空间分配完一般是不变的。
线性表长度是线性表中元素数据的个数，随着线性表插入和删除操作的进行，这个量是变化的。
在任意时刻，线性表的长度应该小于等于数组的长度。
3.4、地址计算方法
线性表的起始是从1开始的，可数组却是从0开始开始第一个下标的，于是线性表中第i个元素，存储在数组小标为i-1的位置。
用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此分配的数组空间要大于等于当前线性表的长度。
由于每个数组元素，不管它是整形、实型还是字符型，它都是需要占用一定的存储空间。
假设占用的是c个存储单元，那么线性表中第i+1个元素的存储位置和第i个元素的存储位置的关系是(LOC表示获得存储位置的函数)：
LOC(ai+1) = LOC(ai) + c;
所以对于第i个数据元素ai的存储位置可以由a1推算出：
LOC(ai) = LOC(ai) + (i-1)*c
通过这个公式，随时可以算出线性表中任意位置的地址，不管他是第一个还是最后一个，都是相同的事件。那么我们对每个线性表位置的存入或者取出数据，对于计算机来说都是相等的时间，也就是一个常数，因此我们算法中学到的时间复杂度的概念来说，它的存取时间的性能为O(1)。我们通常把具有这一特点的存储结构称为随机存取结构。
4、顺序存储结构的插入与删除
4.1、获得元素操作
对于线性的顺序存储结构来说，我们要实现GetItem操作，即将线性表L中的第i个位置元素返回，其实是非常简单的。就程序而言，只要第i个元素在下标的范围内，就是把数组第i-1个下标值返回即可。
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status
//Status是函数的类型，其值是函数结果状态代码，如OK等
//初始条件：顺序线性表L已经存在，1 <=i <= ListLength(L)
//操作结果：用e反回L中第i个元素的值。
Status GeElem(SqList L,int i,ElemType *e){
if(L.length==0 || i < 1 || i >L.length){
return ERROR;
}
*e = L.data[i-1];
return OK;
}
注意这里返回值类型Status是一个整型，返回OK代表1，ERROR代表0。
4.2、插入操作
线性表的顺序存储结构具有随机存储结构的特点，时间复杂度为O(1);
如果我们要实现ListInsert(*L,i,e),即在线性表L中的第i个位置插入新元素e，应该如何操作？
所以插入算法操作：
- 如果插入位置不合理，抛出异常；
- 如果线性表长度大于等于数组长度，则抛出异常或动态增加数组容量；
- 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置。
- 将要插入元素填入位置i处
- 线性表长+1
实现代码如下：
//初始条件:顺序线性表L已存在,1 ≤ i ≤ ListLength(L)
//操作结果:在L的第i个位置插入新的数据元素e,L的长度加1
Status ListInsert(SqList *L,int i,ElemType e)
{
int k;
if(L->length == MAXSIZE)//当线性表已满
return ERROR;
if(i < 1 || i >L->length + 1)//当i不在范围内时
{
return ERROR;
}
if(i <= L->length)//若插入数据位置不在表尾
{
for(k = L->length-1;k > i-1;k--)
{
L->data[k + 1] = L->data[k];
}
}
L->data[i - 1] = e;//将新元素插入
L->length++;
return OK;
}
4.3、删除操作
删除算法的思路：
- 如果删除位置不合理，抛出异常
- 取出删除元素
- 从删除元素位置开始遍历到最后一个元素位置，分别将它们向前移动一个位置
- 表长减一
实现代码如下：
//初始条件:顺序线性表L已经存在，1 <= i <= ListLength(L)
//操作结果:删除L的第i个元素,并用e返回其值,L的长度减1
Status ListDelete(SqList *L ,int i , ElemType *e)
{
int k;
if(L->length == 0)//线性表为空
return ERROR;
if(i < 1 || i > L->length)//删除位置不正确
return ERROR;
*e = L->data[i-1];
if(i < L->length)
{
for(k = i;k < L->length;k++)
L->data[k - 1] = L->data[k];
}
L->length--;
return OK;
}
现在，我们来分析一下，插入和删除的事件复杂度。
现在我们来看最好的情况，如果一个元素要插入到最后一个位置，或者删除最后一个位置，此时时间复杂度为O(1)，因为不需要移动元素的。
最坏的情况呢，如果元素要插入到第一个位置或者删除第一个元素，此时时间复杂度是多少呢？那就意味着所有元素向后或者向前，所以这个时间复杂度为O(n)。
至于平均的情况，由于元素插入到第i个位置，或者删除第i个元素，需要移动n - i个元素，每个位置插入或删除元素的可能性是相同的，也就是位置靠前，移动元素多，位置靠后，移动元素少。最终平均移动次数和最中间那个元素的移动次数相等，为(n - 1)/ 2。
根据时间复杂度的推导，平均时间复杂度还是O(n)。
这说明：
线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1)；而插入或删除时，时间复杂度都是O(n)。这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。
4.4、线性表顺序存储结构的优缺点
优点:
-
无须为表中元素之间的逻辑关系而增加额外的存储空间
-
可以快速地存取表中任一位置的元素
缺点:
-
插入和删除需要移动大量元素
-
当线性表长度变化较大时，难以确定存储空间的容量
-
造成存储空间的“碎片”
特别感谢：
鱼C工作室小甲鱼
微信号kpioneer
网友评论