荣新教育:坚持面授的良心机构
全国咨询热线:400-1335-066
您现在的位置:首页>行业新闻 > 正文

Java数据结构分析

时间:2018-07-11 16:55:46 来源:荣新IT教育培训 作者:荣新科技
挺久没给大家分享关于java的知识了,今天来给大家分享下,因为最近学习Linux的同学比较多,很多专业知识也比较侧重这块。今天荣新教育来给大家分享下关于Java数据结构的一些基础知识,算是给小白的福利吧。
Java数据结构分析
目的 : 加强类与对象的内存分配理解,加强操作能力、理解数据结构。结构 : 数据元素之间的关系。

数据结构 : 带有结构的数据对象。

线性结构: 各数据元素之间的逻辑以用一个线性序列简单的表达出现。反之为非线性结构。

按逻辑结构分为 : 线性结构与非线性结构。

线性结构包括:线性表-数组(顺序表)、链表(链式表)+单链、双链

线性表-队列、栈

非线性结构包括:树、图

线性表:

线性表的顺序存储结构:(数组)

用一组地址连续存储空间,一次存储线性表的数据元素。

特点:

物理上相邻的数据元素,存储的位置也相同。

线性表的链式存储结构:(链表)

用一组任意存储单元,存放线性表的数据元素,并通过指针相连接结点的序列。第一个元素为头结点(头结点必须保护起来不能移动,可以使用第三变量保存,然后使用第三变量进行实际操作)。最后一个为尾结点。

结点包含 数据域: 本身存储的信息。

指针域(链域、引用域):存储后继元素的存储地址。

栈: 限定只能在表的一端进行插入和删除的线性表。

栈顶: 允许入栈出栈的一端。

栈底: 不允许入栈出栈的一端。

特点: 先进后出 First In Last Out

队列: 限定只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。

对首: 删除的一端(出队)

队尾: 插入的一端(入队)

特点: 先进先出 First In First Out

建立链表:①先确定头引用对象 ②在建立表的过程中,每一个数据元素中含指向下一个数据元素的地址。

建立链表的方法:①前插法 ②尾插法 ③插入两个结点之间。

单链表:若链表中的结点包含一个指针域指向后继结点。

缺点:只能顺着结点的直接后继查询结点。

双链表:链表中的结点都包含了两个引用,分别指向直接前驱和直接后继。

双链的组成:数据域、直接前继、直接后继

单链与双链的区别: 单链表是单向访问的,而双链表是可以双向访问的。

单链表的删除,必须知道直接前驱,而双链表的删除,只需知道删除的结点。

顺序表(数组)与链表的区别:

① 存储空间的区别,数组是静态分配内存空间的,所有元素是存放在一组地址连续的存储单元中,一旦分配,不可更改,不便于扩展,数据元素在数组中的顺序号可确定它在存储单元中的位置。因此顺序表中不需要指针域,而链表是动态分配内存空间的,存储空间是不确定的。

② 数组便于查找和修改(下标定位),但不利于插入和删除(数据移动量过大),也不便于扩充(连续的地址,静态存储结构)。而链表不便于查找和修改(从链头到链尾数据量过大),但便于插入和删除并且速度快(断链即可)。

树 : N(N>0)个结点的有限集合。有且仅有一个根结点。

根结点:一棵树中没有父结点的结点。

叶子结点(终端结点):一棵树中没有子结点。

兄弟结点:同一个父结点的所有结点。

结点度(分支度):每一个所拥有结点的个数。

树的度(树的分支度):一棵树中最大的结点。

祖先:由某个结点X到根结点之路径上的所有结点,均为X结点的祖先。

二叉树(二次树或二分树):结点最多只有两个。

二叉树要满足的条件:①有且仅有称为根的结点。

②其余结点分为两个互不相交的集合,称为左子树和右子树。

在二叉树中,第i层的结点总数不超过2^(i-1);

满二叉树:树中所有结点均在同一阶层而其他非终端结点度均为“2”,树的高度为K,其结点为2^K - 1;

完全二叉树:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层有叶子结点,并且叶子结点都是从左到右依次排布。

一棵树如果是满二叉树,那么它一定是完全二叉树,一棵树如果是完全二叉树,它不一定是满二叉树。

(小左大右)

二叉树的遍历:①先序:根 左 右 若二叉树非空,则访问根结点,按先序遍历左子树,再遍历右子树。

②中序:左 根 右 若二叉树非空,按中序遍历左子树,再访问根结点,再按中序遍历右子树。

③后序:左 右 根 若二叉树非空,按后序遍历左子树,再遍历右子树,再访问根结点。

二叉树的删除:①无左无右:分为: 根结点 非根结点,但是是叶子结点(分为:左叶子 右叶子)

②有左无右:分为: 根结点 非根结点(分为:左结点 右结点)

③有右无左:分为: 根结点 非根结点(分为:左结点 右结点)

④有左有右:分为: 根结点 非根结点(分为:左结点 右结点)(判断是要上移左结点的最右边或右结点的最左边)
文章源自荣新教育官网:www.vfast.com.cn欢迎访问,转载需注明出处