数据结构与算法回顾 -1：算法的度量和基本数据结构，近期有面试的必看
private static class Node<E> {
E element;
Node<E> next;
Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
public void push(E element) {
first = new Node<E>(element, first);
size++;
}
public E pop() {
if (size == 0) {
throw new UnsupportedOperationException("The stack is empty.");
}
size --;
Node<E> oldFirst = first;
first = oldFirst.next;
return oldFirst.element;
}
public boolean isEmpty() {
return size == 0;
}
}
[](
)3.5.2 题目：
题 1：3 个不同的元素依次进栈，能得到几种不同的出栈序列？
5 种，abc?acb?bac?bca?cba，最后一种如果以 c 开头，那么 ab 必然已经存入了栈中，取出的顺序只能是 ba，即以 c 开头的只有 cba.
题 2：a?b?c?d?e?f?以所给的顺序依次进栈，若在操作时允许出栈，这得不到的序列为？
A?fedbca????B?bcafed????C?dcefba????D?cabdef
这种题应该从每个选项的第一个字母入手，以 C 为例，如果 d 处在第一个，那么说明前面的 a?b?c 肯定已经存在栈中，那么它们必然按照 c?b?a 的顺序出来；
如果题目中的 c?b?a 的出现次序不对，那么就得不到。然后再使用相同的思路判断第二个字符的情况。答案 D
[](
)3.6 队列
[](
)3.6.1 普通队列
队列也是一种线性表，特性是先入先出，队列和栈的主要区别是插入、删除操作的限定不一样。下面是基于 Java 的一种使用链表来实现的队列：
public class Queue<E> {
private Node<E> first, last;
private int size;
private static class Node<E> {
E element;
Node<E> next;
Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
public void enqueue(E element) {
size++;
Node<E> node = new Node<E>(element, null);
if (last == null) {
first = node;
last = node;
return;
}
last.next = node;
last = node;
}
public E dequeue() {
if (size == 0) {
throw new UnsupportedOperationException("The queue is empty.");
}
size--;
E element = first.element;
first = first.next;
return element;
}
public boolean isEmpty() {
return size == 0;
}
}
[](
)3.6.2 双端队列
队首和队尾都允许入队和出队的队列。
[](
)3.6.3 应用:
栈在括号匹配中的应用：与 [([][])] 类似的括号匹配的问题，遇到一个左括号，判断是否合法，若合法就先存在栈中，等待右括号出现，看是否匹配；
栈在表达式求值中的应用：中缀：A+B*(C-D)-E/F，后缀：ABCD-*+EF/-，然后按照计算的规则，依次进栈、出栈即可求得表达式的结果；
栈在递归中的应用：递归函数在求解的时候，要不断返回结果、传入参数等，因此效率不高，可以借助栈将递归问题转换为非递归问题；
队列在层次遍历中的应用:比如遍历二叉树等；
队列在计算机系统中的应用：用于任务分配，当任务无法立刻全部完成的时候，对无法立刻完成的任务，先将其存入到队列中，等待其他任务完成之后再去执行这些任务。
[](
)3.7 背包
背包是一种不支持从中删除元素的集合数据类型，它的目的就是帮助用例收集并迭代遍历所有收集到的元素。使用背包的很多场景可能使用栈或者队列也能实现，但是使用背包可以说明元素存储的顺序不重要。下面的是一份基于 Java 的背包的实现，在这里我们只是在之前栈的代码的基础之上做了一些修改，并让其实现 Iterable 接口以在 foreach 循环中使用背包遍历元素：
public class Bag<E> implements Iterable<E>{
private int size;
private Node<E> first;
private static class Node<E> {
E element;
Node<E> next;
Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
public void add(E element) {
first = new Node<E>(element, first);
size++;
}
public Iterator<E> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<E> {
private Node<E> current = first;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public E next() {
E element = current.element;
current = current.next;
return element;
}
@Override
public void remove() {}
}
public boolean isEmpty() {
return size == 0;
}
}
[](
)4、非线性表
[](
)4.1 树
[](
)4.1.1 概念
根：树的最上层的顶点；
父结点：某个节点上面的节点；
祖先结点：父节点的父节点等；
结点的度：树中结点的子结点个数；
树的度：树中结点的最大度数；
分支结点：度大于 0 的结点；
叶子结点：度等于 0 的结点；
树的高度：树中结点的最大层数
路径：树中两个结点之间所经过的结点序列
路径长度：路径上经过的边的个数
树的路径长度：从树根到每一结点的路径长度之和
森林：多个树就组成了森林，只要把树个根结点删去就成了森林，只要给 n 课树加上结点，就成了树。
[](
)4.1.2 题目
题：一棵有 n 个结点的树，所有结点的度数之和为_______.
问题转换成：一棵有 3 个结点的树，所有结点的度数之和为____.?因为题目是选择，所以应该尽量简化题目。答案 n-1
[](
)4.2 二叉树
二叉树：每个结点的度不大于 2 的树；
满二叉树：除了叶子结点，其他结点的度都为 2，也就是不存在只有 1 个结点的分支；
完全二叉树：相对于满二叉树，它有的结点度不为 2，但是存在的分支的编号与满二叉树相同
image
在上图中左侧的是完全二叉树，右侧的是满二叉树。
说明：所谓的编号就是指每层从左到右，按照满二叉树的形式编号，上面的满二叉树每个结点的值就是它们的编号。这个编号也是我们在使用顺序存储的时候对应数组的下标。
[](
)4.2.1 二叉树的存储结构
1.顺序存储
这种存储方式，可以理解为使用数组存储，注意开始存储的下标是 1，这是为了与二叉树的性质对应，另外有时候我们也可以将数组的第一个元素作为哨兵。顺序存储的基本思想是，按照满二叉树的编号顺序，如果指定编号（其实就是数组的下标）处有结点的话，数组指定位置的值即为结点的值，否则为 0（表示空结点）。当然，也可以在各个元素中存放一些具有具体含义的值。
如图所示的树在数组中的实际存储为：- 1 2 3 0 4 0 5 0 0 6 0（第 0 位不使用）。
2.链式存储
下面是使用 Java 代码实现的一个二叉树，这里每个结点要包含左右两个子结点以及相应的数据实体。显然，
public class Tree<E> {
private Node<E> root;
private static class Node<E> {
E element;
Node<E> leftChild;
Node<E> rightChild;
Node(Node<E> leftChild, E element, Node<E> rightChild) {
this.leftChild = leftChild;
this.element = element;
this.rightChild = rightChild;
}
}
}
[](
)4.2.2 遍历
先序遍历：a.访问根结点 ?b.按照先序遍历左子树 ?c.按照先序遍历右子树
中序遍历：a.按照中序遍历左子树 ?b.访问根结点 ?c.按照中序遍历右子树
后序遍历：a.按照后序遍历右子树 ?b.按照后序遍历左子树 ?c.访问根结点
层次遍历：借助队列，先将根节点入队，然后出队，访问该结点，将其子结点入队，访问其根结点…直到队列为空。
说明：上述三幅图从左到右的遍历方式依次是先序遍历、中序遍历和后序遍历。
作为练习，这里给出遍历二叉树的方法，可以观察一下二叉树的实现，以及中序遍历的时候输出的二叉树的值，其中 outNode() 方法用来输出结点的值：
/* 先序遍历 */
public void former() {
former(root);
}
private void former(Node<Key, Value> node) {
if (node == null) return;
outNode(node); // 先序
former(node.leftChild);
former(node.rightChild);
}
/* 中序遍历，注意中序输出的结果和排序的结果的关系 */
public void center() {
center(root);
}
private void center(Node<Key, Value> node) {
if (node == null) return;
center(node.leftChild);
outNode(node); // 中序
center(node.rightChild);
}
/* 后序遍历 */
public void latter() {
latter(root);
}
private void latter(Node<Key, Value> node) {
if (node == null) return;
latter(node.leftChild);
latter(node.rightChild);
outNode(node); // 后序
}
结论：
可以看出所谓的中序、先序和后序的主要区别就在于输出遍历结果时候的位置；
中序遍历的时候输出结果就是二叉堆的元素的从小到大的排序结果。
那么从上面的操作中可以看出，所谓的中序就是将输出操作夹在了两个递归之间。因此，如果指定的树不是二叉树，而是多叉树，也就是我们使用一个列表来保存各个子结点，那么是没有中序输出的。
[](
)4.2.3 构造二叉树
注意如果只知道二叉树的先序序列和后序序列是无法唯一地确定一棵二叉树的。
image
如图所示的二叉树，它的三种遍历方式：
先序遍历结果是：- ?+ ?a ?* ?b ?- ?c ?d ?/ ?e ?f
中序遍历结果是：a ?+ ?b ?* ?c ?- ?d ?- ?e ?/ ?f
后序遍历结果是：a ?b ?c ?d ?- ?* ?+ ?e ?f ?/ ?-
说明：先序遍历的时候，根结点处在第 1 的位置；中序遍历的时候根节点前面是左子树，后面是右子树；后序遍历的时候，根结点处在最后的位置。可以根据上面的思路，依次进行判断，从而可以写出完整的树。
[](
)4.2.4 二叉树的性质
二叉树的第 i 层上至多有 2i-1 个结点(i>=1)
深度为 k 的二叉树至多有 2k-1 个结点(k>=1)
对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点树为 n2，则 n0=n2+1.
具有 n 个结点的完全二叉树的深度为 (log2n + 1) 向下取整的结果
对于一颗有 N 个结点的完全二叉树的结点按层序编号，对任一结点 i，有
其父结点是 i/2 向下取整的结果
左孩子是 2i，右孩子是 2i+1
[](
)5、图
[](
)5.1 术语
如果两个顶点通过一条边相连，我们就称这两个顶点是相邻的，并称这条边依附于这两个顶点。某个顶点的度数，即为依附于它的边的总数；
如果从任意一个顶点都存在一条路径达到另一个顶点，就成这幅图是连通图；
树是一幅无环图，互不相连的树组成的集合称为森林。
有向图：边是带方向的，假如边是从 A 到 B 的，那么从 A 到 B 可以，从 B 到 A 就不行，直观来讲就是图的边带箭头；
无向图：边不带方向，如果能从 A 到 B 就能从 B 到 A，直观来讲就是图的边不带箭头；
完全图：无向图中任意两个顶点之间都存在边的为无向完全图；有向图中，任意两个顶点之间都存在方向相反的弧的是有向完全图。
顶点的度、入度和出度：顶点的度是依附于该点的边的数目，对于有向图又有入度和出度之分，顶点的度等于入度+出度。
一条有向边的第一个顶点称为它的头，第二个顶点称为它的尾。
在一幅有向图中，两个顶点之间的关系有四种：不相连；存在从 v 到 w 的边；存在从 w 到 v 的边；同时存在从 v 到 w 的边和从 w 到 v 的边。
有向环 是一条至少含有一条边且起点和终点相同的有向路径。
简单有向环 是一条除了起点和终点必须相同之外，不含重复的顶点和边的环。
有向五环图(DAG) 是一幅不含有向环的有向图。
强连通：如果两个顶点 v 和 w 是相互可达的，则称它们是强连通的，如果一幅图任意两个顶点都是强连通的，则称这幅图是强连通的。
强连通分量：一幅图中的强连通的顶点构成的最大子集，一幅图可以有多个强连通分量组成。
[](
)5.2 图的存储
[](
)5.2.1 邻接矩阵
使用一个 V*V 矩阵来表示，其中 V 是顶点的个数。矩阵的某个元素中存储的可以是布尔变量，表示该边是否存在，在实际应用中也可以将其设置为某个边的权重。使用这种方式的缺点是当数据量比较大的时候会占用很大的存储空间。
[](
)5.2.2 邻接表数组
即使用一个以顶点为数组的索引的列表数组来表示图。以下是图的一个基于 Java 的实现：
public class Graph {
private Bag<Integer>[] adj;
public Graph(int V) {
adj = new Bag[V];
for (int i=0;i<V;i++) {
adj[i] = new Bag<Integer>();
}
}
}
可以看出实际在这里我们使用了背包来存储图的数据。adj 的具体含义是：比如，如果顶点 0 对应的数组元素是 adj[0]，这里的 adj[0] 是一个背包，它里面存储了与顶点 0 相连的其他顶点。如果是无向图的话，只要在背包中存储所有相关的顶点就可以了。如果是有向图的话，需要存储该点指向的顶点的值。
[](
)5.2.3 邻接多重表
它跟邻接表的区别在于，在邻接表中，同一条边由用两个顶点表示，而在邻接多重表中只用一个顶点表示。
[](
)5.2.4 边集数组
还未添加个人签名 2021.10.31 加入
还未添加个人简介
评论