【数据结构手札】顺序表实战指南（五）：查找 | 任意位置增删
🌈个人主页：聆风吟
🔥系列专栏：数据结构手札
🔖少年有梦不应止于心动，更要付诸行动。
文章目录
📚专栏订阅推荐
| 专栏名称 | 专栏简介 |
|---|---|
| C++藏宝阁 | 本专栏聚焦学习阶段核心知识点，深耕基础与实战，干货笔记持续更新，和大家共学共进，夯实编程功底。 |
| 数据结构手札 | 本专栏主要是我的数据结构入门学习手札，记录个人从基础到进阶的学习总结。 |
| 数据结构手札・刷题篇 | 本专栏是《数据结构手札》配套习题讲解，通过练习相关题目加深对算法理解。 |
📋前言 - 顺序表文章合集
一. ⛳️顺序表：重点回顾
1.1 🔔顺序表的定义
顺序表（Sequential List）：用一段物理地址连续的存储单元依次存储数据元素的线性结构。一般情况下采用数组存储。在数组上完成数据的增删查改。
1.2 🔔顺序表的分类
顺序表一般可以分为：静态顺序表和动态顺序表。
1.2.1 👻静态顺序表
静态顺序表：指存储空间是固定的并且在程序运行前就已经确定大小的顺序表。它通常使用数组来实现，即通过定义一个固定长度的数组来存储数据元素。
静态顺序表的结构定义：
//静态顺序表结构定义#defineMAXSIZE7//存储单元初始分配量typedefint SLDataType;//类型重命名，便于统一修改元素类型typedefstructSeqList{ SLDataType data[MAXSIZE];//定长数组int size;//当前有效数据的个数}SeqList;我们可以发现描述静态顺序表需要三个属性：
- 存储空间的起始位置：数组
data，他的存储位置就是存储空间的存储位置； - 线性表的最大存储容量：数组长
MAXSIZE； - 线性表的当前位置：
size。
1.2.2 👻动态顺序表
动态顺序表：通过动态分配内存空间，实现随着数据量的增加而不断扩容的效果。它的结构类似于一个数组，数据元素的存储是连续的，支持随机访问和顺序访问。
动态顺序表的结构定义：
//动态顺序表结构定义typedefint SLDataType;//类型重命名，便于统一修改元素类型typedefstructSeqList{ SLDataType* a;//指向动态开辟的数组int size;//当前有效数据的个数int capacity;//当前分配的总容量}SL;我们可以发现描述动态顺序表也需要三个属性：
- 存储空间的起始位置：指针
a，他里面存储的地址就是存储空间的地址； - 线性表当前最大存储容量：
capacity，可以通过动态分配的方式进行扩容； - 线性表的当前位置：
size。
二. ⛳️顺序表的基本操作实现
通过前面的学习，我们已掌握动态顺序表的初始化、打印、销毁等基础操作，以及尾插 / 尾删、头插 / 头删等针对性插入删除操作。本文将讲解顺序表更通用的操作：查找某个值的下标、在下标为 pos 位置插入 x、删除下标为 pos 位置的数据，实现任意位置的精准操作。
2.1 🔔查找某个值的下标
查找某个值的下标是顺序表的基础查询操作，核心逻辑是遍历顺序表的所有有效元素，逐一比对元素值与目标值，找到匹配项时返回其下标；若遍历结束仍未找到，则返回约定的 “无效标识”（如 - 1）。该操作为后续 “指定位置插入 / 删除” 的前置基础 —— 只有先找到目标元素的位置，才能精准执行插入或删除操作。
//查找某个值的下标,没找到返回-1intSLFind(SL* ps, SLDataType x){//检查顺序表指针有效性assert(ps);//遍历所有有效元素for(int i =0; i < ps->size; i++){//找到匹配值，立即返回对应下标if(ps->a[i]== x)return i;}//遍历结束未找到，返回-1（或无效下标标识）return-1;}时间复杂度：
查找操作需遍历顺序表的有效元素，最坏情况下（目标值不存在或在最后一个位置）需遍历n个元素（n为有效元素个数），因此时间复杂度为O(n)。
2.2 🔔在下标为pos位置插入x
在下标为pos的位置插入元素 x是顺序表插入操作的通用形式（头插是pos=0的特例，尾插是pos=size的特例）。核心逻辑是：先校验插入位置的合法性，再确保容量充足，接着将pos位置及之后的所有元素向后挪动一位，为新元素x腾出pos位置，最后完成插入并更新有效元素个数。整体思路图解：
//在下标为pos的位置插入xvoidSLInsert(SL* ps,int pos, SLDataType x){//检查顺序表指针有效性assert(ps);//检查pos是否在有效范围内assert(pos >=0&& pos <= ps->size);//检查是否需要扩容，保证有空间存放新元素SLCheckCapacity(ps);//挪动数据：从最后一个有效元素开始，到pos位置结束int end = ps->size -1;while(end >= pos){//当前元素向后挪一位 ps->a[end +1]= ps->a[end];//向前移动，处理前一个元素--end;}//插入元素：pos位置已空闲，直接赋值 ps->a[pos]= x;//更新有效元素个数 ps->size++;}时间复杂度：
pos位置插入的时间复杂度取决于需要挪动的元素个数：最优情况：pos=size（尾插），无需挪动元素，时间复杂度O(1)；最坏情况：pos=0（头插），需挪动所有n个元素，时间复杂度O(n)；大 O 阶推导中取最坏情况，因此整体时间复杂度为O(n)（n为有效元素个数）。
2.3 🔔删除下标为pos位置的数据
删除下标为pos位置的数据是顺序表删除操作的通用形式（头删是pos=0的特例，尾删可看作pos=size-1的特例）。核心逻辑是：先校验删除位置的合法性，再将pos+1位置到最后一个有效元素的所有元素向前挪动一位，覆盖被删除的pos位置元素，最后通过size--完成逻辑删除。整体思路图解：
//删除下标为pos位置的数据voidSLErase(SL* ps,int pos){//检查顺序表指针有效性assert(ps);//检查pos是否在有效范围内：0 ≤ pos < size（仅允许删除有效元素）assert(pos >=0&& pos < ps->size);//挪动元素向前覆盖：从pos+1位置开始，到最后一个元素结束int begin = pos +1;while(begin < ps->size){//当前元素向前挪一位，覆盖被删除位置 ps->a[begin -1]= ps->a[begin];//向后移动，处理下一个元素++begin;} ps->size--;//更新有效元素个数}时间复杂度：
pos 位置删除的时间复杂度取决于需要挪动的元素个数：最优情况：pos=size-1（尾删），无需挪动元素，时间复杂度O(1)；最坏情况：pos=0（头删），需挪动所有n-1个元素，时间复杂度O(n)；大 O 阶推导中取最坏情况，因此整体时间复杂度为O(n)（n为有效元素个数）。
三. ⛳️顺序表的源代码
3.1 🔔SeqList.h 顺序表的函数声明
#include<stdio.h>#include<stdlib.h>#include<assert.h>//动态顺序表#defineSLCAPACITY4typedefint SLDataType;typedefstructSeqList{ SLDataType* a;//指向动态开辟的数组int size;//有效数据的个数int capacity;//记录容量的空间大小}SL;//******************** 本文最新学习内容 ********************//查找某个值的下标,没找到返回-1intSLFind(SL* ps, SLDataType x);//在pos位置插入xvoidSLInsert(SL* ps,int pos, SLDataType x);//删除pos位置的数据voidSLErase(SL* ps,int pos);//******************** 前面已学习内容：可能会调用 ********************//初始化voidSLInit(SL* ps);//销毁顺序表voidSLDestroy(SL* ps);//打印顺序表voidSLPrint(SL* ps);//检查容量是否够，不够进行扩容voidSLCheckCapacity(SL* ps);//尾插voidSLPushBack(SL* ps, SLDataType x);3.2 🔔SeqList.c 顺序表的函数定义
#include"SeqList.h"//******************** 本文最新学习内容 ********************//查找某个值的下标,没找到返回-1intSLFind(SL* ps, SLDataType x){//检查顺序表指针有效性assert(ps);//遍历所有有效元素for(int i =0; i < ps->size; i++){//找到匹配值，立即返回对应下标if(ps->a[i]== x)return i;}//遍历结束未找到，返回-1（或无效下标标识）return-1;}//在下标为pos的位置插入xvoidSLInsert(SL* ps,int pos, SLDataType x){//检查顺序表指针有效性assert(ps);//检查pos是否在有效范围内assert(pos >=0&& pos <= ps->size);//检查是否需要扩容，保证有空间存放新元素SLCheckCapacity(ps);//挪动数据：从最后一个有效元素开始，到pos位置结束int end = ps->size -1;while(end >= pos){//当前元素向后挪一位 ps->a[end +1]= ps->a[end];//向前移动，处理前一个元素--end;}//插入元素：pos位置已空闲，直接赋值 ps->a[pos]= x;//更新有效元素个数 ps->size++;}//删除下标为pos位置的数据voidSLErase(SL* ps,int pos){//检查顺序表指针有效性assert(ps);//检查pos是否在有效范围内：0 ≤ pos < size（仅允许删除有效元素）assert(pos >=0&& pos < ps->size);//挪动元素向前覆盖：从pos+1位置开始，到最后一个元素结束int begin = pos +1;while(begin < ps->size){//当前元素向前挪一位，覆盖被删除位置 ps->a[begin -1]= ps->a[begin];//向后移动，处理下一个元素++begin;} ps->size--;//更新有效元素个数}//******************** 前面已学习内容：可能会调用 ********************//初始化顺序表voidSLInit(SL* ps){assert(ps);//使用malloc开辟空间 ps->a =(SLDataType*)malloc(sizeof(SLDataType)* SLCAPACITY);//判断空间是否开辟成功if(NULL== ps->a){//打印错误原因（比如 “malloc failed: Out of memory”），方便定位问题；perror("malloc failed");//终止程序并返回非 0 状态码（约定俗成表示程序异常退出），避免后续无效操作。exit(-1);}//初始化顺序表的有效元素个数为 0。 ps->size =0;//记录顺序表当前的最大容量。 ps->capacity = SLCAPACITY;}//销毁顺序表voidSLDestroy(SL* ps){assert(ps);//释放顺序表底层数组占用的动态内存。free(ps->a);//将指针置空，避免 “野指针” 问题。 ps->a =NULL;//重置顺序表的状态变量，让其回归 “初始无效状态”。 ps->size = ps->capacity =0;}//打印顺序表voidSLPrint(SL* ps){assert(ps);for(int i =0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");}//检查容量是否够，不够进行扩容voidSLCheckCapacity(SL* ps){//断言检查指针有效性assert(ps);//判断是否需要扩容if(ps->size == ps->capacity){//使用realloc进行扩容 SLDataType* temp =(SLDataType*)realloc(ps->a,sizeof(SLDataType)*2*(ps->capacity));//检查是否扩容成功if(temp ==NULL){perror("realloc failed");//打印错误原因（如内存不足）exit(-1);//终止程序，避免后续非法操作} ps->a = temp;//更新数组指针 ps->capacity *=2;//更新容量值}}//尾插voidSLPushBack(SL* ps, SLDataType x){//断言检查指针有效性assert(ps);//检查是否需要扩容SLCheckCapacity(ps); ps->a[ps->size]= x;//尾插核心操作：赋值 ps->size++;//更新已用元素个数}3.3 🔔test.c 顺序表功能测试
#include"SeqList.h"intmain(){ SL sl;//初始化顺序表：前面已经讲过，本文不做过多叙述SLInit(&sl);//尾插：前面已经讲过，本文用于添加测试数据，仅为测试本文函数做铺垫SLPushBack(&sl,10);SLPushBack(&sl,20);SLPushBack(&sl,30);SLPushBack(&sl,40);printf("初始顺序表：");//打印顺序表：前面已经讲过，本文不做过多叙述SLPrint(&sl);// 输出：10 20 30 40printf("\n");printf("******************** 测试1：查找某个值的下标 ********************\n");//测试1：查找某个值的下标int findPos =SLFind(&sl,30);printf("查找值30的下标：%d\n", findPos);//输出：2int findPosNone =SLFind(&sl,50);printf("查找值50的下标（不存在）：%d\n", findPosNone);//输出：-1printf("\n");printf("******************** 测试2：在下标pos位置插入x ********************\n");//测试2：在下标pos位置插入xSLInsert(&sl,2,25);//在下标2插入25printf("下标2的位置插入25后：");SLPrint(&sl);//输出：10 20 25 30 40printf("\n");printf("******************** 测试3：删除下标pos位置的数据 ********************\n");//测试3：删除下标pos位置的数据SLErase(&sl,2);//删除下标2的25printf("删除下标为2的数据后：");SLPrint(&sl);//输出：10 20 30 40printf("\n");//销毁顺序表：前面已经讲过，本文不做过多叙述SLDestroy(&sl);return0;}代码运行图：
📝全文总结
本文重点讲解顺序表的查找某个值的下标、在下标为 pos 位置插入 x、删除下标为 pos 位置的数据三大基础操作。通过这些操作，我们可实现顺序表的精准查询与任意位置的增删，进一步完善了顺序表的核心功能。
今天的干货分享到这里就结束啦！如果觉得文章还可以的话，希望能给个三连支持一下，聆风吟的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的最大动力！
