【初阶数据结构】序列系统重构：顺序表

Ne0inhk

— 11 min read
【初阶数据结构】序列系统重构：顺序表

文章目录

本篇介绍线性结构中的顺序表，这种连续排序的方式，这在需要频繁访问特定位置元素的应用场景（如矩阵运算、数组查询）中非常高效🚀

1.线性表

线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

2.1 概念及结构

顺序表是线性表的一种存储方式，它是用一组连续的存储单元依次存储线性表的数据元素。简单来说，就像是把线性表中的元素一个挨着一个地放在数组中进行增删查改工作，就像在一排连续的小格子里存放东西一样
请添加图片描述

2.1.1 静态顺序表

typedefint SLDataType;//静态开辟（不推荐）#defineN7typedefstructSeqList{ SLDataType array[N];//指向动态开辟的数组int size;//数据个数}SL;

静态顺序表就是创建一个普通的数组，通常数组的长度大小是固定的，所以这种存储方式是不灵活的，静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用，只适用于确定知道需要存多少数据的场景

2.2.2 动态顺序表

typedefint SLDataType;#defineINIT_CAPACITY4typedefstructSeqList{ SLDataType* a;//指向动态开辟的数组int size;//数据个数int capacity;//空间容量}SL;

动态顺序表是用的最多的顺序表，符合大多数场景下的使用，可以根据场景的需要试试调整数组的大小，比静态数组更加灵活

2.2 接口实现

2.2.1 顺序表打印

voidSLPrint(SL* ps){assert(ps);for(int i =0; i < ps->size;++i){printf("%d ", ps->a[i]);}printf("\n");}

因为要访问ps指针，所以基本功能的实现都要用断言来预防非法访问，顺序表的打印和数组的打印基本思路一致，这里不过多赘述

2.2.2 顺序表初始化

voidSeqInit(SL* ps){assert(ps); ps->a =(SLDataType*)malloc(sizeof(SLDataType)* INIT_CAPACITY);if(ps->a ==NULL){perror("malloc fail");return;} ps->size =0; ps->capacity = INIT_CAPACITY;}

对顺序表初始化，这里有个头文件中的宏定义#define INIT_CAPACITY 4，目的是为了方便修改初始化时的大小，不然每次修改要改多处，定义之后就只需要修改一个地方即可，刚开始capacity也要给一定的容量，而不是0

2.2.3 顺序表销毁

voidSLDestroy(SL* ps){assert(ps);free(ps->a); ps->a =NULL; ps->size = ps->capacity =0;}

这里唯一要注意的点就是，释放完动态数组a之后要记得将指针置为空，不然会导致野指针的出现

2.2.4 顺序表容量检查

voidSLCheckCapacity(SL* ps){assert(ps);if(ps->size == ps->capacity){ SLDataType* tmp =(SLDataType*)realloc(ps->a,sizeof(SLDataType)* ps->capacity *2);if(tmp ==NULL){perror("realloc fail");return;}} ps->capacity *=2;}

size表示的是当前顺序表存储了多少数据，capacity表示的是当前顺序表能够存储多少数据，所以当数据存满了之后就需要进行扩容操作，通常我们每次扩容都只扩容两倍，以免空间的浪费

🔥值得注意的是： realloc开辟的空间大小不是ps->capacity * 2，而是sizeof(SLDataType) * ps->capacity * 2，前者是只考虑了扩大数组元素个数，但是没考虑到每个元素的字节大小，这是需要重点注意的

2.2.5 顺序表尾插

voidSLPushBack(SL* ps, SLDataType x){assert(ps);SLCheckCapacity(ps); ps->a[ps->size++]= x;}//O(n)

尾插就是在顺序表最后面插入数据，先检查容量是否足够插入数据，然后ps->a[ps->size++] = x可以拆分为ps->a[ps->size] = x和ps->size++理解，先将下一个数据加入顺序表，然后修改size大小

尾插只需要把n个数据依次放到末尾，所以时间复杂度为O(n)

2.2.6 顺序表头插

voidSLPushFront(SL* ps, SLDataType x){assert(ps);SLCheckCapacity(ps);int end = ps->size -1;while(end >=0){ ps->a[end +1]= ps->a[end]; end--;} ps->a[0]= x; ps->size++;}//O(n^2)

还是一样，先检查容量是否足够插入数据，然后用覆盖的方式，将前一个数据覆盖到后一个数据上，即整体数据向右移动，也可以使用mommove函数，最后记得修改size大小，然后在开头插入数据

🔥值得注意的是： 头插每次插入n个数据之前都需要挪动数据，因此时间复杂度为O(n²)，所以得出结论尾插的效率是高于头插的

2.2.7 顺序表尾删

voidSLPopBack(SL* ps){assert(ps->size>0); ps->a[ps->size -1]=0; ps->size--;}

最后一个数据的索引为size-1，所以将该位置的数据置为0即可，但又有人有疑问了，需不需要把删除的空间回收了?答案是不需要也没必要，因为通常空间的回收都是整体回收而不是一部分，而且多出来的空间也有可能被使用

