目录二、接口实现
一、顺序表的概念
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构 ， 一般采用数组存储 ， 在数组上完成数组的增删查改操作 。
顺序表可分为：
1.1、静态顺序表
静态顺序表是使用定长数组存储元素 。空间小了 ， 不够用 ， 空间大了 ， 浪费 。所以静态顺序表不实用 。
#define N 10typedef int SLDataType;typedef struct SeqList{SLDataType a[N]; // 定长数组int size; // 记录存储多少个数据}SL;
1.2、动态顺序表
动态顺序表是使用动态开辟的数组存储
typedef int SLDataType;typedef struct SeqList{SLDataType* a; // 指向动态开辟的数组int size; // 记录存储多少个有效数据int capacity; // 空间容量大小}SL;
二、接口实现
由于静态顺序表不实用 ， 所以现实中基本都是使用动态顺序表 ， 下面我们来实现动态顺序表
2.1、开辟一个动态顺序表及初始化
1、开辟一个动态顺序表
【2.1、开辟一个动态顺序表及初始化】typedef int SLDataType;typedef struct SeqList{SLDataType* a; // 指向动态开辟的数组int size; // 记录存储多少个有效数据int capacity; // 空间容量大小}SL;
2、顺序表的初始化
void SLInit(SL* ps){assert(ps);ps->a = NULL;ps->size = 0;ps->capacity = 0;}
将指向动态开辟的数组置为NULL 。
2.2、顺序表的增容
先对空间进行判断 ， 若空间为0 ， 则先开辟空间 ， 空间不够 ， 再自动增加空间
代码实现：
void SLCheckCapacity(SL* ps){assert(ps);if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity*sizeof(SLDataType));if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}}
2.3、顺序表的尾插及尾删
1、顺序表的尾插
尾插即是向数组的尾部插入数据 ， 先调用扩容函数判断空间 ， 当尾部空间不够时 ， 就会自动扩容 。
代码实现：
void SLPushBack(SL* ps, SLDataType x){assert(ps);// 扩容SLCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;}
2、顺序表的尾删
尾删就是将数据从尾部开始删除
代码实现：
void SLPopBack(SL* ps){assert(ps);assert(ps->size > 0); // 检查数据是否为NULLps->size--;}
2.4、顺序表的头插及头删
1、顺序表的头插
顺序表头插就是从数组的起始位置开始插入数据 。先判断空间 ， 再把已有的数据向后挪动 ， 然后在头部插入数据 。
代码实现：
void SLPushFront(SL* ps, SLDataType x){assert(ps);SLCheckCapacity(ps);// 挪动数据int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;ps->size++;}
2、顺序表的头删
顺序表的头删是从数组的起始位置删除数据 。把起始位置之后的数据向前挪动 ， 覆盖要删除的数据
代码实现：
void SLPopFront(SL* ps){assert(ps);assert(ps->size > 0);int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;}