1.初识顺序表
在了解顺序表的定义之前，我们需要先了解一下什么是线性表：
线性表，全名为线性存储结构。使用线性表存储数据的方式可以这样理解，即“把所有数据用一根线儿串起来，再存储到物理空间中”
在了解完线性表的概念之后，我们在来看顺序表：
（1）顺序表的定义
数据结构在内存中的表示通常有两种形式，一种是顺序存储，另一种是链式存储。线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的数据元素，我们把这种存储形式存储的线性表称为顺序表。
例如，使用顺序表存储集合 {1,2,3,4,5}，数据最终的存储状态如图 1 所示：
由上图可知顺序表存储数据同数组非常接近。其实，顺序表存储数据使用的就是数组。
（2）顺序表的特点
1. 顺序表的逻辑结构和物理结构是一致的，都是连续的。
2. 顺序表中任意一个数据元素都可以随机存取，所以顺序表是一种随机存取的存储结构。
这样我们就初步的了解了顺序表。
2.顺序表的分类
从上边我们已经了解到了顺序表存储数据使用的就是数组，而数组又分为了静态数组和动态数组，所以顺序表也顺其自然的分成了静态顺序表和动态顺序表。
我们直接使用代码来看一下两种顺序表的定义：
【1】静态顺序表
//静态顺序表 #define SLDateType int #define NUMBER 10 typedef struct SeqList { SLDateType arr[NUMBER]; int size; }SL;
由上边的代码我们可以看到，静态顺序表由一个定长的数组和一个 int 类型的变量size组成（size的作用是用来记录该数组中的元素个数）。
【2】动态顺序表
//动态顺序表 #define SLDateType int typedef struct SeqList { SLDateType* arr; int size; int capacity; }SL;
由上边的代码我们可以看到，动态顺序表是由一个指针（该指针存放一个数组的地址，该数组可以使用一些方法使其长度发生变化），一个 int 类型的变量size（size的作用是用来记录该数组中的元素个数）和一个 int 类型的变量capacity组成（capacity用来记录数组的容量）。
注：当然在日常的使用或者工作中，我们大部分都是使用动态顺序表（相较于静态顺序表更加灵活）来存储数据并使用顺序表的一些功能来对数据进行操作的。
这样我们就了解了顺序表的分类和其它们的定义方式了。
3.顺序表的功能
顺序表可以大致包含以下几个功能：
1. 初始化顺序表中的数据。
2. 打印顺序表中的数据。
3. 对顺序表进行尾插(末尾插入数据)。
4. 对顺序表进行尾删(末尾删除数据)。
5. 对顺序表进行头插(开头插入数据)。
6. 对顺序表进行头删(开头删除数据)。
7. 对顺序表查找数据。
8. 对顺序表数据进行修改。
9. 指定位置插入数据。
10. 删除指定位置数据。
11. 销毁顺序表。
这里我们只需要大致的了解顺序表又哪些功能就可以，下面我们会对这10个功能进行详细的讲解。
4.顺序表中各种功能的实现
接下来我们就开始对顺序表中的几个功能开始进行讲解（使用动态顺序表）：
我们首先定义动态顺序表：
//动态顺序表 #define SLDateType int typedef struct SeqList { SLDateType* arr; int size; int capacity; }SL;
【1】 初始化顺序表中的数据。
我们直接使用代码来看一下：
1. //动态顺序表的初始化 2. void SLInit(SL* sl) 3. { 4. assert(sl); 5. sl->arr = NULL; 6. sl->size = 0; 7. sl->capacity = 0; 8. }
初始化顺序表时，我们先将数组长度设置为0（即为NULL，之后添加数据时在扩容），将元素个数和数组长度设置为0。
【2】 打印顺序表中的数据。
我们直接使用代码来看一下：
//打印数据 void SLPrint(SL* sl) { assert(sl); for (int i = 0; i < sl->size; i++) { printf("%d ", sl->arr[i]); } printf("\n"); }
打印数据只需要使用循环变量数组来打印就可以了。
【3】对顺序表进行尾插(末尾插入数据)。
我们直接使用代码来看一下：
//向数据表的尾部插入数据 void SLPushBack(SL* sl, SLDateType n) { //对传入的指针进行判断，判断是否为空指针 assert(sl); //判断数组是否需要扩容 if (sl->size == sl->capacity) { //如果数组容量为0，则设置为5，如果不为0，则扩大为两倍 int Newcapacity = sl->capacity = 0 ? 5 : 2 * (sl->capacity); SLDateType* temp = (SLDateType*)realloc(sl->arr, Newcapacity * sizeof(SLDateType)); if (temp == NULL) { perror("realloc is wrong"); exit(1); } sl->arr = temp; temp = NULL; sl->capacity = Newcapacity; } //添加数据 sl->arr[sl->size++] = n; }
在上边的代码中我们发现，当数组满了之后，我们需要对数组进行扩容之后，在向数组中添加数据。
【4】对顺序表进行尾删(末尾删除数据)。
我们直接使用代码来看一下：
//删除顺序表尾部数据 void SLPopBack(SL* sl) { //对传入的指针进行判断，判断是否为空指针 assert(sl); //原来的数组中要有数据 assert(sl->size); sl->size--; }
在对顺序表进行尾删的时候，我们根本不需要删除数组末尾的数据，我们只需要将记录元素个数的数减小1，这样我们在使用的时候就不会使用到末尾的数据了。
【5】对顺序表进行头插(开头插入数据)。
我们直接使用代码来看一下：
//向顺序表的头部插入数据 void SLPushFront(SL* sl, SLDateType n) { //对传入的指针进行判断，判断是否为空指针 assert(sl); //判断数组是否需要扩容 if (sl->capacity == sl->size) { //如果数组容量为0，则设置为5，如果不为0，则扩大为两倍 int Newcapacity = sl->capacity = 0 ? 5 : 2 * (sl->capacity); SLDateType* temp = (SLDateType*)realloc(sl->arr, Newcapacity * sizeof(SLDateType)); if (temp == NULL) { perror("realloc is wrong"); exit(1); } sl->arr = temp; temp = NULL; sl->capacity = Newcapacity; } //将所有的数据都往后移动一位 for (int i = sl->size; i >=1 ; i--) { sl->arr[i] = sl->arr[i-1]; } //添加数据 sl->arr[0] = n; sl->size++; }
在进行对顺序表进行头插的时候，我们也需要判断数组是否可以添加一个数据，并且由于我们是头插，所以要将原来数组中所有的数据都往后移动一位
【6】 对顺序表进行头删(开头删除数据)。
我们直接使用代码来看一下：
//删除顺序表头部数据 void SlPopFront(SL* sl) { //对传入的指针进行判断，判断是否为空指针 assert(sl); //原来的数组中要有数据 assert(sl->size); //将除了第一个位置的其他位置的元素往前移动一位 for (int i = 0; i<sl->size-1; i++) { sl->arr[i] = sl->arr[i + 1]; } sl->size--; }
将除了第一个位置的其他位置的元素往前移动一位，这样就可以将第一位的数据进行覆盖掉，完成对顺序表进行头删的操作。
【7】 对顺序表查找数据。
我们直接使用代码来看一下：
//对顺序表查找数据 int SeqListFind(SL*sl, SLDateType n) { //对传入的指针进行判断，判断是否为空指针 assert(sl); int i = 0; for (i = 0; i < sl->size; i++) { if (sl->arr[i] == n) { //找到则返回该值在数组中的下标 return i; } } //没有查找到则返回-1 return -1; }
我们遍历数组查找想要的数据就可以，如果没有找到，则返回-1。
【8】对顺序表数据进行修改。
我们直接使用代码来看一下：
//对顺序表数据进行修改 void SeqListModify(SL* sl, int pos, SLDateType x) { //对传入的指针进行判断，判断是否为空指针 assert(sl); //原来的数组中要有数据 assert(sl->size > 0); //检查pos下标的合法性 assert(pos >= 0 && pos < sl->size); //修改pos下标处对应的数据 sl->arr[pos] = x; }
总体的思路就是先判断是否可行后将对应位置的数据进行修改。
【9】指定位置插入数据
我们直接使用代码来看一下：
//在指定位置插入数据 void SeqInsert(SL* sl, int pos, SeqType n) { //对传入的指针进行判断，判断是否为空指针 assert(sl); //判断指定位置的合理性 assert(pos >= 0 && pos <= sl->size); //判断是否需要扩容 if (sl->size == sl->capacity) { int newcapacity = (sl->capacity == 0 ? 5 : 2 * (sl->capacity)); SeqType* temp = (SeqType*)realloc(sl, newcapacity * sizeof(SeqType)); if (temp == NULL) { perror("realloc fail"); exit(1); } sl = temp; temp = NULL; sl->capacity = newcapacity; } //添加数据 for (int i = sl->size - 1;i>=pos; i--) { sl->arr[i + 1] = sl->arr[i]; } sl->arr[pos] = n; sl->size++; }
在指定位置插入数据时，我们需要判断位置的合理性，即是否是在可以插入的位置进行插入，判断完后，我们判断是否需要扩容，判断完后我们进行数据的插入。
【10】删除指定位置数据
我们直接使用代码来看一下：
//删除指定位置数据 void SeqListErase(SL* sl, int pos) { //对传入的指针进行判断，判断是否为空指针 assert(sl); //顺序表不能为空 assert(sl->size > 0); //检查pos下标的合法性 assert(pos >= 0 && pos < sl->size); //将pos位置后面的数据依次向前挪动一位，完成覆盖 for (int i = pos + 1; i < sl->size; i++) { sl->arr[i - 1] = sl->arr[i]; } //存储的数据-1 sl->size--; }
对于删除指定位置数据，我们只需要将指定位置数据后面的数据全部向前移动一位完成覆盖即可。
【11】 销毁顺序表。
我们直接使用代码来看一下：
//销毁顺序表 void SLDelete(SL* sl) { //将创建的数据空间进行回收 assert(sl); if (sl->arr) { free(sl->arr); sl->arr = NULL; } sl->size = sl->capacity = 0; }
从上边的代码中我们知道，我们开创的数组的空间是由malloc函数开辟的，所以在使用完顺序表之后要对该空间进行归还。
