java数据结构

2022-07-18

java数据结构

自信,坚定信念,throw

数据结构

逻辑结构

  1. 线性结构
  2. 集合结构
  3. 树形结构
  4. 图形结构

物理结构(存储结构)

  1. 顺序存储结构
  2. 链式存储结构

数据类型

一组性质相同的值的集合及定义在此集合上的一些操作的总称

比如说基本数据类型int,自定义的类

抽象数据类型

一个数字模型及定义在该模型上的一组操作

比如说抽象类

线性表(List)

]

特征:一一对应的关系

顺序存储方式线性表

ArrayList 内层为数组结构
(增删改查)

链式存储方式线性表

用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。

里面有一个属性data,用来存储当前元素的对象,还有一个属性next,存放下一个元素的地址(即指向下一个元素的对象)
还有一个属性previous存放上一个元素的地址(即指向上一个元素的对象)(双向链表)

栈(Stack)

栈底就是第一个进栈的数据,栈顶就是最后一个进栈的数据。

波兰表达式(中缀表达式)标准四则运算表达式

逆波兰表达式(后缀表达式)计算机采用的方式

例如:931-3*+10 2/ +

第一步:923*+10 2/ +

第二部:96+10 2/ +

第三步:15 10 2/ +

第四步:15 5 +

第五步:20

利用栈来实现,数字依次入栈,运算符不入栈,遇到运算符,将临近两个元素出栈进行运算后,再入栈。

如何将中缀表达式转后缀表达式

	数字输出,运算符进栈,括号匹配出栈,栈顶优先级低出栈,(直到遇到比他更小的停止)?。

队列(queue)

单端队列,只允许在一端插入,一端删除

插入的一端称为队尾,删除的一端称为队头

队列是用链式存储结构实现的

查找表(Map)

见jsd1802笔记

树(Tree)

树是n(n>=0)个节点的有限集。n=0时称为空树。结合两种存储方式存储

结点的度

	结点拥有的子树数称为结点的度。

	度为0的结点称为叶子结点或终端结点
	度不为0的结点称为分支结点或非终端结点。
	除根节点以外,分支结点也称为内部结点。
	树的度是树内各结点度的最大值

层次与深度

	层次从根定义起,根为第一层
	树中结点的最大层次为树的深度或高度,即层数有多少,深度就是多少

有序与无序

	如果将树中结点的各子树看成从左至右是有次序的,不能互换的,则称该树为有序树,否则为无序数

森林

	森林是m颗互不相交的树的集合

存储方式

双亲表示法,在每个结点中,附设一个指示器指示其双亲结点到链表中的位置

孩子表示法 1

	每个结点是一个数组表示,数组的长度为(树的度+1)
	数组的第一个元素代表自己,以后的元素依此代表孩子,有几个孩子存几个,多余的为空

孩子表示法 2

	动态分配数组空间,没有空

最终方案

	把每个结点的孩子结点排列起来,以单链表作为存储结构,则n个结点有n个孩子链表,
	如果是叶子结点,则此单链表为空,
	然后所有的n个头指针又组成一个线性表,采用顺序存储结构,存放在一个一维数组中。

;

孩子兄弟表示法

	每个结点两个属性,一个表示该结点的第一个子结点,一个代表该结点的右兄弟结点。

;

二叉树,每个结点的度最大为2的树(44.44)


标题:java数据结构
作者:mahaonan
地址:https://mahaonan.fun/articles/2022/07/18/1658147079787.html