耕耘 :C、C、嵌入式技术领域我的个人主页❄️个人专栏《C语言专栏》 《嵌入式专栏》 《数据结构专栏》✨**不要等待机会而要创造机会**✨博主简介:✨✨一位热爱生活的阳光大男孩.✨✨前言本文系统讲解C语言中顺序表的实现涵盖线性表概念、静态与动态顺序表的区别重点展示动态顺序表的结构设计与核心操作初始化、尾插/头插、尾删/头删、任意位置插入与删除、查找等。通过SeqList.h、SeqList.c和测试文件test.c完整演示了增删改查功能强调内存管理、边界判断与错误处理为数据结构学习提供清晰实践范例。文章目录前言1. 线性表2. 顺序表2.1 概念与结构2.2 分类2.2.1 静态顺序表2.2.2 动态顺序表2.3 动态顺序表的实现2.3.1顺序表代码下载链接2.4 顺序表算法题2.4.1 移除元素2.5 顺序表问题与思考结语1. 线性表线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使 ⽤的数据结构常⻅的线性表顺序表、链表、栈、队列、字符串…线性表在逻辑上是线性结构也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。2. 顺序表2.1 概念与结构概念顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构⼀般情况下采⽤数组存储。那顺序表和数组的区别顺序表的底层结构是数组对数组进行封装实现了常⽤的增删改查等接⼝这就是顺序表。2.2 分类2.2.1 静态顺序表概念使⽤定⻓数组存储元素缺陷空间是定值空间给少了不够⽤给多了造成空间浪费//静态顺序表typedefintSLDataType;//方便后面修改数组类型#defineN7;typedefstructSeqList{SLDataType*a[N];//定常数组intsize;// 有效数据个数}SL;2.2.2 动态顺序表// 动态顺序表 -- 按需申请typedefintSLDataType;//方便后面修改数组类型typedefstructSeqList{SLDataType*a;//可增容intsize;// 有效数据个数intcapacity;//空间容量}SL;2.3 动态顺序表的实现定义一个头文件’‘SeqList.h’’#includestdio.h#includestdlib.h#includeassert.h#includestring.h//定义动态顺序表的结构typedefintSLDatatype;//定义数组类型方便后期修改typedefstructSeqList{SLDatatype*arr;intsize;//有效数据的个数intcapacity;//空间容量}SL;//顺序表初始化voidSLIint(SL*ps);//扩容voidSLCheckCapacity(SL*ps);//打印顺序表voidSLPrint(SL*ps);//尾插voidSLPushBsck(SL*ps,SLDatatype x);//x为数组类型方便修改//头插voidSLPushFront(SL*ps,SLDatatype x);//尾删voidSLPopBack(SL*ps);//头删voidSLPopFront(SL*ps);//指定位置插?voidSLInsert(SL*ps,intpos,SLDatatype x);//指定位置删除voidSLErase(SL*ps,intpos);//查找元素voidSLFind(SL*ps,SLDatatype x);在定义一个函数文件SeqList.c#includeSeqList.h//初始化voidSLIint(SL*ps){ps-arrNULL;ps-sizeps-capacity0;}//扩容voidSLCheckCapacity(SL*ps){//判断空间是否足够if(ps-sizeps-capacity){intnewCapacityps-capacity0?4:2*ps-capacity;//增容一般是成倍数扩容一般是2倍可控//realloc第二个参数单位是字节SLDatatype*tmp(SLDatatype*)realloc(ps-arr,newCapacity*sizeof(SLDatatype));if(tmpNULL){perror(realloc fail!);exit(1);}ps-arrtmp;//扩容后的新数组ps-capacitynewCapacity;//扩容后的大小}}//打印顺序表voidSLPrint(SL*ps){for(inti0;ips-size;i){printf(%d ,ps-arr[i]);}printf(\n);}//尾插voidSLPushBsck(SL*ps,SLDatatype x){//判断空间是否足够SLCheckCapacity(ps);//开始插入ps-arr[ps-size]x;}//头插voidSLPushFront(SL*ps,SLDatatype x){assert(ps!NULL);//防止传空指针//判断空间是否足够SLCheckCapacity(ps);//开始插入//将顺序表中所有数据向后移动一位for(intips-size;i0;i--){ps-arr[i]ps-arr[i-1];//先移动后面的数据}ps-arr[0]x;//把数据放在第一位ps-size;}//尾删voidSLPopBack(SL*ps){assert(psps-size);--ps-size;}//头删voidSLPopFront(SL*ps){assert(psps-size);for(inti0;ips-size-1;i){ps-arr[i]ps-arr[i1];}--ps-size;}//任意位置插入voidSLInsert(SL*ps,intpos,SLDatatype x){assert(ps);assert(pos0posps-size);SLCheckCapacity(ps);//判断空间是否足够//pos后面的数据整体向后移动一位for(intips-size;ipos;i--){ps-arr[i]ps-arr[i-1];}ps-arr[pos]x;//插入数据ps-size;}//指定位置删除voidSLErase(SL*ps,intpos){assert(ps);assert(pos0posps-size);//pos之后整体向前移动一位for(intipos;ips-size-1;i){ps-arr[i]ps-arr[i1];}--ps-size;}//查找元素voidSLFind(SL*ps,SLDatatype x){intn1;for(inti0;ips-size;i){if(ps-arr[i]x){n0;printf(找到了%d\n,ps-arr[i]);}}if(n1){printf(没有找到%d\n,x);}}在定义一个测试文件test.c#includeSeqList.h//初始化应用voidtest01(){SL sl;//建一个空表SLIint(sl);//初始化}//尾插应用voidtest02(){SL sl;//建一个空表SLIint(sl);//初始化SLPushBsck(sl,1);//插入数据SLPushBsck(sl,2);SLPushBsck(sl,3);SLPushBsck(sl,4);SLPrint(sl);//打印}//头插应用voidtest03(){SL sl;//建一个空表SLIint(sl);//初始化SLPushFront(sl,1);//插入数据SLPushFront(sl,2);SLPushFront(sl,3);SLPushFront(sl,4);SLPrint(sl);//打印}//尾删应用voidtest04(){SL sl;//建一个空表SLIint(sl);//初始化SLPushBsck(sl,1);//插入数据SLPushBsck(sl,2);SLPushBsck(sl,3);SLPushBsck(sl,4);SLPrint(sl);//打印SLPopBack(sl);//尾删一次SLPrint(sl);//打印SLPopBack(sl);//尾删两次SLPrint(sl);//打印SLPopBack(sl);//尾删三次SLPrint(sl);//打印}//头删应用voidtest05(){SL sl;//建一个空表SLIint(sl);//初始化SLPushBsck(sl,1);//插入数据SLPushBsck(sl,2);SLPushBsck(sl,3);SLPushBsck(sl,4);SLPrint(sl);//打印SLPopFront(sl);//尾删一次SLPrint(sl);//打印SLPopFront(sl);//尾删两次SLPrint(sl);//打印SLPopFront(sl);//尾删三次SLPrint(sl);//打印}//任意插入的应用voidtest06(){SL sl;//建一个空表SLIint(sl);//初始化SLPushBsck(sl,1);//插入数据SLPushBsck(sl,2);SLPushBsck(sl,3);SLPushBsck(sl,4);SLPrint(sl);//打印//任意插入SLInsert(sl,1,100);//在第二位插入数据100SLPrint(sl);//打印}//任意删除的应用voidtest07(){SL sl;//建一个空表SLIint(sl);//初始化SLPushBsck(sl,1);//插入数据SLPushBsck(sl,2);SLPushBsck(sl,3);SLPushBsck(sl,4);SLPrint(sl);//打印//任意删除SLErase(sl,1);//删除下标为1的元素SLPrint(sl);//打印}//查找元素voidtest08(){SL sl;//建一个空表SLIint(sl);//初始化SLPushBsck(sl,1);//插入数据SLPushBsck(sl,2);SLPushBsck(sl,3);SLPushBsck(sl,4);SLPrint(sl);//打印//查找指定元素SLFind(sl,1);//找元素1SLFind(sl,100);//找元素100}intmain(){//想测试哪个就放开哪个test01();//初始化应用//test02();//尾插应用//test03();//头插入应用//test04();//尾删入应用//test05();//头删入应用//test06();//任意插入应用//test07();//任意插入应用//test08();//查找元素return0;}2.3.1顺序表代码下载链接顺序表链接下载2.4 顺序表算法题2.4.1 移除元素给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。假设 nums 中不等于 val 的元素数量为 k要通过此题您需要执行以下操作更改 nums 数组使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。返回 k。示例 1输入nums [3,2,2,3], val 3输出2, nums [2,2,,]intremoveElement(int*nums,intnumsSize,intval){//定义两个变量intdst0,src0;while(srcnumsSize){//src值和val比较if(nums[src]val){nums[dst]nums[src];dst;}src;}returndst;}2.5 顺序表问题与思考• 中间/头部的插⼊删除时间复杂度为O(N)• 增容需要申请新空间拷⻉数据释放旧空间。会有不⼩的消耗。• 增容⼀般是呈2倍的增⻓势必会有⼀定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插⼊了5个数据后⾯没有数据插⼊了那么就浪费了95个数据空间结语愿你收获满满点赞、收藏、转发三连不断好运常伴完. 数据结构——顺序表细致讲解
耕耘 :C、C、嵌入式技术领域我的个人主页❄️个人专栏《C语言专栏》 《嵌入式专栏》 《数据结构专栏》✨**不要等待机会而要创造机会**✨博主简介:✨✨一位热爱生活的阳光大男孩.✨✨前言本文系统讲解C语言中顺序表的实现涵盖线性表概念、静态与动态顺序表的区别重点展示动态顺序表的结构设计与核心操作初始化、尾插/头插、尾删/头删、任意位置插入与删除、查找等。通过SeqList.h、SeqList.c和测试文件test.c完整演示了增删改查功能强调内存管理、边界判断与错误处理为数据结构学习提供清晰实践范例。文章目录前言1. 线性表2. 顺序表2.1 概念与结构2.2 分类2.2.1 静态顺序表2.2.2 动态顺序表2.3 动态顺序表的实现2.3.1顺序表代码下载链接2.4 顺序表算法题2.4.1 移除元素2.5 顺序表问题与思考结语1. 线性表线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使 ⽤的数据结构常⻅的线性表顺序表、链表、栈、队列、字符串…线性表在逻辑上是线性结构也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。2. 顺序表2.1 概念与结构概念顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构⼀般情况下采⽤数组存储。那顺序表和数组的区别顺序表的底层结构是数组对数组进行封装实现了常⽤的增删改查等接⼝这就是顺序表。2.2 分类2.2.1 静态顺序表概念使⽤定⻓数组存储元素缺陷空间是定值空间给少了不够⽤给多了造成空间浪费//静态顺序表typedefintSLDataType;//方便后面修改数组类型#defineN7;typedefstructSeqList{SLDataType*a[N];//定常数组intsize;// 有效数据个数}SL;2.2.2 动态顺序表// 动态顺序表 -- 按需申请typedefintSLDataType;//方便后面修改数组类型typedefstructSeqList{SLDataType*a;//可增容intsize;// 有效数据个数intcapacity;//空间容量}SL;2.3 动态顺序表的实现定义一个头文件’‘SeqList.h’’#includestdio.h#includestdlib.h#includeassert.h#includestring.h//定义动态顺序表的结构typedefintSLDatatype;//定义数组类型方便后期修改typedefstructSeqList{SLDatatype*arr;intsize;//有效数据的个数intcapacity;//空间容量}SL;//顺序表初始化voidSLIint(SL*ps);//扩容voidSLCheckCapacity(SL*ps);//打印顺序表voidSLPrint(SL*ps);//尾插voidSLPushBsck(SL*ps,SLDatatype x);//x为数组类型方便修改//头插voidSLPushFront(SL*ps,SLDatatype x);//尾删voidSLPopBack(SL*ps);//头删voidSLPopFront(SL*ps);//指定位置插?voidSLInsert(SL*ps,intpos,SLDatatype x);//指定位置删除voidSLErase(SL*ps,intpos);//查找元素voidSLFind(SL*ps,SLDatatype x);在定义一个函数文件SeqList.c#includeSeqList.h//初始化voidSLIint(SL*ps){ps-arrNULL;ps-sizeps-capacity0;}//扩容voidSLCheckCapacity(SL*ps){//判断空间是否足够if(ps-sizeps-capacity){intnewCapacityps-capacity0?4:2*ps-capacity;//增容一般是成倍数扩容一般是2倍可控//realloc第二个参数单位是字节SLDatatype*tmp(SLDatatype*)realloc(ps-arr,newCapacity*sizeof(SLDatatype));if(tmpNULL){perror(realloc fail!);exit(1);}ps-arrtmp;//扩容后的新数组ps-capacitynewCapacity;//扩容后的大小}}//打印顺序表voidSLPrint(SL*ps){for(inti0;ips-size;i){printf(%d ,ps-arr[i]);}printf(\n);}//尾插voidSLPushBsck(SL*ps,SLDatatype x){//判断空间是否足够SLCheckCapacity(ps);//开始插入ps-arr[ps-size]x;}//头插voidSLPushFront(SL*ps,SLDatatype x){assert(ps!NULL);//防止传空指针//判断空间是否足够SLCheckCapacity(ps);//开始插入//将顺序表中所有数据向后移动一位for(intips-size;i0;i--){ps-arr[i]ps-arr[i-1];//先移动后面的数据}ps-arr[0]x;//把数据放在第一位ps-size;}//尾删voidSLPopBack(SL*ps){assert(psps-size);--ps-size;}//头删voidSLPopFront(SL*ps){assert(psps-size);for(inti0;ips-size-1;i){ps-arr[i]ps-arr[i1];}--ps-size;}//任意位置插入voidSLInsert(SL*ps,intpos,SLDatatype x){assert(ps);assert(pos0posps-size);SLCheckCapacity(ps);//判断空间是否足够//pos后面的数据整体向后移动一位for(intips-size;ipos;i--){ps-arr[i]ps-arr[i-1];}ps-arr[pos]x;//插入数据ps-size;}//指定位置删除voidSLErase(SL*ps,intpos){assert(ps);assert(pos0posps-size);//pos之后整体向前移动一位for(intipos;ips-size-1;i){ps-arr[i]ps-arr[i1];}--ps-size;}//查找元素voidSLFind(SL*ps,SLDatatype x){intn1;for(inti0;ips-size;i){if(ps-arr[i]x){n0;printf(找到了%d\n,ps-arr[i]);}}if(n1){printf(没有找到%d\n,x);}}在定义一个测试文件test.c#includeSeqList.h//初始化应用voidtest01(){SL sl;//建一个空表SLIint(sl);//初始化}//尾插应用voidtest02(){SL sl;//建一个空表SLIint(sl);//初始化SLPushBsck(sl,1);//插入数据SLPushBsck(sl,2);SLPushBsck(sl,3);SLPushBsck(sl,4);SLPrint(sl);//打印}//头插应用voidtest03(){SL sl;//建一个空表SLIint(sl);//初始化SLPushFront(sl,1);//插入数据SLPushFront(sl,2);SLPushFront(sl,3);SLPushFront(sl,4);SLPrint(sl);//打印}//尾删应用voidtest04(){SL sl;//建一个空表SLIint(sl);//初始化SLPushBsck(sl,1);//插入数据SLPushBsck(sl,2);SLPushBsck(sl,3);SLPushBsck(sl,4);SLPrint(sl);//打印SLPopBack(sl);//尾删一次SLPrint(sl);//打印SLPopBack(sl);//尾删两次SLPrint(sl);//打印SLPopBack(sl);//尾删三次SLPrint(sl);//打印}//头删应用voidtest05(){SL sl;//建一个空表SLIint(sl);//初始化SLPushBsck(sl,1);//插入数据SLPushBsck(sl,2);SLPushBsck(sl,3);SLPushBsck(sl,4);SLPrint(sl);//打印SLPopFront(sl);//尾删一次SLPrint(sl);//打印SLPopFront(sl);//尾删两次SLPrint(sl);//打印SLPopFront(sl);//尾删三次SLPrint(sl);//打印}//任意插入的应用voidtest06(){SL sl;//建一个空表SLIint(sl);//初始化SLPushBsck(sl,1);//插入数据SLPushBsck(sl,2);SLPushBsck(sl,3);SLPushBsck(sl,4);SLPrint(sl);//打印//任意插入SLInsert(sl,1,100);//在第二位插入数据100SLPrint(sl);//打印}//任意删除的应用voidtest07(){SL sl;//建一个空表SLIint(sl);//初始化SLPushBsck(sl,1);//插入数据SLPushBsck(sl,2);SLPushBsck(sl,3);SLPushBsck(sl,4);SLPrint(sl);//打印//任意删除SLErase(sl,1);//删除下标为1的元素SLPrint(sl);//打印}//查找元素voidtest08(){SL sl;//建一个空表SLIint(sl);//初始化SLPushBsck(sl,1);//插入数据SLPushBsck(sl,2);SLPushBsck(sl,3);SLPushBsck(sl,4);SLPrint(sl);//打印//查找指定元素SLFind(sl,1);//找元素1SLFind(sl,100);//找元素100}intmain(){//想测试哪个就放开哪个test01();//初始化应用//test02();//尾插应用//test03();//头插入应用//test04();//尾删入应用//test05();//头删入应用//test06();//任意插入应用//test07();//任意插入应用//test08();//查找元素return0;}2.3.1顺序表代码下载链接顺序表链接下载2.4 顺序表算法题2.4.1 移除元素给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。假设 nums 中不等于 val 的元素数量为 k要通过此题您需要执行以下操作更改 nums 数组使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。返回 k。示例 1输入nums [3,2,2,3], val 3输出2, nums [2,2,,]intremoveElement(int*nums,intnumsSize,intval){//定义两个变量intdst0,src0;while(srcnumsSize){//src值和val比较if(nums[src]val){nums[dst]nums[src];dst;}src;}returndst;}2.5 顺序表问题与思考• 中间/头部的插⼊删除时间复杂度为O(N)• 增容需要申请新空间拷⻉数据释放旧空间。会有不⼩的消耗。• 增容⼀般是呈2倍的增⻓势必会有⼀定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插⼊了5个数据后⾯没有数据插⼊了那么就浪费了95个数据空间结语愿你收获满满点赞、收藏、转发三连不断好运常伴完. RELATED READING
延伸阅读
更多一线实战笔记与深度复盘，助您持续精进
