【JAVA入门】Day28 - 数据结构

2024-08-30 12:04
文章标签 java 入门 数据结构 day28

本文主要是介绍【JAVA入门】Day28 - 数据结构,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【JAVA入门】Day28 - 数据结构


文章目录

  • 【JAVA入门】Day28 - 数据结构
    • 一、栈
    • 二、队列
    • 三、数组
      • 3.1 ArrayList
    • 四、链表
      • 4.1 LinkedList
    • 五、二叉树
      • 5.1 二叉查找树
      • 5.2 二叉树的遍历方式
      • 5.3 平衡二叉树
      • 5.4 平衡二叉树的旋转
      • 5.5 平衡二叉树需要旋转的几种情况
    • 六、红黑树
      • 6.1 红黑规则
      • 6.2 红黑树添加节点的规则


        数据结构就是计算机存储、组织数据的方式。它是指数据相互之间以何种方式排列在一起。数据结构是为了更加方便地管理和使用数据,需要结合具体的业务场景来进行选择。精心选择的数据结构可以给业务带来更高的运行或存储效率。

        常见的数据结构我们讲八种:

  • ① 栈
  • ② 队列
  • ③ 数组
  • ④ 链表
  • ⑤ 二叉树
  • ⑥ 二叉查找树
  • ⑦ 平衡二叉树
  • ⑧ 红黑树

        围绕三个问题,我们可以轻易学习:

1.每种数据结构长什么样子?
2.如何添加数据?
3.如何删除数据?

        学好数据结构是计算机进修的一大基础,下面我们从第一种开始讲起。

一、栈

        栈的特点:后进先出,先进后出
        数据进入栈模型的过程称为:压 / 进栈。
        我们以 A B C D 的顺序压栈,得到的结果如下图所示。
在这里插入图片描述
        此时的栈顶元素为 D,栈底元素为 A。
        数据离开栈模型的过程称为:弹 / 出栈。
        此时栈顶元素先出栈,所以只能按照 D C B A 的顺序依次出栈。
        在 Java 的内存结构当中,有一块区域被称为栈内存,也是利用了栈的原理。
在这里插入图片描述

二、队列

        队列的特点是:先进先出,后进后出
在这里插入图片描述
        A B C D 按顺序进入队列,会先从后端(队尾)依次进入,我们称之为入队列。随后,会按 A B C D 的顺序从前端(队头)依次出去,我们称之为出队列
