【数据结构手札】顺序表实战指南（五）：查找 | 任意位置增删

🌈个人主页：聆风吟
🔥系列专栏：数据结构手札
🔖少年有梦不应止于心动，更要付诸行动。

📚专栏订阅推荐

📋前言 - 顺序表文章合集

-【顺序表（一）：线性表定义 | 顺序表定义】

-【顺序表（二）：初始化 | 打印 | 销毁】

-【顺序表（三）：扩容 | 尾插 | 尾删】

-【顺序表（四）：头插 | 头删】

-【顺序表（五）：查找 | 任意位置增删】

后续文章会陆续补充，尽情期待…

一. ⛳️顺序表：重点回顾

1.1 🔔顺序表的定义

顺序表（Sequential List）：用一段物理地址连续的存储单元依次存储数据元素的线性结构。一般情况下采用数组存储。在数组上完成数据的增删查改。

1.2 🔔顺序表的分类

顺序表一般可以分为：静态顺序表和动态顺序表。

1.2.1 👻静态顺序表

静态顺序表：指存储空间是固定的并且在程序运行前就已经确定大小的顺序表。它通常使用数组来实现，即通过定义一个固定长度的数组来存储数据元素。

静态顺序表的结构定义：

//静态顺序表结构定义#defineMAXSIZE7//存储单元初始分配量typedefintSLDataType;//类型重命名，便于统一修改元素类型typedefstructSeqList{SLDataType data[MAXSIZE];//定长数组intsize;//当前有效数据的个数}SeqList;

我们可以发现描述静态顺序表需要三个属性：

• 存储空间的起始位置：数组data，他的存储位置就是存储空间的存储位置；
• 线性表的最大存储容量：数组长MAXSIZE；
• 线性表的当前位置：size。

1.2.2 👻动态顺序表

动态顺序表：通过动态分配内存空间，实现随着数据量的增加而不断扩容的效果。它的结构类似于一个数组，数据元素的存储是连续的，支持随机访问和顺序访问。

动态顺序表的结构定义：

//动态顺序表结构定义typedefintSLDataType;//类型重命名，便于统一修改元素类型typedefstructSeqList{SLDataType*a;//指向动态开辟的数组intsize;//当前有效数据的个数intcapacity;//当前分配的总容量}SL;

我们可以发现描述动态顺序表也需要三个属性：

• 存储空间的起始位置：指针a，他里面存储的地址就是存储空间的地址；
• 线性表当前最大存储容量：capacity，可以通过动态分配的方式进行扩容；
• 线性表的当前位置：size。

二. ⛳️顺序表的基本操作实现

通过前面的学习，我们已掌握动态顺序表的初始化、打印、销毁等基础操作，以及尾插 / 尾删、头插 / 头删等针对性插入删除操作。本文将讲解顺序表更通用的操作：查找某个值的下标、在下标为 pos 位置插入 x、删除下标为 pos 位置的数据，实现任意位置的精准操作。

2.1 🔔查找某个值的下标

查找某个值的下标是顺序表的基础查询操作，核心逻辑是遍历顺序表的所有有效元素，逐一比对元素值与目标值，找到匹配项时返回其下标；若遍历结束仍未找到，则返回约定的 “无效标识”（如 - 1）。该操作为后续 “指定位置插入 / 删除” 的前置基础 —— 只有先找到目标元素的位置，才能精准执行插入或删除操作。

//查找某个值的下标,没找到返回-1intSLFind(SL*ps,SLDataType x){//检查顺序表指针有效性assert(ps);//遍历所有有效元素for(inti=0;i<ps->size;i++){//找到匹配值，立即返回对应下标if(ps->a[i]==x)returni;}//遍历结束未找到，返回-1（或无效下标标识）return-1;}

时间复杂度：

查找操作需遍历顺序表的有效元素，最坏情况下（目标值不存在或在最后一个位置）需遍历n个元素（n为有效元素个数），因此时间复杂度为O(n)。

2.2 🔔在下标为pos位置插入x

在下标为pos的位置插入元素x是顺序表插入操作的通用形式（头插是pos=0的特例，尾插是pos=size的特例）。核心逻辑是：先校验插入位置的合法性，再确保容量充足，接着将pos位置及之后的所有元素向后挪动一位，为新元素x腾出pos位置，最后完成插入并更新有效元素个数。整体思路图解：

//在下标为pos的位置插入xvoidSLInsert(SL*ps,intpos,SLDataType x){//检查顺序表指针有效性assert(ps);//检查pos是否在有效范围内assert(pos>=0&&pos<=ps->size);//检查是否需要扩容，保证有空间存放新元素SLCheckCapacity(ps);//挪动数据：从最后一个有效元素开始，到pos位置结束intend=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,intpos){//检查顺序表指针有效性assert(ps);//检查pos是否在有效范围内：0 ≤ pos < size（仅允许删除有效元素）assert(pos>=0&&pos<ps->size);//挪动元素向前覆盖：从pos+1位置开始，到最后一个元素结束intbegin=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>//动态顺序表#defineSLCAPACITY4typedefintSLDataType;typedefstructSeqList{SLDataType*a;//指向动态开辟的数组intsize;//有效数据的个数intcapacity;//记录容量的空间大小}SL;//******************** 本文最新学习内容 ********************//查找某个值的下标,没找到返回-1intSLFind(SL*ps,SLDataType x);//在pos位置插入xvoidSLInsert(SL*ps,intpos,SLDataType x);//删除pos位置的数据voidSLErase(SL*ps,intpos);//******************** 前面已学习内容：可能会调用 ********************//初始化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(inti=0;i<ps->size;i++){//找到匹配值，立即返回对应下标if(ps->a[i]==x)returni;}//遍历结束未找到，返回-1（或无效下标标识）return-1;}//在下标为pos的位置插入xvoidSLInsert(SL*ps,intpos,SLDataType x){//检查顺序表指针有效性assert(ps);//检查pos是否在有效范围内assert(pos>=0&&pos<=ps->size);//检查是否需要扩容，保证有空间存放新元素SLCheckCapacity(ps);//挪动数据：从最后一个有效元素开始，到pos位置结束intend=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,intpos){//检查顺序表指针有效性assert(ps);//检查pos是否在有效范围内：0 ≤ pos < size（仅允许删除有效元素）assert(pos>=0&&pos<ps->size);//挪动元素向前覆盖：从pos+1位置开始，到最后一个元素结束intbegin=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(inti=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：查找某个值的下标intfindPos=SLFind(&sl,30);printf("查找值30的下标：%d\n",findPos);//输出：2intfindPosNone=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 位置的数据三大基础操作。通过这些操作，我们可实现顺序表的精准查询与任意位置的增删，进一步完善了顺序表的核心功能。

今天的干货分享到这里就结束啦！如果觉得文章还可以的话，希望能给个三连支持一下，聆风吟的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的最大动力！