线性表的学习
- 线性表

定义
n个类型相同数据元素的有限序列,记作:a0,a1,a2,a3,...ai-1,ai,ai+1...an-1(这里的0,1,2,3,i-1,i,i+1,n-1都是元素的序号)
特点
除第一个元素无直接前驱。最后一个元素无直接后续,集合中每个元素都有一个直接前驱和一个后续元素
删除和插入元素,再插入或删除位置之后的所有元素都会移动位置
插入元素

删除元素

线性表的链式存储
单链表
链表是一些列存储数据元素的单元通过指针串联起来,每个单元有两个域,一个用于存储数据,一个是指向其他单元的指针。这个单元称为节点。

数据域存储的是数据的引用。指针域存储的是下一节点的引用。
节点的的数据域存储当前节数据的物理地址,指针域存储下一个节点的地址信息
单链表结构

单链表特点
从单链表的结构可以看出,由于链表前一个结点的指针指向后一个结点,所以单链表可以通过前一个元素找到后一个元素,但无法通过后一个结点找到前一个结点。
单链表的查找
单链表的查找只能从首结点开始依次查每个节点的next。

单链表插入
不需要移动所有元素

单链表删除结点

双向链表
双向链表是在单项链表的基础上增加一个域,该域用于指向该结点的前驱结点。
双向链表的结点:

由于双向链表结构特点,结点中存储了前一个结点和后一个结点的指针,所以双向链表可以通过前一个结点查找后一个结点,也可以通过后一个结点查找前一个结点。
双向链表结构

双向链表插入

双向链表的删除

数组,单链表,双链表三种线性表的比较:
基于时间的比较
查找
数组属于顺序存储,可以随机存取,每个元素都有一个存储序号,查找时根据序号查找,查找速度较快。链式存储的双向链表和单向链表查找时需要从头开始查找,依次遍历目标元素之前的元素。所以查找速度低于顺序存储的数组。
因此查找速度:
数组>单项链表/双向链表
插入,删除
对于数组而言,首先需要通过序号定位元素,然后将目标元素插入或者删除,插入或删除位置之后的元素需要改变位置。这些操作可能引起大量元素移动。双向链表和单项链表删除或插入时,只需要在插入位置将前后指针更改即可,因此链表的删除插入操作呢优于数组。
删除,插入性能:
单项链表/双向链表>数组
基于空间的比较
顺序存储空间是预先分配好的,属于静态分配,如果没有使用完成吗,就会造成大量空闲空间。链式结构是动态分配空间,不会存在剩余情况,因此不会造成浪费。
从空间的角度看:
链式存储>顺序存储
链接表
对于链表的删除,插入和空间利用率都比较有优势,但是对于定位元素必须从头或从尾部开始,比较耗时。
- 栈与队列
栈和队列从结构上来说也属于线性结构,区别在于某些操作与上面说的线性结构有区别。
栈:先进后出
队列:先进先出
栈
栈就像一个桶,桶装满东西,只能从入口倒出去,桶的顶端叫栈顶,桶的底端叫栈底。只允许在一端插入和删除,不允许在任何位置查找,删除,插入。栈中没有东西叫空栈,往栈里面放元素叫入栈,删除元素叫出栈,

栈的存储
栈是一种操作受限的线性表,所以可以用线性表来实现栈,可以链式存储也可以顺序存储。顺序存储可以选择数组来实现,选择数组的下标最大的一端作为栈顶,还需要设置一个指针top指向栈顶,如果是空栈,top=-1;
链式存储选择单链表实现,由于链表的特性,链表的头部作为栈顶,可以使用带头结点的链表和不带头结点的链表。

队列
队列也是一种受限的线性结构,队列就像是一根水管(比喻不是很恰当,但大概是这个意思),只能从一端进入,一端出去。因此队列是先进先出。
一般从队列尾部插入元素,从队列首部删除元素。向队尾插入元素叫入队,从队首删除元素叫出队,删除后,后面的元素成为新的队首元素。
队列的顺序存储
队列的顺序存储
队列的顺序存储可以使用数组实现,但数组实现不是很好,删除或插入时,数组的每个元素都需要移动一个为位置,改用循环数组实现。队尾指针指向最后一个元素的下一个单元,队首指针指向队首元素所在的单元。需要入队时,元素直接存入队尾指针指向的单元,队尾指针逆时针转动一位;需要出队时,只需要将队首指针逆时针转动一位即可。

