【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 的类初始化机制

JVM 的类初始化机制

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

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

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

浅析Spring Security认证过程

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

Spring Security--Architecture Overview

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

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

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

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

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
Java进阶13讲__第12讲_1/2

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智听未来一站式有声阅读平台听书系统小程序源码

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

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

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

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

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2