数据结构—顺序表

Ne0inhk

— 10 min read
数据结构—顺序表

数据结构—顺序表

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使用的
数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的， 线性
表在物理上存储时，通常以数组和链式结构的形式存储。

顺序表

概念与结构

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采用数组存储。
顺序表
逻辑结构：线性
物理结构（存储结构：线性

顺序表和数组区别

顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接口

数组 ⊆ 线性表 数组 \subseteq 线性表 数组⊆线性表

分类

静态顺序表

概念：使用定长数组存储元素
在这里插入图片描述
静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费
但是在竞赛中经常用静态申请数组的方式，接下来也会说到

动态顺序表

动态顺序表按需申请，不会造成浪费
在这里插入图片描述

动态顺序表模拟实现

定义动态顺序表结构

·头文件中

//定义动态顺序表的结构typedefint SLTDataType;typedefstructSeqList{ SLTDataType* arr;//存储数据int size;//有效数据个数int capacity;//空间大小}SL;

顺序表初始化

voidSLInit(SL* ps){ ps->arr =NULL; ps->size = ps->capacity =0;}

顺序表销毁

voidSLDestroy(SL* ps){if(ps->arr)//避免重复释放free(ps->arr); ps->arr =NULL; ps->size = ps->capacity =0;}

顺序表打印

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

顺序表动态扩容

voidSLCheckCapacity(SL* ps){if(ps->size == ps->capacity){int newCapacity = ps->capacity ==0?4:2* ps->capacity;//增容 SLTDataType* tmp =(SLTDataType*)realloc(ps->arr, newCapacity *sizeof(SLTDataType));if(tmp ==NULL){perror("realloc fail!");exit(1);} ps->arr = tmp; ps->capacity = newCapacity;}}

尾插

//尾插voidSLPushBack(SL* ps, SLTDataType x){assert(ps);//空间不够SLCheckCapacity(ps);//空间足够 ps->arr[ps->size++]= x;}

头插

//头插voidSLPushFront(SL* ps, SLTDataType x){//温柔的处理方式//if (ps == NULL)//{// return;//}assert(ps !=NULL);//等价于assert(ps）//空间不够SLCheckCapacity(ps);//数据整体向后挪动一位for(int i = ps->size; i >0; i--){ ps->arr[i]= ps->arr[i -1];} ps->arr[0]= x; ps->size++;}

尾删

//尾删voidSLPopBack(SL* ps){assert(ps && ps->size); ps->size--;}

头删

//头删voidSLPopFront(SL* ps){assert(ps && ps->size);//数据整体向前挪动一位for(int i =0; i < ps->size -1; i++){ ps->arr[i]= ps->arr[i +1];} ps->size--;}

查找

//查找intSLFind(SL* ps, SLTDataType x){assert(ps);for(int i =0; i < ps->size; i++){if(ps->arr[i]== x){//找到了return i;}}//未找到return-1;}

指定位置之前插入

//指定位置之前插⼊voidSLInsert(SL* ps,int pos, SLTDataType x){assert(ps);//0<= pos < ps->sizeassert(pos >=0&& pos < ps->size);//判断空间是否足够SLCheckCapacity(ps);//pos及之后数据向后挪动一位for(int i = ps->size; i > pos; i--){ ps->arr[i]= ps->arr[i -1];} ps->arr[pos]= x; ps->size++;}

删除pos位置的数据

//删除pos位置的数据voidSLErase(SL* ps,int pos){assert(ps);//pos:[0，ps->size)assert(pos >=0&& pos < ps->size);//pos后面的数据向前挪动一位for(int i = pos; i < ps->size -1; i++){ ps->arr[i]= ps->arr[i +1];} ps->size--;}

竞赛中的静态顺序表

静态申请数组

1.单个顺序表

//1·单个顺序表#include<iostream> using namespace std;constint N =1e6+10;// 根据实际情况而定// 创建顺序表int a[N];// 用足够大的数组来模拟顺序表int n;// 标记顺序表里面有多少个元素// 打印顺序表voidprint(){for(int i =1; i <= n; i++){ cout << a[i]<<" ";} cout << endl << endl;}//尾插voidpush_back(int x){ a[++n]= x;}// 头插voidpush_front(int x){// 1. 先把 [1, n] 的元素统一向后移动一位for(int i = n; i >=1; i--){ a[i +1]= a[i];}// 2. 把 x 放在表头 a[1]= x; n++;// 元素个数 +1}// 在任意位置插入voidinsert(int p,int x){// 1. 先把 [p, n] 的元素统一向后移动一位for(int i = n; i >= p; i--){ a[i +1]= a[i];} a[p]= x; n++;}// 尾删voidpop_back(){ n--;}// 头删voidpop_front(){// 1. 先把 [2, n] 区间内的所有元素，统一左移一位for(int i =2; i <= n; i++){ a[i -1]= a[i];} n--;}// 任意位置删除voiderase(int p){// 把 [p + 1, n] 的元素，统一左移一位for(int i = p +1; i <= n; i++){ a[i -1]= a[i];} n--;}// 按值查找intfind(int x){for(int i =1; i <= n; i++){if(a[i]== x)return i;}return0;}// 按位查找intat(int p){return a[p];}// 按位修改voidchange(int p,int x){ a[p]= x;}// 清空操作voidclear(){ n =0;}

2.多个顺序表

只需要在传入一个参数：对应的数组（传引用节省空间）
// 1. 需要多个顺序表，才能解决问题int a1[N], n1;int a2[N], n2;int a3[N], n3;//修改上面的代码 例如// 尾插voidpush_back(int a[],int& n,int x){ a[++n]= x;}//测试尾插voidtest(){push_back(a1, n1,1);push_back(a3, n3,2);}

封装静态顺序表

// 使用类或者结构体封装一个静态顺序表 class SqList {int a[N];int n; public:// 构造函数SqList(){ n =0;}// 尾插voidpush_back(int x){ a[++n]= x;}// 尾删voidpop_back(){ n--;}// 打印voidprint(){for(int i =1; i <= n; i++){ cout << a[i]<<" ";} cout << endl;}};intmain(){ SqList s1, s2;// 创建了两个顺序表for(int i =1; i <=5; i++){ s1.push_back(i); s2.push_back(i *2);} s1.print(); s2.print();return0;}//封装 通过调用 各种各样的接口//已经写好的 STL 可以通过 "." 调⽤各种各样的接⼝ 不用再人为重复造轮子//比如 vector 动态顺序表

动态顺序表–vector

如果需要用动态顺序表，有更好的⽅式：C++ 的 STL 提供了⼀个已经封装好的容器 - vector
有的地⽅也叫作可变⻓的数组。vector 的底层就是⼀个会⾃动扩容的顺序表，
其中创建以及增删查改等等的逻辑已经实现好了，并且也完成了封装

创建vector

// 1. 创建 vector 常用的四种方式 vector<int> a1;// 创建了一个名字为 a1 的空的可变长数组，里面都是 int 类型的数据 vector<int>a2(N);// 创建了一个大小为 10 的可变长数组，里面的值默认都是 0 vector<int>a3(N,2);// 创建了一个大小为 10 的可变长数组，里面的值都初始化为 2 vector<int> a4 ={1,2,3,4,5};// 初始化列表的创建方式// <> 里面可以存放任意的数据类型，这就体现了模板的作用，也体现了模板的强大之处// 这样，vector里面就可以存放我们见过的所有的数据类型，甚至是 STL 本身 vector<string> a5;// 存字符串 vector<node> a6;// 存结构体 vector<vector<int>> a7;// 创建了一个二维的可变长数组//vector<array<int, 5>> a8;// 二维数组 代替c风格数组 需要包含头文件arrayint a10[N];// 创建了一个大小为 N 的 int类型数组 数组名叫a10 vector<int> a9[N];// 创建了一个大小为 N 的 vector 数组 数组名叫a9

size / empty

// 2. size / empty//size 返回实际元素的个数print(a2);print(a3);print(a4);//empty 返回顺序表是否为空，返回类型是⼀个 bool 类型的返回值。// 如果为空返回 true，不空返回 falseif(a2.empty()) cout <<"空"<< endl;else cout <<"不空"<< endl;if(a1.empty()) cout <<"空"<< endl;else cout <<"不空"<< endl;

begin / end

begin 返回起始位置的迭代器（左闭) end 返回终点位置的下⼀个位置的迭代器（右开） 利⽤迭代器可以访问整个 vector 存在迭代器的容器就可以使⽤范围 for 遍历 迭代器类型 vector<int>::iterator 用auto 
voidtest_it(){ vector<int>a(10,1);// 迭代器的类型是 vector<int>::iterator，但是⼀般使⽤ auto 简化for(auto it = a.begin(); it != a.end(); it++){ cout <<*it <<" ";} cout << endl << endl;// 使⽤语法糖 - 范围 for 遍历for(auto x : a){ cout << x <<" ";} cout << endl << endl;}

push_back / pop_back

// 4. 尾插以及尾删for(int i =0; i <5; i++){ a1.push_back(i);print(a1);}while(!a1.empty()){ a1.pop_back();print(a1);}

front / back

// 5. front / back// front ：返回⾸元素；// back ：返回尾元素；//cout << a4.front() << " " << a4.back() << endl;voidtest_fb(){ vector<int>a(5);for(int i =0; i <5; i++){ a[i]= i +1;} cout << a.front()<<" "<< a.back()<< endl;}

resize

如果⼤于原始的⼤⼩，多出来的位置会补上默认值，⼀般是 0 。
如果⼩于原始的⼤⼩，相当于把后⾯的元素全部删掉。
// 如果不加引⽤，会拷⻉⼀份，时间开销很⼤voidprint(vector<int>& a){for(auto x : a){ cout << x <<" ";} cout << endl;}// 6. resizevoidtest_resize(){ vector<int>a(5,1); a.resize(10);// 扩⼤print(a); a.resize(3);// 缩⼩print(a);// 扩大成 5，并且多余的修改为 2 a.resize(5,2);print(a);}

clear

清空vector
//底层实现的时候，会遍历整个元素，⼀个⼀个删除，因此时间复杂度 O(N)  cout << a.size()<< endl; a.clear(); cout << a.size()<< endl;

insert / erase

//8.insert/erase 参数为迭代器 a4.insert(a4.begin()+2,0);print(a4); a4.erase(a4.begin()+2);print(a4);return0;}

仓库—代码总结

代码地址

感谢大佬们三连，你的鼓励就是对我创作的激励！！！ \color{purple}{感谢大佬们三连，你的鼓励就是对我创作的激励！！！} 感谢大佬们三连，你的鼓励就是对我创作的激励！！！

在这里插入图片描述

Read more

【Electron架构解析】打破浏览器沙盒：从 Web 前端到桌面客户端的技术跨越

【Electron架构解析】打破浏览器沙盒：从 Web 前端到桌面客户端的技术跨越

在现代企业级应用开发中，纯粹的 B/S（Browser/Server）架构有时难以满足日益复杂的业务需求。当项目交付形态从 Web 链接转变为桌面可执行程序（.exe/.dmg）时，这标志着我们进入了 Electron 的领域。对于习惯了 Chrome 开发者工具的前端工程师而言，理解 Electron 的本质，是完成从“网页开发”到“应用开发”思维转型的关键一步。 本文将深入剖析 Electron 的双进程架构，并以实际工程中的配置文件为例，解读它是如何利用 Web 技术栈突破浏览器安全沙盒的限制。 目录 一、 混合运行时：Chromium 与 Node.js 的深度融合 二、 核心中枢：主进程 (Main Process) 的权限突破 三、 安全桥梁：

By Ne0inhk
电影票房数据采集分析可视化系统 | Python Flask MySQL Echarts Requests爬虫 大数据 人工智能 毕业设计源码（建议收藏）✅

电影票房数据采集分析可视化系统 | Python Flask MySQL Echarts Requests爬虫 大数据 人工智能 毕业设计源码（建议收藏）✅

博主介绍：✌全网粉丝10W+,前互联网大厂软件研发、集结硕博英豪成立工作室。专注于计算机相关专业项目实战6年之久，选择我们就是选择放心、选择安心毕业✌ > 🍅想要获取完整文章或者源码，或者代做，拉到文章底部即可与我联系了。🍅 点击查看作者主页，了解更多项目！ 🍅感兴趣的可以先收藏起来，点赞、关注不迷路，大家在毕设选题，项目以及论文编写等相关问题都可以给我留言咨询，希望帮助同学们顺利毕业 。🍅 1、毕业设计：2026年计算机专业毕业设计选题汇总（建议收藏）✅ 2、大数据毕业设计：2026年选题大全 深度学习 python语言 JAVA语言 hadoop和spark（建议收藏）✅ 1、项目介绍 技术栈 采用Python语言开发，结合Flask框架搭建后端服务，使用MySQL数据库存储数据，借助Echarts实现数据可视化效果，通过requests库编写爬虫程序，从艺恩电影票房网获取相关数据。 功能模块 * 地区票房占有率分析 * 月份票房分析 * 电影类型票房占有率分析 * 首页展示 * 实时票房排名 * 采集日志 * 数据采集 项目介绍 该电影票

By Ne0inhk

Palantir Foundry 五层架构模型详解

整体架构层次 Palantir Foundry 五层架构模型 ┌─────────────────────────────────────────────────────────────┐ │ 决策编排层 (Decision Orchestration) │ │ ┌─────────────────────────────────────────────────────┐ │ │ │ 分析应用层 (Analytic Applications) │ │ │ │ ┌─────────────────────────────────────────────┐ │ │ │ │ │ 本体层 (Ontology Layer) │ │ │ │ │ │ ┌─────────────────────────────────────┐ │ │ │ │ │ │ │ 模型层 (Model Layer) │ │ │ │ │ │ │ │ ┌─────────────────────────────┐ │ │ │ │ │ │ │ │ │ 数据层 (Data Layer) │ │ │ │ │ │ │ │ │ │

By Ne0inhk
MySQL 表约束核心指南：从基础约束到外键关联（含实战案例）

MySQL 表约束核心指南：从基础约束到外键关联（含实战案例）

🔥草莓熊Lotso：个人主页 ❄️个人专栏: 《C++知识分享》《Linux 入门到实践：零基础也能懂》 ✨生活是默默的坚持，毅力是永久的享受！ 🎬 博主简介： 文章目录 * 前言： * 一. 表约束核心概念 * 二. 基础约束：NULL/NOT NULL 与 DEFAULT * 2.1 空属性约束（NULL/NOT NULL） * 2.2 默认值约束（DEFAULT） * 2.3 列描述（COMMENT） * 2.4 零填充约束（ZEROFILL） * 三. 核心约束：主键、自增长与唯一键 * 3.1 主键约束（PRIMARY KEY） * 3.

By Ne0inhk