前言
本章讲解线性表中最基础的顺序表，觉得有用的话记得点点关注。
正文
1. 线性表
线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的
数据结构,常见的线性表:顺序表、链表、栈、队列、字符串 ….
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性
表在物理上存储时,通常以数组和链式结构的形式存储。
逻辑上连续体现在线性表的呈现，线性表在屏幕上是以连续形式呈现，故为线性结构。
物理结构上不一定连续体现在线性表的内存形式。因为每个元素储存的地址大概率不是连续的，而是随机分布在线性表所申请的空间中。
2. 顺序表
2.1 概念与结构
概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。（顺序表的底层结构是数组）
顺序表=数组+增加数据+删除数据+修改数据+查找数据+ …
顺序表分为静态顺序表和动态顺序表。根据不同场景创建顺序表。
前者空间有限，申请小了不够用，申请多了用不完，后者需要动态申请空间，因此需要malloc calloc realloc 之一。
malloc：一次申请连续空间。
calloc：同malloc，还会初始化。
realloc：同malloc，还会扩容。
因此，动态顺序表用realloc动态申请内存。
静态顺序表：
//静态顺序表
typedef int SLDataType;
#define N 7
typedef struct SeqList {
SLDataType a[N];
int size;//有效数据个数
}SL;
动态顺序表：
// 动态顺序表 -- 按需申请
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int size;//有效数据个数
int capacity;//空间大小
}SL;
关于上述代码typedef int SLDataType;
此处重定义int为了方便更改顺序表里元素的类型，如果需要更改，只要将int更改即可。
2.2 顺序表的初始化
初始化顺序表的成员arr,size,capacity。
size:顺序表初始化时输入数据在数组中的位置。
capacity：数组中数组空间的最大值。
//创建顺序表
typedef int SLDataType;
typedef struct SeqList {
SLDataType* arr;
int size;
int capacity;
}SL;
//顺序表初始化
void SLInit(SL* ps)
{
ps.arr = NULL;
ps.size = ps.capacity = 0;
}
//测试代码，检测是否有误
void test01()
{
SL s1;
SLInit(&s1);//传址调用
}
//main函数
int main()
{
test01();
return 0;
}
传址调用（取地址）：形参的改变会影响到实参。
传值调用（不取地址）：形参改变不会影响到实参。
2.3 顺序表的数据插入
尾插
尾插之前需要判断顺序表空间是否足够，若不够，则需要realloc扩容。
关于realloc，一般成2倍扩容。因为用++（前置++/后置++）扩容时，如果堆区的数组后面的空间小于扩容需求，则数组会在堆区找更大的空间，接着拷贝旧数据，释放旧空间，把数据粘贴到新空间，所以用二倍扩容，避免多次拷贝释放粘贴。
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
if (ps->size == ps->capacity)
{
ps->arr = (SLDataType*)realloc(ps->arr, 2 * ps->capacity);
}
ps->arr[ps->size++] = x;
}
以上代码又有什么问题呢？
capacity初始为0；空间可能申请失败；realloc第二个参数的单位是字节…
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
if (ps->size == ps->capacity)
{
//解决capacity初始为0的问题
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//解决realloc第二个参数的单位是字节的问题
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * 4);
//解决空间可能申请失败的问题
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
ps->arr[ps->size++] = x;
}
时间复杂度O(1)
温馨提示：写完尾插之后记得调用函数SLPushBack(SL* ps, SLDataType x)运行测试。
头插
//判断空间是否满了
void SLCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
}
//头插
void SLPushFront(SL* ps, SLDataType x)
{
SLCheckCapacity(ps);
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
}
如果如下传参，程序就崩了，而且退出码是随机数。
所以需要判断一下传的指针是否为空。
SLPushFront(NULL, 1);
修改后：
//头插
void SLPushFront(SL* ps, SLDataType x)
{
/*温柔的处理方式
if (ps == NULL)
{
return;
}*/
//assert（表达式）表达式为真，程序继续进行；为假，报错。
assert(ps);
SLCheckCapacity(ps);
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
}
时间复杂度O(N)
温馨提示：写完头插之后记得调用函数SLPushFront(SL* ps, SLDataType x)运行测试。
数据插入后的顺序表：
size:顺序表初始化时输入数据在数组中的位置，也是顺序表中有效数据个数。
capacity：数组中数组空间的最大值。
2.4 顺序表的数据删除
删除不一定要将数据覆盖为0，也可以将数据标记为空。
尾删
//尾删
void SLPopBack(SL* ps)
{
//顺序表不为空
assert(ps && ps->size);
//有效数据减1，故size--
--ps->size;
}
时间复杂度O(1)
尾删只需要将最后一个标记为空，故将有效数据个数减1。
温馨提示：写完尾删之后记得调用函数SLPopBack(SL* ps)运行测试。
头删
//头删
void SLPopFrnt(SL* ps,int size)
{
//顺序表不为空
assert(ps && ps->size);
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
//有效数据减1，故size--
--ps->size;
}
时间复杂度O(N)
头删只需将第二个数据赋值给第一个数据，第三个赋值给第二个…依次遍历
温馨提示：写完头删之后记得调用函数SLPopFront(SL* ps，int size)运行测试。
2.5 关于顺序表的其他操作
对顺序表有兴趣的可以自行探索其他操作。
数据查找
//数据查找
//找到了，返回下标；未找到，返回-1
int SLFind(SL* ps,SLDataType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}
温馨提示：记得测试。
指定位置之前插入数据
//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos <= 0 && pos <= ps->size);
SLCheckCapacity(ps);
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
++ps->size;
}
温馨提示：记得测试。
指定位置删除数据
//指定位置删除数据
void SLErase(SL* ps, int pos)
{
assert(ps && ps->size);
assert(pos >= 0 && pos < ps->size);
for (int i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i+1];
}
--ps->size;
}
温馨提示：记得测试。
销毁
//销毁
void SLDesTroy(SL* ps)
{
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}