3.1、数据结构-线性表
数据结构
- 数据结构
- 线性结构
- 线性表
- 顺序存储和链式存储区别
- 单链表的插入和删除
- 练习题
- 栈和队列
- 练习题
- 串(了解)
数据结构
数据结构该章节非常重要,上午每年都会考10-12分选择题+下午一个大题
什么叫数据结构?我们首先来理解一下什么叫程序,程序就是数据结构+算法。由数据结构和算法就可以来组成我们的各种程序,比如说你的手机的点外卖程序,打车程序,这些程序底层就是由这两部分来组成的。
那数据结构又包含了两层的意义,一层叫数据,一层叫结构。
所谓的数据就是通过数据库那一章来专门来进行讲解,通过SQL语句来操作各种数据库,以及现在的大数据,数据存储,数据挖掘,数据分析。
结构是什么意思?是指我们的数据在内存或CPU中,在我们的程序使用过程中,它是以什么样的结构而存在的,这就我们所谓的数据结构。所以我们本章节的特点是在结构这两个字,而不是在数据两个字上。
那么结构呢,它又分成了很多种。比如说线性结构(线性结构有线性表,有站和队列,还有串)、数组、矩阵结构和广义表、树结构、图结构。这就是说我们的重点,都是数据存储的一个一个的结构。
我们的数据放在这个结构里面,我们怎么来对这些数据进行查找以及我们怎么来对这些数据来进行一个升序或者降序的一个排列,这就是我们所谓的一个算法。
线性结构
线性表
线性结构:每个元素最多只有一个出度
和一个入度
,表现为一条线状。线性表按存储方式分为顺序表和链表。
看下图:顺序表里2和3是线性结构中的两个元素,那么每一个元素是不是只有前面一个元素指向它,那么这个前面一个元素指向它的我们把给称之为入度。然后它再指向下一个元素代表出度。所以我们的首元素是只有出度没有入度,我们的尾元素只有入度没有出度。
顺序表的每一个元素与另一个元素之间紧紧贴在一起。注意:贴在一起不仅仅是我们看上去贴在一起,实际在内存中的存储也是紧密的挨在一起的
链表结构有三种方式:单链表、循环链表、双向链表
- 单链表
每个元素都有两个部分组成,其中一个区域存放数据,另外一个区域存放下一个元素的地址。
它只能从首元素->尾元素走下去。 - 双向链表
由三个部分组成,一部分存放上一个元素的地址,一个存放数据,还有一个存放下一个元素的地址。
可以从首元素->尾元素走,也可以从尾元素->首元素走。
它是可以双向进行的,查询效率比单链表快上一倍。
首节点的上一个元素地址为NULL,尾结点的下一个元素地址是NULL - 循环链表:首节点的上一个节点指向尾结点,尾结点的下一个节点指向首节点。形成一个闭环,这个闭环就叫循环链表
顺序列表由于元素与元素之间是相邻的,我们可以直接从首元素来查到每个元素的位置。但是链表这里存储一个原来,那里存储一个元素,然后通过地址的形式进行一个强关联,这样会浪费一些空间用来存储地址,所以它的利用率没有顺序列表高。
存储结构:
- 顺序存储:用一组地址连续的存储单元依次存储线性表中的数据元素,使得逻辑上相邻的元素物理上也相邻。
- 每一个元素与元素之间是直接相邻的并且紧紧的相邻进行一个存储的
- 我们的头元素是没有入度,尾元素没有出度
- 链式存储:存储各数据元素的结点的地址并不要求是连续的,数据元素逻辑上相邻,物理上分开。
顺序存储和链式存储区别
在空间方面,因为链表还需要存储指针,因此有空间浪费存在。
在时间方面,由顺序表和链表的存储方式可知,当需要对元素进行破坏性操作(插入、删除)时,链表效率更高,因为其只需要修改指针指向即可,而顺序表因为地址是连续的,当删除或插入一个元素后,后面的其他节点位置都需要变动。
而当需要对元素进行不改变结构操作时(读取、查找),顺序表效率更高,因为其物理地址是连续的,如同数组一般,只需按索引号就可快速定位,而链表需要从头节点开始,一个个的查找下去。
单链表的插入和删除
- (a)在单链表中插入节点:在a和b中间插入一个c
1)先创建c
2)将c的下一个元素地址指向b
3)把a下一个元素地址指向b的断开改为指向c - (b) 在单链表中删除节点:删除b
断开b的下一个元素地址c,断开a的下一个元素地址b并指向c
在上图中p所指向的节点后插入s所指向的节点,操作为:
s->next=p->next,
p->next=s;
同理,在单链表中删除p所指向节点的后继节点q时,操作为:
free(p);
p->next=p->next->next;
练习题
〖2014年〗对于线庄表,相对于顺序存储,采用链表存储的缺点是()。
A.数据元素之间的关系需要占用存储空间,导致存储密度不高
B.表中结点必须占用地址连续的存储单元,存储密度不高
C.插入新元素时需要遍历整个链表,运算的时间效率不高
D.删除元素时需要遍历整个链表,运算的时间效率不高
答案:A
栈和队列
队列、栈也是线性结构,结构如下图,队列是先进先出,分队头和队尾;栈是先进后出,只有栈顶能进出。
队列:FIFO(先进先出),比如:水管,先进去的水滴先出来
栈:FILO(先进后出),比如:枪的弹夹,先放进去的子弹最后才能出来
循环队列中,头指针指向第一个元素,尾指针指向最后一个元素的下一个位置,因此,当队列空时,head=tail,当队列满时,head=tail,这样就无法区分了。
因此,一般将队列少存一个元素,这样,队列满时的条件就变为tail+1=head,而考虑是循环队列,必须要除以最大元素数来取余数,即(tail+1)%size=head,如上图右边所示两个公式。循环队列的长度公式为(Q.tail-Q.head)%size。
优先队列:元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。使用堆来存储因为其不是按照元素讲队列的顺序来决定的。
练习题
【2014年】某双端队列如下图所示,要求元素进出队列必须在同一端口,即从A端进入的元素必须从A端出、从B端进入的元素必须从B端出,则对于4个元素的序列e1、e2、e3、e4,若要求前2个元素(e1、e2)从A端口按次序全部进入队列,后两个元素(e3、e4)从B端口按次序全部进入队列,则可能得到的出队序列是()
A. e1、e2、e3、e4
B. e2、e3、e4、e1
C. e3、e4、e1、e2
D. e4、e3、e2、e1
答案:D
只要找到e2>e1,e4>e3的
【2021年】设有栈S和队列Q初始状态为空,数据元素序列a,b,c,d,e,f依次通过栈S,且多个元素从S出栈后立即进入队列Q,若出队的序列是b,d,f,e,c,a,则S中的元素最多时,栈底到栈顶的元素依次为()。
A、a,b,c
B、a,c,d
C、a,c,e,f
D、a,d,f,e
答案C
串(了解)
字符串是一种特殊的线性表,其数据元素都为字符。
- 空串:长度为0的字符串,没有任何字符。
- 空格串:由一个或多个空格组成的串,空格是空白字符,占一个字符长度。
- 子串:串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串,空串是任意串的子串。
例如:abcdef为主串,abf是子串
学过编程的应该见过indexOf函数:python,javascript等都有,是用来查找子串位置的。以下就是查找的相关算法(很复杂,花大量时间学习不划算,了解即可)
- 串的模式匹配算法:子串的定位操作,用于查找子串在主串中第一次出现的位置的算法。
- 基本的模式匹配算法:也称为布鲁特一福斯算法,其基本思想是从主串的第1个字符起与模式串的第1个字符比较,若相等,则继续逐个字符进行后续的比较;否则从主串中的第2个字符起与模式串的第1个字符重新比较,直至模式串中每个字符依次和主串中的一个连续的字符序列相等时为止,此时称为匹配成功,否则称为匹配失败。
- KMP算法:对基本模式匹配算法的改进,其改进之处在于:每当匹配过程中出现相比较的字符不相
等时,不需要回溯主串的字符位置指针,而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离,再继续进行比较。
相关文章:

