请选择 进入手机版 | 继续访问电脑版

【Java基础进阶笔记】- Day03 - 第一章 数据结构

[复制链接]
太阳神鹰 发表于 2021-1-1 10:31:36 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
Java基础进阶条记 - Day03 - 第一章 数据布局



Java基础进阶条记 - Day03 - 第一章 数据布局

  系统:Win10
JDK:1.8.0_121
IDE:IntelliJ IDEA 2017.3.7
1.1 数据布局有什么用?

数据布局是盘算机存储、组织数据的方式,是指相互之间存在一种或多种特定关系的数据元素的聚集。通常情况下,经心选择的数据布局可以带来更高的运行大概存储效率。
我们常见的数据布局有:数组(Array)、栈(Stack)、队列(Queue)、链表(Linked List)、树(Tree)、图(Graph)、堆(Heap)、散列表(Hash)等
学习数据布局能够资助我们知道步伐的底层是怎么工作的,不仅限于为了编程而编程,而是让我们明确我们为什么要这样做,这个语句为什么要这样设计,能不能有更好的办法实现同一个功能。
1.2 常见的数据布局

常见的数据布局我们上面有列出来,这里我们主要学习此中的:栈、队列、数组、链表和红黑树(树的一种)




  • 栈(Stack):又称堆栈,它是运算受限的线性表,其限制是仅允许在线性表的一端举行插入和删除利用,不允许在其他位置举行添加、查找、删除等利用
  • 先进后出(即先存进去的元素,要在他反面进去的元素都出来后,才能取出该元素):比方,子弹压进弹夹,先压进去的子弹在下面,后压进去的子弹在上面,先弹出上面的子弹,然后才能弹出下面的子弹
  • 栈的入口、出口都是在栈的顶端位置

这里要注意两个名词:


  • 压栈(入栈):就是存元素(插入),将寄存器的数据存入栈中
  • 弹栈(出栈):就是取元素(删除),将栈顶元素复制到寄存器,然后删除栈顶元素,原栈顶底下的元素变为新的栈顶
队列



  • 队列(Queue):简称队,同堆栈一样,也是一种运算受限的线性表,其限制的是仅允许在表达一端举行插入,另一端举行删除
  • 先进先出(即先存进去的元素,要先取出来,才能取反面存的元素):比方,火车过山洞,车头先进去,车位后进去;车头先出来,车位后出来
  • 队列的入口、出口各占一侧

数组



  • 数组(Array):是有序的元素序列,数组是在内存中开发一段一连的空间,并在此空间存放元素。就像是一排挤租屋,有100个房间,从001到100每个房间都有固定的编号,通过编号就可以快速找到租房子的人。
    简朴的来说,接纳该布局的聚集,对元素的存取有如下的特点:
  • 查找元素快:通过索引,可以快速访问指定位置的元素

  • 增删元素慢
    指定索引位置增加元素:需要创建一个新数组,将指定新元素存储在指定索引位置,再把原数组元素根据索引,复制到新数组对应索引的位置

    指定索引位置删除元素:需要创建一个新数组,把原数组元素根据索引,复制到新数组对应索引的位置,原数组中指定索引位置元素不复制到新数组中

链表



  • 链表(Linked List):由一系列结点node(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包罗两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地点的指针域。我们常说的链表布局有单向链表与双向链表,这里先容的是单向链表

  • 多个节点之间,通过地点举行毗连。比方,老鹰捉小鸡时,小鸡们依次拉着上一个人,这样多个人就连在一起,被母鸡掩护在反面了
  • 查找元素慢:想查找某个元素,需要通过毗连的节点,依次向后查找指定元素
  • 增删元素快
    增加元素:只需要修改毗连下个元素的地点即可

    删除元素:只需要修改毗连下个元素的地点即可

红黑树



  • 有序树(Ordered Tree):树中任意节点的子结点之间有顺序关系
  • 二叉树(Binary Tree):每个节点最多含有两个子树的有序树,双方分别根据左右被称为“左子树”和“右子树”
  • 二叉排序树(Binary Sort Tree):又称二叉查找树(Binary Serach Tree),是一种具有特殊性质的二叉树
  • 红黑树(Red Black Tree):是一种自平衡的二叉查找树
二叉树的额外要求:

  • 每个节点最多有两颗子树,所以二叉树中不存在度大于2的节点
  • 左子树和右子树是有顺序的,序次不能任意颠倒
  • 纵然树中某个节点只有一颗树,也要区分它是左子树照旧右子树
二叉树示例:

二叉排序树的额外要求:

  • 若左子树不为空,左子树上所有节点的值均小于或即是它的根结点的值
  • 若右子树不为空,右子树上所有节点的值均大于或即是它的根结点的值
  • 左、右子树也分别为二叉排序树
二叉排序树示例:

红黑树的额外要求:

  • 节点必须是玄色大概赤色
  • 根结点是玄色
  • 所有叶子结点(叶子是NIL节点)都是玄色
  • 每个赤色节点的所有子节点都是玄色
  • 任何一个节点到其每一个叶子节点的所有路径上玄色节点数相同
红黑树的特点:速度特别快,趋近平衡树,查找叶子元素最少和最多次数不多于两倍
红黑树示例:


来源:https://blog.csdn.net/qq_35132089/article/details/112000014
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )