目的 : 加强类与对象的内存分配理解, 加强操作能力, 理解数据结构.
结构 : 数据元素之间的关系.
数据结构 : 带有结构的数据对象.
线性结构: 各数据元素之间的逻辑以用一个线性序列简单的表达出现. 反之为非线性结构.
按逻辑结构分为 : 线性结构与非线性结构.
线性结构包括: 线性表 - 数组(顺序表), 链表(链式表)+ 单链, 双链
线性表 - 队列, 栈
非线性结构包括: 树, 图
线性表:
线性表的顺序存储结构:(数组)
用一组地址连续存储空间, 一次存储线性表的数据元素.
特点:
物理上相邻的数据元素, 存储的位置也相同.
线性表的链式存储结构:(链表)
用一组任意存储单元, 存放线性表的数据元素, 并通过指针相连接结点的序列. 第一个元素为头结点(头结点必须保护起来不能移动, 可以使用第三变量保存, 然后使用第三变量进行实际操作). 最后一个为尾结点.
结点包含 数据域: 本身存储的信息.
指针域(链域, 引用域): 存储后继元素的存储地址.
栈: 限定只能在表的一端进行插入和删除的线性表.
栈顶: 允许入栈出栈的一端.
栈底: 不允许入栈出栈的一端.
特点: 先进后出 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 层有叶子结点, 并且叶子结点都是从左到右依次排布.
一棵树如果是满二叉树, 那么它一定是完全二叉树, 一棵树如果是完全二叉树, 它不一定是满二叉树.
(小左大右)
二叉树的遍历:先序: 根 左 右 若二叉树非空, 则访问根结点, 按先序遍历左子树, 再遍历右子树.
中序: 左 根 右 若二叉树非空, 按中序遍历左子树, 再访问根结点, 再按中序遍历右子树.
后序: 左 右 根 若二叉树非空, 按后序遍历左子树, 再遍历右子树, 再访问根结点.
二叉树的删除:无左无右: 分为: 根结点 非根结点, 但是是叶子结点(分为: 左叶子 右叶子)
有左无右: 分为: 根结点 非根结点(分为: 左结点 右结点)
有右无左: 分为: 根结点 非根结点(分为: 左结点 右结点)
有左有右: 分为: 根结点 非根结点(分为: 左结点 右结点)(判断是要上移左结点的最右边或右结点的最左边)
来源: https://www.cnblogs.com/798911215-Darryl-Tang/p/9292166.html