🌳前言
顺序表 本质上就是数组，这也表明 顺序表 的基本要求是存储空间要连续，并且元素必须是连续存储。除了数组外，我们还可以使用堆区上开辟的空间，这也是可以实现 顺序表 的，下面一起来看看怎么实现吧！
🌳正文
🌲结构
首先认识一下 顺序表 的基本结构
typedefintSLDatatype; //顺序表类型typedefstructSeqListInfo//基本结构{ SLDatatype*data; //数据size_tsize; //实际有效数据数size_tcapacity; //容量}SL;
可以看到 顺序表 数据类型使用了 typedef 重命名，这样做的好处是方便后续切换 顺序表 数据元素类型，比如现在存储的是 整型 ，后续想存 字符型 ，直接把 int 换成 float 就行了
本文的 顺序表 是动态的 ，因此不需要预设大小，需要多少空间就申请多少就行了，顺序表 本质上是数组，因此 下标 size 是少不了的，size 代表有效元素数 ；为了方便扩容，还需要一个 容量值 capacity辅助 判断是否需要进行扩容。
🌲初始化
初始化的目的很简单
把顺序表指针 data 置空
将下标 size 归零
将容量 capacity 归零
//注意：这里是ps就是指向顺序表s的指针//这里的代码位于初始化函数内部，当然后面的ps，都是这个意思ps->data=NULL; //指针置空ps->size=ps->capacity=0; //数据、容量归零
原因：刚开始都是 随机值 ，需要 规范 一下
🌲销毁
动态申请的空间位于堆区 ，本着 有借有还，再借不难 的原则，我们在使用完堆区空间后，要记得释放空间 ，养成一个良好习惯，避免出现 内存泄漏 的问题，关于动态内存管理的介绍可以点这里。
free(ps->data); //直接释放顺序表数据域SeqListInit(ps); //代码复用
释放完空间后，原指针要置空，下标和容量要归零 ，这里直接调用前面的初始化函数就行(偷个懒)
🌲打印
打印的话，可以根据 size 写一个 for 循环，因为 size 代表有效存储元素个数，比如 size=3，那么依靠下标 0、1、2 就能打印所有元素。
size_ti=0; //定义一个同样类型的变量i//配合size进行打印for (i=0; i<ps->size; i++) printf("%d ", ps->data[i]); //ps->data[i]相当于我们熟悉的arr[i]printf("\n"); //全部输出结束后，可以换行
🌲尾插与尾删
尾插尾删比较简单，这也是 顺序表 的优势之一。
🌱尾插
🪴容量检查
尾插的话，直接在 顺序表 尾部，也就是 ps->data[ps->size] 处插入目标元素就行了，当然插入成功后 size+1 。值得一提的是，我们在 插入前要进行容量检查 ，判断已有的空间是否足够使用，如果不够，就向堆区申请扩容，至于扩多大，可以自己把握 ，当然我们第一次是肯定要扩的。
可以看动图(第一次制作，不足还请多包涵)
if (ps->size==ps->capacity) { size_tnewcapacity=ps->capacity==0?4 : ps->capacity*2; //两倍扩容SLDatatype*tmp= (SLDatatype*)realloc(ps->data, sizeof(SLDatatype) *newcapacity); assert(tmp); //断言，可能存在扩容失败的情况ps->data=tmp; ps->capacity=newcapacity; }
🪴执行尾插
检查容量结束后，就可以直接执行尾插程序了。
decideCapacity(ps); //判断是否需要扩容ps->data[ps->size++] =x; //尾插成功
🌱尾删
先说明一个概念：删除不是真删除，想办法让你碰不到待删除元素就行了 ，比如我们可以将 size-1 ，这样有效存储元素数量就会-1，在进行后续操作时，就找不到最后一个元素了。
可以看下面的动图
下面是代码实现
assert(ps->size>0); //需要断言一下，如果顺序表本来一个元素都没有，是肯定删不了的ps->size--; //有效数据-1，就是尾删
注意： 一定要断言或进行特殊处理 ，不然会出错，size - 1 时，前置后置都一样
🌲头插与头删
头部操作会比尾部操作复杂一些，比如 头插需要把所有元素整体往后移动，头删需要把元素整体往前移动 ，当然头插前需要检查容量。
🌱头插
头插的容量检查和尾插一样，对 size 和 capacity 进行比较，相等就扩容。
头插的步骤：
确定起点与终点
通过 while 循环使元素整体往后移动
在顺序表首位， ps->data[0] 处插入元素值
其中第一点需要特别注意，起点是 ps->size ，而终点是 0处(不能为0) ，否则会发生越界行为；另一种组合方式为 ps->size-1 与 0处(可以为0) ，两种方法的移动实现不同，这里演示第一种方式。
注意： 实际使用时创建一个 end 变量存储起点信息，避免原起点被改变
decideCapacity(ps); //判断扩容//先把数据整体往后挪动，再头插size_tend=ps->size; while (end>0) { ps->data[end] =ps->data[end-1]; end--; } ps->data[end] =x; ps->size++;
🌱头删
顺序表 的头删基本逻辑与头插差不多，但头删是 将元素整体往前移动(覆盖) ，整体覆盖结束后，size-- 就行了，通俗来说跟尾删一样，真移动，假删除。
注意： 这里也需要一个变量 begin 来记录起点位置，终点就是 ps->size-1
//同头插原理一样，需要把数据整体往前挪动size_tbegin=0; while (begin<ps->size-1) { ps->data[begin] =ps->data[begin+1]; begin++; } ps->size--; //有效元素-1，就可以实现头删
注意： 凡是涉及删除的操作，都要 断言，防止 顺序表 为空的情况，同样的 前置后置++在这里的效果都一样
头删gif动图中的终止条件有误，应该为 begin < ps->size-1，不会造成很大影响，提前说声抱歉，因为动图不太好改
🌲任意位置插入与删除
任意位置插入与删除就像是头插与头删的升级版，不过是多了一个参数 pos
🌱插入
头插是整体从后往前移动，任意位置插也是如此，不过任意位置插的结束条件不再是 0 ，而是 pos(不能等于 pos)，当 end 变量等于 pos 时，就可以停止移动了，此时将 ps->data[pos] 处赋为目标值，ps->size++ ，就完成了任意插，当然，插入前要先检查容量。
assert(pos>=0); assert((size_t)pos<=ps->size); decideCapacity(ps); //判断容量//原理有点类似头插，不过终止条件依赖于possize_tend=ps->size; while (end> (size_t)pos) { ps->data[end] =ps->data[end-1]; end--; } ps->data[pos] =x; ps->size++;
注意： 对于传入的下标参数 pos，需要做断言检查 ，如果 pos 是非法的，就无法继续完成插入程序
🌱删除
任意位置删除与头删类似，都是将元素整体往前移动，不过起始变量 begin 变成了参数 pos，终止变量依旧可以使用 ps->size-1 ，任意位置删除就像是 “可控的头删” 。
assert(pos>=0); assert((size_t)pos<ps->size); //类似于头删size_tbegin= (size_t)pos; while (begin<ps->size-1) { ps->data[begin] =ps->data[begin+1]; begin++; } ps->size--;
注意： 删除前要判断参数 pos 是否合法，此时不需要判断 顺序表 为空的情况，因为 pos < ps->size 就已经可以排除这种情况了
任意位置删除gif动图中的终止条件有误，应该为 begin == ps->size-1，不会造成很大影响，提前说声抱歉，因为动图不太好改
🌲关于其他需要补充的点
🌱查找
查找功能就是 遍历+比较 ，类似于打印函数,不过加了一个比较而已，这个函数可以设置返回值，返回下标，如果没找到返回-1(没有-1这个下标)，这个比较简单，就不做动图展示了
size_ti=0; for (i=0; i<ps->size; i++) { if (ps->data[i] ==x) returni; } return-1; //没有找到目标元素
修改就是在调用查找的基础上进行操作，如果找到了目标元素，返回 对应下标 ，根据此下标直接修改值就可以了，这个也比较简单，可以自己试着实现一下吧！
可以看出，在查找元素方面是 顺序表 的强项，提供下标，那么对应元素可以秒出结果
🌱复用
其实不难发现，任意位置插删与头尾插删有很多相似之处 ，并且 任意插删 包含 头尾插删 因此我们可以通过调用函数来节省代码量，在调用时，调好起始(终止)条件就行了
比如，在头插中，调用任意插入函数，可以写成:
SeqListInsert(ps, 0, x); //可以使用任意位置插入，替代插入
其他函数调用可以自己去试试
🌱断言
为了确保发生某些隐藏事我们能知晓，可以常用 assert 断言函数。对于上面的所有功能函数，我们都可以在函数内部先写上一条断言语句，防止空指针的传入导致的程序崩溃。
assert(ps); //断言，防止空指针
🌲源码区
是整个 顺序表 工程的源码，可以随意 review
🌱功能声明头文件部分
typedefintSLDatatype; //顺序表类型typedefstructSeqListInfo//基本结构{ SLDatatype*data; //数据size_tsize; //实际有效数据数size_tcapacity; //容量}SL; voidSeqListInit(SL*ps); //顺序表初始化voidSeqListDestroy(SL*ps); //销毁顺序表voidSeqListPrint(SL*ps); //打印顺序表voidSeqListPushBack(SL*ps, SLDatatypex); //尾插voidSeqListPopBack(SL*ps); //尾删voidSeqListPushFront(SL*ps, SLDatatypex); //头插voidSeqListPopFront(SL*ps); //头删voidSeqListInsert(SL*ps, intpos, SLDatatypex); //任意插voidSeqListErase(SL*ps, intpos); //任意位置删除intSeqListFind(SL*ps, SLDatatypex); //查找元素
🌱功能实现源文件部分
voidSeqListInit(SL*ps) //顺序表初始化{ assert(ps); ps->data=NULL; //指针置空ps->size=ps->capacity=0; //数据、容量归零} voidSeqListDestroy(SL*ps) //销毁顺序表{ assert(ps); free(ps->data); //直接释放顺序表数据域SeqListInit(ps); //代码复用} voidSeqListPrint(SL*ps) //打印顺序表{ assert(ps); size_ti=0; //定义一个同样类型的变量i//配合size进行打印for (i=0; i<ps->size; i++) printf("%d ", ps->data[i]); //ps->data[i]相当于我们熟悉的arr[i]printf("\n"); //全部输出结束后，可以换行} voiddecideCapacity(SL*ps) //判断容量{ assert(ps); if (ps->size==ps->capacity) { size_tnewcapacity=ps->capacity==0?4 : ps->capacity*2; //两倍扩容SLDatatype*tmp= (SLDatatype*)realloc(ps->data, sizeof(SLDatatype) *newcapacity); assert(tmp); //断言，可能存在扩容失败的情况ps->data=tmp; ps->capacity=newcapacity; } } voidSeqListPushBack(SL*ps, SLDatatypex) //尾插{ assert(ps); decideCapacity(ps); //判断是否需要扩容ps->data[ps->size++] =x; //尾插成功//SeqListInsert(ps, ps->size, x); //可以使用任意位置插入，替代插入} voidSeqListPopBack(SL*ps) //尾删{ assert(ps); assert(ps->size>0); //需要断言一下，如果顺序表本来一个元素都没有，是肯定删不了的ps->size--; //有效数据-1，就是尾删//SeqListErase(ps, ps->size - 1); //可以使用任意位置删除，替代删除} voidSeqListPushFront(SL*ps, SLDatatypex) //头插{ assert(ps); decideCapacity(ps); //判断扩容//先把数据整体往后挪动，再头插size_tend=ps->size; while (end>0) { ps->data[end] =ps->data[end-1]; end--; } ps->data[end] =x; ps->size++; //SeqListInsert(ps, 0, x); //可以使用任意位置插入，替代插入} voidSeqListPopFront(SL*ps) //头删{ assert(ps); assert(ps->size>0); //同头插原理一样，需要把数据整体往前挪动size_tbegin=0; while (begin<ps->size-1) { ps->data[begin] =ps->data[begin+1]; begin++; } ps->size--; //有效元素-1，就可以实现头删//SeqListErase(ps, 0); //可以使用任意位置删除，替代删除} voidSeqListInsert(SL*ps, intpos, SLDatatypex) //任意插{ assert(ps); assert(pos>=0); assert((size_t)pos<=ps->size); decideCapacity(ps); //判断容量//原理有点类似头插，不过终止条件依赖于possize_tend=ps->size; while (end> (size_t)pos) { ps->data[end] =ps->data[end-1]; end--; } ps->data[pos] =x; ps->size++; } voidSeqListErase(SL*ps, intpos) //任意位置删除{ assert(ps); assert(pos>=0); assert((size_t)pos<ps->size); //类似于头删size_tbegin= (size_t)pos; while (begin<ps->size-1) { ps->data[begin] =ps->data[begin+1]; begin++; } ps->size--; } intSeqListFind(SL*ps, SLDatatypex) //查找元素{ assert(ps); size_ti=0; for (i=0; i<ps->size; i++) { if (ps->data[i] ==x) returni; } return-1; //没有找到目标元素}
🌱主函数调用源文件部分
voidmenu() { printf("*******************************\n"); printf("****** 0.退出 1.打印 ******\n"); printf("****** 2.尾插 3.尾删 ******\n"); printf("****** 4.头插 5.头删 ******\n"); printf("****** 6.任意插 7.任意删******\n"); printf("****** 8.按元素值插入 ******\n"); printf("****** 9.按元素值删除 ******\n"); printf("*******************************\n"); } intmain() { intinput=1; SLs; SeqListInit(&s); //创建一个顺序表while (input) { intpos=0; SLDatatypex=0; SLDatatypey=0; menu(); printf("请选择:>"); scanf("%d", &input); switch (input) { case0: printf("退出顺序表!\n"); SeqListDestroy(&s); break; case1: SeqListPrint(&s); break; case2: printf("请输入一个值:>"); scanf("%d", &x); SeqListPushBack(&s, x); break; case3: SeqListPopBack(&s); break; case4: printf("请输入一个值:>"); scanf("%d", &x); SeqListPushFront(&s, x); break; case5: SeqListPopFront(&s); break; case6: printf("请输入下标和目标值:>"); scanf("%d %d", &pos, &x); SeqListInsert(&s, pos, x); break; case7: printf("请输入下标:>"); scanf("%d", &pos); SeqListErase(&s, pos); break; case8: printf("请输入待插入元素值和目标值:>"); scanf("%d %d", &y, &x); SeqListInsert(&s, SeqListFind(&s, y), x); break; case9: printf("请输入待删除元素值:>"); scanf("%d", &y); SeqListErase(&s, SeqListFind(&s, y)); break; default : printf("选择错误，请重新选择!\n"); break; } } return0; }
🌳总结
以上就是关于 顺序表 的所有内容了，希望你再看完后能够有所收获，掌握数据结构中最简单的存储结构，慢慢来，万丈高楼平地起!
如果本文有不足或错误的地方，随时欢迎指出，我会在第一时间改正
