数据结构之顺序表的增删查改等操作详解
顺序表的增删查改
⽂章⽬录
顺序表
⼀段物理地址连续的存储单元依次存储数据元素的线性结构，其实就是数组，要求存储的数据是依次连续存储顺序表的顺序存储⽰意图如下：
静态顺序表：使⽤定长数组存储元素
固定⼤⼩的定义，给⼩了可能不够⽤，给⼤可能浪费
动态顺序表：使⽤动态开辟的数组存储
动态适应我们需求的⼤⼩，⽐较灵活
所基本的增删改查语句
以我们主要针对动态顺序表进⾏讲解顺序表的增删查改等操作实现
⾸先我们创建三个⽂件，分别是：
SeqList.h对相关头⽂件的包含，以及实现顺序表的结构和函数的声明
SeqList.c对实现顺序表增删查改等操作的函数进⾏定义
test.c⽂件进⾏顺序表相关函数和顺序表功能的测试
我们实现顺序表，⾸先需要对顺序表结构进⾏定义
//动态顺序表结构
typedef struct SeqList
{
int* a;//定义⼀个指针指向动态开辟的内存，即存储顺序表数据的空间
int size;//当前顺序表的数据个数
int capacity;//顺序表的容量
};
在动态顺序表结构中，我们定义了⼀个指针指向动态开辟的内存，即存储顺序表数据的空间，定义size记录当前顺序表的数据个数，定义capacity记录当前顺序表的容量，但是我们想⼀下，我们顺序表的存储数据⼀定是整形吗？万⼀我想改变顺序表的数据类型呢？
这样定义的话，我们想要改变顺序表的数据类型时，就会很⿇烦，所有涉及到的地⽅都需要修改，所以我们这样定义：
typedef int SQDataType
//动态顺序表结构
typedef struct SeqList
{
SQDataType* a;//定义⼀个指针指向动态开辟的内存，即存储顺序表数据的空间
int size;//当前顺序表的数据个数
int capacity;//顺序表的容量
}SLT;
这样定义我们在想要修改顺序表存储的数据类型时，就直接在typedef(类型重定义)这⾥修改就可以了，这样就⽅便了很多。
接下来我们在test.c中创建⼀个结构体变量(注意包含SeqList.h头⽂件)，开始定义顺序表的增删查改等操作。
然后我们来写顺序表的初始化接⼝的实现：
在定义函数之前，我们考虑这么⼀件事情
注意：
InitSeqList(s);
InitSeqList(&s);
我们在传结构体变量时是传值呢还是传址呢？
答案是传地址，因为函数传参的时候，参数是需要压栈的。如果传递⼀个结构体对象的时候，结构体过⼤，参数压栈的系统开销⽐较⼤，所以会导致性能的下降。
顺序表的初始化
void SeqListInit(SLT* psl)
{
assert(psl);//我们断⾔⼀下，因为创建结构体变量的地址不能为NULL
psl->a=NULL;
psl->size=psl->capacity=0;
}
因为创建结构体变量的地址不能为NULL，所以我们在⾥⾯断⾔⼀下，将指针a置为空以及size和capacity置为0。
有初始化顺序表那就有销毁顺序表，下⾯我们看顺序表的销毁
顺序表的销毁
void SeqListDestory(SLT* psl)
{
assert(psl);
if(psl->a)
{
free(psl->a);
psl->a=NULL;
}
}
当指向动态开辟的内存的指针不为NULL时，说明有顺序表的数据，我们将这段动态开辟的空间释放掉，并把它置为NULL。
然后我们再写⼀个打印顺序表数据的函数：
打印顺序表数据
void SeqListPrint(SLT* psl)
{
assert(psl);
int i=0;
for(i=0;i<psl->size;i++)
{
printf("%d ",psl->a[i]);
}
printf("\n");
}
打印的函数⼗分简单，就是相当于数组的遍历⽽已
写完上⾯的这些函数，我们就要进⼊我们顺序表的增删查改等操作的正题了。
顺序表尾插数据
⾸先是尾插数据函数，那么我们如何尾插⼀个元素呢？有⼈会说，我们不是有⼀个记录数据个数的变量size嘛，那么⽐如当前元素个数是size，那么我们要尾插的位置的下标应该就是size，仔细想⼀想对不对呢？是对的。但是我们在尾插前需要考虑的是，我们现在都没有空间，怎么存放数据呀，就算有了空间，你怎么知道当前这块空间有没有满呢？这⾥就需要⽤到我们的capacity变量了，故我们在尾插前⼀定要先检查是不是需要增容。
由于后⾯的⼀些操作也会⽤到考虑是不是需要增容，所以我们将判断是不是需要增容封装成⼀个函数：
void SeqListCheckCapacity(SLT* psl)
{
assert(psl);
if(psl->size==psl->capacity)//当当前元素个数等于我们的当前容量时我们要增容
{
//增容
int newcapacity = psl->capacity==0?4:psl->capacity*2;
psl->a=(SQDataType*)realloc(psl->a,newcapacity*sizeof(SQDataType));
if(psl->a==NULL)
{
perror("psl->a");
return;
}
psl->capacity=newcapacity;
}
}
当当前元素个数等于我们的当前容量时我们要增容，我们在增容时，如果capacity是0时我们先开辟存
储4个数据的内存，不是0时，我们就进⾏⼆倍的增容，如果开辟失败了，我们加⼀个判断pal->a是不是NULL，是NULL则打印错误返回，最后将capacity更新。
这时我们就可以写尾插的函数了：
void SeqListPushBack(SLT* psl,SQDataType x)
{
assert(psl);
//检查增容
SeqListCheckCapacity(psl);
psl->a[psl->size]=x;
psl->size++;
}
⾸先检查增容，然后进⾏插⼊，我们要尾插的位置的下标就是size，插⼊然后将size++，就实现了尾插的操作。
我们进⾏测试发现，没有任何问题，完成了插⼊。
下⾯我们进⾏下⼀个操作：头插。
顺序表头插数据
同样地，在头插之前我们需要检查是否需要增容
void SeqListPushFront(SLT* psl,SQDataType x)
{
assert(psl);
//检查增容
SeqListCheckCapacity(psl);
int end=psl->size-1;
while(end>=0)
{
psl->a[end+1]=psl->a[end];
end--;
}
psl->a[0]=x;
psl->size++;
}
在头插时，我们需要将后⾯的元素依次向后移动⼀个单元，然后在第⼀个位置插⼊，最后size++。注意：
在移动元素时，我们需要从后往前开始移动，从前往后会将后⾯元素覆盖。
下⾯我们再进⾏下⼀个操作：尾删
void SeqListPopBack(SLT* psl)
{
assert(psl);
if(psl->size>=)
{
psl->size--;
}
}
尾删⾮常简单，我们直接将size–，就相当于删除了最后⼀个元素。
尾删之后我们再来看看头删：
顺序表头删数据
void SeqListPopFront(SLT* psl)
{
assert(psl);
int begin=0;
while(begin<psl->size-1)
{
psl->a[begin]=psl->a[begin+1];
begin++;
}
psl->size--;
}