3.1、数据结构-线性表
数据结构 数据结构线性结构线性表顺序存储和链式存储区别单链表的插入和删除练习题 栈和队列练习题 串(了解) 数据结构 数据结构该章节非常重要,上午每年都会考10-12分选择题下午一个大题 什么叫数据结构?我们首先来理解一下什…...

记一次对HTB:Carpediem的渗透测试
信息收集 端口扫描 通过nmap对靶机端口进行探测,发现存在22和80端口。 访问web页面。发现是一个静态页面,没有可利用的部分。 目录扫描 子域枚举 通过对域名进行fuzz子域名,发现存在portal一级域名。 将它加入/etc/hosts,访问之…...

MATH2 数据集:AI辅助生成高挑战性的数学题目
随着大型语言模型(LLMs)在理解和生成复杂数学内容方面的能力显著提高,通过利用所有公开数据以及相当一部分私有数据,已经取得了进展。然而,高质量、多样化和具有挑战性的数学问题来源正在逐渐枯竭。即使是寻找新的评估…...

加密货币“蓄势待发”!美国松口降息!九月开始连续降息8次?2025年利率目标3.25-3.5%?
今晨,美国联准会(Fed)结束FOMC会议,一如市场预期第八度冻涨利率在5.25%-5.5%。不过主席鲍威尔(Jerome Powell)在会后的记者会访出鸽派讯号,暗示9月降息脚步将近。这一消息令金融市场顿时沸腾,美股全面大涨&…...
Vue.js 3.x 必修课|005|代码规范与 ESLint 入门
欢迎关注公众号:CodeFit 创作不易,如果你觉得这篇文章对您有帮助,请不要忘了 点赞、分享 和 关注,为我的 持续创作 提供 动力! 1. 代码规范的重要性 在现代软件开发中,代码规范扮演着至关重要的角色。 特别是在团队协作的环境中,统一的代码风格可以大大提高工作效率和…...