🔥值得注意的是： 要考虑顺序表没有数据的情况，如果没有数据了还删除肯定是会造成访问错误的，所以要加断言assert(ps->size> 0)，头删也是如此

2.2.8 顺序表头删

voidSLPopFront(SL* ps){assert(ps);assert(ps->size >0);int begin =1;while(begin < ps->size){ ps->a[begin -1]= ps->a[begin];++begin;} ps->size--;}

先检查容量是否足够插入数据，然后用覆盖的方式，将后一个数据覆盖到前一个数据上，即整体数据向左移动，也可以使用mommove函数，最后记得修改size大小

2.2.9 顺序表在pos位置插入x

voidSLInsert(SL* ps,int pos, SLDataType x){assert(ps);assert(pos <= ps->size && pos >=0);SLCheckCapacity(ps);int end = ps->size -1;while(end >= pos){ ps->a[end +1]= ps->a[end]; end--;} ps->a[pos]= x; ps->size++;}

在pos位置之后将所有数据向左移，然后在pos位置插入数据，注意要断言pos <= ps->size && pos >= 0，避免传入的pos地址是个无效地址

2.2.10 顺序表在pos位置删除x

voidSLErase(SL* ps,int pos, SLDataType x){assert(ps);assert(pos <= ps->size && pos >=0);int begin = pos +1;while(begin < ps->size){ ps->a[begin -1]= ps->a[begin];++begin;} ps->size--;}

定义变量 begin 从要删除元素的下一个位置开始，使用 while 循环将从 pos + 1 位置开始的元素依次向左移动一个位置，覆盖要删除的元素

🔥值得注意的是： 最后一个元素不需要特殊处理。因为顺序表的元素个数是由 size 控制的，当 size 减 1 后，无论原来最后一个元素的值是什么，它都不在有效的元素列表中了，所以不需要对其进行特殊处理，如将其置为某个默认值或进行其他操作

2.2.11 顺序表查找

intSLFind(SL* ps, SLDataType x){assert(ps);for(int i =0; i < ps->size; i++){if(ps->a[i]== x){return i;}}return-1;}

遍历数组，符合则返回索引值，不符合返回-1

3.顺序表的优劣

🚩1. 中间/头部的插入删除，时间复杂度为O(N)

🚩2. 增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗

🚩3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间

4.代码展示

传送门：Gitee顺序表代码

4.1 SeqList.h

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint SLDataType;//静态开辟（不推荐）//#define N 7//typedef struct SeqList//{// SLDataType array[N];//指向动态开辟的数组// int size;//数据个数//}SL;//动态开辟#defineINIT_CAPACITY4typedefstructSeqList{ SLDataType* a;//指向动态开辟的数组int size;//数据个数int capacity;//空间容量}SL;voidSeqInit(SL* s);voidSeqDestory(SL* s);voidSLCheckCapacity(SL* ps);voidSLPushBack(SL* ps, SLDataType x);voidSLPushFront(SL* ps, SLDataType x);voidSLPopBack(SL* ps);voidSLPopFront(SL* ps);voidSLInsert(SL* ps,int pos, SLDataType x);voidSLErase(SL* ps,int pos, SLDataType x);intSLFind(SL* ps, SLDataType x);

4.2 SeqList.c

#define_CRT_SECURE_NO_WARNINGS#include"SeqList.h"//顺序表打印voidSLPrint(SL* ps){assert(ps);for(int i =0; i < ps->size;++i){printf("%d ", ps->a[i]);}printf("\n");}//顺序表初始化voidSeqInit(SL* ps){assert(ps); ps->a =(SLDataType*)malloc(sizeof(SLDataType)* INIT_CAPACITY);if(ps->a ==NULL){perror("malloc fail");return;} ps->size =0; ps->capacity = INIT_CAPACITY;}//顺序表销毁voidSLDestroy(SL* ps){assert(ps);free(ps->a); ps->a =NULL; ps->size = ps->capacity =0;}//检查空间，如果满了，进行增容voidSLCheckCapacity(SL* ps){assert(ps);if(ps->size == ps->capacity){ SLDataType* tmp =(SLDataType*)realloc(ps->a,sizeof(SLDataType)* ps->capacity *2);if(tmp ==NULL){perror("realloc fail");return;}} ps->capacity *=2;}//顺序表尾插voidSLPushBack(SL* ps, SLDataType x){assert(ps);SLCheckCapacity(ps); ps->a[ps->size++]= x;}//O(n)//顺序表头插voidSLPushFront(SL* ps, SLDataType x){assert(ps);SLCheckCapacity(ps);int end = ps->size -1;while(end >=0){ ps->a[end +1]= ps->a[end]; end--;} ps->a[0]= x; ps->size++;}//O(n^2)//顺序表头删voidSLPopFront(SL* ps){assert(ps);assert(ps->size >0);int begin =1;while(begin < ps->size){ ps->a[begin -1]= ps->a[begin];++begin;} ps->size--;}//顺序表尾删voidSLPopBack(SL* ps){assert(ps->size>0); ps->a[ps->size -1]=0; ps->size--;}//顺序表在pos位置插入xvoidSLInsert(SL* ps,int pos, SLDataType x){assert(ps);assert(pos <= ps->size && pos >=0);SLCheckCapacity(ps);int end = ps->size -1;while(end >=0){ ps->a[end +1]= ps->a[end]; end--;} ps->a[pos]= x; ps->size++;}//顺序表删除pos位置的值voidSLErase(SL* ps,int pos, SLDataType x){assert(ps);assert(pos <= ps->size && pos >=0);int begin = pos +1;while(begin < ps->size){ ps->a[begin -1]= ps->a[begin];++begin;} ps->size--;}//顺序表查找intSLFind(SL* ps, SLDataType x){assert(ps);for(int i =0; i < ps->size; i++){if(ps->a[i]== x){return i;}}return-1;}

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！

