一、什么是顺序表
本质：一种基本的数据结构，底层使用数组类型这种顺序存储结构所实现的一种线性表（逻辑上连续，物理内存也连续的线性存储结构）
性质：线性数据结构（除了首尾之外，其他节点有且仅有一个前驱项和后继项）
基于内存分配方式，顺序表分为两种：静态顺序表和动态顺序表（动态可扩容数组）
作用：1.存储只存在线性关系的数据；2.作为其他数据结构的底层实现（如：栈，队列，哈希表等）
二、顺序表的优缺点
优点：1.支持下标随机访问（效率是O(1)）；
2.对CPU高速缓存比较友好（顺序表物理地址连续，满足空间局部性，遍历时缓存命中率高，因此 CPU 缓存友好）；
缺点：1.数据移动和删除会导致大量数据移动，性能比较低；
2.需要足够大一整块连续的内存空间，容易开辟失败，容易产生空间浪费；
顺序表的使用场景：适用于尾插访问多，中间插入删除少的场景
三、顺序表结构体设计及实现接口
·静态顺序表：基于栈内存固定数组实现，容量编译时固定，无法扩容
数据结构设计：
#define INIT_CAPACITY 20 typedef int DataType; typedef struct { DataType data[INIT_CAPACITY];//固定容量的数组 size_t size;//当前有效元素个数 }StaticArray;·动态顺序表：基于堆内存动态开辟实现，支持经典二倍扩容，容量灵活可变。
数据结构设计：
typedef int DataType; typedef struct { DataType* data; // 存储管理（动态堆内存数组） size_t size; // 数据量管理（有效数据个数） size_t capacity; // 容量管理（最大存储上限） }SeqList;具体实现接口声明：初始化，销毁，扩容（动态顺序表），增删改查，获取容量，判空，清空顺序表
//初始化 extern ErrorCode SeqListInit(SeqList* plist); //销毁 extern ErrorCode SeqListDestroy(SeqList* plist); //清空 extern ErrorCode SeqListClear(SeqList* plist); //判空判满 extern int SeqListIsEmpty(const SeqList* plist); extern int SeqListIsFull(const SeqList* plist); //扩容 extern ErrorCode SeqListRealloc(SeqList* plist); //获取数据量、容量 extern size_t SeqListGetSize(const SeqList* plist); extern size_t SeqListGetCapacity(const SeqList* plist); //头尾插入 extern ErrorCode SeqListPushFront(SeqList* plist, const DataType val); extern ErrorCode SeqListPushBack(SeqList* plist, const DataType val); //指定位置插入 extern ErrorCode SeqListInsert(SeqList* plist, int pos, const DataType val); //头尾删除 extern ErrorCode SeqListPopFront(SeqList* plist); extern ErrorCode SeqListPopBack(SeqList* plist); //按下表删除 extern ErrorCode SeqListErase(SeqList* plist, int pos); //按值删除 extern ErrorCode SeqListRemove(SeqList* plist, DataType val); extern int SeqListRemoveAll(SeqList* plist, DataType val); //修改获取 extern ErrorCode SeqListModify(SeqList* plist, int pos, const DataType val); extern ErrorCode SeqListGetAt(const SeqList* plist, int pos, DataType* val); //查找 extern int SeqListFind(SeqList* plist, const DataType val); //输出打印 extern ErrorCode SeqListPrint(const SeqList* plist);接口实现：
ErrorCode SeqListInit(SeqList* plist) { //参数校验 if (plist==NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //申请空间并初始化 plist->data = (DataType*)malloc(sizeof(DataType) * INIT_CAPACITY); if (plist->data == NULL) { LOG("空间申请失败"); return ERR_MALLOC; } memset(plist->data, 0x00, sizeof(DataType) * INIT_CAPACITY); //初始化其他成员 plist->capacity = INIT_CAPACITY; plist->size = 0; //返回成功 return SUCCESS; } ErrorCode SeqListDestroy(SeqList* plist) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //释放空间 free(plist->data); //初始化其他成员 plist->data = NULL; plist->capacity = plist->size = 0; //返回成功 return SUCCESS; } ErrorCode SeqListClear(SeqList* plist) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //数据量归零 plist->size = 0; //返回成功 return SUCCESS; } int SeqListIsEmpty(const SeqList* plist) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //判空 return plist->size == 0; } int SeqListIsFull(const SeqList* plist) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //判满 return plist->size == plist->capacity; } ErrorCode SeqListRealloc(SeqList* plist) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //判满：空间满了则扩容，没满则返回 if (!SeqListIsFull(plist))return SUCCESS; //扩容：经典2倍扩容 size_t newCapacity = plist->capacity * 2; DataType* newdata = (DataType*)realloc(plist->data, newCapacity * sizeof(DataType)); if (newdata == NULL) { LOG("扩容失败"); return ERR_MALLOC; } //更新数据成员 plist->data = newdata; plist->capacity = newCapacity; //返回成功 return SUCCESS; } size_t SeqListGetSize(const SeqList* plist) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //返回size return plist->size; } size_t SeqListGetCapacity(const SeqList* plist) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //返回capacity return plist->capacity; } ErrorCode SeqListPushFront(SeqList* plist, const DataType val) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //判满，满了则扩容 if (SeqListIsEmpty(plist))SeqListRealloc(plist); //移动数据 memmove(plist->data + 1, plist->data, plist->size * sizeof(DataType)); //头插元素 plist->data[0] = val; //size++ plist->size++; return SUCCESS; } ErrorCode SeqListPushBack(SeqList* plist, const DataType val) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //判满，满了则扩容 if (SeqListIsEmpty(plist))SeqListRealloc(plist); //尾插data[size]=val plist->data[plist->size] = val; //size++ plist->size++; return SUCCESS; } ErrorCode SeqListInsert(SeqList* plist, int pos, const DataType val) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } if (pos<0 || pos>plist->capacity) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //判满，满了扩容 if (SeqListIsEmpty(plist))SeqListRealloc(plist); //移动数据 memmove(plist->data + pos + 1, plist->data + pos, sizeof(DataType) * plist->size - pos); //插入数据 plist->data[pos] = val; //size++ plist->size++; //返回成功 return SUCCESS; } ErrorCode SeqListPopFront(SeqList* plist) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //判空 if (SeqListIsEmpty(plist))return ERR_EMPTY; //移动数据 memmove(plist->data, plist->data + 1, sizeof(DataType) * (plist->size - 1)); //size-- plist->size -= 1; return SUCCESS; } ErrorCode SeqListPopBack(SeqList* plist) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //判空 if (SeqListIsEmpty(plist))return ERR_EMPTY; //size-- plist->size--; return SUCCESS; } ErrorCode SeqListErase(SeqList* plist, int pos) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } if (pos<0 || pos>plist->capacity) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //判空 if (SeqListIsEmpty(plist))return ERR_EMPTY; //移动数据 memmove(plist->data + pos, plist->data + pos + 1, sizeof(DataType) * (plist->size - pos - 1)); //size-- plist->size--; //返回成功 return SUCCESS; } //删除一个指定数据 ErrorCode SeqListRemove(SeqList* plist, DataType val) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //判空 if (SeqListIsEmpty(plist))return ERR_EMPTY; //遍历顺序表：找到要删除的元素，删除，返回success for (int i = 0; i < plist->size; i++) { if (plist->data[i] == val) { SeqListErase(plist, i); return SUCCESS; } } //没有找到返回 return ERR_DATA_NOT_EXISTS; } //删除指定数据: 删除所有的该数据, 返回实际删除的数据数量 int SeqListRemoveAll(SeqList* plist, DataType val) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //判空 if (SeqListIsEmpty(plist))return ERR_EMPTY; size_t count = 0;//统计删除的数据量 //遍历顺序表：找到要删除的元素，删除，返回success for (int i = 0; i < plist->size; i++) { if (plist->data[i] == val) { SeqListErase(plist, i); count++; } } //没有找到返回 return count; } ErrorCode SeqListModify(SeqList* plist, int pos, const DataType val) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } if (pos<0 || pos>plist->capacity) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //判空 if (SeqListIsEmpty(plist))return ERR_EMPTY; //修改指定下标元素 plist->data[pos] = val; return SUCCESS; } ErrorCode SeqListGetAt(const SeqList* plist, int pos, DataType* val) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } if (pos<0 || pos>plist->capacity) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //判空 if (SeqListIsEmpty(plist))return ERR_EMPTY; //获得对应下标的元素 *val = plist->data[pos]; return SUCCESS; } int SeqListFind(SeqList* plist, const DataType val) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //判空 if (SeqListIsEmpty(plist))return ERR_EMPTY; //遍历顺序表：找到对应元素的下标，并返回；没有找到返回-1 for (int i = 0; i < plist->size; i++) { if (plist->data[i] == val)return i; } return -1; } ErrorCode SeqListPrint(const SeqList* plist) { //参数校验 if (plist == NULL) { LOG("参数不合法"); return ERR_INVALID_PARAM; } //遍历顺序表输出 for (int i = 0; i < plist->size; i++) { printf("%d ", plist->data[i]); } printf("\n"); return SUCCESS; }