![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/5e7c9b85df0e436fa806d57d02aa32bf.png

在这里插入图片描述

三、数组

        数组也是一种数据结构,相关操作我们讲了很多了,不需要多讲。
在这里插入图片描述
        我们只需要知道,查询数据时,是通过数组的地址值索引直接定位的,查询任意数据耗时相同(因为元素在内存中是连续存储的)。
        数组的删除效率是非常低的,删除一个数据之后,要同时把后面每一个数据都前移。
在这里插入图片描述
在这里插入图片描述
        数组的添加效率也是非常低的,除非你在数组 0 索引前或最后索引后添加,否则中间插入元素需要把添加位置后的每个数据都往后移动,再插入元素。
在这里插入图片描述
        由此可见,数组是一种查询快,增删慢的数据模型。

3.1 ArrayList

        之前讲的 ArrayList 底层就是数组集合。

四、链表

        链表与数组刚好相反,它是一种查询慢,增删快的数据模型。
        链表中的每一个元素,我们有专业的名词来描述:结点(Node)。每一个结点都是一个独立的对象,它会有自身的存储位置(地址值),在结点内部,它还会存储具体的数据,同时也存储下一个结点的地址值。
在这里插入图片描述
        在链表中,第一个创建出来的结点,我们称为头结点,头结点里有自己的地址值,然后下一个结点地址值暂时记录为空。
在这里插入图片描述
        此时如果要添加一个数据A,我们就要新开辟一个新空间,存储数据A,然后将下一个结点地址值记录为空。
在这里插入图片描述
        然后我们只需要把前一个结点的“指向下一个结点地址值”的数据修改为新结点的地址值,即可完成两个结点之间的链接。
在这里插入图片描述
        从而我们可以创建一条完整的链表,内部的每一个结点都是一个独立的对象,在内存中是不连续的。
在这里插入图片描述
        因此,链表在查询时,无论查询哪个数据,都要从头结点开始找。
        但是,链表的增删是非常快的,每次增删不需要移动元素。当插入新结点时,只需要令上一个结点指向它,它的下一个结点指向原来的下一个结点,即可完成插入;删除也是一样的道理只需要断链把结点孤立出来,再清除它的内存空间即可。
        而且,链表还有双向的改进链表等,通过加入“上一个结点”的地址值,可以提高查找效率。

4.1 LinkedList

        LinkedList 在底层其实就是一个双向链表,它的特点是查询慢,增删快,但是如果操作的是首位元素,速度也是极快的。Java 给 LinkedList API 提供了很多独有方法,用于链表操作。

特有方法说明
public void addFirst(E e)在该列表开头插入指定的元素
public void addLast(E e)将指定的元素追加到此列表的末尾
public E getFirst()返回此列表中的第一个元素
public E getLast()返回此列表中的最后一个元素
public E removeFirst()从此列表中删除并返回第一个元素
public E removeLast()从此列表中删除并返回最后一个元素

五、二叉树

        二叉树是一种全新的数据结构。
在这里插入图片描述
        从根节点,向两边延伸出子节点,一个左子节点,一个右子节点,生生不息,延绵不绝。
        在 Java 中,实际上每个节点都是一个单独的对象,其内部存储着自身的值,还存储着父节点地址值、左子节点地址值、右子节点地址值,如果没有左右子节点,地址值就为空。
在这里插入图片描述
        在树的数据结构中,有一些专有名词需要认识。

  • 度:每一个节点的子节点数量。在二叉树中,任意节点的度<=2。
  • 树的高度:一棵树的总层数叫做树的高度。
    在这里插入图片描述
  • 根节点:最顶层的节点。
  • 左子节点:一个节点左下方的孩子节点。
  • 右子节点:一个节点右下方的孩子节点。
  • 根节点的左子树:如图所示。
    在这里插入图片描述
  • 根节点的右子树:如图所示。
    在这里插入图片描述
  • 其他节点的左右子树:如图所示。

在这里插入图片描述

5.1 二叉查找树

        如果一棵树的每一个节点都满足以下规律:它的左子节点的存储的数据比自己小,它的右子节点存储的数据比自己大,我们就把这棵树称为二叉查找树,又叫二叉排序树或二叉搜索树。
        二叉查找树在添加节点时一定要遵从以下规则:
1.小的存左边
2.大的存右边
3.一样的不存
在这里插入图片描述
        在查找时,从根节点开始,依次比较,如果比它小,看左边;比它大,看右边,依次摸索,直到找到或找不到。

5.2 二叉树的遍历方式

        二叉树有四种遍历方式:
①前序遍历
②中序遍历
③后序遍历
④层序遍历
        前序遍历:从根节点开始,按照当前节点,左子节点,右子节点的顺序遍历。
在这里插入图片描述
        中序遍历:从根节点开始,按照左子节点,当前节点,右子节点的顺序遍历。
        ※按照中序遍历的二叉排序树,其获取的数据是从小到大排列的。
在这里插入图片描述
        后序遍历:从根节点开始,按照左子节点,右子节点,当前节点的顺序遍历。
在这里插入图片描述
        层序遍历:从根节点开始,一层一层地遍历。
在这里插入图片描述

5.3 平衡二叉树

在这里插入图片描述

        如果严格按照二叉查找树的创建方式,可能会出现这种严重倾斜的情况,这样严重影响了查找的效率。一棵二叉树如果想要提高查找效率,那它的左右分支就应该差不多大,因此,我们需要引入平衡二叉树的概念。
在这里插入图片描述
        平衡二叉树是在二叉查找树的基础上,又加入了以下规则:任意节点左右子树的高度差不超过1

5.4 平衡二叉树的旋转

  • 平衡二叉树的左旋

        平衡二叉树在旋转时,要先确定支点,从添加的节点开始,不断地往父节点找不平衡的节点。
在这里插入图片描述
        所谓不平衡节点,就是左子树和右子树节点差值超过2的节点,可以轻易地发现图中是 10 节点,而 10 节点的左子树小于右子树,所以要进行左旋。
在这里插入图片描述
        这种简单左旋,旋转方式如下。
在这里插入图片描述
在这里插入图片描述
        稍微复杂一点的左旋,如下图所示:
在这里插入图片描述
        确认不平衡支点为 7 节点,左旋后如下:
在这里插入图片描述

  • 平衡二叉树的右旋

        平衡二叉树右旋,简单情况如下:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
        稍微复杂一点的情况,如下:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

5.5 平衡二叉树需要旋转的几种情况

  • 左左:当根节点左子树的左子树有节点插入,导致二叉树不平衡时。

在这里插入图片描述

在这里插入图片描述
此时进行右旋即可。
在这里插入图片描述

  • 左右:当根节点左子树的右子树有节点插入,导致二叉树不平衡时。

在这里插入图片描述
在这里插入图片描述
此时应该先对子树进行一次左旋,把情况变成左左,再进行整体的右旋。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

  • 右右:当根节点的右子树的右子树有节点插入,导致二叉树不平衡时。
    在这里插入图片描述
    此时直接整体左旋即可。
    在这里插入图片描述
  • 右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡时。
    在这里插入图片描述
    在这里插入图片描述
    应该先把局部位置进行右旋。
    在这里插入图片描述
    在这里插入图片描述
    此时变为右右,整体左旋即可。
    在这里插入图片描述

六、红黑树

        红黑树是一种自平衡的二叉查找树,是计算机科学中用到的一种数据结构。
        红黑树自1972年出现,曾被命名为平衡二叉B树,后于1978年被修改命名为红黑树
        红黑树是一种特殊的二叉查找树,它的每一个节点上都有存储位表示节点的颜色
        红黑树的每一个节点可以是或者,红黑树不是高度平衡的,它的平衡是通过红黑规则进行实现的。

在这里插入图片描述

6.1 红黑规则

① 每一个节点或者是红色,或者是黑色。
② 根节点必须是黑色。
③ 如果一个节点没有子节点或者父节点,则该节点相应指针属性值为Nil,这些Nil视为叶节点,每个叶节点(Nil)是黑色的。
④ 如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)。
⑤ 对每一个节点而言,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。
在这里插入图片描述
        如果一个节点没有左子节点,也没有右子节点,那么都记为Nil。
在这里插入图片描述
        然后会在它的两侧生成两个空节点,也就是叶子节点,其内部没有任何数据。

6.2 红黑树添加节点的规则

  • 默认颜色:添加的节点默认是红色的,因为红色节点添加效率高。使用红色节点造树,添加三个节点才需要调整一次这棵树。
  • 调整的规则如下图:
    在这里插入图片描述

        红黑树的增删改查,效率都是极高的。

这篇关于【JAVA入门】Day28 - 数据结构的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1120771

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig