1. 顺序表的定义
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。动态顺序表与数组的本质区别是——根据需要动态的开辟空间大小。
2. 顺序表的功能
动态顺序表的功能一般有如下几个：
- 初始化顺序表
- 打印顺序表中的数据
- 检查顺序表的容量
- 顺序表头部插入数据
- 顺序表尾部插入数据
- 顺序表头部删除数据
- 顺序表尾部删除数据
- 顺序表任意位置插入数据
- 顺序表任意位置删除数据
- 顺序表中查找数据
- 顺序表中修改指定位置数据
- 顺序表的销毁
3.顺序表各功能的实现
3.1 创建顺序表
typedef int SQDateType;//对int进行重命名，可增加代码的普适性。 typedef struct SeqList { SQDateType* a; size_t size; //有效数据 size_t capacity;//容量的空间大小 }SL;//对这个结构体重命名为SL，书写方便
3.2 初始化顺序表
由于建立顺序表后并没有原始空间，所以我们自行动态开辟空间，又因为后续要进行扩容，所以我们必须初始化容量大小。
void SeqListInit(SL*ps) { ps->a = (SQDateType*)malloc(sizeof(SQDateType) * 4);//初始化开辟4个int类型的空间 //检查是否开辟成功 if (ps->a == NULL) { printf("malloc fail!\n"); return; } ps->capacity = 4;//初始化容量大小为4 ps->size = 0; }
3.3 打印顺序表中的数据
对顺序表进行增删查改等操作后，我们要把数据打印在控制台以便观察。
void SeqListPrint(SL* ps) { //判断顺序表中是否有数据 assert(ps->size > 0); for (int i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n"); }
3.4 检查顺序表的容量
对顺序表进行插入（增加）数据的操作时，我们必须先对顺序表进行容量的检查，若容量不够，则扩容。
并且扩容的幅度一般是原来容量的2倍。
void CheckSeqListCapacity(SL*ps) { assert(ps);//断言 //检查容量是否已满 if (ps->capacity == ps->size) { //扩容 SQDateType* tmp = (SQDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(SQDateType*)); if (tmp == NULL) { printf("realloc fail!\n"); return; } else { ps->a = tmp; ps->capacity *= 2;//容量增大为原来的两倍 } } }
3.5 顺序表头部插入数据
头插，意思是在顺序表的最前面插入一个数据。我们需要把顺序表里的原数据（如果原来有数据的话）从后往前向后挪一个空间，再把要插入的数据放到第一个位置即可。时间复杂度：O(N).
代码实现如下：
void SeqListPushFront(SL* ps, SQDateType x) { assert(ps); //检查是否要扩容 CheckSeqListCapacity(ps); int end = ps->size; for (end = ps->size ; end >0; end--) { ps->a[end] = ps->a[end - 1]; } ps->a[end] = x; ps->size++;//有效数据+1 }
3.6 顺序表尾部插入数据
尾插，意思是在顺序表的最后面插入一个数据。只需要找到该位置的下标（ps->size处)直接插入即可。
代码实现如下：
void SeqListPushBack(SL* ps, SQDateType x) { assert(ps); //检查是否要扩容 CheckSeqListCapacity(ps); ps->a[ps->size] = x; ps->size++;//有效数据+1 }
3.7 顺序表头部删除数据
头删，意思是删除一个顺序表最前面的数据。只需把原数据从前往后开始向前覆盖一个空间即可。时间复杂度：O(N).
代码实现如下：
void SeqListPopFront(SL* ps) { assert(ps->size > 0);//断言，当顺序表内有数据时才删除 for (int start = 0; start < ps->size; start++) { ps->a[start] = ps->a[start + 1]; } ps->size--;//有效数据-1 }
3.8 顺序表尾部删除数据
尾删，直接删除顺序表中最后一个数据即可。
void SeqListPopBack(SL* ps) { assert(ps->size > 0); ps->size--;//有效数据-1 }
3.9 顺序表任意位置插入数据
在顺序表的pos位置处插入一个数据，先要把pos处及其后面的原数据向后挪一个空间，再把数据放入pos处。时间复杂度：O(N).
代码实现如下：
void SeqListInsert(SL* ps, int pos, SQDateType x) { assert(ps && pos < ps->size);//pos<size时才满足 CheckSeqListCapacity(ps); int end = ps->size ; for (end = ps->size ; end > pos; end--) { ps->a[end] = ps->a[end-1]; } ps->a[pos] = x;//在pos的位置放入数据 ps->size++;//有效数据+1 }
3.10 顺序表任意位置删除数据
在顺序表的pos位置处删除一个数据，只要把pos处后面的数据向前覆盖一个空间。时间复杂度：O(N).
代码实现如下：
void SeqListEarse(SL* ps, int pos) { assert(ps && pos < ps->size);//pos<size时才满足 int start = pos; for (start = pos; start < ps->size; start++) { ps->a[start] = ps->a[start + 1]; } ps->size--;//有效数据-1 }
3.11 顺序表中查找数据
把顺序表中的数据循环遍历，判断每个数据与查找数据是否相等，若相等，返回1，否则返回-1。
int SeqListFind(SL* ps, SQDateType x) { assert(ps && ps->size > 0);//表中有数据时才能查找 for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { return 1; break; } } return -1; }
3.12 顺序表中修改指定位置数据
只要在顺序表中找到指定位置，把修改的值赋给它即可。
void SeqListModify(SL* ps, int pos, SQDateType x) { assert(ps && pos < ps->size);//要修改的位置要小于数据个数 ps->a[pos] = x; }
3.13 顺序表的销毁
顺序表的空间的动态开辟的，最后需要free释放空间，避免造成空间泄漏。
void SeqListDestory(SL* ps) { free(ps->a); ps->a = NULL; ps->capacity = 0; ps->size = 0; }
4. 完整代码
SeqList.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SQDateType; typedef struct SeqList { SQDateType* a; size_t size; //有效数据 size_t capacity;//容量的空间大小 }SL; //初始化顺序表 void SeqListInit(SL* ps); //头部插入数据 void SeqListPushFront(SL* ps, SQDateType x); //尾部插入数据 void SeqListPushBack(SL* ps, SQDateType x); //头部删除数据 void SeqListPopFront(SL* ps); //尾部删除数据 void SeqListPopBack(SL* ps); //任意位置插入数据 void SeqListInsert(SL* ps, int pos,SQDateType x); //任意位置删除数据 void SeqListEarse(SL* ps, int pos); //打印数据函数 void SeqListPrint(SL* ps); //查找数据 int SeqListFind(SL* ps, SQDateType x); //修改指定位置数据 void SeqListModify(SL* ps, int pos, SQDateType x); //销毁顺序表 void SeqListDestory(SL* ps);
SeqList.c
#define _CRT_SECURE_NO_WARNINGS #include "SeqList.h" void SeqListInit(SL*ps) { ps->a = (SQDateType*)malloc(sizeof(SQDateType) * 4);//初始化开辟4个int类型的空间 if (ps->a == NULL) { printf("malloc fail!\n"); return; } ps->capacity = 4; ps->size = 0; } void CheckSeqListCapacity(SL*ps) { assert(ps); //检查容量是否已满 if (ps->capacity == ps->size) { //扩容 SQDateType* tmp = (SQDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(SQDateType*)); if (tmp == NULL) { printf("realloc fail!\n"); return; } else { ps->a = tmp; ps->capacity *= 2; } } } void SeqListPushFront(SL* ps, SQDateType x) { assert(ps); CheckSeqListCapacity(ps); int end = ps->size; for (end = ps->size ; end >0; end--) { ps->a[end] = ps->a[end - 1]; } ps->a[end] = x; ps->size++; } void SeqListPrint(SL* ps) { //判断顺序表中是否有数据 assert(ps->size > 0); for (int i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n"); } void SeqListPushBack(SL* ps, SQDateType x) { CheckSeqListCapacity(ps); ps->a[ps->size] = x; ps->size++; } void SeqListPopFront(SL* ps) { assert(ps->size > 0); for (int start = 0; start < ps->size; start++) { ps->a[start] = ps->a[start + 1]; } ps->size--; } void SeqListPopBack(SL* ps) { assert(ps->size > 0); ps->size--; } void SeqListInsert(SL* ps, int pos, SQDateType x) { assert(ps && pos < ps->size); CheckSeqListCapacity(ps); int end = ps->size ; for (end = ps->size ; end > pos; end--) { ps->a[end] = ps->a[end-1]; } ps->a[pos] = x; ps->size++; } void SeqListEarse(SL* ps, int pos) { assert(ps && pos < ps->size); int start = pos; for (start = pos; start < ps->size; start++) { ps->a[start] = ps->a[start + 1]; } ps->size--; } int SeqListFind(SL* ps, SQDateType x) { assert(ps && ps->size > 0); for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { return 1; break; } } return -1; } void SeqListModify(SL* ps, int pos, SQDateType x) { assert(ps && pos < ps->size); ps->a[pos] = x; } void SeqListDestory(SL* ps) { free(ps->a); ps->a = NULL; ps->capacity = 0; ps->size = 0; }
test.c
#define _CRT_SECURE_NO_WARNINGS #include "SeqList.h" void SeqListTest() { SL sl; //在这里调用各数据接口（函数）进行测试 } int main() { SeqListTest(); return 0; }
