数据结构复习记录

基本概念

线性表

线性表是最简单也最常用的一种数据结构，是由n($n\ge 0$)个类型相同的数据元素组成的有限序列，是一种逻辑结构，有两种表示方式（即存储结构）：顺序表示和链式表示。

栈和队列

栈：一种只能在一端进行进行插入和删除操作的线性表。特点：后进先出，存储结构：顺序存储和链式存储。
队列：一种运算受限的线性表，插入在队尾，删除在队头。特点：先进先出，存储结构：顺序、链式。

字符串

由n($n\ge 0$)个字符的顺序排列所组成的线性表。一般会在串的最后添加一个结束标记'\0'表示串的结尾。

数组

数组分为一维数组和多维数组。一维数组是相同类型的元素在连续存储空间上的排列的集合。

数组的压缩存储

稀疏矩阵：非零元素的个数远小于零元素个数，可由如下方式表示：

• 三元组表：通过(行下标、列下标、值)三元组来唯一的表示一个元素，属于顺序存储结构。
• 十字链表：每个节点保存(head, value, row, column, down, right)这六个值，down和right分别指向行和列上的下一个非零元素，属于链式存储结构。

树

树是n($n\ge 0$)个节点的有限集合。

存储表示法有：

• 双亲表示法：每个节点保存(data, parent)，顺序存储。
• 子女链表示法：每个节点保存(data, first)，first指向子女链表，每个节点顺序存储。
• 子女兄弟链表表示法：树的二叉树表示法，每个节点保存(data, first_child, firs_brother)，其实就是转一个角度看。
• 广义表表示法：(A(B(D(G,H,I)),C(E,F)))
  

二叉树

一些特殊的二叉树：

存储结构可以是线性或者链表，线性适合满二叉树或者完全二叉树，否则会造成空间浪费。

二叉树的一些特性：

• 第$i(i\ge 1)$层，至多有$2^{i-1}$ 个节点。
• 深度为$k(k\ge 1)$，节点个数n：$k\le n\le 2^k-1$
• 叶节点数等于度为2的节点的个数+1（数学归纳法可以证明）
• n节点完全二叉树的深度为$lo{g}_2(n+1)$向上取整。

树、森林

树、森林、二叉树的转换：都是唯一的

• 森林->二叉树：就是先把每棵树转化为二叉树，由于这样得到的二叉树的根节点没有右子节点，所以把第n棵树作为n-1棵树的右子节点即可。
• 二叉树->树/森林：如果右子节点为空，直接转化为树，否则先拆成n个右子节点为空的二叉树，再转化为森林

树的遍历：

• 深度优先
  • 先序遍历
  • 后序遍历
• 广度优先

森林的遍历：

• 深度优先
  • 先序遍历：先访问第一个树的根，然后第一棵树的子树，然后其他树
  • 中序遍历：先访问第一棵树的子树，第一棵树的根，然后其他子树
• 广度优先

树和森林的先序遍历、中序遍历、后序遍历、广度优先遍历都和转化为的二叉树的结果一致。非常巧妙！！！

哈夫曼树

权重小的路径更长。

图

由顶点集合V和顶点间的关系集合E组成的一种数据结构。存储结构有

• 邻接矩阵
• 邻接表：每个顶点节点(data, adj)，adj指向一个链表，依次连接和顶点相连的顶点。
• 无向图的邻接多重表表示：每个顶点节点(data, firstout)，firstout指向一个边节点，边节点的结构包括(mark, vertex1, vertex2, path1, path2)，path* 指向依附于vertex*的下一条边。
• 有向图的十字链表表示：顶点节点包括(data, firstin, firstout)，边节点包括(mark, vertex1, vertex2, nextout, nextin)

遍历：深度优先，广度优先

一些概念：

• 强连通图：有向图中，连通且1到2和2到1都有路径。
• 连通分量：非连通图的极大连通子图
• 生成树：一个无向连通图的生成树是它的极小连通子图

最小生成树

• Prim：从1个顶点扩张到所有顶点，每次选取已选顶点和未选顶点中最小的边
• Kruskal：每次选择一个权重最小的、两个顶点分别来自两个连通分量的边，把两个连通分量联合起来，直到只剩一个连通分量。

活动网络

AOV网络：用顶点表示活动的有向图
AOE网络：用边来表示活动的有向图，边上的权值表示活动的持续时间
关键路径：AOE网络上从源点到汇点具有最大长度的路径。特征：最早开始时间等于最晚开始时间。

最短路径

• Dijkstra算法：非负权值的单源最短路径
• Floyd算法：非负权值的所有顶点之间的最短路径

查找

• 顺序查找：又称线性查找
• 折半查找：又称二分查找，前提是有序存储
• 分块查找：又称索引顺序查找，把线性表分块，块中的数据无序存储，块与块之间是有序的（当然不一定要有序存储，只是说一个块中的所有节点必须都小于或大于另一个块的所有节点），再建一个索引表，把每个块的最大关键码作为索引表的关键码，关键码按序存储，即通过二分查找找到所在的块，然后通过顺序查找在块中找到具体的数据。
• 散列查找：又称哈希法或杂凑法，Address=Hash(key)

二叉查找树

节点的值大于左子树，小于右子树。

平衡二叉树（AVL）：平衡的二叉查找树，左右子树高度差不超过1

B树：高度平衡的m叉查找树

B+树：B树的特殊情况，所有关键码都放在叶子节点，上层非叶子节点的关键码是其子树最大关键码的复写。叶节点本身按从小到大的顺序连接。常用于数据库的索引，这样查找到每一个关键码的时间都是固定的。

内排序

• 比较排序：有O(n log n) 下限
  • 冒泡排序：稳定
  • 插入排序：稳定
  • 选择排序：每次选择最小（大）的元素与未排序的部分的最前（后）面的元素交换。因为有交换，所以都不稳定。
    • 直接选择排序：每次选择都把未排序的元素遍历一遍
    • 树选择排序：第一次选择要遍历所有元素，然后构建一个树，数组的元素放在叶子结点，非叶子节点是两个子节点的最小值。之后的每次选择都只要从上次选择的元素所在的叶子结点开始往根节点走一遍即可。
    • 堆排序：其实也是树排序，只不过可以直接在原数组上建立树（堆），节省空间。
  • 希尔排序：gap>1的时候的交换会导致不稳定
  • 快速排序：基准值的选取随机，所以不稳定。递归占据的空间为O(log N)~O(N)
  • 归并排序：稳定，但是要额外创建数组，且有递归，空间复杂度为O(N)
  • 基数排序：从低位到高位比较，稳定
• 非比较排序：没有O(n log n) 下限
  • 计数排序，也叫鸽巢排序，只适用于整数
  • 桶排序：或所谓的箱排序，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。

总结：稳定的只有冒泡、插入、归并、基数。

算法设计与分析