数据结构

Jun 22, 2015

版权声明：本文为博主原创，未经作者许可谢绝转载。
如有任何疑问或者建议，请联系 xiangchen.cs@gmail.com

线性结构

数组与链表

操作 数组 链表
构造 $O(1)$ $O(1)$
销毁 $O(1)$ $O(n)$
取元 $O(1)$ $O(n)$
插入 $O(n)$ $O(1)$
删除 $O(n)$ $O(1)$
优点 可随机存取 插入删除快，空间效率高

循环链表：从任何节点出发可以遍历链表。

双向链表：快速访问前驱。

其他

稀疏矩阵（通常认为稀疏因子（非零元素占比）不超过 0.05 的矩阵）的存储方式：三元组，十字链表（同一行的非零元通过 right 域链接成一个循环链表，同一列的非零元通过 down 域链接成一个循环链表）。

比较 顺序栈 链式栈
空间 需要初始化规模，空间利用率低 无需初始化规模，空间利用率高
操作 进出栈 $O(1)$，清空栈 $O(1)$ 进出栈 $O(1)$，清空栈 $O(n)$

栈的应用：括号匹配，后缀表达式，递归，回溯

队列的应用：缓冲

为了提高顺序栈的空间利用效率，可以将顺序栈做成双栈。

为了提高顺序队列的空间利用效率，可以将顺序队列做成循环队列。

树

基本概念与性质

节点的度：节点的子节点个数

树的度：树中所有节点的度的最大值

满二叉树：深度为 $h$，节点数为 $2^h-1$ 的二叉树

完全二叉树：深度为 $h$，且仅 $h$ 层从右向左连续缺若干节点的二叉树

树的性质：

  • 节点数目 = 节点度数之和加 1
  • 二叉树叶子节点个数 = 度为 2 的节点个数加 1
  • 从 0 开始对完全二叉树的节点依次编号，则节点 n 的左孩子是 2n+1，右孩子是 2n+2

完全二叉树可用顺序存储

树的存储：广义表、双亲表示、左孩子右兄弟

遍历

  • 先中后序：可递归实现，可用显式栈替代递归
    • 非递归先序遍历：访问根节点；右节点入栈；左节点存在则转向左节点，否则转向栈顶元素
    • 非递归中序遍历：当前节点入栈；左节点存在则转向左节点；否则访问栈顶元素，并转向栈顶元素右节点
    • 非递归后序遍历：当前节点入栈并置左标志；左节点存在则转向左节点；否则取出栈顶元素，若为左标志则置右标志放回栈内并转向右节点，若为右标志则访问节点并转向栈顶元素
  • 层序：可用队列实现

由二叉树的前序序列和中序序列可唯一地确定一棵二叉树

堆

  • 若节点值小于子节点值：自顶向下堆化：$O(h)$
  • 若节点值大于父节点值：自底向上堆化：$O(h)$
  • 自顶向下堆构造：向堆尾插入新节点，调用自底向上堆化操作：$O(N\log N)$
  • 自底向上堆构造：从 $n/2$ 位置反向遍历数组，调用自顶向下堆化操作：$O(N)$

可用于实现优先级队列

图

图的相关问题和算法见另一篇博文。

参考资料：

清华大学电子系吴及老师课件