个人主页ꪔ小林Y✨个人专栏《C小白闯关日记》《C语言小白闯关日记》《数据结构入门——从原理到实战》代码信条每一行代码都是成长的脚印每一次调试成功都是对坚持的回应目录线性表顺序表一.分类1.静态顺序表2.动态顺序表二.顺序表的初始化三.顺序表的插入操作1.尾插2.头插四.顺序表的删除操作1.尾删2.头删五.查找操作六.指定位置之前插入操作七.删除pos位置的数据八.顺序表的销毁线性表线性表是n个具有相同特性【逻辑结构人为想出来的一定是线性的物理结构不一定是线性的】的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表链表栈队列字符串…线性表在逻辑上是线性结构也就是说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。顺序表顺序表【逻辑结构线性物理结构线性】是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储顺序表的底层是数组顺序表是数组来实现的一.分类1.静态顺序表使用定长数组存储元素2.动态顺序表按需申请二.顺序表的初始化头文件“SeqList.h”#includestdio.h#includestdlib.h//定义动态顺序表的结构typedefintSLTDataType;typedefstructSeqListSL;//给结构体取别名structSeqList{SLTDataType*arr;//存储数据intsize;//有效数据个数intcapacity;//空间大小};voidSLInit(SL*s);实现文件文件“SeqList.c”#includeSeqList.hvoidSLInit(SL*ps){ps-arrNULL;ps-sizeps-capacity0;}测试文件“tset.c”#includeSeqList.hvoidtest01(){SL sl;SLInit(sl);//注意这里传的是一个地址}intmain(){test01();return0;}三.顺序表的插入操作1.尾插1空间足够2空间不够sizecapacity所以这时候就需要增容了3代码头文件“SeqList.h”#includestdio.h#includestdlib.h//定义动态顺序表的结构typedefintSLTDataType;typedefstructSeqListSL;//给结构体取别名structSeqList{SLTDataType*arr;//存储数据intsize;//有效数据个数intcapacity;//空间大小};voidSLInit(SL*s);//尾插voidSLPushBack(SL*ps,SLTDataType x);实现文件文件“SeqList.c”#includeSeqList.hvoidSLInit(SL*ps){ps-arrNULL;ps-sizeps-capacity0;}//尾插操作voidSLPushBack(SL*ps,SLTDataType x){//空间不够if(ps-sizeps-capacity){intnewCapacityps-capacity0?4:2*ps-capacity;//增容SLTDataType*tmp(SLTDataType*)realloc(ps-arr,newCapacity*sizeof(SLTDataType));if(tmpNULL){perror(realloc fail!);exit(1);}ps-arrtmp;ps-capacitynewCapacity;}//空间足够ps-arr[ps-size]x;}测试文件“test.c”#includeSeqList.hvoidtest01(){SL sl;SLInit(sl);SLPushBack(sl,1);SLPushBack(sl,2);SLPushBack(sl,3);SLPushBack(sl,4);SLPushBack(sl,5);}intmain(){test01();return0;}2.头插头文件“SeqList.h”//头插#includestdio.h#includestdlib.h#includeassert.h//定义动态顺序表的结构typedefintSLTDataType;typedefstructSeqListSL;//给结构体取别名structSeqList{SLTDataType*arr;//存储数据intsize;//有效数据个数intcapacity;//空间大小};voidSLInit(SL*s);//头插voidSLPushFront(SL*ps,SLTDataType x);实现文件SeqList.c#includeSeqList.hvoidSLInit(SL*ps){ps-arrNULL;ps-sizeps-capacity0;}//增容voidSLCheckCapacity(SL*ps){if(ps-sizeps-capacity){intnewCapacityps-capacity0?4:2*ps-capacity;//增容SLTDataType*tmp(SLTDataType*)realloc(ps-arr,newCapacity*sizeof(SLTDataType));if(tmpNULL){perror(realloc fail!);exit(1);}ps-arrtmp;ps-capacitynewCapacity;}}//头插voidSLPushFront(SL*ps,SLTDataType x){//防止传参异常/*if (ps NULL) { return; }*///也可以使用断言assert(ps!NULL);//assert(ps);//空间不够//因为头插操作也用到了增容所以我们就可以对增容操作单独写一个函数SLCheckCapacity(ps);//空间足够//数据整体向后挪动一位for(intips-size;i0;i--){ps-arr[i]ps-arr[i-1];}ps-arr[0]x;ps-size;}测试文件test.c#includeSeqList.hvoidtest01(){SL sl;SLInit(sl);SLPushFront(sl,1);SLPushFront(sl,2);//2 1SLPushFront(sl,3);//3 2 1SLPushFront(sl,4);//4 3 2 1}intmain(){test01();return0;}四.顺序表的删除操作1.尾删我们注意删除的时候不能使用free去释放空间因为free释放的是一个连续的空间而我们往往删除的只是一个位置的数据。直接size–就可以了头文件“SeqList.h”#includestdio.h#includestdlib.h#includeassert.htypedefintSLTDataType;typedefstructSeqListSL;structSeqList{SLTDataType*arr;intsize;intcapacity;};voidSLPrint(SL*ps);//打印voidSLInit(SL*s);//尾插voidSLPushBack(SL*ps,SLTDataType x);//尾删voidSLPopBack(SL*ps);实现文件“SeqList.c”#includeSeqList.hvoidSLInit(SL*ps){ps-arrNULL;ps-sizeps-capacity0;}//打印voidSLPrint(SL*ps){for(inti0;ips-size;i){printf(%d ,ps-arr[i]);}printf(\n);}//增容函数voidSLCheckCapacity(SL*ps){if(ps-sizeps-capacity){intnewCapacityps-capacity0?4:2*ps-capacity;//增容SLTDataType*tmp(SLTDataType*)realloc(ps-arr,newCapacity*sizeof(SLTDataType));if(tmpNULL){perror(realloc fail!);exit(1);}ps-arrtmp;ps-capacitynewCapacity;}}//尾插voidSLPushBack(SL*ps,SLTDataType x){//空间不够SLCheckCapacity(ps);//空间足够ps-arr[ps-size]x;}//尾删voidSLPopBack(SL*ps){assert(psps-size);ps-size--;}测试文件“test.c”#includeSeqList.hvoidtest01(){SL sl;SLInit(sl);SLPushBack(sl,1);SLPushBack(sl,2);SLPushBack(sl,3);SLPushBack(sl,4);SLPopBack(sl);SLPrint(sl);SLPopBack(sl);SLPrint(sl);SLPopBack(sl);SLPrint(sl);SLPopBack(sl);SLPrint(sl);SLPopBack(sl);}intmain(){test01();return0;}运行2.头删头文件“SeqList.h”//头删voidSLPopFront(SL*ps);实现文件“SeqList.c”//头删voidSLPopFront(SL*ps){assert(psps-size);//数据整体向前挪动一位for(inti0;ips-size-1;i){ps-arr[i]ps-arr[i1];}ps-size--;}测试文件 “test.c”voidtest01(){SL sl;SLInit(sl);//尾插SLPushBack(sl,1);SLPushBack(sl,2);SLPushBack(sl,3);SLPushBack(sl,4);//头删SLPopFront(sl);SLPrint(sl);SLPopFront(sl);SLPrint(sl);SLPopFront(sl);SLPrint(sl);SLPopFront(sl);SLPrint(sl);}时间复杂度尾插O(1)头插O(n)尾删O(1)头删O(n)五.查找操作头文件“SeqList.h”//查找intSLFind(SL*ps,SLTDataType x);实现文件“SeqList.c”//查找intSLFind(SL*ps,SLTDataType x){assert(ps);for(inti0;ips-size;i){if(ps-arr[i]x){//找到了returni;}}//未找到return-1;}测试文件 “test.c”//测试查找intposSLFind(sl,3);if(pos0){printf(未找到\n);}else{printf(找到了\n);}六.指定位置之前插入操作头文件“SeqList.h”//指定位置之前插入voidSLInsert(SL*ps,intpos,SLTDataType x);实现文件“SeqList.c”//指定位置之前插入voidSLInsert(SL*ps,intpos,SLTDataType 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;}测试文件 “test.c”voidtest01(){SL sl;SLInit(sl);//尾插一些数据SLPushBack(sl,1);SLPushBack(sl,2);SLPushBack(sl,3);SLPushBack(sl,4);SLPrint(sl);//在指定位置之前插入SLInsert(sl,pos,100);SLPrint(sl);}运行时间复杂度O(n)七.删除pos位置的数据头文件“SeqList.h”//删除pos位置的数据voidSLErase(SL*ps,intpos);实现文件“SeqList.c”//删除pos位置的数据voidSLErase(SL*ps,intpos){assert(ps);assert(pos);//pos后面的数据向前挪一位for(intipos;ips-size-1;i){ps-arr[i]ps-arr[i1];}ps-size--;}测试文件 “test.c”#includeSeqList.hvoidtest01(){SL sl;SLInit(sl);SLPushBack(sl,1);SLPushBack(sl,2);SLPushBack(sl,3);SLPushBack(sl,4);SLPrint(sl);intposSLFind(sl,2);//测试删除pos位置的数据SLErase(sl,pos);SLPrint(sl);}运行八.顺序表的销毁头文件“SeqList.h”//销毁voidSLDestroy(SL*ps);实现文件“SeqList.c”//销毁顺序表voidSLDestroy(SL*ps){if(ps-arr)free(ps-arr);ps-arrNULL;ps-sizeps-capacity0;}本期数据结构的内容就结束了。如果文中有表述不准的地方或是你有更清晰的理解思路强烈欢迎在评论区留言交流——技术路上多碰撞才能更快进步觉得内容对你有帮助的话别忘了点赞❤️➕收藏方便后续回顾复习想跟着一起系统学习数据结构的朋友也可以点击关注下一期我们会聚焦更进一步的学习带你从理论走进实操。下期不见不散✌️