数据结构浅谈

April 12, 2020 4989

结构的分类

逻辑结构

  1. 集合结构：每个元素平等，相互之间没有关系
  2. 线性结构：元素之间，一对一的关系
  3. 树形结构：一对多
  4. 图形结构：多对多

物理结构

  1. 顺序存储结构：地址连续的存储单元
  2. 链式存储结构

算法

五大特性

输入、输出、有穷性、确定性和可行性

设计要求

  • 正确性：没有语法错误（基本）-> 合法输入得到输出结构（核心）-> 非法输入、异常捕捉（优秀）-> 对特殊情况的处理（bonus）
  • 可读性
  • 健壮性
  • 时间、空间效率高

时间复杂度

O(1) < O(logN) 对数阶，二分法< O(n) < O(NlogN) < O(n^2) < O(n^3) < O(2^n) 指数阶< O(n!) < O(n^n)

线性表

定义和特性

0个或多个数据元素的有限序列
第一个元素无前驱，最后一个元素无后继，其余每个元素都有且仅有一个前驱和一个后继

操作

  • 创建和初始化
  • 检查是否为空
  • 清空
  • 根据索引取元素
  • 查找元素
  • 插入元素
  • 删除制定索引的元素
  • 返回当前长度

存储

  1. 顺序存储
    用一段地址连续的存储单元一次存储线性表的数据元素
    优点：
  • 存取元素方便
  • 无须空间存储元素间的关系
    缺点：
  • 插入和删除操作需要移动大量元素
  • 当线性表长度变化较大时，难以确定存储空间容量
  • 造成存储空间的“碎片”
  1. 链式存储
    优点：
  • 插入、删除方便
  • 个数灵活不受限
    缺点：
  • 存取不易

单链表

用一组任意的存储单元存放线性表的元素

静态链表

用数组描述链表，又称游标实现法
优点：插入删除快
缺点：内存分配问题没有解决，存取不易

循环链表

终端节点的指针端由空指针改为头节点，使整个单链表形成一个头尾相接的环。

双向链表

在每个结点再设置一个指向其前驱节点的指针域

栈

定义和特性

仅在表尾进行插入和删除操作的线性表
**先进后出(last in first out, LIFO)**，栈顶(top, 操作端，表尾)，栈低(bottom，表头，固定的)
插入，进栈
删除，出栈

1
2
3
4
5
6
数字1，2，3依此进栈，会有几种出栈次序？
1. 123进，321出 -> 321
2. 12进，21出，3进，3出 -> 213
3. 12进，2出，3进，31出 -> 231
4. 1进，1出，23进，32出 -> 132
5. 1进，1出，2进，2出，3进，3出 -> 123

实现

  • 顺序存储结构，用数组实现
  • 两栈共享空间
  • 链式存储

应用

  1. 实现递归
  2. 四则运算表达式求值
    后缀（逆波兰）表示法：一种不需要括号的算式表达法
    1. 将中缀表达式转为后缀表达式
      从左到右遍历表达式中缀表达式中的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号，则栈顶元素依次出栈并输出，将当前符号进栈，直到最终输出后缀表达式为止
    2. 计算值
      从左到右遍历表达式后缀表达式中的每个数字和符号，遇到数字就进栈，遇到符号将栈顶两个数字出栈进行运算，结果进栈，一直到获得最终结果 
      1
      2
      3
      9+(3-1)*3+10/2
      1. 9 3 1 - 3 * + 10 2 / +
      2. 20

队列

定义和特性

只允许一端进行插入操作、另一端进行删除操作的线性表
**先进先出(first in first out,FIFO)**，队头（允许删除），队尾（允许插入）
插入，入队
删除，出队

实现

  1. 顺序存储，采用循环队列，用两个指针front和rear实现
  2. 链式存储

串

KMP模式匹配算法了解一下？

树

定义

n (n>=0) 个结点的有限集
n = 0，空树
根只有一个
子树互不交叉

分类

度(Degree)：结点拥有的子树数
度 = 0，叶结点(Leaf) / 终端结点
度 != 0，分支结点 = 根结点 + 内部结点
树的度 = 树内各结点的度的最大值

结点之间的关系

父(Parent)、子(Child)、兄弟(Sibling)

其他概念

  • 层次 (Level)
  • 深度 (Depth) / 高度
  • 次序 = 有序树 + 无序树

表示法

  1. 双亲表示法
    • 每个结点存储当前值和父亲的位置
    • 查找父亲很方便，但是查找子很麻烦
  2. 多重链表表示法
    • 每个结点有多个指针域，每个指针指向一个子树的根结点
    • 方案一：指针域的个数 = 树的度
    • 方案二：当前结点指针域的个数 = 当前结点的度
  3. 孩子表示法
    • 把每个结点的子结点排列起来，以单链表作存储结构
  4. 兄弟姐妹表示法
    • 每个结点存储第一个孩子和它的右兄弟
    • 找子结点方便
    • 优化：加parent指针域来查找父亲

二叉树

特点

  • 每个结点最多两棵子树
  • 子树是有序的，左右不同

基本形态

  • 空树
  • 只有一个根结点
  • 根结点只有左子树
  • 根结点只有右子树
  • 根结点既有左子树又有右子树

特殊二叉树

  • 斜树：所有结点都只有左/右子树
  • 满二叉树：所有的分支结点都存在左子树和右子树，且所有的叶子结点都在同一层上。（叶子结点只出现在最下一层；非叶子结点的度 = 2；同样深度的二叉树，满二叉树的结点个数最多，叶子树最多）
  • 完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同。（叶子结点只出现在最下两层；最下层的叶子一定集中在左部连续位置；倒数二层，若有叶子结点，一定在右部连续位置；(结点度 == 1) => 该结点只有左子树；同样结点的二叉树，完全二叉树的深度最小）

