「 每日一句 · Daily Quote 」“我这个人走得很慢但是我从不后退。”— 亚伯拉罕·林肯文章目录前言一、线性表二、顺序表2.1 概念与结构2.2 分类2.2.1 静态顺序表2.2.2 动态顺序表三、动态顺序表的实现3.1 定义动态顺序表的结构3.2 初始化顺序表3.3 检查空间容量是否足够3.4 打印顺序表3.5 销毁顺序表3.6 尾插3.7 头插3.8 尾删3.9 头删3.10 在指定位置之前插入数据3.11 删除pos位置的数据3.12 查找总结前言数据结构是程序员的必修内功而顺序表是最基础、最常用的线性结构之一。本文将从线性表的概念入手介绍顺序表的定义及其与数组的区别对比静态与动态顺序表的优劣重点讲解动态顺序表的完整实现包括初始化、扩容、头尾插入删除、指定位置插入删除、查找等核心接口并逐段分析代码逻辑。掌握顺序表是学习链表、栈、队列等复杂数据结构的第一步。一、线性表线性表linear list是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串…线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不⼀定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。二、顺序表2.1 概念与结构概念顺序表是用⼀段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。顺序表和数组的区别顺序表的底层结构是数组对数组的封装实现了常用的增删改查等接口打个比方数组相当于未经雕琢的“基础食材/菜品”仅提供最底层的连续物理存储能力;而顺序表则是以此为核心原料进行高级封装后的“完整料理”其底层结构依然是原生数组却拥有增、删、改、查等一系列标准数据结构接口2.2 分类2.2.1 静态顺序表概念使用定长数组存储元素静态顺序表缺陷空间给少了不够用给多了造成空间浪费2.2.2 动态顺序表三、动态顺序表的实现3.1 定义动态顺序表的结构typedefintSLDataType;typedefstructSeqList{SLDataType*arr;intsize;//有效数据个数intcapacity;//空间容量}SL;typedef int SLDataType对类型重命名: 方便未来需要储存其他新的类型变量typedef struct SeqList { ... } SL;结构体定义与别名: 提升书写效率SLDataType* arr首元素地址size有效数据个数: 记录当前顺序表中实际已存入的元素数量capacity物理容量上限: 指该顺序表最大能储存的元素个数3.2 初始化顺序表//初始化voidSLInit(SL*ps){ps-arrNULL;ps-sizeps-capacity0;}让arr置为空,size,capacity置为03.3 检查空间容量是否足够voidCheckcapacity(SL*ps){assert(ps);if(ps-sizeps-capacity){//检查空间容量是否为0intnewcapcity(ps-capacity0)?4:ps-capacity*2;//扩容//realloc第二个参数,单位是字节SLDataType*tmp(SLDataType*)realloc(ps-arr,newcapcity*sizeof(SLDataType));//扩容失败if(tmpNULL){perror(realloc fail);exit(1);}//扩容成功ps-arrtmp;ps-capacitynewcapcity;}}如果size capacity,说明容量已经满了,需要扩容检查空间容量是否为0,如果空间容量为0,则默认赋4个元素空间;如果空间容量不为0, 则按 2 倍增长用realloc进行扩容,并用临时变量tmp接收判断扩容是否成功,若扩容成功,则更新结构体元数据3.4 打印顺序表//打印voidSLPrint(SL*ps){assert(ps);for(inti0;ips-size;i){printf(%d ,ps-arr[i]);}printf(\n);}用for循环遍历所有元素并打印换行3.5 销毁顺序表//销毁voidSLDestroy(SL*ps){assert(ps);ps-capacityps-size0;free(ps-arr);ps-arrNULL;}令capacity和size都为0free掉之前通过realloc申请的内存将arr指针置空,规避野指针3.6 尾插//尾插voidSLPushBack(SL*ps,SLDataType x){assert(ps);Checkcapacity(ps);ps-arr[ps-size]x;}先checkcapacity检查一下空间容量是否足够有效元素自增1,并且将数据写入3.7 头插//头插voidSLPushFront(SL*ps,SLDataType x){assert(ps);Checkcapacity(ps);for(intips-size;i0;i--){ps-arr[i]ps-arr[i-1];}ps-arr[0]x;//增加size数量ps-size;}先用Checkcapcity检查空间容量是否足够利用for循环将每个元素向后移动1位将首位元素写入并将有效元素个数加13.8 尾删//尾删voidSLPopBack(SL*ps){//检查ps和size都不为空assert(psps-size);Checkcapacity(ps);ps-size--;}确保ps和size都不为空将有效元素个数减13.9 头删//头删voidSLPopFront(SL*ps){//检查assert(psps-size);for(inti0;ips-size-1;i){ps-arr[i]ps-arr[i1];}ps-size--;}先用Checkcapacity检查空间容量是否充足将每个元素复制到前一个元素位置将有效元素个数减13.10 在指定位置之前插入数据voidSLInsert(SL*ps,intpos,SLDataType x){assert(pspos0posps-size);//检查空间是否足够Checkcapacity(ps);for(intips-size;ipos;i--){ps-arr[i]ps-arr[i-1];}ps-arr[pos]x;ps-size;}检查空间容量是否足够将下标区间[pos, size - 1]内的元素整体向后移动一位。将目标值 x 写入pos位置有效元素个数加13.11 删除pos位置的数据//删除pos位置的数据voidSLErase(SL*ps,intpos){assert(pspos0posps-size);for(intipos;ips-size-1;i){ps-arr[i]ps-arr[i1];}ps-size--;}将下标区间[pos, size - 1]内的元素整体向前移动一位。有效元素个数减13.12 查找//查找intSLFind(SL*ps,SLDataType x){assert(ps);for(inti0;ips-size;i){//找到了if(ps-arr[i]x)returni;}//没找到return-1;}将所有元素遍历一遍,寻找目标元素找到目标元素,返回该元素下标没找到该元素,返回-1总结以上就是本篇博客的核心内容。本文介绍了线性表的概念与分类重点讲解了顺序表的定义及其两种实现方式静态与动态顺序表详细实现了动态顺序表的常用接口初始化、扩容、头尾插入删除、指定位置插入删除、查找、打印与销毁并分析了各接口的代码逻辑与注意事项。掌握顺序表就为后续学习链表、栈、队列等数据结构打下了坚实基础。