区分队列为空还是满方法:
少使用一个空间,当队尾指针逆时针转动一位指向队首指针时,表示队列已经满了,不能再入队。此时认为已经满了。

或者增加变量size来表示,如果size=maxSize则认为队列满了。
队列的链表实现
可以采用带头结点的单链表实现。选择链表的头部作为队首,链表的尾部作为队尾。需要两个指针,分别是队首指针和队尾指针。
队首指针始终指向链表头结点,即首个元素的前一个没有元素的头结点。队尾指针指向队尾当前队尾元素所在的结点,如果队列为空,队尾指针和队首指针均指向头结点。

堆栈的应用
1.进制转换,如十进制转换为二进制,每次进行除2当时,得到每次的余数,恰好是将最后得到的数先输出。

2023转换为二进制是11111100111。
2.嵌套的括号校验,有了开始的括号,必须要有结束括号与之匹配,才算正确.
如:{[]()}和{[{}][()]}这些是正确的,但如果是{[}],{[(]])}这些是错误的。
3.迷宫就求解
相关文章:
线性表的学习
线性表定义 n个类型相同数据元素的有限序列,记作:a0,a1,a2,a3,...ai-1,ai,ai1...an-1(这里的0,1,2,3,i-1,i,i1,n-1都是元素的序号) 特点 除第一个元素无直接前驱。最后一个元素无直接后续&am…...
51单片机学习笔记_13 ADC
ADC 使得调节开发板上的电位器时,数码管上能够显示 AD 模块 采集电位器的电压值且随之变化。 开发板上有三个应用:光敏电阻,热敏电阻,电位器。 一般 AD 转换有多个输入,提高使用效率。 ADC 通过地址锁存与译码判断采…...
类和对象的基本认识之内部类
什么是内部类?当一个事物的内部,还有一个部分需要一个完整的结构进行描述,而这个内部的完整的结构又只为外部事物提供服 务,那么这个内部的完整结构最好使用内部类。在 Java 中,可以将一个类定义在另一个类或者一个方法…...
【操作系统】进程和线程是什么之间是如何通信的
文章目录1、进程1.1、什么是进程1.2、进程的状态1.3、进程的控制结构1.4、进程的控制1.5、进程的上下文切换1.6、进程上下文切换场景1.7、进程间通信2、线程2.1、什么是线程2.2、线程的上下文切换2.3、线程间通信3、线程与进程的联系1、进程 1.1、什么是进程 进程(process) 是…...
setup、ref、reactive、computed
setup 理解:Vue3.0 中一个新的配置项,值为一个函数 setup 是所有 Composition API(组合API)“表演的舞台” 组件中所用到的数据、方法等,均要配置在 setup 中 setup 函数的两种返回值: 若返回一个对象…...
【Gem5】有关gem5模拟器的资料导航
网上有关gem5模拟器的资料、博客良莠不齐,这里记录一些总结的很好的博客与自己的学习探索。 一、gem5模拟器使用入门 官方的教程: learning_gem5:包括gem5简介、修改扩展gem5的示例、Ruby相关的缓存一致性等。gem5 Documentation࿱…...
【CSS】清除浮动 ① ( 清除浮动简介 | 清除浮动语法 | 清除浮动 - 额外标签法 )
文章目录一、清除浮动简介二、清除浮动语法三、清除浮动 - 额外标签法1、额外标签法 - 语法说明2、问题代码示例3、额外标签法代码示例一、清除浮动简介 在开发页面时 , 遇到下面的情况 , 父容器 没有设置 内容高度 样式 , 容器中的 子元素 设置了 浮动样式 , 脱离了标准流 , …...
Shell test 命令
文章目录Shell test 命令数值测试字符串测试文件测试Shell test 命令 Shell中的 test 命令用于检查某个条件是否成立,它可以进行数值、字符和文件三个方面的测试。 数值测试 参数说明-eq等于则为真-ne不等于则为真-gt大于则为真-ge大于等于则为真-lt小于则为真-le…...
pytorch项目实战之实时人脸属性检测系统
简介 本项目采用CelebA人脸属性数据集训练人脸属性分类模型,使用mediapipe进行人脸检测,使用onnxruntime进行模型的推理,最终在intel的奔腾cpu上实现30-100帧完整的实时人脸属性识别系统。 ps:本来是打算写成付费专栏的,毕竟这是…...
JS和Jquery
js函数 function 方法名(参数){ 方法体 return 返回值; } js事件 事件介绍 事件指的就是当某些组件执行了某些操作后,会触发某些代码的执行 onload 某个页面或图像被完成加载 onsubmit 当表单提交时触发事件 onclick 鼠标单击事件…...
Linux设置固定IP
vi /etc/sysconfig/network-scripts/ifcfg-ens33 第一个修改是开启网络 修改完成后重启网络服务 sudo service network restart 然后就可以看到ip 地址了 然后我们开始修改固定IP 主要是下图中的两部分 BOOTPROTO从dhcp改为static HWADD好像改不改都行,我改了&…...
面试准备啊
fail fast 是把数组原来的更改次数记住 每次都去比较 变了 就抛异常 如果数组容量没到64 会先扩容 再树化 缺点:全是偶数 hash分布不均匀 质数比较好(二次哈希也不需要) 效率好 2的n次幂 使用内存屏障解决指令重排序 第一次扩容和之后的不…...
机器人工程专业师生的第二张名片
课堂上多次提及第二张名片。什么是CatGPT-使用效果如何-专业感性非理性总结如下:机器人工程的工作与考研之困惑→汇总篇←其中包括:☞ 机器人工程的工作与考研之困惑“卷”☞ 机器人工程的工作与考研之困惑“歧视”☞ 机器人工程的工作与考研之困惑“取舍…...
【云原生之企业级容器技术 Docker实战一】Docker 介绍
目录一、Docker 介绍1.1 容器历史1.2 Docker 是什么1.3 Docker 和虚拟机,物理主机1.4 Docker 的组成1.5 Namespace1.6 Control groups1.7 容器管理工具1.8 Docker 的优势1.9 Docker 的缺点1.10 容器的相关技术1.10.1 容器规范1.10.2 容器 runtime1.10.3 容器管理工具…...
【Microsoft】与 Bing AI 进行 ⌈狂飙⌋
🎊 今天是3月8号,❤️农历二月十七,💕祝广大女同胞们👩女神节快乐🎉!——以创作之名致敬女性开发者文章目录序言Ⅰ、Bing AI初体验Ⅱ、代码生成Ⅲ、生成图像Ⅳ、使用次数Ⅴ、总结序言 近期&…...
PyDolphinScheduler发布4.0.2版本,修复无法提交工作流到DolphinScheduler 3.1.4的问题
点击蓝字 关注我们PyDolphinScheduler 正式发布 4.0.2 版本,主要修复了 4.0.1 版本无法提交工作流到 Apache DolphinScheduler 3.1.4 的问题。除此之外,PyDolphinScheduler 4.0.2 较大的优化还包括:PyDolphinScheduler 校验 Apache DolphinSc…...
go-cqhttp安装使用
2023-03-28 时效性强 go-cqhttp qq机器人 qq bot 安装 本地虚拟机 centos7安装使用 浏览官方文档go-cqhttp 帮助中心 下载:Releases Mrs4s/go-cqhttp GitHub 当前最新版本v1.0.0-rc5 下载go-cqhttp_1.0.0-rc5_linux_amd64.rpm 传到服务器,新…...
论文阅读和分析:Hybrid Mathematical Symbol Recognition using Support Vector Machines
HMER论文系列 1、论文阅读和分析:When Counting Meets HMER Counting-Aware Network for HMER_KPer_Yang的博客-CSDN博客 2、论文阅读和分析:Syntax-Aware Network for Handwritten Mathematical Expression Recognition_KPer_Yang的博客-CSDN博客 3、论…...
05期:面向业务的消息服务落地实践
这里记录的是学习分享内容,文章维护在 Github:studeyang/leanrning-share。 我们在上次分享中聊到了领域驱动设计和微服务,在 DDD 中有一个术语叫做领域事件,例如订单模型中的订单已创建、商品已发货。领域事件会触发下一步的业务…...
代码随想录|day26|回溯算法part03● 39. 组合总和● 40.组合总和II● 131.分割回文串
今天的练习基本就是回溯法组合问题,这一节只要看labuladong即可。 组合问题: 39. 组合总和---------------------形式三,元素无重可复选 链接:代码随想录 一次对,同样在进入下次循环时,注意startindex是从j…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
