引言
数据结构世界的起源——顺序表（Sequential List）
在世界创造之初，顺序的力量首先降临，它让这个数据结构世界有了顺序的方式运作。顺序的力量拥有一种本源神通——空间随机访问
一、最基础的数据结构：数组
【思考】有了数组，为什么还要学习其他的数据结构？
假定数组有10个空间，已经使用了5个，向数组中插入数据步骤：
求数组的长度，求数组的 有效数据个数 ，向下标为数据有效个数的位置插入数据（注意：这里是否要判断数组是否满了，满了还能继续插入吗）.....
假设数据量非常庞大，频繁的获取数组有效数据个数会影响程序执行效率。
结论 ：最 基础 的数据结构能够提供的操作已经不能完全满足 复杂 算法实现。
二、顺序表与数组的区别
顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口
三、静态顺序表
这里使用typedef定义数据类型，使得后续方便改动 ；同时缩减结构体名称，方便书写
静态顺序表缺陷：空间给少了不够⽤，给多了造成空间浪费
四、动态顺序表
4.1 定义
顺序表的各种功能，都是通过函数来实现的
4.2 初始化
这里注意，函数参数是传结构体指针，这样才能在函数内部对顺序表进行各种解引用操作
对于动态顺序表，初始化则用malloc函数动态开辟内存空间 ；存储个数为0，容量初始置为4
4.3 销毁
销毁的实现就比较容易了，对于用free函数将动态开辟的空间进行释放，并将指针置为NULL ；再将存储个数和容量置为0
4.4 尾插
在顺序表尾部插入数据
根据当前已有的元素个数，对数组进行下标访问并赋值，size自增
普通写法
合并写法
但是，我们会发现一个问题，如果尾插时，数组满了怎么办？那么，我们就需要扩容，定义一个函数专门来检测容量，如果容量满了，则进行扩容
我们使用realloc函数动态开辟空间进行扩容，而扩容的大小则为原来容量的2倍 （这样比较合理，扩容多了浪费空间，扩容少了空间又不够）
4.5 打印
对顺序表进行了操作，总得打印出来看看吧~
for循环遍历数组，打印对应下标的元素
运行结果
4.6 头插
与尾插相同，先检测容量，再用循环将数组中每个元素向后挪动一格，最后在头部插入数据，size自增
4.7 尾删
尾部删除的实现，就直接让size自减，使得不再能够访问尾部数据。尾删时要注意使用断言assert，保证size大于零，不会造成越界访问
4.8 头删
与尾删相同，使用断言assert，再用循环将数组中每个元素向前挪动一格，覆盖头部数据，实现头部删除，size自减
提醒：对于各种判断条件不清楚，请一定要画图！！！
4.9 指定插入
输入指定位置的下标，用循环将pos往后的所有数据向后挪动一格 ，再于指定位置插入数据，size自增；同样，断言assert保证pos不会越界
有些人有可能会疑惑，为什么不判断是否为头插和尾插呢？答案是，因为我们可以运用这个应用更广的指定插入，来实现头插和尾插 ，以此增强函数的复用性
尾插
头插
4.10 指定删除
输入指定位置的下标，用循环将pos往后的所有数据向前挪动一格 ，以此覆盖pos位置的数据，达到指定删除的目的；同样，断言assert保证pos不会越界（此处与指定插入比少了一个等号，仔细思考一下为什么？）
与指定插入相同，延续函数的复用性，实现头删和尾删
头删
尾删
4.11 查找
for循环遍历数组，找到返回下标，找不到返回-1
4.12 修改
同样，只要有pos就用断言assert，再直接通过下标访问数组进行修改
在后续调试过程中发现，对于psl指针，如果有人误传了NULL，则会导致程序崩溃，所以最好在每个函数前断言assert，保证psl指针的有效性
这样我们就完成了顺序表的增删查改等功能的实现
五、顺序表oj题
仅仅了解顺序表的知识是不够的，让我们来刷刷题吧！
26.删除有序数组中的重复项（LeetCode）-CSDN博客
看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！
💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖
拜托拜托这个真的很重要！
你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信呢秒回哦。
源代码
seqlist.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //静态顺序表 //#define N 10 //typedef int SLDataType; // //typedef struct SeqList //{ // SLDataType a[N]; // int size; //}SL; //动态顺序表 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 SLPushBack(SL* psl, SLDataType x); //头插 void SLPushFront(SL* psl, SLDataType x); //尾删 void SLPopBack(SL* psl); //头删 void SLPopFront(SL* psl); //指定插入 void SLInsert(SL* psl, int pos, SLDataType x); //指定删除 void SLErase(SL* psl, int pos); //查找 int SLFind(SL* psl, SLDataType x); //修改 void SLModify(SL* psl, int pos, SLDataType x);
seqlist.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"seqlist.h" void SLInit(SL* psl) { assert(psl); psl->a = (SLDataType*)malloc(sizeof(SLDataType) * 4); if (psl->a == NULL) { perror("malloc fail"); return; } psl->size = 0; psl->capacity = 4; } void SLDestroy(SL* psl) { assert(psl); free(psl->a); psl->a = NULL; psl->size = 0; psl->capacity = 0; } void SLPrint(SL* psl) { assert(psl); int i = 0; for (i = 0; i < psl->size; i++) { printf("%d ", psl->a[i]); } } static void CheckCapacity(SL* psl) { assert(psl); if (psl->size == psl->capacity) { SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * psl->capacity * 2); if (tmp == NULL) { perror("realloc fail"); return; } psl->a = tmp; psl->capacity *= 2; } } void SLPushBack(SL* psl, SLDataType x) { assert(psl); //CheckCapacity(psl); //psl->a[psl->size++] = x; SLInsert(psl, psl->size, x); } void SLPushFront(SL* psl, SLDataType x) { assert(psl); //CheckCapacity(psl); //int end = psl->size - 1; //while (end >= 0) //{ // psl->a[end + 1] = psl->a[end]; // end--; //} //psl->a[0] = x; //psl->size++; SLInsert(psl, 0, x); } void SLPopBack(SL* psl) { assert(psl); //assert(psl->size > 0); //psl->size--; SLErase(psl, psl->size - 1); } void SLPopFront(SL* psl) { assert(psl); //assert(psl->size > 0); //int start = 0; //while (start < psl->size - 1) //{ // psl->a[start] = psl->a[start + 1]; // start++; //} //psl->size--; SLErase(psl, 0); } void SLInsert(SL* psl, int pos, SLDataType x) { assert(psl); assert(pos >= 0 && pos <= psl->size); CheckCapacity(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 start = pos + 1; while (start < psl->size) { psl->a[start - 1] = psl->a[start]; start++; } psl->size--; } int SLFind(SL* psl, SLDataType x) { assert(psl); int i = 0; for (i = 0; i < psl->size; i++) { if (psl->a[i] == x) { return i; } } return -1; } void SLModify(SL* psl, int pos, SLDataType x) { assert(psl); assert(pos >= 0 && pos < psl->size); psl->a[pos] = x; }
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"seqlist.h" void TestSeqList1() { SL s; SLInit(&s); SLPushBack(&s, 1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushBack(&s, 4); SLPushFront(&s, 5); SLPushFront(&s, 6); SLPushFront(&s, 8); SLPushFront(&s, 9); SLPrint(&s); SLDestroy(&s); } void TestSeqList2() { SL s; SLInit(&s); SLPushBack(&s, 1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushBack(&s, 4); SLPushFront(&s, 5); SLPopBack(&s); SLPushFront(&s, 8); SLPopBack(&s); SLPrint(&s); SLDestroy(&s); } int main() { TestSeqList2(); return 0; }
