基于常见数据结构整理

数据结构

数据存储的常用结构有：栈、队列、数组、链表和红黑树

栈

1.stack,又称堆栈，它是运算受限的线性表。

2. 其限制是仅允许在标的一端进行插入和删除操作，不允许在其他任何位置进行添加、查找、删除等操作。
   先进后出（即，存进去的元素，要在后它后面的元素依次取出后，才能取出该元素）

• 打个比方：
  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.结点可以是红色的或者黑色的

2. 根结点是黑色的。

3. 叶子结点(特指空结点)是黑色的。

4. 每个红色结点的子结点都是黑色的。

5. 任何一个结点到其每一个叶子结点的所有路径上黑色结点数相同。
   二叉树的特点
   速度特别快,趋近平衡树,查找叶子元素少和多次数不多于二倍。

二叉树的存储形式：

• 顺序存储：
  完全二叉树：对结点按照上至下，从左到右的次序进行存储。

图片.png

• 链式存储
  二叉树结点由一个数据元素和分别指向其左，右子树的两个分支构成。
  表示二叉树的链表中的结点至少包含3个域：数据域，左，右指针域（双向指针）

图片.png