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算法:对基本模式匹配算法的改进,其改进之处在于:每当匹配过程中出现相比较的字符不相
    等时,不需要回溯主串的字符位置指针,而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离,再继续进行比较。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/870166.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

算法与算法分析

目录 一.前言 二.算法的特性和要求 三.分析算法--时间效率 四. 分析算法--空间效率 一.前言 算法就是对特定问题求解方法和步骤的一种描述,它是指令的有限序列。其中,每个指令表示一个或多个操作。总而言之,我们数据结构就是通过算法实现操…

记录|C# winform布局学习

目录 前言一、自适应布局Step1. 添加AutoAdaptWindowsSize类Step2. Form中引用Step3. 创建SizeChanged事件函数Step4. 在Fram.Disiger中添加 更新时间 前言 参考视频: C#5分钟winform快速自适应布局 参考文章: 其他参考: 写这篇文章&#xff…

Elasticsearch:Java ECS 日志记录 - log4j2

ECS 记录器是你最喜欢的日志库的格式化程序/编码器插件。它们可让你轻松将日志格式化为与 ECS 兼容的 JSON。ECS 兼容的 JSON 日志记录可以帮我们简化很多分析,可视化及解析的工作。在今天的文章里,我来详述如何在 Java 应用里生成 ECS 相兼容的日志。 …

为什么样本方差(sample variance)的分母是 n-1?

样本均值与样本方差的定义 首先来看一下均值,方差,样本均值与样本方差的定义 总体均值的定义: μ 1 n ∑ i 1 n X i \mu\frac{1}{n}\sum_{i1}^{n} X_i μn1​i1∑n​Xi​ 也就是将总体中所有的样本值加总除以个数,也可以叫做总…

【PHP】系统的登录和注册

一、为什么要学习系统的登录和注册 系统的登录和注册可能存在多种漏洞,这些漏洞可能被恶意攻击者利用,从而对用户的安全和隐私构成威胁。通过学习系统的登录和注册理解整个登录和注册的逻辑方便后续更好站在开发的角度思考问题发现漏洞。以下是一些常见…

学习小型gpt源码(自用)

数据集构建_哔哩哔哩_bilibili (b站上有一系列课,从数据处理到模型构建和训练使用) 什么是batch? 为什么一个batch内的句子要一样长? 不同batch的长度可以不一样,但是同一个batch内长度一样!…

DBeaver Ultimate 22.1.0 连接数据库(MySQL+Mongo+Clickhouse)

前言 继续书接上文 Docker Compose V2 安装常用数据库MySQLMongo,部署安装好之后我本来是找了一个web端的在线连接数据库的工具,但是使用过程中并不丝滑,最终还是选择了使用 DBeaver ,然后发现 mongo 还需要许可,又折…

pdf格式过大怎么样变小 pdf文件过大如何缩小上传 超实用的简单方法

面对体积庞大的 PDF 文件,我们常常需要寻找有效的方法来缩减其大小。这不仅能够优化存储空间,还能提升文件的传输和打开速度。PDF文件以其稳定性和跨平台兼容性成为工作和学习中的重要文件格式。然而,当我们需要通过邮件发送或上传大文件时&a…

vue3 动态el-table表格 动态数据 新增修改删除的简单判断

<template><div class"app-container"><el-form:model"queryParams"ref"queryRef":inline"true"v-show"showSearch"label-width"68px"><el-form-item label"年份选择" prop"…

DevExpress中文教程 - 如何在.NET MAUI应用中实现Material Design 3?

DevExpress .NET MAUI多平台应用UI组件库提供了用于Android和iOS移动开发的高性能UI组件&#xff0c;该组件库包括数据网格、图表、调度程序、数据编辑器、CollectionView和选项卡组件等。 获取DevExpress v24.1正式版下载 Material Design是一个由Google开发的跨平台指南系统…

iOS ------ Block的相关问题

