前言
在介绍数据机构时，我们说到了4类基本的数据结构，而今天要聊到的就是最常见的一种数据结构--线性表。而线性表因为自身的一些差异，又分为很多类型。由存储方式不同，而出现了顺序表和链表。由对表的操作限制，而出现了栈和队列。今天就和大家聊一下顺序表。
1.1、什么是线性表
线性表是非常常见的一种数据结构，想我们之前接触过的数组就是一种线性表。线性表的特点就是，元素之间存在一对一的关系。我们先假设有如下顺序表L：
L = {a1, a2, a3, a4, a5, a6......an} 复制代码
我们先选取a2作为参考，a2前面一个元素我们称为直接前驱；a2后面一个元素我们称为直接后继。上面的表中我们可以看到，L中任意一个元素最多有一个直接前驱和一个直接后继。这也就是线性表的性质，只有0或1个直接前驱，只有0或1个直接后继。这也就是我们所说的一对一的关系。
1.2、有哪些常见的线性表
在后续的学习中，我们会学到四种线性表，分别是：顺序表、链表、栈和队列。它们都属于线性表，其中由于物理实现（存储方式）不同，产生了顺序表和链表，两者的区别在于顺序表使用顺序存储结构，而链表使用链式存储结构。我们对线性表的基础操作进行限制，从而产生了栈和队列，栈只能从表的一头进行进出操作，而队列只能在队头进行删除操作，在队尾进行插入操作。
1.3、线性表的一些操作
在具体讲解顺序表之前，我们先看一下我们通常需要实现的一些基于线性表的操作，这些操作对于顺序表，大多都是通用的。
/** * 作用：初始化线性表 * L：线性表的指针 * return：当初始化成功返回1，初始化失败返回0 */ int InitList(*L); /** * 作用：将已经存在的线性表销毁 * L：要销毁的线性表的指针 */ void DestroyList(*L); /** * 作用：清空已存在的线性表 * L：要清空的线性表的指针 */ void CleaerList(*L); /** * 作用：获取线性表长度 * L：要获取长度的线性表 * return：线性表的长度 */ int LengthList(*L); /** * 作用：判断线性表是否为空 * L：要判断的线性表 * return：如果为空返回0，不为空返回其长度 */ int EmptyList(*L); /** * 作用：获取线性表L中的第i个元素，并用*e存储 * L：要操作的线性表 * i：要获取元素的位置 * e：用来存储获取的元素 * return：获取成功返回1，否则返回0 */ int GetEleme(*L, int i, ElemType *e); /** * 作用：获取元素e在线性表L中第一次出现的位置，并用*i存储位置 * L：要操作的线性表 * e：要定位的元素 * i：用于存放获取的定位 * return：定位成功返回1，否则返回0 */ int LocateElem(*L, ElemType e, int *i); /** * 作用：将元素e插入到线性表L中的第i个位置 * L：进行操作的线性表 * i：要插入的位置，从1开始 * e：要插入的元素 * return：如果插入成功返回1，否则返回0 */ int InsertList(*L, int i, ElemType e); /** * 作用：删除L中的第i个元素，用*e来存储 * L：要操作的线性表 * i：要删除元素的位置，从1开始 * e：用来存储被删除的元素 * return：当删除成功返回1，否则返回0 */ int DeleteList(*L, int i, ElemType *e); /** * 作用：打印线性表 * L：要打印的线性表 */ void DisplayList(*L); 复制代码
上面定义了一些线性表的基础操作，在了解这些基础操作后我们就可以进入顺序表的学习了。
二、顺序表
前面也说过顺序表是线性表的一种，可以说常规线性表使用顺序存储结构实现就是顺序表。顺序表中的元素存储在连续的内存中，这种存储方式方便查找，所以对于经常需要查找的数据集合，我们可以选择使用顺序表来存储。
2.1、顺序表的表示
我们在学习数据结构时，通常使用结构体表示一个数据类型。顺序表的表示需要3个数据项，分别是数据、下标、内存大小。其中数据的类型我们通常是不确定的，所以我们需要一个自定义类型，方面修改：
typedef int ElemType; 复制代码
这里我们把int定义为ElemType，后续数据的类型我们将用ElemType代替，接下来我们实现顺序表的结构体：
typedef struct{ ElemType *elem; //数据元素的头指针（基地址） int length; //顺序表的当前长度 int listsize; //顺序表的最大内存：listsize*sizeof(ElemType) }SqList; 复制代码
当然，顺序表的表示方法不是唯一的，有许多教程直接使用一个定长的数组作为数据项也是可以的。
2.2、顺序表的实现
我们知道如何表示顺序表后，就可以实现其各个操作了，在实现各个操作之前，我们先给出几个宏定义：
#define LIST_INIT_SIZE 100 #define LIST_INCREMENT 10 复制代码
其中LIST_INIT_SIZE表示顺序表初始化的长度，LIST_INCREMENT表示当表长不够时，顺序表增加的长度，具体数值可以自己定义。接下来我们来初始化顺序表。
（1）初始化顺序表
表的初始化我们要分别对三个数据项进行操作，各个操作如下：
- elem：动态分配内存，内存空间为（LIST_INIT_SIZE*sizeof(ElemType)）
- length：初始化表长为0
- listsize：初始化表的内存为LIST_INIT_SIZE
我们使用代码实现上面的操作：
int InitList_Sq(SqList *L){ //动态分配内存 L->elem = (ElemType*)malloc(sizeof(ElemType)*LIST_INIT_SIZE); //内存不足 if(!L->elem){ return 0; } //将初始化表长设置为0 L->length = 0; //将初始化表的内存设置为LIST_INIT_SIZE L->list_size = LIST_INIT_SIZE; return 1; } 复制代码
上述方法传入一个顺序表的指针，当初始化成功返回1，失败返回0。
注意：在动态分配内存时，通常会进行强制转换，但是这个操作不是必要的。如果是参加考试，这一步有必要加上。
（2）销毁顺序表
有初始化就有销毁，因为我们是动态分配的内存，需要使用free()函数来将内存释放，代码实现如下：
void DestroyList_Sq(SqList *L){ //释放内存 free(L->elem); //将长度设置为0 L->length = 0; //将内存设置为0 L->list_size = 0; } 复制代码
（3）插入数据
为了尽快检测这个顺序表的功能，我们先来实现插入操作。我们再看看插入输入的流程图：
为了简便流程图，扩展表长时我没有添加对内存是否充足的判断。接下来，我们使用代码来实现上面流程图：
int InsertList_Sq(SqList *L, int i, ElemType e){ //定义一个ElemType指针，当长度不足时用来扩展内存 ElemType *newbase; int j; //插入位置不合法 if(i <= 0 || i > L->length+1){ return 0; } //当前顺序表装满了 if(L->length == L->list_size){ //使用realloc函数重新分配内存 newbase = realloc(L->elem, (L->list_size + LIST_INCREMENT)*sizeof(ElemType)); //无法分配新内存 if(!newbase){ return 0; } //更新为内存扩展后的顺序表 L->elem = newbase; L->list_size += LIST_INCREMENT; } //将最后一个元素，到第i个元素全部往后移动 for(j = L->length; j >= i; j--){ L->elem[j] = L->elem[j-1]; } //将e放入第i个元素的存放的位置，该位置为：L->elem[i-1] L->elem[i-1] = e; //顺序表的长度+1 L->length++; return 1; } 复制代码
（4）显示顺序表
接下来我们看看如何显示这个顺序表，因为指针很多用法和数组一样，我们可以使用下标的方式来访问顺序表的元素：
void DisplayList_Sq(SqList *L){ for (int i = 0; i < L->length; i++) { printf("%d\n", L->elem[i]); } } 复制代码
我们还可以使用下面方式访问元素：
printf("%d\n", *((L->elem)+i)); 复制代码
这里就是指针的知识了，在这里就不继续扩展了。
注意：L->elem[0]实际上是*(L->elem)的简便写法，只是一个语法糖，本质没有区别。
然后我们可以测试一下上面的方法：
int main(){ SqList L; //声明一个顺序表 InitList_Sq(&L); //初始化顺序表 //循环添加数据 for(int i = 0; i < 300; i++){ InsertList_Sq(&L, i+1, i+1); } //显示顺序表 DisplayList_Sq(&L); //销毁顺序表 DestroyList_Sq(&L); return 0; } 复制代码
因为数据量比较大，打印结果就不贴出来了，大家可以自己测试一下。
注意：for(int i = 0; i < 10; i++)这种在循环内定义变量的方式是c99中的新特性。考试中不认同这种写法。
（5）删除数据
删除数据我们同样需要传入三个参数，第一个是顺序表，第二个是要删除元素的位置，第三个则是用来返回删除的元素。具体实现如下：
int DeleteList_Sq(SqList *L, int i, ElemType *e){ //当传入的位置不合法 if(i < 0 || i > L->length-1){ return 0; } //用e接收删除的数据 *e = L->elem[i-1]; //顺序表的长度减1 L->length--; //从第i个元素（第i个元素下标为i-1）开始遍历数据 for(int j = i-1; j < L->length; j++){ //将后一个元素的值赋值给前一个 L->elem[j] = L->elem[j+1]; } return 1; } 复制代码
（6）定位元素
这里我们是获取某个元素在顺序表中第一次出现的位置，并用一个变量来存储这个位置。
int LocateElem_Sq(SqList *L, ElemType e, int *i){ int j; //遍历顺序表中的元素 for(j = 0; j < L->length; j++){ //当匹配到了数据时 if(L->elem[j] == e){ //记住其位置，（下标+1）返回1 *i = j+1; return 1; } } //未匹配到任何数据 return 0; } 复制代码
（7）获取元素
上面是通过数据元素获取其位置，而这里是通过下标获取元素。这个要更简单一些。
int GetElem_Sq(SqList *L, int i, ElemType *e){ //当传入的i不合法，返回0 if(i < 0 || i > L->length){ return 0; } //存储顺序表中第i个元素 *e = L->elem[i-1]; return 1; } 复制代码
（8）清空顺序表
顺序表的清空和销毁是不同的概念，清空只是对表中的数据清空，不会对内存进行释放。而表的销毁则是将我们动态申请的内存释放掉。
void ClearList_Sq(SqList *L){ //将顺序表的长度置为0 L->length = 0; } 复制代码
在我们调用该方法后，其实我们仍然可以使用基地址获取到其它元素，但是我们设想的是关于顺序表的全部操作都使用我们预定义的这些方法来实现，这样我们是获取不到那些数据的。
（9）判断表是否为空
int EmptyList_Sq(SqList *L){ //长度为0是返回1，表示是空表 if(L->length == 0){ return 1; } //否则返回0，表示不是空表 return 0; } 复制代码
（10）获取表的长度
int LengthList_Sq(SqList *L){ //返回表的长度 return L->length; } 复制代码
到此为止，我们就实现了顺序表常用的一些基本操作了。
2.3、顺序表的一些其它操作
除了一些常用的操作外，有时候我们还需要实现一些特殊的操作，像是表的复制、表的合并、表的反转等，现在我们就来实现一些特殊的操作，读者可以根据自己的兴趣选择阅读。
（1）复制顺序表
复制顺序表的实现需要我们传入两个顺序表，第一个是被复制的顺序表，我们将第一个顺序表的数据复制到第二个顺序表中。
int CopyList_Sq(SqList *L1, SqList *L2){ //申请和L1大小一致的内存空间 L2->elem = malloc(sizeof(ElemType)*L1->list_size); //内存不足是返回0 if(!L2->elem){ return 0; } //设置L2的长度 L2->length = L1->length; //设置L2的内存 L2->list_size = L1->list_size; //循环赋值 for(int i = 0; i < L2->length; i++){ L2->elem[i] = L1->elem[i]; } return 1; } 复制代码
（2）合并顺序表
在实现合并顺序表的时候，我们可以借用已经实现的一些操作，让我们的合并更简单。
int MergeList_Sq(SqList *L1, SqList *L2, SqList *L3){ int status = -1; //先复制L1表 status = CopyList_Sq(L1, L3); if(!status){ return 0; } //将L2表中的数据添加到L3中 for(int i = 0; i < L2->length; i++){ status = InsertList_Sq(L3, L3->length+1, L2->elem[i]); if(!status){ return 0; } } return 1; } 复制代码
上述算法实现起来比较简单，但是其效率是非常低的，大家可以自己改进一下。
（3）反转顺序表
void ReversalList_Sq(SqList *L){ //临时变量，用于交换 ElemType temp; //将顺序表前一半元素和后一半元素交换 for(int i = 0; i < L->length/2; i++){ temp = L->elem[i]; L->elem[i] = L->elem[L->length-1-i]; L->elem[L->length-1-i] = temp; } } 复制代码
关于顺序表的知识，就讲到这了。