性质

  • 二叉树的第i层，至多有2^(i-1)个结点
  • 深度为k的二叉树至多有2^k-1个结点
  • 对任一二叉树，given其终端结点数n0，度为2的结点数n2 => n0 = n2 + 1
    —————- 完全二叉树 —————-
  • 具有n个结点的完全二叉树的深度 = floor(lnN) + 1
  • 如果对一棵有n个结点的完全二叉树的结点按层序编号，对任一结点i有：
    • i == 1 => i == root || i > 1 => parent of i == floor(i/2)
    • 2i > n => i == leaf || left child of i == 2i
    • 2i + 1 > n => i has no right child || right child of i == 2i + 1

存储结构

  1. 顺序存储
  2. 二叉链表

遍历方法

  1. 前序遍历：根 -> 左 -> 右
  2. 中序遍历：左 -> 根 -> 右
  3. 后序遍历：左 -> 右 -> 根
  4. 层序遍历

已知前序遍历序列和中序遍历序列 ===> 唯一确定一棵二叉树
已知后序遍历序列和中序遍历序列 ===> 唯一确定一棵二叉树
已知前序遍历序列和后序遍历序列 =X=> 唯一确定一棵二叉树

赫夫曼树

赫夫曼编码

图

定义

由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为 G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合

图中数据元素称为顶点（Vertex）

顶点集合V有穷非空

顶点之间的逻辑关系用边来表示，边集可以为空

无向边：若顶点vi, vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶对 (vi, vj) 来表示

无向图：图中任意两个顶点之间的边都是无向边

有向边：若从顶点vi到 vj的边有方向，则称这条边为有向边，也称为弧（Arc），用<A,D>来表示，A是弧尾，D是弧头，弧从A指向D

有向图：图中任意两个顶点之间的边都是有向边

简单图：图中不存在顶点到其自身的边，且同一条边不重复出现

无向完全图：任意两个顶点之间都存在边的无向图，含有n个顶点的无向完全图有n*(n-1)/2条边

有向完全图：任意两个顶点之间都存在方向互为相反的两条弧的有向图，含有n个顶点的有向完全图有n*(n-1)条弧

权：与图的边或弧相关的数

网：带权的图

子图：假设有两个图G=(V,{E})和G’=(V’,{E’})，如果V’⊆V，E’⊆E，则称G’为G的子图

图的顶点与边间关系

对于无向图G=(V,{E})，如果边(v,v’)∊E，则称顶点v和v’互为**邻接点(Adjacent)，即v和v’相邻接。边(v,v’)依附(incident)于顶点v和v’，或者说(v,v’)与顶点v和v’相关联。顶点v的度(Degree)**是和v相关联的边的数目，记为TD(v)。图的边数其实就是各顶点度数和的一半，e=∑TD(v)/2。

对于有向图G=(V,{E})，如果弧<v,v’>∊E，则称顶点v邻接到顶点v’，顶点v’邻接自顶点v。弧<v,v’>和顶点v，v’相关联。以顶点v为头的弧的数目称为v的**入度(InDegree)，记为ID(v)；以v为尾的弧的数目称为v的出度(OutDegree)**，记为OD(v)；顶点v的度为TD(v)=ID(v)+OD(v)。有向图的弧数等于各顶点的出度，也等于各顶点的入度，e=∑ID(v)=∑OD(v)。
无向图G·(V.{E》)中从顶点v到顶点V的路径(Path)是一个顶点序列。

路径的长度是路径上的边或弧的数目。

环/回路：第一个顶点到最后一个顶点相同的路径。

简单路径：序列中顶点不重复出现

简单环/简单回路：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。

连通：在无向图种，两个顶点之间有路径，则称它们是连通的。如果任意两个顶点都连通，则该图为连通图。

连通分量：无向图中的极大_连通_子图。

强连通图：有向图中，两两顶点之间存在路径。

强连通分量：有向图中的极大_强连通_子图。

连通图的生成树：一个极小的连通子图，它还有图中的全部n个顶点，但只有足以构成一棵树的n-1条边。

有向树：一个有向图，恰有一个顶点的入度为0，其余顶点的入度均为1。

有向图的生成森林：由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。

图的表示方式

  1. 矩阵 2[n][n]
  2. 二维数组 2[n][0-n]
    …

查找

查找的方法

  1. 折半查找, mid = (low + high) / 2
  2. 插值查找, mid = low + (high - low) * (key - a[low])/ (a[high] - a [low])
  3. 斐波那契查找, mid = low + F[k-1] - 1

线性索引查找

  1. 稠密索引，一一对应
  2. 分块索引，块内无序，块间有序
  3. 倒排索引，次关键码为key，序号为值

二叉排序树 / 二叉查找树

若左子树不空，则左子树上所有结点的值均小于它的根结构的值；
若右子树不空，则右子树上所有结点的值均大于它的根结构的值；
左、右子树都为二叉排序树。
平衡二叉树：每一个节点的左子树和右子树的高度差至多=1

多路查找树

每一个结点的孩子数 > 2，每一个结点可以存储多个元素

  1. 2-3树：每一个结点都具有两个孩子（2结点）或三个孩子（3结点），2结点包含一个元素和两个孩子，左子树所有元素小于此元素，右子树所有元素大于此元素，3结点包含两个元素和三个孩子，左子树所有元素小于较小元素，右子树所有元素大于较大元素，中间树包含介于两者之间的元素
  2. 2-3-4树：有2结点，3结点和4结点

B树

B树是一种平衡的多路查找树，结点最大的孩子数目称为B树的阶（Order）