基于常见数据结构整理
数据结构
数据存储的常用结构有：栈、队列、数组、链表和红黑树
栈
1.stack,又称堆栈，它是运算受限的线性表。
- 其限制是仅允许在标的一端进行插入和删除操作，不允许在其他任何位置进行添加、查找、删除等操作。
先进后出（即，存进去的元素，要在后它后面的元素依次取出后，才能取出该元素）
- 打个比方：
1. 压栈（存元素）：（小时候玩玩具枪的时候，先装的子弹在最下方，后装的子弹在最上方）。
2. 弹栈（取元素）：（最上方的子弹先打出去，然后才是下面的子弹逐个打出去）。
队列
- queue,简称队，同样也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入， 而在表的另一端进行删除。
- 队首：允许进行删除的一端（先进去的）。
- 队尾：允许进行插入的一端（最后进入的）。
- 队列中没有元素时称为空队列。
先进先出（存进去的元素，要在后它前面的元素依次取出后，才能取出该元素）。
例如：小火车过山洞（中间的部分不能进行操作）
入队：车头先进去，车尾后进去；
出队：车头先出来，车尾后出来。
数组
有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间存放元素。
例如：一个班级的学号最后两位数的，大多情况下的班级30人：都是从1到30固定到每个学生，但是数组索引只是从0开始的。
数组的特点
查询快，增删慢。
查询元素：
查询数组的元素是根据索引直接查找该元素
增加元素：
增加元素时需要创建新数组，将指定新元素存储在指定索引位置，再把原数组元素根 据索引，复制到新数组对应索引的位置。
图片.png
删除元素：
指定索引位置删除元素：需要创建一个新数组，把原数组元素根据索引，复制到新数组对应索引的位 置，原数组中指定索引位置元素不复制到新数组中
图片.png
链表
链表:linked list,由一系列结点node（链表中每一个元素称为结点）组成。
- 结点可以在运行时i动态生成。
-
每个结点包括两个部分：
一个是存储数据元素的数据域，
另一个是存储下一个结点地址的指针域。
也就是说：链表结构有单向链表与双向链表。 -
单向链表：
多个结点之间，通过地址进行连接。
图片.png -
例如：多个人手拉手，每个人使用自己的右手拉住下个人的左手，依次 类推，这样多个人就连在一起了。
图片.png
链表的特点
增删快，查询慢。
- 查找元素慢：
想查找某个元素，需要通过连接的节点，依次向后查找指定元素。（从第一个元素开始向后逐个查询） - 增删元素：
1.增加元素
只需要修改连接下个元素的地址即可。
图片.png
-
删除元素：也只需要修改下一个地址即可
图片.png
树
1.树的定义
n(n>=0)个结点的有限集T.
- n=0:空树
- n=1:有且仅有一个结点的树，称为树的根。
- n>=2:其余节点可分为m(m>0)个互不相交的有限集T1，T2，...Tm。其中每一个集合本身就是一棵树，称为根的子树。
子树： - 子树是相交的
- 除了根结点外，每个结点都只有一个父结点
- 一棵N个结点的树，共有N-1条边。
2.树的基本术语
- 结点---表示树的元素，包含数据元素及其若干指向其子树的分支。
- 结点的度---结点拥有的子树数。
- 叶子(终端节点)---度为零的结点。
- 分支结点---度不为零的结点。
- 树的度---一棵树中最大的结点度数。
- 孩子---结点子树的根称为该节点的孩子。
- 双亲---孩子结点的上层结点叫该结点的双亲。
- 兄弟---同一双亲的孩子。
- 祖先结点---从根结点到该结点路径上所有结点。
- 子孙结点---一个结点的直接后续和间接后继。
- 结点的层次---从根结点算起，根为第一层，它的孩子为第二层.......
- 深度---树中的最大层次数。
树型结构与线性结构的区别
- 线性结构：
第一个元素（无前驱），最后一个数据元素无后继，其他数据元素（一个前驱，一个后继）。 - 树型结构：
根结点（无前驱），多个叶子结点（无后继），其他数据元素（一个前驱，多个后继）。
树的存储结构 孩子表示法
- 孩子链表：
每个结点的孩子结点用单链表存储，在用含n个元素的结构数组指向每个孩子链表。
树的存储结构 孩子兄弟表示法
- 实现：设计统一的结点结构，没个结点的两个指针域指向其第一个孩子结点和下一个兄弟结点。
- 特点：
操作容易，空间浪费少。
二叉树：
也叫做红黑树，binary tree ,是每个结点不超过2的有序树（tree）。
图片.png
二叉树的子树有五种基本的形态
注意：二叉树的子树有左右之分
图片.png
二叉树的性质
在二叉树的第i层上至多有2^(i-1)个结点(i>=1)。
深度为k的二叉树至多有2^k -1个结点(k>=1)。
对任何一棵二叉树T，如果其终端结点数为N0，度为2的结点数位N2，则N0=N2+1。
具有N个结点的完全二叉树的深度为[log2 N]+1。
图片.png
二叉树的约束：
1.结点可以是红色的或者黑色的
根结点是黑色的。
叶子结点(特指空结点)是黑色的。
每个红色结点的子结点都是黑色的。
任何一个结点到其每一个叶子结点的所有路径上黑色结点数相同。
二叉树的特点
速度特别快,趋近平衡树,查找叶子元素少和多次数不多于二倍。
二叉树的存储形式：
- 顺序存储：
完全二叉树：对结点按照上至下，从左到右的次序进行存储。
图片.png
- 链式存储
二叉树结点由一个数据元素和分别指向其左，右子树的两个分支构成。
表示二叉树的链表中的结点至少包含3个域：数据域，左，右指针域（双向指针）
图片.png
