目录
① 初始化和销毁
② 增加数据
③ 删除数据
④ 查找
线性表
定义：线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使用的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的， 线性表在物理上存储时，通常以数组（顺序存储结构）和链式结构（链式存储结构）的形式存储。
另外要提及到的一点就是，当我们传递一个参数给函数时，这个参数会不会在函数内被改动决定了使用什么参数形式。
①如果需要被改动，则需要传递指向这个参数的指针。
②如果不用被改动，可以直接传递这个参数。
这个大家一定要搞明白，因为后面线性表的实现都涉及到参数的传递。
顺序表
概念
顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储。
此时可能会有同学问既然顺序表是采用数组存储，那它们两个的区别是什么呢？
区别就是顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接口。
动态顺序表
接下来就是我们本章的重头戏，大家一定要多敲，多画，这就是学习数据结构的精髓。另外编写代码过程中要勤测试，避免写出⼤量代码后再测试⽽导致出现问题，问题定位⽆从下⼿。
动态顺序表的实现
结构
typedef int SLDataType;
typedef struct SeqList{
SLDataType* arr;
int size; //有效数据个数
int capacity; //空间容量
}SeqList;初始化和销毁
//初始化
void SeqListInit(SeqList* ps)
{
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
//销毁
void SeqListDestroy(SeqList* ps)
{
if(ps->arr)
{
free(ps->arr);
}
ps->arr = NULL;
ps->capacity = ps->size = 0;
}增加数据
增加数据时可能会遇到空间充足和空间不足两种情况：
若空间不足则需要增容，其中增容又分为两种情况：
（1）连续空间足够，直接扩容
（2）连续空间不够
① 重新找一块地址，分配足够的内存
② 拷贝数据到新的地址
③ 销毁旧地址
//检查空间大小是否足够
void SLCheckCapacity(SeqList* ps)
{
if (ps->size == ps->capacity)
{
//因为初始化将capacity赋值为0，此时capacity有可能为0
//0乘以任何数都为0，所以如果是第一次扩容则赋值4给capacity
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDateType* tmp = (SLDateType*)realloc(ps->arr, newcapacity * sizeof(SLDateType));
if (tmp == NULL)
{
perror("realloc");
exit(1);
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
}此时可能会有同学问，为什么不可以一次增加一个呢？这样不就没有空间浪费了吗？
我的解释是：增容的操作本身就有一定的程序性能的消耗，若频繁的增容会导致程序效率低下。（并且增容一般是成倍数的增加，一般为2倍增加，另外增量和插入数据的个数是正相关的，这是一个概率学问题，感兴趣的话可以去了解一下）
//尾插
void SeqListPushBack(SeqList* ps, SLDateType x)
{
assert(ps);
SLCheckCapacity(ps);
ps->arr[ps->size++] = x;
}
//头插
void SeqListPushFront(SeqList* ps, SLDateType x)
{
assert(ps);
SLCheckCapacity(ps);
//将数组里的元素整体往后移动一位
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
ps->size++;
}我在代码中使用了断言是因为如果参数传递NULL的话，对NULL解引用那是非法的，所以我就加了一个断言，即使传了一个NULL，程序走到断言处就会结束，不会再进一步对NULL解引用，并且会显示在哪断言错误。assert断言非常好用，推荐大家使用。
删除数据
删除前需要判断顺序表是否为空，如果顺序表为空就不能删除数据。
//头删
void SeqListPopFront(SeqList* ps)
{
assert(ps);
assert(ps->size); //size指的是有效数据个数
//数据整体向前移动一位
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
//尾删
void SeqListPopBack(SeqList* ps)
{
assert(ps);
assert(ps->size);
ps->size--;
}查找
//顺序表查找
int SeqListFind(SeqList* ps, SLDateType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
//没有找到则返回一个无效的下标
return -1;
}在pos位置之前插入数据
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
assert(ps);
//要判断插入的位置是否合理
assert(pos >= 0 && pos <= ps->size);
//pos及之后的数据整体往后移动一位
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
ps->size++;
}删除pos位置的数据
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
//pos之后的数据整体往前移动一位
for (int i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}以上就是顺序表所实现的功能，我已经介绍完了，大家也可以尝试实现一下这些功能。
静态顺序表
概念：使用定长数组存储元素
通过这张图片，我们就可以知道如果空间给少了就不够用，给多了又会造成浪费。
我们很少会遇到需要使用静态顺序表的场景，所以大家了解一下就行了。
本篇文章到这里就结束啦，下篇我将介绍顺序表算法题，敬请期待！希望大家多多来支持一下！
标签：,ps,arr,顺序,SeqList,pos,size From： https://blog.csdn.net/2402_84433929/article/details/143983245