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)

​