博客大纲
顺序表
顺序表定义
顺序表的定义要求，用一组连续的地址依次存储相同类型的数据。
不知道大家看完这个定义，有没有想起我们曾学过的数组，数组的数据类型是一致的，而一个数组的地址也是连续的。
顺序表其实就是一个进阶版本的数组，它可以做到在指定位置增删元素，按需更改长度，并保证数据依然是连续的。
接下来我们就讲解顺序表的C语言实现。
需要具备的知识主要包括：结构体，指针，函数，动态内存管理。
构造顺序表的基本结构分析
我们实现的顺序表要求：随意更改长度，指定位置增删元素。
既然要随意更改长度，必然会使用到动态内存，我们可以在堆区开辟空间，在顺序表空间不足时用realloc及时开辟空间。
既然使用了动态内存，不论是使用malloc还是realloc开辟空间，我们得到的返回值都是一个指针，想要使用这个顺序表，就需要用到指针来访问。
我们实现的顺序表功能有非常多，如果用户要使用我们的顺序表，就要有一定的输入方式，在此我们可以利用不同的函数来实现不同功能，像这样的函数就叫做“接口”。
那么我们现在如果得到一个顺序表，我们会需要用到顺序表的什么信息？
我们需要这个顺序表的指针来访问顺序表
我们需要这个顺序表的当前元素个数，比如在输出顺序表时控制边界，在插入或删除元素时控制顺序表的元素移动。
我们需要这个顺序表当前所拥有的内存，当其内存不足以插入新数据时，及时开辟新的内存
我们既然有这么多的信息需要存储，我们就使用一个结构体，将顺序表的信息存储下来，在需要用到相应的信息时从结构体中提取。
我们的顺序表就分为以下两个部分：
接下来我们先用代码实现结构体部分：
见上图左侧部分，我们创建了一个结构体，顺序表达英文名为sequence list，这里进行缩写SeqList。
用指针a来存储动态开辟的内存的地址
用size来记录当前结构体的元素个数
用capacity来记录当前结构体具有的空间数量（以一个元素需要的大小为单位）。
这样的顺序表有两个问题：
1.我们无法随意更改存入顺序表的数据类型，只能存int
2.我们在创建顺序表时，太复杂了，可以进行简化
对于问题1：
我们用typedef关键字，将int重命名为SLDataType，即顺序表数据类型。在后续用此顺序表存其它数据时，只需要在此处把int改为其它类型，就可以将整个顺序表作用的类型改变。
对于问题2：
我们也使用typedef关键字，将结构体重命名为SL，后续使用此顺序表只需要输入SL x；就可以创建一个名为x的顺序表了。
经过上述改动后，我们后续与结构体储存的数据类型有关的变量都要改为SLDataType类型，此处由于a是一个指针，它接收动态内存的地址，a的指针类型决定每次访问几个字节地址，为了保证后续改动类型时，a都能访问对内存的个数，此处要把a的类型改为SLDataType*。
对于size与capacity两个成员，只需要保持int类型即可，因为它们存储的为元素个数与内存个数（以一个元素所需大小为单位），会一直保持为整数，并不会因为顺序表元素类型改变而改变。
先不谈其它的功能实现，我们先将顺序表的创建与销毁说完：
顺序表的初始化
我们在创建一个存储信息的结构体后，内部的capacity和size的值是随机的，a也是一个野指针。
注意此时我们还没有为这个顺序表开辟空间，也就是没有内存可以储存数据，那么capaciy与size毫无疑问就应该是0。
在此我们需要先对这个结构体的信息初始化，将a置空，把capacity和size变为0。
在实现代码前，先思考：我们传入结构体部分时，是传值调用void SLInit(SL sl)；还是应该传址调用void SLInit(SL* psl)？
考虑这个问题，那我们就先要问：我们是否需要改变这个结构体的数据？答案是需要的，我们是希望结构体的数据跟随着顺序表的变化而变化的，所以我们后续所有对数据改动的函数接口，都要进行传址调用。
代码如下：
//初始化 void SLInit(SL* psl) { assert(psl); psl->a = NULL; psl->size = 0; psl->capacity = 0; }
上述代码的后三行，就是我们初始化的基本操作，但是在初始化之前，有没有可能用户在使用顺序表的时候传入了一个空指针？在此我们使用assert断言，防止对一个空指针进行操作，造成程序错误。而后续的所有代码，我们都要先用assert断言保证指针的有效性。
顺序表的销毁
既然要销毁这个顺序表，就要将a指针指向的动态内存释放掉，毫无疑问需要用到free()函数。我们在判断传入的地址不是空指针后，先free掉指针a指向的内存，此时a的内存储的值是不变的。也就是说a已经指向了一块不被使用的空间，a就变成了野指针，对于野指针，我们要及时置空。
当我们将存储数据的空间释放掉后，我们的所有数据就丢失了，此时size与capacity也应该变回0。
顺序表的销毁代码如下：
//销毁 void SLDestroy(SL* psl) { if (psl->a != NULL) { free(psl->a); psl->a = NULL; psl->size = 0; psl->capacity = 0; } }
顺序表的动态内存开辟
在我们后续进行插入元素之前，我们需要确保有空间可以插入新元素，一旦空间不足，就要及时开辟新的空间。当realloc传入的参数为NULL的时候，它会实现malloc的功能，直接开辟一个空间，并返回指针，当不为NULL的时候，就在原先内存上增加空间。利用此特性，在我们刚初始化完顺序表时，把a传入realloc，就可以实现内存的第一次开辟，后续需要增加内存的时候，也可以利用这一个函数。
先上代码，后分析。
//检查顺序表空间是否充足 void SLCheck(SL* psl) { if (psl->capacity == psl->size) { int NewCapacity = psl->capacity == 0 ? 4 : 2 * psl->capacity; SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * NewCapacity); if (tmp == NULL) { perror("realloc fail!"); return; } psl->a = tmp; psl->capacity = NewCapacity; } }
此处我们的函数并没有用assert来防止空指针，因为这个函数不是给用户用的，这个函数是给其它函数调用的，比如用户需要插入一个数据，利用插入数据的函数（假设为函数function1），函数function1调用此函数来保证空间足够。在这个过程中，我们只需要在函数function1内使用assrt就可以同属确保function1和SLCheck的指针都不为空。
我们利用此函数，首先利用if语句，一旦capacity = size，说明当前的元素刚好占满了空间；或者capacity = size =0，说明此时还没有开辟空间给顺序表。如果if不成立了，说明当前空间足够，则函数不执行功能，直接退出。
int NewCapacity = psl->capacity == 0 ? 4 : 2 * psl->capacity;
为了实现第一次开辟内存与后续增加内存的统一，我们利用了三目操作符，当问号前的条件(psl->capacity == 0 )成立说明此次为第一次开辟内存，程序指向冒号前的值赋给NewCapacity，即(int NewCapacity = 4)，相当于给顺序表分配四个内存空间；当条件不成立说明此次不是第一次开辟内存了，我们将原先的内存乘二，即(int NewCapacity = 2 * psl->capacity)。这样就可以让内存变成原来的两倍。
上述操作还没有真正实现内存的开辟，只是在决定要开辟多少内存，第三条语句才是内存开辟的语句：
SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * NewCapacity);
realloc的返回值有两种情况，1.内存开辟成功，返回新的内存的地址 2.内存开辟失败，返回NULL
不妨设想，这里的内存一旦开辟失败，如果直接用a接收这个NULL，那么我们的整个顺序表的数据就无法访问了
为了防止这种情况，我们用中间值tmp接收返回值，并后续判断其是否为NULL，如果为NULL说明开辟失败。利用perror函数报错。；如果不为NULL，说明开辟成功，此时才可以将地址传给a。
当内存开辟好后，内存的大小就发生了改变，此时capacity要得到新的内存大小(psl->capacity = NewCapacity;)
在顺序表头部插入元素（头插）
想要在头部插入元素，我们会涉及到以下步骤：
- 确保顺序表内存足够
- 将顺序表当前所有元素后移一位
- 在头部插入元素
我们先上代码：
//头插 void SLPushFront(SL* psl, SLDataType x) { assert(psl); SLCheck(psl); for (int i = psl->size; i > 0;i--) { psl->a[i] = psl->a[i - 1]; } psl->a[0] = x; psl->size++; }
这个函数，参数x为要插入的数值，注意：此x要用SLDataType类型，确保后续改变数据类型时统一处理。
assert(psl);
SLCheck(psl);
这两串代码功能分别是确保指针有效性，以及确保空间足够。SLCheck即我们上一步实现的函数，可以发现，我们在调用SLCheck前，就已经使用过assert了。故SLCheck内部无需再次assert。
for (int i = psl->size; i > 0;i–)
{
psl->a[i] = psl->a[i - 1];
}
这部分代码用于将所有元素后移，如果利用i = 0；i++这个组合从前往后后移的话，会导致前面一个元素将后面的元素覆盖掉，下次进行下一个元素的移动时，元素已经被改变了，最后所有元素都会被改为同一个值，如下图所示：
所以移动元素要从后往前移动。
psl->a[0] = x;
psl->size++;
当我们完成元素后移一位后，就把头部第一个元素改为目标值x。
由于这个过程增加了一个元素，size需要自增。
在顺序表尾部插入元素（尾插）
尾插十分简单，只需要在尾部插入一个元素即可，在此直接放代码了，此处所有代码的解释在头插部分都解释过。
//尾插 void SLPushBack(SL* psl, SLDataType x) { assert(psl); SLCheck(psl); psl->a[psl->size] = x; psl->size++; }
在顺序表头部删除元素（头删）
想要在头部删除一个元素，需要执行以下步骤：
- 确保当前元素个数不为0，即有元素可以删除
- 将所有元素向前移动一位，直接将第一位元素覆盖掉即可
代码如下：
//头删 void SLPopFront(SL* psl) { assert(psl); assert(psl->size > 0); for (int i = 0; i < psl->size; i++) { psl->a[i] = psl->a[i + 1]; } psl->size--; }
assert(psl->size > 0);
想要确保当前元素个数不为0，即size不为0，直接利用assert断言。
for (int i = 0; i < psl->size; i++)
{
psl->a[i] = psl->a[i + 1];
}
此处的for循环和上方的for循环刚好相反，需要所有元素向前移动一位。这种情况下就需要从前往后覆盖，若从后往前，会发生和刚刚类似的情况：所有元素都变成了最后一位元素。
当完成以上操作，当前元素就减少了一个，size–。
在顺序表尾部删除元素（尾删）
想要在尾部删除一个元素，其实只需要size–即可，我们顺序表的数据范围是size决定的。如果size–，相当于把最后一位数字踢出了顺序表，虽然数据仍然保留在这个位置，但是下一次使用此位置时，这个位置的数据会被新元素覆盖，所以不用管原本的数据。
当然，和头删一样，要确保当前有元素可以删除。
代码如下：
//尾删 void SLPopBack(SL* psl) { assert(psl); assert(psl->size > 0); psl->size--; }
在顺序表任意下标位置插入
想要在一个下标位置插入一个元素，我们就需要传入一个下标(pos)以及插入元素(x)。
完成传参后，在函数内部要执行以下过程：
- 判断下标pos是否在当前元素个数（0-size）范围内
- 将插入位置开始往后的元素后移一位
- 在下标为pos的位置插入元素x
//下标插入 void SLInsert(SL* psl, int pos, SLDataType x) { assert(psl); assert(0 <= pos && pos <= psl->size); for (int i = psl->size; i > pos; i--) { psl->a[i] = psl->a[i - 1]; } psl->a[pos] = x; psl->size++; }
assert(0 <= pos && pos <= psl->size);
这条语句的作用已经讲解过了，但是有一个问题值得讨论：pos能不能等于size？
下标为size的位置，就是当前最后一个元素的后面一个位置，当pos = size其实就相当于尾插了，所以是可以等于的。
for (int i = psl->size; i > pos; i–)
{
psl->a[i] = psl->a[i - 1];
}
这个循环，把元素往后移动，所以要从后往前移动。当i = pos + 1时，此时i-1就已经是pos的位置了。
此时pos的值被拷贝到后一位，把pos的位置空出给x。所以i >pos无需取等。
最后再将x插入pos下标位置处，再size++。
在顺序表任意下标位置删除
过程和上方函数极为相似：
- 判断下标pos是否在当前元素个数（0-size）范围内
- 将插入位置开始往后的元素前移一位
//下标删除 void SLErase(SL* psl, int pos) { assert(psl); assert(0 <= pos && pos < psl->size); for (int i = pos; i < psl->size; i++) { psl->a[i] = psl->a[i + 1]; } psl->size--; }
assert(0 <= pos && pos < psl->size);
此处assert有一点和上方不一样，就是再pos = size处没有元素，也就无需删除，所以后面不能取等。
输出当前顺序表
void SLPrint(SL* psl) { assert(psl); for (int i = 0; i < psl->size; i++) { printf("%d ", psl->a[i]); } printf("\n"); }
顺序表全部代码展示：
SeqList.h头文件：
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLDataType; typedef struct SeqList { SLDataType* a; int size; int capacity; }SL; //检查顺序表空间是否充足 void SLCheck(SL* psl); //初始化 void SLInit(SL* psl); //销毁 void SLDestroy(SL* psl); //头插 void SLPushFront(SL* psl, SLDataType x); //尾插 void SLPushBack(SL* psl, SLDataType x); //头删 void SLPopFront(SL* psl); //尾删 void SLPopBack(SL* psl); //下标插入 void SLInsert(SL* psl, int pos, SLDataType x); //下标删除 void SLErase(SL* psl, int pos); //输出顺序表 void SLPrint(SL* psl);
SeqList.c源文件：
#include "SeqList.h" //初始化 void SLInit(SL* psl) { assert(psl); psl->a = NULL; psl->size = 0; psl->capacity = 0; } //销毁 void SLDestroy(SL* psl) { if (psl->a != NULL) { free(psl->a); psl->a = NULL; psl->size = 0; psl->capacity = 0; } } //检查顺序表空间是否充足 void SLCheck(SL* psl) { if (psl->capacity == psl->size) { int NewCapacity = psl->capacity == 0 ? 4 : 2 * psl->capacity; SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * NewCapacity); if (tmp == NULL) { perror("realloc fail!"); return; } psl->a = tmp; psl->capacity = NewCapacity; } } //头插 void SLPushFront(SL* psl, SLDataType x) { assert(psl); SLCheck(psl); for (int i = psl->size; i > 0;i--) { psl->a[i] = psl->a[i - 1]; } psl->a[0] = x; psl->size++; } //尾插 void SLPushBack(SL* psl, SLDataType x) { assert(psl); SLCheck(psl); psl->a[psl->size] = x; psl->size++; } //头删 void SLPopFront(SL* psl) { assert(psl); assert(psl->size > 0); for (int i = 0; i < psl->size; i++) { psl->a[i] = psl->a[i + 1]; } psl->size--; } //尾删 void SLPopBack(SL* psl) { assert(psl); assert(psl->size > 0); psl->size--; } //下标插入 void SLInsert(SL* psl, int pos, SLDataType x) { assert(psl); assert(0 <= pos && pos <= psl->size); for (int i = psl->size; i > pos; i--) { psl->a[i] = psl->a[i - 1]; } psl->a[pos] = x; psl->size++; } //下标删除 void SLErase(SL* psl, int pos) { assert(psl); assert(0 <= pos && pos < psl->size); for (int i = pos; i < psl->size; i++) { psl->a[i] = psl->a[i + 1]; } psl->size--; } void SLPrint(SL* psl) { assert(psl); for (int i = 0; i < psl->size; i++) { printf("%d ", psl->a[i]); } printf("\n"); }
test.c源文件：
#include "SeqList.h" void test() { SL sl; SLInit(&sl); SLPushFront(&sl, 1); SLPushFront(&sl, 2); SLPushFront(&sl, 3); SLPushFront(&sl, 4); SLPushFront(&sl, 5); SLPushFront(&sl, 6); SLPrint(&sl); SLPushBack(&sl, 10); SLPushBack(&sl, 20); SLPushBack(&sl, 30); SLPushBack(&sl, 40); SLPrint(&sl); SLPopBack(&sl); SLPopBack(&sl); SLPopBack(&sl); SLPrint(&sl); SLPopFront(&sl); SLPopFront(&sl); SLPrint(&sl); SLErase(&sl, 2); SLPrint(&sl); SLErase(&sl, 3); SLPrint(&sl); SLInsert(&sl, 1, 100); SLPrint(&sl); SLInsert(&sl, 0, 200); SLPrint(&sl); SLInsert(&sl, 2, 300); SLPrint(&sl); SLInsert(&sl, 5, 500); SLPrint(&sl); SLInsert(&sl, 7, 1000); SLPrint(&sl); SLDestroy(&sl); } int main() { test(); }
