1. 线性表
线性表是n个具有相同特性的数据元素的有限序列，
常见的线性表：顺序表、链表、栈、队列、字符串等等。
2. 顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构。
2.1 动态顺序表
我们一般使用的都是动态的顺序表。
3. 接口实现
前期工作
在VS上建三个工程文件，
test.c用来测试顺序表；
SeqList.c用来实现接口；
SeqList.h用来包头文件，和创建动态顺序表的基本结构；
头文件如下：
#pragma once #include #include #include #define INIT_CAPACITY 4 //选择需要的类型 typedef int SLDatatype; //动态的顺序表 typedef struct SeqList { SLDatatype* a; int size; //有效的数据个数 int capacity; //顺序表的空间容量 }SL; //顺序表的增删查改: //初始化顺序表 void SeqInit(SL* s); //销毁顺序表 void SeqDestory(SL* s); //打印顺序表 void SeqPrint(SL* s); //检查容量 void CheckCapacity(SL* s); //尾插 void SeqPushBack(SL* s, SLDatatype x); //尾删 void SeqPopBack(SL* s); //头插 void SeqPushFront(SL* s, SLDatatype x); //头删 void SeqPopFront(SL* s); //插入 void SeqInsert(SL* s, int pos, SLDatatype x); //删除 void SeqErase(SL* s, int pos);
3.1 初始化、销毁与检查容量
接口如下：
3.1.1 初始化
//初始化顺序表 void SeqInit(SL* ps) { //结构体指针不能为空 assert(ps); //开辟空间 ps->a = (SLDatatype*)malloc(sizeof(SLDatatype) * INIT_CAPACITY); //检查 if (ps->a == NULL) { perror("malloc fail"); } ps->size = 0; ps->capacity = INIT_CAPACITY; }
3.1.2 销毁
//销毁顺序表 void SeqDestory(SL* ps) { //结构体指针不能为空 assert(ps); //释放并置空 free(ps->a); ps->a = NULL; ps->capacity = ps->size = 0; }
3.1.3 检查容量
//检查容量 void CheckCapacity(SL* ps) { //结构体指针不能为空 assert(ps); if (ps->size == ps->capacity) { //增容（两倍） SLDatatype* tmp = (SLDatatype*)realloc(ps->a, sizeof(SLDatatype) * ps->capacity * 2); //检查是否增容成功 if (tmp == NULL) { perror("realloc fail"); return; } ps->a = tmp; ps->capacity *= 2; } }
3.2 尾插
//尾插 void SeqPushBack(SL* ps, SLDatatype x) { //代码复用 SeqInsert(ps, ps->size, x); /*单独实现 //结构体指针不能为空 assert(ps); //检查容量 CheckCapacity(ps); //尾插 ps->a[ps->size++] = x; */ }
3.3 尾删
//尾删 void SeqPopBack(SL* ps) { //代码复用 SeqErase(ps, ps->size - 1); /*单独实现 //结构体指针不能为空 assert(ps); //检查顺序表是否为空 assert(ps->size); //尾删 ps->size--; */ }
3.4 头插
//头插 void SeqPushFront(SL* ps, SLDatatype x) { //代码复用 SeqInsert(ps, 0, x); /*单独实现 //结构体指针不能为空 assert(ps); //检查容量 CheckCapacity(ps); //把值往后挪 int end = ps->size - 1; while (end >= 0) { ps->a[end + 1] = ps->a[end]; end--; } //头插 ps->a[0] = x; ps->size++; */ }
3.5 头删
//头删 void SeqPopFront(SL* ps) { //代码复用 SeqErase(ps, 0); /*单独实现 //结构体指针不能为空 assert(ps); //当顺序表为零时就不能删了 assert(ps->size); //将数据往前覆盖 int begin = 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; */ }
/
3.6 插入
//插入 void SeqInsert(SL* ps, int pos, SLDatatype x) { //结构体指针不能为空 assert(ps); //pos需要在有数据的区间 assert(pos >= 0 && pos <= ps->size); //检查容量 CheckCapacity(ps); //往后挪动数据 int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; end--; } //插入数据 ps->a[pos] = x; ps->size++; }
3.7 删除
//删除 void SeqErase(SL* ps, int pos) { //结构体指针不能为空 assert(ps); //pos需要在有数据的区间 assert(pos >= 0 && pos < ps->size); //挪动数据 int begin = pos + 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; }
我们发现，
其实顺序表核心的功能就是插入和删除，
只要我们完成这两个接口，
其他的接口的实现都是大同小异。
顺序表源码
SeqList.h #pragma once #include #include #include #define INIT_CAPACITY 4 //选择需要的类型 typedef int SLDatatype; //动态的顺序表 typedef struct SeqList { SLDatatype* a; int size; //有效的数据个数 int capacity; //顺序表的空间容量 }SL; //顺序表的增删查改: //初始化顺序表 void SeqInit(SL* s); //销毁顺序表 void SeqDestory(SL* s); //打印顺序表 void SeqPrint(SL* s); //检查容量 void CheckCapacity(SL* s); //尾插 void SeqPushBack(SL* s, SLDatatype x); //尾删 void SeqPopBack(SL* s); //头插 void SeqPushFront(SL* s, SLDatatype x); //头删 void SeqPopFront(SL* s); //插入 void SeqInsert(SL* s, int pos, SLDatatype x); //删除 void SeqErase(SL* s, int pos); SeqList.c #define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h" //初始化顺序表 void SeqInit(SL* ps) { //结构体指针不能为空 assert(ps); //开辟空间 ps->a = (SLDatatype*)malloc(sizeof(SLDatatype) * INIT_CAPACITY); //检查 if (ps->a == NULL) { perror("malloc fail"); } ps->size = 0; ps->capacity = INIT_CAPACITY; } //销毁顺序表 void SeqDestory(SL* ps) { //结构体指针不能为空 assert(ps); //释放并置空 free(ps->a); ps->a = NULL; ps->capacity = ps->size = 0; } //打印 void SeqPrint(SL* ps) { //结构体指针不能为空 assert(ps); //遍历打印 for (int i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n"); } //检查容量 void CheckCapacity(SL* ps) { //结构体指针不能为空 assert(ps); if (ps->size == ps->capacity) { //增容（两倍） SLDatatype* tmp = (SLDatatype*)realloc(ps->a, sizeof(SLDatatype) * ps->capacity * 2); //检查是否增容成功 if (tmp == NULL) { perror("realloc fail"); return; } ps->a = tmp; ps->capacity *= 2; } } //尾插 void SeqPushBack(SL* ps, SLDatatype x) { //代码复用 SeqInsert(ps, ps->size, x); /*单独实现 //结构体指针不能为空 assert(ps); //检查容量 CheckCapacity(ps); //尾插 ps->a[ps->size++] = x; */ } //尾删 void SeqPopBack(SL* ps) { //代码复用 SeqErase(ps, ps->size - 1); /*单独实现 * //结构体指针不能为空 assert(ps); //检查顺序表是否为空 assert(ps->size); //尾删 ps->size--; */ } //头插 void SeqPushFront(SL* ps, SLDatatype x) { //代码复用 SeqInsert(ps, 0, x); /*单独实现 //结构体指针不能为空 assert(ps); //检查容量 CheckCapacity(ps); //把值往后挪 int end = ps->size - 1; while (end >= 0) { ps->a[end + 1] = ps->a[end]; end--; } //头插 ps->a[0] = x; ps->size++; */ } //头删 void SeqPopFront(SL* ps) { //代码复用 SeqErase(ps, 0); /*单独实现 //结构体指针不能为空 assert(ps); //当顺序表为零时就不能删了 assert(ps->size); //将数据往前覆盖 int begin = 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; */ } //插入 void SeqInsert(SL* ps, int pos, SLDatatype x) { //结构体指针不能为空 assert(ps); //pos需要在有数据的区间 assert(pos >= 0 && pos <= ps->size); //检查容量 CheckCapacity(ps); //往后挪动数据 int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; end--; } //插入数据 ps->a[pos] = x; ps->size++; } //删除 void SeqErase(SL* ps, int pos) { //结构体指针不能为空 assert(ps); //pos需要在有数据的区间 assert(pos >= 0 && pos < ps->size); //挪动数据 int begin = pos + 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; } test.c #define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h" //测试接口 void SLTest() { SL s; SeqInit(&s); SeqPushBack(&s, 1); SeqPushBack(&s, 2); SeqPushBack(&s, 3); SeqPushBack(&s, 4); SeqPushBack(&s, 5); SeqPushBack(&s, 6); SeqPrint(&s); SeqPopBack(&s); SeqPopBack(&s); SeqPrint(&s); SeqPushFront(&s, 10); SeqPushFront(&s, 50); SeqPrint(&s); SeqPopFront(&s); SeqPopFront(&s); SeqPopFront(&s); SeqPrint(&s); SeqDestory(&s); } int main() { SLTest(); return 0; }
测试结果无误。
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
