> 作者简介：დ旧言~，目前大一，现在学习Java，c，c++，Python等
> 座右铭：松树千年终是朽，槿花一日自为荣。
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言
梦回数组，当我们开辟了一个数组，数组的大小就已经确定了，不能括容，也不能减容，为了解决这个问题，在数据结构有一个这样的知识--《顺序表》。顺序表连续开辟一个空间，能括容，也能减容，今天我们手撕顺序表。
🌙主体
咱们从三个方面实现顺序表，动态管理，头插头删尾插尾删，增删查改。
在程序中为了实现顺序表，需要创建头文件SeqList.h ，创建源文件test.c，SeqList.c。
🌠动态管理
💤初始化动态顺序表
- 首先定义一个结构体（在源文件中），结构体里面有可变数组（a），数组初始长度（size），初始空间（capacity）。
- 初始化动态顺序表（SeqList.h中），需要开辟空间，再判断空间是否为空，再初始化数组长度，空间。
//动态顺序表 typedef int SLDataType; typedef struct SeqList { //定义一个可变数组 SLDataType* a; //定义数组初始长度 int size; //定义空间大小 int capacity; }SL; //初始化动态顺序表 void SLInit(SL* ps) { //开辟空间 ps->a = (SLDataType*)malloc(sizeof(SLDataType*) * 4); //判断空间是否为空 if (ps->a == NULL) { perror("malloc failed"); exit(-1); } //初始化 ps->size = 0; ps->capacity = 4; }
1.防止一直创建结构体，为了一劳永逸，我们把动态顺序表放在源文件中。
2.这里我们用typedef int SLDataType，给数据类型重定义名字，这样就可以防止修改数据类型。
💤扩容顺序表空间
当数组初始长度（size），初始空间（capacity）相同时，这里们就需要扩容，这里我们扩容两倍。（在头文件中SeqList.c中）
//扩容空间 void SLCheckCapacity(SL* ps) { //如果size和capacity相同 if (ps->size == ps->capacity) { //扩大两倍 SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(SLDataType)); //判断tmp是否为空 if (tmp == NULL) { perror("realloc failed"); exit(-1); } //赋值 ps->a = tmp; ps->capacity = ps->capacity * 2; } }
💤释放顺序表内存
可变数组（a）置为（NULL），数组长度（size）置为（0），初始空间（capacity）置为（0）。
//释放内存 void SLDestroy(SL* ps) { //断言 assert(ps); free(ps->a); ps->a = NULL; ps->size = 0; ps->capacity = 0; }
🌠头插头删尾插尾删
💤添加元素
首先需要断言防止顺序表为空。这里需要注意空间是否满了。这里的实现和在pos位置插入x有类似，等我们实现这个函数，就可以直接调用这个函数，更加简便。（在头文件中SeqList.c中）
//添加元素 void SLPushBack(SL* ps, SLDataType x) { //断言 assert(ps); //判断空间是否满了，需要调用函数 SLCheckCapacity(ps); //添加元素 ps->a[ps->size] = x; ps->size++; //在pos位置插入x //SLInsert(ps, ps->size, x); }
💤打印元素
打印元素太简单啦，直接用for循环就行。（在头文件中SeqList.c中）
//打印数组 void SLPrint(SL* ps) { for (int i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n"); }
💤尾删
直接在末尾删除就行，之后这里只要size减减就好了，后面的元素会覆盖。这里的实现和在pos位置插入x有类似，等我们实现这个函数，就可以直接调用这个函数，更加简便。(在头文件中SeqList.c中）
//尾删 void SLPopBack(SL* ps) { //断言 assert(ps); // 温柔的检查 //if (ps->size == 0) //return; // 暴力的检查 assert(ps->size > 0); //ps->a[ps->size - 1] = 0; //这里只要size减减就好了，后面的元素会覆盖 ps->size--; //删除pos位置的值 //SLErase(ps, ps->size - 1); }
💤头插（重点）
这里需要注意要让ps->size加加，这里的实现和在pos位置插入x有类似，等我们实现这个函数，就可以直接调用这个函数，更加简便。(在头文件中SeqList.c中）
//头插 void SLPushFront(SL* ps, SLDataType x) { //断言 assert(ps); //定义最后一个元素 int end = ps->size - 1; //循环 while (end >= 0) { ps->a[end + 1] = ps->a[end]; end--; } //x赋给最前的数字 ps->a[0] = x; //指向下一个数字 ps->size++; //在pos位置插入x //SLInsert(ps, 0, x); }
💤头删（重点）
这里需要注意要让ps->size减减，这里的实现和删除pos位置的值相似，等我们实现这个函数，就可以直接调用这个函数，更加简便。(在头文件中SeqList.c中）
//头删 void SLPopFront(SL* ps) { //断言 assert(ps); //断言(指向不能为零) assert(ps); //指向头前面的那个数字 int begin = 1; //循环 while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; //删除pos位置的值 //SLErase(ps, 0); }
🌠增删查改
💤在pos位置插入x
首先这里需要判断pos是否在数组空间内，其次判断空间是否充足，然后循环，最后ps->size++
这里的插入本质和头插相似。（元素向后移动一格）
//在pos位置插入x void SLInsert(SL* ps, int pos, SLDataType x) { //断言，这里pos assert(ps); assert(pos >= 0 && pos < ps->size); //内存不够需要括容 SLCheckCapacity(ps); int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[pos] = x; ps->size++; }
💤删除pos位置的值
首先这里需要判断pos是否在数组空间内，其次判断空间是否充足，然后循环，最后ps->size--
这里的删除本质和头删相似。（元素向前移动一格）
//删除pos位置的值 void SLErase(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--; }
💤修改pos位置的信息
这个实现太简单啦。
//修改pos位置的信息 void SLModify(SL* ps, int pos, SLDataType x) { //断言 assert(ps); //判断pos assert(pos >= 0 && pos < ps->size); //直接换 ps->a[pos] = x; }
🌠主函数
int main() { //定义结构体 SL sl; //初始动态列表 SLInit(&sl); //释放内存 SLDestroy(&sl); return 0; }
🌙代码总结
🌠主函数
//主函数（包含头文件） #include"SeqList.h" //尾删 void TestSeqList1() { //定义结构体 SL sl; //初始化 SLInit(&sl); //添加元素 SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPushBack(&sl, 6); SLPushBack(&sl, 6); SLPushBack(&sl, 0); SLPushBack(&sl, 0); //打印元素 SLPrint(&sl); //尾删 SLPopBack(&sl); SLPopBack(&sl); //打印元素 SLPrint(&sl); //尾删 SLPopBack(&sl); SLPopBack(&sl); SLPopBack(&sl); SLPopBack(&sl); SLPopBack(&sl); SLPopBack(&sl); SLPopBack(&sl); //打印元素 SLPrint(&sl); //添加元素 SLPushBack(&sl, 1); SLPushBack(&sl, 2); //打印元素 SLPrint(&sl); //释放内存 SLDestroy(&sl); } //头删 void TestSeqList2() { //定义结构体 SL sl; //初始动态列表 SLInit(&sl); //添加元素 SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLPushBack(&sl, 5); //打印元素 SLPrint(&sl); //头插 SLPushFront(&sl, 10); SLPushFront(&sl, 20); SLPushFront(&sl, 30); SLPushFront(&sl, 40); //头删 SLPopFront(&sl); SLPopFront(&sl); SLPopFront(&sl); //打印元素 SLPrint(&sl); //释放内存 SLDestroy(&sl); } //在pos位置插入x void TestSeqList3() { //定义结构体 SL sl; //初始动态列表 SLInit(&sl); //添加元素 SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLPushBack(&sl, 5); //打印元素 SLPrint(&sl); //在pos位置插入x int input = 0; printf("请输入插入的位置："); scanf("%d", &input); int number = 0; printf("请输入插入的数字："); scanf("%d", &number); SLInsert(&sl, input, number); //打印元素 SLPrint(&sl); //释放内存 SLDestroy(&sl); } //删除pos位置的值 void TestSeqList4() { //定义结构体 SL sl; //初始动态列表 SLInit(&sl); //添加元素 SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLPushBack(&sl, 5); //打印元素 SLPrint(&sl); //删除pos位置的值 int input = 0; printf("请输入删除的位置："); scanf("%d", &input); SLErase(&sl, input); //打印元素 SLPrint(&sl); //释放内存 SLDestroy(&sl); } //删除pos位置的值 void TestSeqList5() { //定义结构体 SL sl; //初始动态列表 SLInit(&sl); //添加元素 SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLPushBack(&sl, 5); //打印元素 SLPrint(&sl); //修改pos位置的信息 int input = 0; printf("请输入需要修改的位置："); scanf("%d", &input); int number = 0; printf("请输入需要修改的数字："); scanf("%d", &number); SLModify(&sl, input, number); //打印元素 SLPrint(&sl); //释放内存 SLDestroy(&sl); } int main() { //TestSeqList1(); //TestSeqList2(); //TestSeqList3(); //TestSeqList4(); TestSeqList5(); return 0; }
🌠SeqList.h头文件
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //动态顺序表 typedef int SLDataType; typedef struct SeqList { //定义一个可变数组 SLDataType* a; //定义数组初始长度 int size; //定义空间大小 int capacity; }SL; //动态管理 //初始化动态顺序表 void SLInit(SL* ps); //释放内存 void SLDestroy(SL* ps); //打印数组 void SLPrint(SL* ps); //扩容空间 void SLCheckCapacity(SL* ps); // 头插头删 尾插尾删 void SLPushBack(SL* ps, SLDataType x);//添加元素 void SLPopBack(SL* ps);//尾删 void SLPushFront(SL* ps, SLDataType x);//头插元素 void SLPopFront(SL* ps);//头删 //返回下标，没有找打返回-1 int SLFind(SL* ps, SLDataType x); //在pos位置插入x void SLInsert(SL* ps, int pos, SLDataType x); //删除pos位置的值 void SLErase(SL* ps, int pos); //修改pos位置的信息 void SLModify(SL* ps, int pos, SLDataType x);
🌠SeqList.c源文件
#include"SeqList.h" //初始化动态顺序表 void SLInit(SL* ps) { //开辟空间 ps->a = (SLDataType*)malloc(sizeof(SLDataType*) * 4); //判断空间是否为空 if (ps->a == NULL) { perror("malloc failed"); exit(-1); } //初始化 ps->size = 0; ps->capacity = 4; } //释放内存 void SLDestroy(SL* ps) { //断言 assert(ps); free(ps->a); ps->a = NULL; ps->size = 0; ps->capacity = 0; } //打印数组 void SLPrint(SL* ps) { for (int i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n"); } //扩容空间 void SLCheckCapacity(SL* ps) { //如果size和capacity相同 if (ps->size == ps->capacity) { //扩大两倍 SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(SLDataType)); //判断tmp是否为空 if (tmp == NULL) { perror("realloc failed"); exit(-1); } //赋值 ps->a = tmp; ps->capacity = ps->capacity * 2; } } //添加元素 void SLPushBack(SL* ps, SLDataType x) { //断言 assert(ps); /*//判断空间是否满了，需要调用函数 SLCheckCapacity(ps); //添加元素 ps->a[ps->size] = x; ps->size++;*/ //在pos位置插入x SLInsert(ps, ps->size, x); } //尾删 void SLPopBack(SL* ps) { //断言 assert(ps); /*// 温柔的检查 //if (ps->size == 0) //return; // 暴力的检查 assert(ps->size > 0); //ps->a[ps->size - 1] = 0; //这里只要size减减就好了，后面的会覆盖 ps->size--;*/ //删除pos位置的值 SLErase(ps, ps->size - 1); } //头插 void SLPushFront(SL* ps, SLDataType x) { //断言 assert(ps); /*//定义最后一个元素 int end = ps->size - 1; //循环 while (end >= 0) { ps->a[end + 1] = ps->a[end]; end--; } //x赋给最前的数字 ps->a[0] = x; //指向下一个数字 ps->size++;*/ //在pos位置插入x SLInsert(ps, 0, x); } //头删 void SLPopFront(SL* ps) { //断言 assert(ps); /*//断言(指向不能为零) assert(ps); //指向头前面的那个数字 int begin = 1; //循环 while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--;*/ //删除pos位置的值 SLErase(ps, 0); } //返回下标，没有找打返回-1 int SLFind(SL* ps, SLDataType x) { //断言 assert(ps); //遍历 for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { return i; } } return -1; } //在pos位置插入x void SLInsert(SL* ps, int pos, SLDataType x) { //断言，这里pos assert(ps); assert(pos >= 0 && pos < ps->size); //内存不够需要括容 SLCheckCapacity(ps); int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[pos] = x; ps->size++; } //删除pos位置的值 void SLErase(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--; } //修改pos位置的信息 void SLModify(SL* ps, int pos, SLDataType x) { //断言 assert(ps); //判断pos assert(pos >= 0 && pos < ps->size); //直接换 ps->a[pos] = x; }
🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小说手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