【Linux】动态库|静态库|创建使用|动态库加载过程
目录 编辑 前言 静态库 为什么要使用库(形成原理 ) 生成一个静态库 静态库的使用 动态库 生成一个动态库 动态库的使用 解决方法 动态库加载过程 编辑 前言 库(Library)是一种方式,可以将代码打包成可重用的格式(站…...

WebSocket 协议与 HTTP 协议、定时轮询技术、长轮询技术
目录 1 为什么需要 WebSocket?2 WebSocket2.1 采用 TCP 全双工2.2 建立 WebSocket 连接2.3 WebSocket 帧 3 WebSocket 解决的问题3.1 HTTP 存在的问题3.2 Ajax 轮询存在的问题3.3 长轮询存在的问题3.4 WebSocket 的改进 参考资料: 为什么有 h…...
二叉树节点问题
问题:设一棵二叉树中有3个叶子结点,有8个度为1的结点,则该二叉树中总的结点数为( 13)个 设某种二叉树有如下特点:每个结点要么是叶子结点,要么有2棵子树。假如一棵这样的二叉树中有m(m>0&…...

公司里的IT是什么?
公司里的IT是什么? 文章目录 公司里的IT是什么?1、公司里的IT2、IT技术3、IT行业4、IT行业常见证书 如果对你有帮助,就点赞收藏把!(。・ω・。)ノ♡ 前段时间,在公…...

【小程序爬虫入门实战】使用Python爬取易题库
文章目录 1. 写在前面2. 抓包分析 【🏠作者主页】:吴秋霖 【💼作者介绍】:擅长爬虫与JS加密逆向分析!Python领域优质创作者、CSDN博客专家、阿里云博客专家、华为云享专家。一路走来长期坚守并致力于Python与爬虫领域研…...

案例 —— 怪物出水
一,Ocean Setup 设置海洋Surface Grid(使用Large Ocean工具架) 调节默认Grid的大小尺寸及细分(使用非常小尺寸来测试);调整频谱输入点的多少,频谱Grid Size,波浪方向,速度…...
vue中使用print.js实现页面打印并增加水印
1.安装print.js npm install print-js --save2.在main.js文件中引入并注册(我使用的是print.js的源码文件,并且做了一修改) //引入 import Print from ./utils/print//注册 Vue.use(Print); //注册3.在页面中使用 <template> <div class&quo…...

计算机基础(Windows 10+Office 2016)教程 —— 第5章 文档编辑软件Word 2016(下)
文档编辑软件Word 2016 5.4 Word 2016的表格应用5.4.1 创建表格5.4.2 编辑表格5.4.3 设置表格 5.5 Word 2016的图文混排5.5.1 文本框操作5.5.2 图片操作5.5.3 形状操作5.5.4 艺术字操作 5.6 Word 2016的页面格式设置5.6.1 设置纸张大小、页面方向和页边距5.6.2 设置页眉、页脚和…...

简单洗牌算法
🎉欢迎大家收看,请多多支持🌹 🥰关注小哇,和我一起成长🚀个人主页🚀 ⭐目前主更 专栏Java ⭐数据结构 ⭐已更专栏有C语言、计算机网络⭐ 在学习了ArrayList之后,我们可以通过写一个洗…...

JVM: 堆上的数据存储
文章目录 一、对象在堆中的内存布局1、对象在堆中的内存布局 - 标记字段2、JOL打印内存布局 二、元数据指针 一、对象在堆中的内存布局 对象在堆中的内存布局,指的是对象在堆中存放时的各个组成部分,主要分为以下几个部分: 1、对象在堆中的…...

AI产品经理的职责与能力:将AI技术转化为实际价值
一、AI产品经理的职责 发现和解决问题:AI产品经理需要具备敏锐的洞察力,能够发现用户需求和痛点,并提出相应的解决方案。传递价值给用户:AI产品经理需要确保产品能够满足用户的需求,提供价值,并提升用户体…...

【独家原创RIME-CNN-LSSVM】基于霜冰优化算法优化卷积神经网络(CNN)结合最小二乘向量机(LSSVM)的数据回归预测
【独家原创RIME-CNN-LSSVM】基于霜冰优化算法优化卷积神经网络(CNN)结合最小二乘向量机(LSSVM)的数据回归预测 目录 【独家原创RIME-CNN-LSSVM】基于霜冰优化算法优化卷积神经网络(CNN)结合最小二乘向量机(LSSVM)的数据回归预测效果一览基本介绍程序设计参考资料 效果一览 基本…...
如何对B站的热门视频进行分析
1. 视频内容分析 主题和类型:确定视频的主题和类型(如游戏、教育、生活、科技等),分析其是否符合当前流行趋势或特定兴趣群体。内容创意:评估视频内容的创意性和原创性,是否具有吸引力和独特性。内容质量&…...

MobaXterm tmux 配置妥当
一、事出有因 缘由:接上篇文章,用Docker搭建pwn环境后,用之前学过的多窗口tmux进行调试程序,但是鼠标滚动的效果不按预期上下翻屏。全网搜索很难找到有效解决办法,最后还是找到了一篇英文文章,解决了&…...

排序算法:快速排序,golang实现
目录 前言 快速排序 代码示例 1. 算法包 2. 快速排序代码 3. 模拟程序 4. 运行程序 5. 从大到小排序 快速排序的思想 快速排序的实现逻辑 1. 选择基准值 (Pivot) 2. 分区操作 (Partition) 3. 递归排序 循环次数测试 假如 10 条数据进行排序 假如 20 条数据进行…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...