线性表理解
线性表是指具有一类相同特性的数据结构的集合
比如：当提到水果时，我们会知道有苹果、香蕉、梨等
当提到蔬菜时我们会知道白菜、黄瓜、青菜等
而这些就是具有蔬菜特性的集合，叫做蔬菜
在线性表中，包含顺序表、链表等一类相同特性的数据结构的集合
这里说的相同特性主要包含两个方面：逻辑结构和物理结构
逻辑结构：人为想象出来的数据的组织形式，比如想象下我们吃饭时人们需要排成一条线才能进行打饭，这就是人们象限出来的逻辑结构
物理结构：数据在内存中的存储形式，比如 int a = 5; 这里的数据 5 是以整型的形式存储在内存中的
逻辑结构和物理结构分为是线性和非线性两种，在线性表中，逻辑结构一定是线性的，物理结构不一定是线性的（也就是有些是线性的，有些不是线性的）
顺序表
顺序表是线性表的一种，因此顺序表的逻辑结构也是线性的；又因为顺序表的底层逻辑是数组，而数组在内存中是连续存储的，所以顺序表的物理结构也是线性的
顺序表和数组有什么区别吗？
对数组进行封装，增加了一些增删查改的操作就摇身一变成了顺序表，就好比数组是路边的苍蝇馆子，而顺序表则是米其林餐厅
顺序表的定义
我们可以对照前面对数组的定义，对顺序表进行定义；除此之外我们定义顺序表时还需要用到结构体
在VS中 Ctrl + h是一件替换的功能
动态顺序表和静态顺序表的优缺点
我们了解到顺序表分为动态顺序表和静态顺序表，哪一个更好呢？
答案是动态顺序表，它可以使用realloc进行动态的增容
静态顺序表给小了不够用会造成数据丢失（有经济损失，切记不要这样搞）；给大了会造成空间的浪费
动态顺序表不会有这样的问题，他虽然也有一定的空间浪费，但在可控的范围之内。
动态顺序表的实现
在实现时我们需要创建一下三个文件：
其中，SeqList.h 就像是一本书的目录，方便我们快速浏览有哪些操作，SeqList 则像是书中具体的实现的内容，Test.c文件则是为了测试前面两个文件中的内容是否正确。
我们每写完一个功能就要进行测试
初始化
核心代码
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
销毁
核心代码
void SLDestroy(SL* ps)
{
if (ps->arr)//等价于ps->arr != NULL
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
尾插
增容
如何增容呢？
以二倍的形式增容。 为啥以二倍增容原因：是个概率论问题， 增量和插入的个数是正相关的，了解即可
以二倍的形式增容会造成一定的空间浪费,但是是在可控的范围之内的
那为什么不一个一个的增容呢？
增容的操作本身就有一定的程序性能的消耗。若频繁的增容会导致程序效率低下
下面是对增容造成的程序性能消耗的解释:
增容操作也分为两种情况：
1.连续空间足够，直接扩容
2.连续空间不够
1)重新找一块地址,分配足够的内存
2）拷贝数据到新的地址
3)销毁旧地址
因此增容操作本身就有程序性能的消耗，不可一个一个的去增容
核心代码：
void SLCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)//判断空间是否足够 -- 这个是通用的，我们可以将他单独设为一个函数
{
//增容
//ps->arr = (SLDataType)realloc(ps->arr, 2 * ps->capacity);
//防止增容失败后将数组中原有的数据给置为空了，这里需要创建临时变量
//踩坑点2：如果这里的capacity = 0 呢？ -- 给个默认值， 使用三目操作符解决
int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//SLDataType* tmp = (SLDataType*)realloc(ps->arr, NewCapacity);//注意这里realloc的括号里面的类型
//踩坑点3：//这里的增容有问题，realloc的第二个参数单位是申请多少个字节，初始情况下我们需要的是四个整型大小的空间，因此我们要乘以单个类型的字节大小
SLDataType* tmp = (SLDataType*)realloc(ps->arr, NewCapacity * (sizeof(SLDataType)));//注意这里realloc的括号里面的类型
if (tmp == NULL)
{
perror("realloc fail");
exit(1);//等价于return 1;
}
//到这里就说明申请成功了 -- 将申请的空间给给数组，并且及时将记录空间容量的capacity进行增加
ps->arr = tmp;
ps->capacity = NewCapacity;
}
}
尾插的核心代码：
void SLPushBack(SL* ps, SLDataType x)
{
//顺序表的地址不能为空
// 粗暴的解决方式：
assert(ps);//等价于ps != NULL -- 要包含头文件 在SeqList.h 文件中
SLCheckCapacity(ps);
ps->arr[ps->size++] = x;
//等价于：
//ps->arr[ps->size] = x;
//ps->size++
}
打印
核心代码：
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
头插
先将原数组中整体向后移动一位（从后往前移动，不会覆盖元数据），再进行头插操作
核心代码：
void SLPushFrant(SL* ps, SLDataType x)
{
assert(ps);
//判断空间是否足够
SLCheckCapacity(ps);
//将原数组中的数据整体向后移动一位
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];// ps->arr[1] = ps->arr[0]
}
//进行头插
ps->arr[0] = x;
ps->size++;
}
再写for循环时先写循环内部，条件通过内部的内容进行推导出来
尾删
核心代码：
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->arr);
//ps->arr[ps->size - 1] = 0;//写这个代码多余了
ps->size--;
}
头删
核心代码：
void SLPopFrant(SL* ps)
{
assert(ps);
assert(ps->arr);
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];//ps->arr[size - 2] = ps->arr[size - 1];
}
ps->size--;
}
在任意位置之前插入数据
核心代码：
void SLInsert(SL* ps, SLDataType x, int pos)////这里的pos的类型为int，代表数组中指定位置的下标
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
//判断空间是否足够
SLCheckCapacity(ps);
//方法1：
for (int i = ps->size - 1; i >= pos; i--)
{
ps->arr[i + 1] = ps->arr[i];//pa->arr[pos + 1] = ps->arr[pos];
}
////方法2：
//for (int i = ps->size; i > pos; i--)
//{
// ps->arr[i] = ps->arr[i - 1];//ps->arr[pos + 1] = ps->arr[pos];
//}
//ps->arr[pos] = x;
//ps->size++;
}
相关经验总结
只要是插入数据的操作：需要判断空间是否足够，并且插入数据后需要进行size++；
在顺序表中需要将数组从后往前移动时，for循环通常应该这样写：
• 初始化：i = 数组有效个数 -1（从最后一个元素开始）
• 循环条件：i >= 0（确保索引不越界）
• 迭代方式：i–（每次递减，向前移动）
这样可以避免覆盖未处理的元素。"
适用于整体后移、删除元素（避免数据覆盖）。
从前往后遍历的 for循环写法
•初始化：i = 0（从第一个元素开始）
•循环条件：i < n（确保不越界）
•迭代方式：i++（每次向后移动一位）
不覆盖数据
适用于读取、查找、部分插入（不涉及数据覆盖）。