一.原理
1.线性表、顺序表
线性表（Linear list）是n个具有相同特性的数据元素的有限序列。线性表在逻辑上是线性结构，就如同一条连续的直线，但是在物理结构上不一定是连续的。
顺序表（Sequence list）是线性表的一种，但顺序表不仅在逻辑上是线性的，它在物理上同样是线性的。顺序表的底层结构是数组，数组本身就是同一类型数据的集合，顺序表在对数组的封装上实现了常用的增删改查等接口。
2.静态顺序表
静态顺序表的实现如下，在一个自定义结构体SL中定义一个定长数组和已用长度size,在对顺序表进行增删时size（也就是当前数组元素个数进行加减），但之所以叫作静态顺序表，就是因为在开始数组的大小就被给定了（就是MAX），数据最多只能存储到MAX个，因此MAX的大小设置成了问题，空间给少了不够用，给多了造成空间浪费，因此就有了动态顺序表。
3.动态顺序表
动态顺序表在静态的基础上，将定长数组改为一个指针，这样对于就能使用realloc函数合理地进行扩容，并且容量（capacity）也能随时变化，做到了动态地变化。
二.实现
1.初始化、销毁
在进行实现之前需要注意一点：结构体传参的时候，要传结构体的地址。（这点在我之前结构体的文章介绍过）不仅是由于压栈，在如下顺序表初始化的函数中，需要给结构体成员赋值，只有指针能做到，传值的话只能改变形式参数，无法达到效果。
无论是初始化还是销毁，只要传参传的地址，先使用assert对其进行断言保障安全性，初始化指针赋NULL，元素个数size和容量都为0即可。销毁时需要释放动态开辟的空间，并且将指针赋NULL。
//初始化
void SLInit(SL* ps)
{
assert(ps);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
//销毁
void SLDestroy(SL* ps)
{
assert(ps);
assert(ps->arr);
free(ps->arr);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}2.打印
打印需要分不同的类型，在之前的结构体定义前对类型统一命名为SLdatatype，方便修改和阅览。如果对SLdatatype重命名的是int，那么此时的打印方式就以int的形式进行。
//打印
void SLPrint_int(SL* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}3.头插、尾插
在正式进行插入前，首先要进行容量判定，如果容量不够怎么能成功插入呢？如果不够就进行扩容，在扩容时选择一个标准，一般是成倍数的进行扩容（2倍，3倍），这样能较好的节约空间并且也能足够使用。在此作者选择2倍扩容，不过在最开始（即ps->capacity = 0）时先扩容四个元素大小，检查容量是否足够就是检查capacity是否等于size。
//容量检查、扩容
void SLcheckcapacity(SL* ps)
{
assert(ps);
if (ps->capacity == ps->size)
{
int newspace = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLdatatpye* tmp = (SLdatatpye*)realloc(ps->arr, newspace * sizeof(SLdatatpye));
if (tmp == NULL)
{
perror("realloc");
exit(1);
}
ps->arr = tmp;
ps->capacity = newspace;
}
}头插，需要把每个元素往后移动一位，使用for循环实现，随后在第一位插入输入的值，最后不要忘了size++，只要是插入建议先写size++防止忘记。尾插则更为简单，只需要在size出赋值就行。不过需要知道，size是代表元素个数，而元素个数要是表示下标，那就是最后一个元素的后一位。
//头插
void SLPushfront(SL* ps, SLdatatpye value)
{
assert(ps);
SLcheckcapacity(ps);
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];//arr[1] = arr[0]
}
ps->arr[0] = value;
ps->size++;
}
//尾插
void SLPushback(SL* ps, SLdatatpye value)
{
assert(ps);
SLcheckcapacity(ps);
ps->arr[ps->size++] = value;
}4.头删、尾删
与头插尾插同理，头删需要将第一位后的数字都往前移动一位，随后就是size--（删掉了一个元素）。而尾删只需要size--就行，不会影响其他函数，能达到删除的功能。
//头删
void SLDeletefront(SL* ps)
{
assert(ps);
assert(ps->size);
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];//size - 2 = size - 1
}
ps->size--;
}
//尾删
void SLDeleteback(SL* ps)
{
assert(ps);
assert(ps->size);
ps->size--;
}5.指定位置插入、删除
将头插尾插进行广泛化，但核心原理是相同的，只不过起点可以指定而已，此处对于指定位置需要进行判断，必须大于等于0和小于（等于）size。
//指定位置插入
void SLInsert(SL* ps, int pos, SLdatatpye value)
{
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];//pos+1 = pos
}
ps->arr[pos] = value;
ps->size++;
}
//指定位置删除
void SLDelete(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
for (int i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];//size -2 = size - 1
}
ps->size--;
}6.查找
对动态数组进行遍历，查看是否有与输入值相等的值，若有则返回下标。
//查找
int SLFind(SL* ps, SLdatatpye value)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == value)
return i;
}
return -1;
}三.完整代码
头文件：SeqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLdatatpye;
typedef struct Seqlist
{
SLdatatpye* arr;
int size;
int capacity;
}SL;
//初始化
void SLInit(SL*);
//销毁
void SLDestroy(SL* ps);
//打印
void SLPrint_int(SL* ps);
//检查容量、扩容
void SLcheckcapacity(SL* ps);
//头插
void SLPushfront(SL* ps, SLdatatpye value);
//尾插
void SLPushback(SL* ps, SLdatatpye value);
//头删
void SLDeletefront(SL* ps);
//尾删
void SLDeleteback(SL* ps);
//指定位置插入
void SLInsert(SL* ps, int pos, SLdatatpye value);
//指定位置删除
void SLDelete(SL* ps, int pos);
//查找
int SLFind(SL* ps, SLdatatpye value);
源文件：SeqList.c
#include"SeqList.h"
void SLInit(SL* ps)
{
assert(ps);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
void SLDestroy(SL* ps)
{
assert(ps);
assert(ps->arr);
free(ps->arr);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
void SLPrint_int(SL* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
void SLcheckcapacity(SL* ps)
{
assert(ps);
if (ps->capacity == ps->size)
{
int newspace = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLdatatpye* tmp = (SLdatatpye*)realloc(ps->arr, newspace * sizeof(SLdatatpye));
if (tmp == NULL)
{
perror("realloc");
exit(1);
}
ps->arr = tmp;
ps->capacity = newspace;
}
}
void SLPushfront(SL* ps, SLdatatpye value)
{
assert(ps);
SLcheckcapacity(ps);
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];//arr[1] = arr[0]
}
ps->arr[0] = value;
ps->size++;
}
void SLPushback(SL* ps, SLdatatpye value)
{
assert(ps);
SLcheckcapacity(ps);
ps->arr[ps->size++] = value;
}
void SLDeletefront(SL* ps)
{
assert(ps);
assert(ps->size);
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];//size - 2 = size - 1
}
ps->size--;
}
void SLDeleteback(SL* ps)
{
assert(ps);
assert(ps->size);
ps->size--;
}
void SLInsert(SL* ps, int pos, SLdatatpye value)
{
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];//pos+1 = pos
}
ps->arr[pos] = value;
ps->size++;
}
void SLDelete(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
for (int i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];//size -2 = size - 1
}
ps->size--;
}
int SLFind(SL* ps, SLdatatpye value)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == value)
return i;
}
return -1;
}源文件：test.c
#include"Seqlist.h"
void testSL01(SL* ps)
{
SLInit(ps);
SLPushback(ps, 1);
SLPushback(ps, 2);
SLPushback(ps, 3);
SLPushback(ps, 4);
SLPrint_int(ps);
SLInsert(ps, 2, 3);
SLInsert(ps, 0, 0);
SLPrint_int(ps);
SLDelete(ps, 3);
SLDelete(ps, 0);
SLPrint_int(ps);
int ret = SLFind(ps, 2);
if (ret != -1)
{
printf("找到了，下标为：%d\n", ret);
}
else
{
printf("找不到\n");
}
SLDestroy(ps);
}
int main()
{
SL s;
testSL01(&s);
}