说在前面
数据结构内容不管是在考研还是工作方面都是非常重要的部分，难度也是非常的高。不管你有没有学过数据结构，这篇文章都会带你了解每一行代码的意思，使你彻底清楚具体的实现原理。
本篇文章将会超详细地介绍最基础的线性数据结构 —— 顺序表 的实现。
文章的最后附有完整源码。
一、顺序表
在说顺序表之前，我们需要知道什么是线性表。线性表的含义就是数据与数据之间呈线性关系，也就是一对一的关系，最多一个“因”，最多一个“果”。
而顺序表就是在线性表的基础上，使其在物理地址上连续，也就是说在内存中，数据与数据是连续存储的。我们非常容易联想到数组对吧，数组在内存中就是连续存储的，数据从低地址向高地址方向存储。
所以说，实现顺序表的一些功能，无非是对数组进行操作罢了。
二、顺序表头文件的编写
为了使代码分工明确，更加容易阅读，我们采用将代码根据功能分成不同的文件的方式来完成代码，我们首先需要创建一个叫做 “SeqList.h” 的头文件。
1.引入库函数头文件
#include<stdio.h> #include<stdlib.h> #include<assert.h>
这三个头文件是我们等会要用到的库函数头文件，对这几个头文件有不了解的地方可以查阅一下。
2.定义顺序表结构体
// 宏定义数据类型 typedef int SLDataType; // 顺序表结构体 typedef struct SeqList { // 指向数组的指针，指针的类型是SLDataType* SLDataType* a; // 顺序表储存的数据个数 int size; // 顺序表所能存放的最多数据个数 int capacity; }SL;
顺序表存储的数据类型一定是 int 型的吗，当然不一定，那难道我们需要根据存储的数据类型来大动干戈地修改代码吗，这太麻烦了，所以我们可以通过 typedef 关键字来对数据类型进行重定义为 SLDataType ，之后的需要数据类型地方统一使用 SLDataType 代替即可，要是数据类型改变了，我们也只需要改变原本的 int 就能完美解决。
同样的，我们在书写结构体时，由于需要带上结构体名称前面的 struct 导致结构体类型太长，不方便书写，于是我们也采用 typedef 的方式，在结构体末尾的分号内书写重定义后的名称，即可代替原来的结构体数据类型，在上面的结构体中，我们就将 struct SeqList 重定义为 SL ，所以它俩的本质就是一样的了。
如注释所示，在结构体内部，我们定义了一个指向数组的指针，为什么不直接定义一个数组呢，因为顺序表的实质就是对数组进行操作改变，如果结构体内定义的是数组，那么数组改变的时候结构体就会改变，学到后面我们会发现，改变结构体的属性是一件非常非常麻烦的事，所以我们定义的是指向数组的指针。
3.声明顺序表的功能函数
// 顺序表的初始化 void SLInit(SL* psl); // 顺序表的销毁 void SLDestroy(SL* psl); // 顺序表的打印 void SLPrint(SL* psl); // 顺序表的扩容 void SLCheckCapacity(SL* psl); // 顺序表的尾插 void SLPushBack(SL* psl, SLDataType x); // 顺序表的头插 void SLPushFront(SL* psl, SLDataType x); // 顺序表的尾删 void SLPopBack(SL* psl); // 顺序表的头删 void SLPopFront(SL* psl); // 顺序表的查找 int SLFind(SL* psl, SLDataType x); // 顺序表的任意位置前面插入 void SLInsert(SL* psl, int pos, SLDataType x); // 顺序表的任意位置删除 void SLErase(SL* psl, int pos);
或许我们都知道，形参只是实参的一份临时拷贝，给函数传参的时候，若是需要改变实参的值，那我们就需要传实参的地址过去，通过修改地址的方式来改变实参的值。上面的函数参数里面，出现最多的就是 SL* psl，意思就是传入一个结构体指针，叫做 psl ，你有没有发现，这个名字也是很有深意的。
三、顺序表主函数文件的编写
主函数文件我们独立出来，不包含其他函数的实现，仅仅用作函数测试。我们创建一个叫做 test.c 的源文件。
1.包含头文件
#include"SeqList.h"
2.测试函数的编写
void TestSL() { // 创建一个顺序表结构体变量 sl SL sl; // 初始化 SLInit(&sl); // 尾插 SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLPushBack(&sl, 5); // 打印 SLPrint(&sl); // 头插 SLPushFront(&sl, 9); SLPushFront(&sl, 8); SLPushFront(&sl, 7); SLPushFront(&sl, 6); // 打印 SLPrint(&sl); // 尾删 SLPopBack(&sl); SLPopBack(&sl); SLPopBack(&sl); // 打印 SLPrint(&sl); // 头删 SLPopFront(&sl); SLPopFront(&sl); // 打印 SLPrint(&sl); // 查找数据内容为2的数组下标 int pos = SLFind(&sl, 2); // 在pos下标位置前面插入 SLInsert(&sl, pos, 0); // 打印 SLPrint(&sl); // 删除pos-2下标位置的数据 SLErase(&sl, pos - 2); // 打印 SLPrint(&sl); // 销毁 SLDestroy(&sl); }
上面的测试用例仅仅是我随手编写的测试用例，读者可以根据自身情况任意改动。
由于函数的参数是顺序表结构体指针，所以创建了顺序表变量后，将变量的地址传入函数即可。
3.主函数的编写
int main() { // 调用测试函数 TestSL(); return 0; }
在主函数内直接调用测试函数即可，读者也可创建其他测试函数。
四、顺序表功能函数文件的编写
同样的，我们再创建一个 SeqList.c 的源文件。这个文件里面包含了顺序表每个功能函数的具体实现。
1.包含头文件
#include"SeqList.h"
2.顺序表的初始化
void SLInit(SL* psl) { // assert()内为真通过，为假直接报错，终止程序 assert(psl); // 指向数组的指针初始化 psl->a = NULL; // 数据个数清零 psl->size = 0; // 顺序表容量清零 psl->capacity = 0; }
在前面测试函数的编写部分我们已经介绍了，我们创建了一个结构体变量 sl ，传参时都是传的 sl 的地址 &sl ，如果 sl 存在，那么 &sl 必不可能为空，所以 psl 必不可能为空，如果为空，那只能说明要么根本没有创建 sl ，要么传参错误。我们通过 assert 函数断言一下，可以轻松知道错误原因。在你认为必须为真的情况下，都可以采用 assert 函数断言一下。
后面的内容就是给结构体赋初始值。或许有人不了解 “.” 和 “->” 的区别，“.” 是结构体成员运算符，用法如 sl.size ，左边是结构体变量，右边是结构体成员。“->” 是指向结构体成员运算符，用法如 “psl->size” ，左边是指向结构体的指针变量，右边是结构体成员。如果你的变量是结构体，就用 “.” ，是指向结构体的指针，就用 “->”。
3.顺序表的销毁
void SLDestroy(SL* psl) { // 为空则弹出警告 assert(psl); // 当线性表含有至少一个数据的时候 if (psl->a != NULL) { // 释放数组空间 free(psl->a); // 指针置空 psl->a = NULL; // 顺序表数据个数清零 psl->size = 0; // 顺序表容量清零 psl->capacity = 0; } }
顺序表的销毁当然是在顺序表含有最少一个数据的时候才有意义，我们通过判断指向数组的指针是否为空来决定是否执行销毁操作。销毁操作也是比较简单，释放掉数组指针a所指向的数组空间，然后将结构体内容给初始掉即可。free 函数的意思是释放括号内的指针所指向的空间，在空间被释放后，指向该空间的指针一般需要进行置空处理，以避免发生野指针问题。
4.顺序表的打印
void SLPrint(SL* psl) { // psl不能为空 assert(psl); // 定义局部变量，含义为数组下标 int begin = 0; // 遍历数组 while (begin < psl->size) { // 通过下标begin找到数据并打印数据内容 printf("%d ", psl->a[begin]); // 数组下标+1 ++begin; } printf("\n"); }
打印顺序表内容，我们不得不去遍历数组，通过size我们可以知道顺序表的数据个数有多少个，又由于数组在内存中是连续存储的，所以直接创建临时变量从数组第一个数据遍历到最后一个数据并打印出来就可以了。要注意的是，结构体里面是没有数组的，只有一个指向数组的指针，我们需要通过 “psl->a” 找到数组，在通过下标找到数组元素的位置，故为 “psl->a[begin]” 。
5.顺序表的扩容
void SLCheckCapacity(SL* psl) { // psl不能为空 assert(psl); // 如果存放的数据个数等于顺序表的容量，说明顺序表已满，需要扩容操作 if (psl->size == psl->capacity) { // 新的容量所能包含的数据个数 int newCapacity = psl->size == 0 ? 4 : psl->capacity * 2; // 根据新的容量来开辟空间 SLDataType* tmp = (SLDataType*)realloc(psl->a, newCapacity * sizeof(SLDataType)); // 当空间开辟失败时 if (tmp == NULL) { // 报错并退出 perror("realloc fail"); exit(-1); } // 新的数组空间的地址传给指向数组的指针 psl->a = tmp; // 改变顺序表的容量大小 psl->capacity = newCapacity; } }
在对顺序表进行增加数据的操作时，难免会遇到数组空间被使用完毕的情况，如果一开始就开辟非常非常大的空间又容易造成空间浪费，所以动态的分配空间是一个性价比非常高的方法，当我们的数据个数与容量相等的时候，说明顺序表，或者说数组已经存放满了，需要进行扩容。使用三目运算符来解决新的空间容量大小的问题，当第一次扩容时，容量大小设置为4，此后每次就是上一次容量的二倍，这样就能实现空间够用而且也不会产生过多浪费的问题。
数组是连续存储的，还需要保留没扩容前的内容，使用 realloc 函数就能完美解决数组扩容和内存连续的问题，创建一个临时指针变量 tmp ，指针指向的数据类型是 SLDataType 类型，realloc 函数会通过参数 psl->a 找到原本的那份空间，将其拷贝一下，然后从内存中找到一片空间大小满足 newCapacity(数据个数) × sizeof(SLDataType)(单个数据的字节大小) 字节的空间，将拷贝的内容复制到此地址并将此空间地址强制类型转换为 SLDataType* 类型的指针，传递给 tmp 。于是 tmp 就指向了新地址的空间，但由于空间还可能开辟失败，失败 realloc 函数会返回 NULL ，所以需要判断一下。最后通过改变相应的参数就完成了扩容操作。
6.顺序表的尾插
void SLPushBack(SL* psl, SLDataType x) { // psl不能为空 assert(psl); // 判断是否需要扩容 SLCheckCapacity(psl); // 在尾部插入 psl->a[psl->size] = x; // 数据个数+1 ++psl->size; }
对顺序表进行增加数据的操作时，必不可少的就是刚刚实现的扩容函数，只有当空间足够的时候我们才能去合法尾插，否则都是属于越界行为。数组的下标是从 0 开始，而数据个数 size 是从 1 开始的，所以数组的最后一个数据的下标是 psl->size-1 ，而尾插就是在最后一个数据的下一个位置插入，因此就是在 psl->a[psl->size] 位置插入，先通过指针 a 找到数组，在通过数据个数 size 找到最后一个元素的下一个位置。在最后别忘了给数据个数+1。
7.顺序表的头插
void SLPushFront(SL* psl, SLDataType x) { // psl不能为空 assert(psl); // 判断是否需要扩容 SLCheckCapacity(psl); // 找到数组的最后一个元素，从后往遍历 int end = psl->size - 1; // 遍历到数组的第一个元素 while (end >= 0) { // 将该下标的元素往后挪一位 psl->a[end + 1] = psl->a[end]; // 下标end往前移动一位 --end; } // 在将x赋值到数组的第一个元素里 psl->a[0] = x; // 数据个数+1 ++psl->size; }
顺序表的头插也是会让数据个数增加，所以同样要判断受否要进行扩容操作。直接将x的值赋值给数组的第一个元素会导致原本的第一个元素的值被覆盖掉，所以在赋值前，必须要给x把第一个元素的空间给“空”出来，数组的元素是连续存储的，想要把第一个空间给空出来，必须要把之后的数据一个一个往后挪，但是能从前面的数据开始往后挪吗，这当然是不可以的！ 前面的数据往后挪动后，后面的数据内容就已经被破坏掉了，再挪动就没了意义，所以只能从后面开始，一个一个往后挪动数据。在正确挪动完数据后就可进行赋值和+1操作了。
8.顺序表的尾删
void SLPopBack(SL* psl) { // psl不能为空 assert(psl); // 顺序表至少有一个数据的时候才能删除 assert(psl->size > 0); // 数据个数-1 --psl->size; }
顺序表最方便的操作就是尾删了，因为顺序表找到尾部元素非常方便，通过下标即可直接访问到，又因为 size 的意思是有效数据的个数，我们只需将 size-1 ，使最后一个元素成为无效数据就完成了尾删操作。
9.顺序表的头删操作
void SLPopFront(SL* psl) { // psl不能为空 assert(psl); // 有至少一个数据才能删除 assert(psl->size > 0); // 创建局部变量，代表数组下标 int begin = 0; // 遍历到倒数第二个元素，注意边界问题 while (begin < psl->size - 1) { // 后一个位置覆盖到前一个位置 psl->a[begin] = psl->a[begin + 1]; // 下标右移 ++begin; } // 数据个数-1 --psl->size; }
顺序表删除第一个元素或许有人觉得使指向数组的指针+1，指向第二个元素即可，但是这样有个很严重的问题，那就是内存泄漏，指针+1的话，每次头插就会使第一个元素的空间即被占用，也无法访问，这时候内存就发生了泄露问题，那为什么不释放第一个元素的空间呢？原因是：数组是不支持只释放部分空间的，也就是说不支持“分期付款”，要释放空间必须一次性释放全部空间。
所以我们删除第一个元素只能使用后面的元素将前面的元素给覆盖掉。由于是后面的元素往前覆盖，所以每次覆盖必须保证前面的数据已经完成了他本该覆盖的操作。也就是说需要从数组的第一个元素开始，一直往后移动，每次移动使后面的数据覆盖前面的数据，唯一要注意的一点就是边界问题，边界是不需要后面的无效数据覆盖最后一个数据的，这样会产生数组越界问题。
10.顺序表的查找
int SLFind(SL* psl, SLDataType x) { // psl不可能为空 assert(psl); // 创建局部变量，含义为数组下标 int begin = 0; // 遍历到数组最后一个元素 while (begin < psl->size) { // 如果找到数据与x相等的元素 if (psl->a[begin] == x) { // 返回该元素的下标 return begin; } // 下标右移 ++begin; } // 没找到返回-1 return -1; }
顺序表的查找与打印是非常相似的，都是从数组的第一个元素遍历到最后一个元素，唯一不同的是，查找在找到了与参数x的值相同的元素的时候就返回下标并终止遍历。
11.顺序表的任意位置前插入
void SLInsert(SL* psl, int pos, SLDataType x) { // psl不可能为空 assert(psl); // 下标pos合法，不能超出范围 assert(pos >= 0 && pos <= psl->size); // 判断是否需要扩容 SLCheckCapacity(psl); // 创建变量，含义是最后一个元素的下标 int end = psl->size - 1; // 遍历到pos位置 while(end >= pos) { // 数据后移 psl->a[end + 1] = psl->a[end]; // 下标-1 --end; } // 将x的值赋值给下标为pos的元素 psl->a[pos] = x; // 数据个数+1 ++psl->size; }
顺序表的任意位置插入属于顺序表的不完全头插，头插是每个数据都后移一位，直到后移到数组的第一个元素的位置，而任意位置插入就是后移到pos位置罢了。然后将准备插入的值赋值给下标为pos的元素。最后使数据个数+1即可。
12.顺序表的任意位置删除
void SLErase(SL* psl, int pos) { // psl不可能为空 assert(psl); // 下标pos必须合法，不能超出范围 assert(pos >= 0 && pos < psl->size); // 创建变量，含义为与pos相同的下标 int begin = pos; // 从pos往后遍历到倒数第二个元素 while (begin < psl->size - 1) { // 数据前移 psl->a[begin] = psl->a[begin + 1]; // 下标+1 ++begin; } // 数据个数-1 --psl->size; }
顺序表的任意位置删除也是属于不完全的头删，将pos后面的所有元素都往前移动一位即可，后面的数据覆盖前面的数据，所以需要保证前面的元素已经完成了他本该完成的前移覆盖操作，所以需要从pos下标的下一个位置开始往数组结尾方向遍历，每个元素往前覆盖。最后数组的末尾还有一个无效的元素，咱们让size-1就可以了。
四、代码整合及结果演示
1.代码整合
若在整合时出现一些例如scanf函数怎么怎么样的报错，请在头文件里面再加上下面这行代码。
#define _CRT_SECURE_NO_WARNINGS 1
1.头文件 SeqList.h 部分
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLDataType; typedef struct SeqList { SLDataType* a; int size; int capacity; }SL; // 初始化 void SLInit(SL* psl); // 销毁 void SLDestroy(SL* psl); // 打印 void SLPrint(SL* psl); // 扩容 void SLCheckCapacity(SL* psl); // 尾插 void SLPushBack(SL* psl, SLDataType x); // 头插 void SLPushFront(SL* psl, SLDataType x); // 尾删 void SLPopBack(SL* psl); // 头删 void SLPopFront(SL* psl); // 查找 int SLFind(SL* psl, SLDataType x); // 任意位置前插入 void SLInsert(SL* psl, int pos, SLDataType x); // 任意位置删除 void SLErase(SL* psl, int pos);
2.源文件 SeqList.c 部分
#include"SeqList.h" void SLInit(SL* psl) { assert(psl); psl->a = NULL; psl->size = 0; psl->capacity = 0; } void SLDestroy(SL* psl) { assert(psl); if (psl->a != NULL) { free(psl->a); psl->a = NULL; psl->size = 0; psl->capacity = 0; } } void SLPrint(SL* psl) { assert(psl); int begin = 0; while (begin < psl->size) { printf("%d ", psl->a[begin]); ++begin; } printf("\n"); } void SLCheckCapacity(SL* psl) { assert(psl); if (psl->size == psl->capacity) { int newCapacity = psl->size == 0 ? 4 : psl->capacity * 2; SLDataType* tmp = (SLDataType*)realloc(psl->a, newCapacity * sizeof(SLDataType)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } psl->a = tmp; psl->capacity = newCapacity; } } void SLPushBack(SL* psl, SLDataType x) { assert(psl); SLCheckCapacity(psl); psl->a[psl->size] = x; ++psl->size; } void SLPushFront(SL* psl, SLDataType x) { assert(psl); SLCheckCapacity(psl); int end = psl->size - 1; while (end >= 0) { psl->a[end + 1] = psl->a[end]; --end; } psl->a[0] = x; ++psl->size; } void SLPopBack(SL* psl) { assert(psl); assert(psl->size > 0); --psl->size; } void SLPopFront(SL* psl) { assert(psl); assert(psl->size > 0); int begin = 0; while (begin < psl->size - 1) { psl->a[begin] = psl->a[begin + 1]; ++begin; } --psl->size; } int SLFind(SL* psl, SLDataType x) { assert(psl); int begin = 0; while (begin < psl->size) { if (psl->a[begin] == x) { return begin; } ++begin; } return -1; } void SLInsert(SL* psl, int pos, SLDataType x) { assert(psl); assert(pos >= 0 && pos <= psl->size); SLCheckCapacity(psl); int end = psl->size - 1; while(end >= pos) { psl->a[end + 1] = psl->a[end]; --end; } psl->a[pos] = x; ++psl->size; } void SLErase(SL* psl, int pos) { assert(psl); assert(pos >= 0 && pos < psl->size); int begin = pos; while (begin < psl->size - 1) { psl->a[begin] = psl->a[begin + 1]; ++begin; } --psl->size; }
3.源文件 test.c 部分
#include"SeqList.h" void TestSL() { SL sl; SLInit(&sl); SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPrint(&sl); SLPushFront(&sl, 9); SLPushFront(&sl, 8); SLPushFront(&sl, 7); SLPushFront(&sl, 6); SLPrint(&sl); SLPopBack(&sl); SLPopBack(&sl); SLPopBack(&sl); SLPrint(&sl); SLPopFront(&sl); SLPopFront(&sl); SLPrint(&sl); int pos = SLFind(&sl, 1); SLInsert(&sl, pos, 0); SLPrint(&sl); SLErase(&sl, pos - 2); SLPrint(&sl); SLDestroy(&sl); } int main() { TestSL(); return; }
2.结果演示
我并没有书写菜单调用的函数，读者要是需要使用菜单调用，则修改我的测试函数为菜单函数。
结语
本篇文章篇幅还是蛮长的，不一定会有很多人能读到这里，但还是感谢大家的支持，我写这篇文章的初衷就是想帮助那些根本看不懂代码的人，我当时学数据结构的时候就是那样的，知道一些理论，但是代码完全看不懂，为了让大家能够真正深刻了解代码的含义，我写下了这篇文章，尽可能的把每个细节都能够介绍到，让大家能有更好的阅读体验。
这篇文章或许也有错误和不足的地方，欢迎大家指正，我也是一位学习者。如果文章内容帮助到了你，也请三连支持一下，这些都是创作者的动力，谢谢。
