目录
1.顺序表的结构
顺序表在逻辑结构和物理结构（存储结构）上都是连续的
顺序表的底层结构是数组，是对数组的封装，从而实现增删查改等接口
2.顺序表的分类
2.1 静态顺序表
- 使用定长数组存储元素
- 静态顺序表缺陷：空间给少了不够用，给多了浪费
2.2 动态顺序表
- 动态顺序表是按需申请
3. 接口实现
顺序表的接口一般包含：初始化，销毁，头插，尾插，头删，尾删，在指定位置之前插入，删除指定位置上的数据，判空，修改数据，查找数据的位置等等。
下面就来对某些接口进行实现
3.1 初始化
//初始化顺序表
void SLInit(ST* ps)
{
ps->a = (SQDataType*)malloc(sizeof(SQDataType) * 4);
if (ps->a == NULL)
{
perror("malloc");
return;
}
ps->size = 0;
ps->capacity = 4;
}
先给a申请4个空间，但是size（元素的有效个数）仍然=0，因为现在还没有向顺序表中插入数据，现在的顺序表是一个空表。
3.2 尾插
开辟空间函数，空间不够了就要进行扩容，在下面其他插入中也会使用到
//开辟空间函数
void SLCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
//开辟空间
SQDataType* tmp = realloc(ps->a, ps->capacity * sizeof(SQDataType)*2);//用realloc进行空间开辟
//为什么要重新创建一个tmp变量来接收realloc开辟的空间的首地址呢？
//因为如果用ps->a接收realloc函数开辟空间，如果开辟的空间失败，会把原先有的数据也丢失掉
//判断realloc开辟空间是否失败
if (tmp == NULL)
{
perror("realloc");
exit(1);
}
//空间开辟成功
ps->a = tmp;
ps->capacity *=2 ;
}
}
//尾插
void SLPushBack(SL* ps, SQDataType x)
{
assert(ps);//ps!=NULL;
//看空间够不够，如果不够就扩容
SLCheckCapacity(ps);//这个是一个空间开辟函数的调用
ps->a[ps->size] = x;
ps->size++;
}
尾插：就是在顺序表的有效元素之后插入数据，但是数组下标是从0开始的，所有插入数据的下标便是size，插入完成之后别忘了让size++
3.3 头插
//头插
void SLPushFront(SL* ps, SQDataType x)
{
assert(ps);//ps!=NULL;
//看空间够不够，如果不够就扩容
SLCheckCapacity(ps);
int i = ps->size;//从移动后面的元素，再移动前面的元素，否则会对元素进行覆盖
for (; i>0 ; i--)
{
ps->a[i] = ps->a[i - 1];//ps->a[1]=ps->a[0]
}
ps->a[0] = x;
ps->size++;
}
头插：头插和尾插都需要看看是不是要扩容，不同点是头插还需要移动元素，在0号位进行插入，而尾插不需要。如果头插不移动元素，直接进行插入就会把原有的0号位上有效元素给覆盖点，从而导致数据丢失。既然是向顺序表中插入数据，那肯定要size++
3.4 尾删
//尾删
void SLPopFront(SL* ps)
{
assert(ps->size);//有效个数=0了，就不需要再删了
assert(ps->a);
ps->size--;
}
尾删：不用改变原先最后一个有效元素，直接进行size - -，这样顺序表的有效个数就少了一个，到时候访问时也访问不到，不在有效范围内的数据
3.5 头删
//头删
void SLPopBack(SL* ps)
{
assert(ps->size);//有效个数=0了，就不需要再删了
assert(ps->a);
int i = 0;
for (i = 0; i < ps->size-1 ; i++)
{
ps->a[i] = ps->a[i + 1];//ps->a[ps->size-2]=ps->a[ps->size-1]
}
ps->size--;
}
头删：头删和头插一样都需要移动元素的位置，这会使得时间效率很低下。最后删完了别忘了进行size- -
3.6 在指定位置之前插入数据
//在指定位置之前插入
void SLInsert(SL* ps, int pos, SQDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);//pos不能超过有效个数的范围
//看空间够不够，不够就扩容
SLCheckCapacity(ps);
for (int i = ps->size; i >= pos+1 ; i--)
{
ps->a[i] = ps->a[i - 1];//a[pos+1]=a[pos]
}
ps->a[pos] = x;
ps->size++;
}
在指定位置之前插入数据：需要将指定位置及其它后面的元素都向后移动，既然是插入，别忘了最后的size++
3.7 删除指定位置上的数据
//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);//pos要在有效的范围内才能进行删除数据的操作
for (int i = pos; i < ps->size-1 ; i++)
{
ps->a[i] = ps->a[i + 1];
}
ps->size--;
}
3.8 销毁顺序表
//销毁顺序表
void Destroy(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->size = ps->capacity = 0;
}