数据结构 （不完整待更新）
数据结构与算法
-
定义：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
-
传统上，把数据结构分为 逻辑结构 和 物理结构 。
-
逻辑结构：指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后间关系，而与他们在计算机中的存储位置无关。
-
物理结构：指数据的逻辑结构在计算机存储空间的存放形式。
-
数据结构 = 逻辑结构 + 存储结构
数据结构 = 逻辑结构 + 存储结构 + （在存储结构上的）运算/操作
-
数据的运算:检索、排序、插入、删除、修改等。
逻辑结构
- 分类：线性结构 和 非线性结构 。
- 线性结构：有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。
- 分类：线性结构 和 非线性结构 。
- 线性结构：线性表 、栈 、队列 、串及数组 。
- 非线性结构：树形结构 、图形结构 。
线性表（Linear List）
- 一个线性表是n个具有相同特性的数据元素的有限序列。
- 逻辑结构为线性表的结构，存储结构的顺序表，链表都可以实现。
链表(Linked List)
- 单向链表
- 双向链表
- 循环链表
栈和队列(Stack & Queue)
栈 (Stack)
- 特点：先进后出
队列(Queue)
- 特点：先进先出
树(Tree)
-
结点的度：节点拥有的子树的数目称为 度 。
-
度为0的结点称为 叶子结点 或 终端结点 。
-
度不为0的结点称为 非终端结点 或 分支结点 。除跟之外的分支结点也称为 内部结点 。
-
数内各结点的度的最大值称为 树的度 。
-
结点的 层次 从根开始定义，层次数为1的结点是 根节点 ，其子树的根的层次数为 2 。
-
树中结点的最大层次称为树的 深度 或 高度 。
-
父亲：一个结点的直接前驱结点。
儿子：一个结点的直接后继结点。
兄弟：同一个父亲结点的其他结点。
-
m叉树：树中所有结点最大度数为 m 的有序树称为 m叉数
二叉树（Binary Tree）
-
定义：每个结点的度均不超过2的有序树，称为二叉树（binary tree）。
-
分类：满二叉树 、 完全二叉树。
满二叉树：
a. 高度为k，并且有 2^（k+1） - 1。
b.每一层结点个数，都是上面全部层结点数+1。完全二叉树：
a.若在一颗满二叉树中，在最下层从最右侧起去掉相邻的若干叶子结点，得到的二叉树即为完全二叉数。
b.满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。
-
二叉树的存储结构： 1. 顺序存储结构 和 链式存储结构。
-
二叉树的遍历：按照某种次序访问树中的所有结点，且每个结点恰好访问一次。
- 先序遍历： 根 左子树 右子树
- 中序遍历：左子树 根 右子树
- 后序遍历：左子树 右子树 根
-
二叉查找树（Binary Search Tree）/二叉搜索树/二叉排序树（Binary Sort Tree）
a.特点：左子树（left subtree）上所有结点的值 均小于它的根结点（root）的值，右子树（right subtree）均大于它的根结点（root）的值。
b.对二叉查找树进行中序遍历，就可以得到有序集合。
-
平衡二叉树（Self-balancing binary search tree）：左右两个子树的高度差（平衡因子）的绝对值 不超过1 。
-
红黑树（Red-Black Tree）：一种特殊的 平衡二叉树 。
图（Graph）
物理结构
- 物理结构：物理结构又叫存储结构，指数据的逻辑结构在计算机存储空间的存放形式。
- 分类：**顺序存储 ** 链式存储 索引存储 散列存储 。
- 顺序存储：把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。
- 链式存储：计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。
- 索引存储：所有的存储结点存放在一个区域。另设置一个索引区域存储结点之间的关系。
- 散列存储：又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。