Block的定义 Block可以截获局部变量的匿名函数&#xff0c; 是将函数及其执行上下文封装起来的对象。 Block的实现 通过Clang将以下的OC代码转化为C代码 // Clang xcrun -sdk iphoneos clang -arch arm64 -rewrite-objc main.m//main.m #import <Foundation/Foundation.…

60个常见的 Linux 指令

1.ssh 登录到计算机主机 ssh -p port usernamehostnameusername&#xff1a; 远程计算机上的用户账户名。 hostname&#xff1a; 远程计算机的 IP 地址或主机名。 -p 选项指定端口号。 2.ls 列出目录内容 ls ls -l # 显示详细列表 ls -a # 显示包括隐藏文件在内的所有内…

封装和桥接Unity 协程体系

简介 协程&#xff08;Coroutine&#xff09;在C#中是一种特殊的函数&#xff0c;它允许开发者编写可以暂停执行并在未来某个时刻恢复执行的代码块。协程通常用于实现异步操作&#xff0c;如延时执行、等待某个事件发生、或者分段执行复杂的任务。在Unity游戏引擎中&#xff0c…

Conda和Pip有什么区别?

conda和pip是Python中两种常用的包管理工具&#xff0c;它们在用途、包来源以及环境管理等方面存在区别。以下是具体分析&#xff1a; 用途 conda&#xff1a;conda是Anaconda发行版中的包管理工具&#xff0c;可以管理包括非Python软件包在内的各种包。它是一个全面的环境管理…

【数据结构】建堆算法复杂度分析及TOP-K问题

【数据结构】建堆算法复杂度分析及TOP-K问题 &#x1f525;个人主页&#xff1a;大白的编程日记 &#x1f525;专栏&#xff1a;数据结构 文章目录 【数据结构】建堆算法复杂度分析及TOP-K问题前言一.复杂度分析1.1向下建堆复杂度1.2向上建堆复杂度1.3堆排序复杂度 二.TOP-K问…

Leetcode—769. 最多能完成排序的块【中等】

2024每日刷题&#xff08;149&#xff09; Leetcode—769. 最多能完成排序的块 实现代码 class Solution { public:int maxChunksToSorted(vector<int>& arr) {int ans 0;int mx INT_MIN;for(int i 0; i < arr.size(); i) {mx max(arr[i], mx);if(mx i) {a…

数据库安全:MySQL安全配置,MySQL安全基线检查加固

「作者简介」:冬奥会网络安全中国代表队,CSDN Top100,就职奇安信多年,以实战工作为基础著作 《网络安全自学教程》,适合基础薄弱的同学系统化的学习网络安全,用最短的时间掌握最核心的技术。 这一章节我们需要知道MySQL的安全基线标准和加固方式。 MySQL基线检查 1、更新…

Cannot access org.springframework.context.ConfigurableApplicationContext

Cannot access org.springframework.context.ConfigurableApplicationContext SpringApplication.run曝红 解决方案&#xff1a; File -> Invalidate Cache and Restart 如果对你有用就点个赞&#xff01;

项目实战——外挂开发(30小时精通C++和外挂实战)

项目实战——外挂开发&#xff08;30小时精通C和外挂实战&#xff09; 外挂开发1-监控游戏外挂开发2-秒杀僵尸外挂开发3-阳光地址分析外挂开发4-模拟阳光外挂开发5-无限阳光 外挂开发1-监控游戏 外挂的本质 有两种方式 1&#xff0c;修改内存中的数据 2&#xff0c;更改内存中…

【Stable Diffusion】AI生成新玩法:图像风格迁移

【Stable Diffusion】 AI生成新玩法&#xff1a;图像风格迁移 1 背景导入 你是否曾梦想过让自己融入梵高的星空之中 或是将一幅风景画赋予毕加索的立体主义之魂 还是把人物送进宫崎骏的动画世界&#xff1f; 下面让我们来看看如何通过 Stable Diffusion 实现在图像中玩…