请添加图片描述

Read more

3DMAX VR渲染器局部渲染设置教程

3DMAX VR渲染器局部渲染设置教程

VR 渲染器局部渲染设置 VR 渲染器的局部渲染功能灵活适配多种场景（尤其全景图），操作步骤如下： 1. 调出渲染设置面板：在 3DMAX 软件中，直接按下快捷键「F10」，快速打开渲染设置窗口（也可通过顶部菜单栏「渲染」→「渲染设置」手动调出）。 2. 确认渲染器类型：在渲染设置面板中，切换到「指定渲染器」选项卡，确保当前选定的渲染器为「V-Ray 渲染器」（若未选中，点击下拉菜单切换即可）。 1. 打开 VR 帧缓冲器：切换到「V-Ray」选项卡，找到「帧缓冲器」设置项，勾选「启用内置帧缓冲器」（部分版本默认开启），点击右侧「显示 VFB」按钮，调出 VR 帧缓冲窗口。 1.

By Ne0inhk
手把手教你用 OpenClaw + 飞书，打造专属 AI 机器人

手把手教你用 OpenClaw + 飞书，打造专属 AI 机器人

手把手教你用 OpenClaw + 飞书，打造专属 AI 机器人 当前版本 OpenClaw（2026.2.22-2）已内置飞书插件，无需额外安装。 你有没有想过，在飞书里直接跟 AI 对话，就像跟同事聊天一样自然？ 今天这篇文章，带你从零开始，用 OpenClaw 搭建一个飞书 AI 机器人。全程命令行操作，10 分钟搞定。 一、准备工作 1.1 安装 Node.js（版本 ≥ 22） OpenClaw 依赖 Node.js 运行，首先确保你的 Node 版本不低于 22。 推荐使用 nvm 管理 Node

By Ne0inhk
本地部署中文OpenClaw 飞书机器人部署指南

本地部署中文OpenClaw 飞书机器人部署指南

适用场景：在 Windows 本地（PowerShell）一键部署 OpenClaw，使用阿里云百炼作为大模型后端，通过飞书长连接模式实现 AI 机器人。 安装skills工具参考：OpenClaw 最新必安装 10 个 Skills-ZEEKLOG博客 自动化发布小红书：OpenClaw 实现小红书自动化发文：操作指南 步骤 1：安装 OpenClaw（openclaw中文社区） 1. 打开 PowerShell。 2. 执行以下命令一键安装： # 在 PowerShell 中运行 iwr -useb https://clawd.org.cn/install.ps1 | iex * 安装过程会自动下载 Node.js、依赖等，耗时几分钟。 * 安装完成后会自动进入配置向导，或提示你继续下一步。

By Ne0inhk
龙虾机器人（OpenClaw）本地部署完全技术指南

龙虾机器人（OpenClaw）本地部署完全技术指南

龙虾机器人（OpenClaw）本地部署完全技术指南 前言：什么是“龙虾机器人”？ 在开始部署之前，我们需要明确部署的对象。通常所说的“龙虾机器人”指的是开源项目 OpenClaw（曾用名：Clawdbot、Moltbot）。它由程序员彼得·斯坦伯格开发，是一个开源的、可本地部署的通用型AI代理系统。与ChatGPT等对话式AI不同，OpenClaw被赋予了操作系统的权限：它可以执行终端命令、读写文件、操控浏览器、安装软件，甚至通过MCP协议调用外部工具。 由于其强大的系统操控能力，安全性是部署时需关注的首要问题。官方及社区普遍建议：不要在主力机或存有敏感数据的生产环境直接裸奔部署，最好使用虚拟机、Docker容器或专用硬件（如Mac Mini或AI开发盒子）进行隔离。 第一章：环境准备与核心依赖 在安装OpenClaw之前，必须准备好运行环境。OpenClaw的核心由TypeScript编写，因此Node.js是必不可少的运行环境。此外，根据安装方式的不同，可能还需要Git、Docker或Python环境。 1.1 硬件建议与系统选择 * Linux

By Ne0inhk