数据结构与算法一直是比较薄弱的地方，不仅在面试的时候会问相关问题、手写代码，而且在笔试的时候发挥重要作用。
这次选择看的书籍是 《图解数据结构-使用Java》 ，先入门，后面再深入学习。
算法的时间复杂度，用来度量算法的运行时间，记作: T(n) = O(f(n))。它表示随着 输入大小 n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述。
线性表是 n 个元素的有限序列（n >= 0），是计算机科学中一种相当基础的数据结构。
数组
数组 其实是一排紧密相邻的可读内存，并提供一个能够 直接访问 单一数据内容的计算方法。
这样能够直接通过计算，并访问任一位置的数据，即所谓的数组的 随机读取 。
当 Java 数组声明时会在内存中分配一定的暂存空间，空间大小以数据类型和数组数量为依据。
一维数据、二维数组、三维数组、n 维数组。
数组可用于矩阵、多项式等的运算。
链表
链表 是由许多相同数据类型的元素按照特定顺序排列而成的线性表，其在内存中是不连续与随机存储的。
这样就不能像数组那样随机读取数据，而要 按照顺序 找到所需数据。
单向链表
单向链表是由节点组成，指针方向相同的链表。其中节点由数据字段和链接字段组成。
在 Java 中，声明节点：
public class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
|
而 Java 中没有指针的概念，我们声明两个对象分别指向第一个和最后一个节点：
public class LinkedList {
private Node first;
private Node last;
...
}
|
1、单向链表的创建
下面创建简单单向链表类：
public class LinkedList {
private Node first;
private Node last;
public boolean isEmpty() {
return first == null;
}
public void insert(int data) {
Node node = new Node(data);
if (this.isEmpty()) {
first = node;
last = node;
} else {
last.next = node;
last = node;
}
}
public void print() {
Node current = first;
while (current != null) {
System.out.println("current.data=" + current.data);
current = current.next;
}
}
}
|
然后实例化链表对象即可：
public class Main {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.insert(99);
linkedList.insert(90);
linkedList.insert(95);
linkedList.print();
}
}
|
这样所有节点都知道下个节点在哪里，只要有首节点的存在，就可以对整个列表进行遍历、插入及删除节点等动作。
2、单向链表节点的删除
将欲删除节点的前一个节点的指针指向欲删除节点的下一个节点即可。
如果删除 首节点，将首节点的下个节点设置为首节点；如果删除 末节点，将前一个节点指向 null 即可。
public void delete(Node node) {
Node newNode;
Node temp;
if (first.data == node.data) {
first = first.next;
} else if (last.data == node.data) {
temp = first;
while (temp.next != last) {
temp = temp.next;
}
temp.next = last.next;
last = temp;
} else {
newNode = first;
temp = first;
while (temp.data != node.data) {
newNode = temp;
temp = temp.next;
}
newNode.next = temp.next;
}
}
|
这样删除有点弊端，根据 node 节点的值判断是否是同一节点，并且没有对节点是否存在做判断。
3、单向链表节点的添加
添加节点和删除节点有点类似，将前一个节点指向新添加的节点，然后将新添加节点指向下一个节点即可。
如果添加为 首节点 ，将欲添加节点指向首节点；如果添加为 末节点 ，将原末节点指向新节点即可。
public void insert(Node node) {
Node newNode;
Node temp;
if (node.next == first) {
node.next = first;
first = node;
} else if (node.next == null) {
last.next = node;
node.next = null;
} else {
newNode = first;
temp = first;
while (node.next != newNode.next) {
temp = newNode;
newNode = newNode.next;
}
temp.next = node;
node.next = newNode;
}
}
|
这样在节点位置的判断上还是有弊端的。
4、单向链表的反转
面试有时候会让手写这个代码。
遍历法: 从链表头部开始，逐个反转节点。
public Node reverse(Node head) {
if (head == null) return null;
if (head.next == null) return head;
Node preNode = null;
Node nowNode = head;
while (nowNode != null) {
Node nextNode = nowNode.next;
nowNode.next = preNode;
preNode = nowNode;
nowNode = nextNode;
}
return preNode;
}
|
递归法：从链表尾部开始，逐个反转节点。
public Node reverse(Node node) {
if (node == null || node.next == null) return node;
Node headNode = reverse(node.next);
node.next.next = node;
node.next = null;
return headNode;
}
|
以上算法都需要传入链表的头部节点，打印时需要注意头部和尾部节点引用。
5、单向链表的串联
将列表的首位节点相连即可。
public LinkedList connect(LinkedList list1, LinkedList list2) {
LinkedList list = list1;
list.last.next = list2.first;
return list;
}
|
环形链表
我们把单向链表的尾部指向头部，整个链表就成为单向环形结构。
这里创建链表、插入节点、删除节点、链表串联都很类似。
双向链表
双向链表基本结构和单项连链表类似，至少一个节点存放数据，另外它有两个字段存放指针。
堆栈
堆栈是一种抽象的数据结构：只能从堆栈的 顶端 访问数据；数据访问符合 后进先出 的原则。
堆栈的数组实现
class StackByArray {
private int[] stack;
private int top;
public StackByArray(int stack_size) {
stack = new int[stack_size];
top = -1;
}
public boolean push(int data) {
if (top >= stack.length) {
System.out.println("堆栈已满，无法再加入");
return false;
} else {
stack[++top] = data;
return true;
}
}
public boolean empty() {
if (top == -1) return true;
else return false;
}
public int pop() {
if (empty())
return -1;
else
return stack[top--];
}
}
|
堆栈的链表实现
class Node
{
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class StackByLink {
public Node front;
public Node rear;
public boolean isEmpty() {
return front == null;
}
public void output_of_Stack() {
Node current = front;
while (current != null) {
System.out.print("[" + current.data + "]");
current = current.next;
}
System.out.println();
}
public void insert(int data) {
Node newNode = new Node(data);
if (this.isEmpty()) {
front = newNode;
rear = newNode;
} else {
rear.next = newNode;
rear = newNode;
}
}
public void pop() {
Node newNode;
if (this.isEmpty()) {
System.out.print("===目前为空堆栈===\n");
return;
}
newNode = front;
if (newNode == rear) {
front = null;
rear = null;
System.out.print("===目前为空堆栈===\n");
} else {
while (newNode.next != rear)
newNode = newNode.next;
newNode.next = rear.next;
rear = newNode;
}
}
}
|
堆栈的应用
二叉树及森林的遍历；图形的深度优先遍历；递归程序的调用及返回等等。
队列
队列是一种抽象的数据结构：只能从队列的 两端 访问数据；数据访问符合 先进先出 的原则。
队列的数组实现
public class ArrayQueue {
private int[] data;
private int size;
private int front;
private int rear;
public ArrayQueue() {
data = new int[10];
size = 0;
front = 0;
rear = 0;
}
public void add(int t) {
if (isFull()) {
resize();
front = 0;
}
rear = (front + size) % data.length;
System.out.println(rear);
data[rear] = t;
size++;
}
public int remove() {
if (isEmpty()) {
throw new RuntimeException("队列为空!");
}
int tempData = data[front];
data[front] = 0;
front = (front + 1) % (data.length);
size--;
return tempData;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == data.length;
}
public void resize() {
int[] tmp = new int[data.length * 2];
System.arraycopy(data, 0, tmp, 0, data.length);
data = tmp;
tmp = null;
}
}
|
队列的链表实现
class QueueNode
{
int data;
QueueNode next;
public QueueNode(int data) {
this.data = data;
next = null;
}
}
class Linked_List_Queue {
public QueueNode front;
public QueueNode rear;
public Linked_List_Queue() {
front = null;
rear = null;
}
public boolean enqueue(int value) {
QueueNode node = new QueueNode(value);
if (rear == null)
front = node;
else
rear.next = node;
rear = node;
return true;
}
public int dequeue() {
int value;
if (!(front == null)) {
if (front == rear) rear = null;
value = front.data;
front = front.next;
return value;
} else return -1;
}
}
|
环形队列、优先队列、双向队列
树状结构
树是一种用来表述有 分支 的数据结构，是由一个或者一个以上的节点组成的有限集合。
树的专有名词：
结点度：结点子树的个数；树的度：树中最大的结点度。
叶子节点：没有子节点的节点，即度为 0 的节点。
二叉树
二叉树最多有两个子节点，即度 <= 2 的树。
特殊的二叉树：
1、满二叉树，树的高度为 h 树的节点为 $2^h-1$ 我们称为满二叉树。
2、完全二叉树，树的高度为 h 树的节点小于 $2^h-1$ ，但是其节点和满二叉树从左到右，从上到下的顺序一一对应。
3、歪二叉树，当一个二叉树完全没有右节点/左节点时。
4、严格二叉树，每个二叉树都有非空的左右子树。成为严格二叉树。
二叉树的存储方式
1、数组表示法
首先将二叉树想象为满二叉树，然后依次存放入数组中，空位为 null 即可。
以数组建立二叉树，要求小于父节点的值放在左子节点，反之放在右边。
public class CH06_01 {
public static void main(String args[]) throws IOException
{
int i, level;
int data[] = {6, 3, 5, 9, 7, 8, 4, 2};
int btree[] = new int[16];
for (i = 0; i < 16; i++) btree[i] = 0;
System.out.print("原始数组内容: \n");
for (i = 0; i < 8; i++)
System.out.print("[" + data[i] + "] ");
System.out.println();
for (i = 0; i < 8; i++) {
for (level = 1; btree[level] != 0; ) {
if (data[i] > btree[level])
level = level * 2 + 1;
else
level = level * 2;
}
btree[level] = data[i];
}
System.out.print("二叉树内容：\n");
for (i = 1; i < 16; i++)
System.out.print("[" + btree[i] + "] ");
System.out.print("\n");
}
}
|
2、链表表示法
二叉链表结构主要由一个数据域和两个分别指向左、右孩子的结点组成，其结构如下：
TreeNode 及 BinaryTree 声明如下：
class TreeNode {
int value;
TreeNode left_Node;
TreeNode right_Node;
public TreeNode(int value) {
this.value = value;
this.left_Node = null;
this.right_Node = null;
}
}
class BinaryTree {
public TreeNode rootNode;
public BinaryTree(int[] data) {
for (int i = 0; i < data.length; i++)
Add_Node_To_Tree(data[i]);
}
void Add_Node_To_Tree(int value) {
TreeNode currentNode = rootNode;
if (rootNode == null) {
rootNode = new TreeNode(value);
return;
}
while (true) {
if (value < currentNode.value) {
if (currentNode.left_Node == null) {
currentNode.left_Node = new TreeNode(value);
return;
} else currentNode = currentNode.left_Node;
} else {
if (currentNode.right_Node == null) {
currentNode.right_Node = new TreeNode(value);
return;
} else currentNode = currentNode.right_Node;
}
}
}
}
|
这样增删很容易，但是不容易找到父节点，除非增加字段。
二叉树的遍历
二叉树的遍历：即“访问树中所有节点各一次”。按照二叉树特性，一律从左向右。
根据访问根节点的顺序，二叉树的遍历规则主要有四种，先根次序遍历，中根次序遍历，后根次序遍历以及层次遍历。
public void InOrder(TreeNode node) {
if (node != null) {
InOrder(node.left_Node);
System.out.print("[" + node.value + "] ");
InOrder(node.right_Node);
}
}
public void PreOrder(TreeNode node) {
if (node != null) {
System.out.print("[" + node.value + "] ");
PreOrder(node.left_Node);
PreOrder(node.right_Node);
}
}
public void PostOrder(TreeNode node) {
if (node != null) {
PostOrder(node.left_Node);
PostOrder(node.right_Node);
System.out.print("[" + node.value + "] ");
}
}
|
图形结构
图形结构是用来探讨两个顶点间是否相连的关系图，若在边上加权值，这类图成为“网络”。
图形介绍
图形有两种：有向图、无向图。
图形的专业术语：
度：一个顶点所拥有边的总数。
入/出度：在有向图中，定点为箭头终点的边的个数为入度；出度为起点边的个数。
图形的表示法
1、邻接矩阵法/相邻表法
2、相邻多元列表法/索引表格法
图形的遍历
图形的遍历方法有两种：深度优先遍历、广度优先遍历。
1、深度优先使用递归与 堆栈 的技巧
从图形的某一顶点开始遍历，被访问过的顶点就做上已访问的记号，接着遍历此顶点的所有相邻且未访问过的顶点中的任意一个顶点，并做上已访问的记号，再以该点为新的起点继续进行先深后广的搜索。
（1）从起点 1 开始，将相邻的 2 3 放入堆栈
3 2
（2）将 2 取出，并将与 2 相邻且未访问的 4 5 放入堆栈
3 5 4
（3）将 4 取出，并将与 4 相邻且未访问的 8 放入堆栈
3 5 8
（4）将 8 取出，并将与 8 相邻且未访问的 5 放入堆栈
3 5 5
（5）将 5 取出，发现与 5 相邻的节点都访问过了，这里就舍去
3
（6）将 3 取出，并将与 3 相邻且未访问的 6 7 放入堆栈
7 6
（7）最后将堆栈的节点逐个判断即可。
7 7
最终遍历顺序为：1 -> 2 -> 4 -> 8 -> 5 -> 3 -> 6 -> 7
public static void dfs(int current)
{
run[current] = 1;
System.out.print("[" + current + "]");
while ((Head[current].first) != null) {
if (run[Head[current].first.x] == 0)
dfs(Head[current].first.x);
Head[current].first = Head[current].first.next;
}
}
|
2、广度优先使用递归与 队列 的技巧
从图形的某顶点开始遍历，被访问过的顶点就做上已访问的记号，接着遍历此顶点的所有相邻且未访问过的顶点中的任意个顶点，并做上已访问的记号，再以该点为新的起点继续进行先广后深的搜索。
（1）从起点 1 开始，将相邻的 2 3 放入堆栈
2 3
（2）将 2 取出，并将与 2 相邻且未访问的 4 5 放入堆栈
3 4 5
（3）将 3 取出，并将与 3 相邻且未访问的 6 7 放入堆栈
4 5 6 7
（4）将 4 取出，并将与 4 相邻且未访问的 8 放入堆栈
5 6 7 8
（5）将 5 取出，并将与 5 相邻且未访问的 8 放入堆栈
6 7 8 8
（6）将 6 取出，并将与 6 相邻且未访问的 7 放入堆栈
7 8 8 7
（7）将 7 取出，发现与 7 相邻的节点都访问过了，这里就舍去
8 8 7
（8）最后将队列的节点逐个判断即可。
8 7
最终遍历顺序为：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
public void bfs(int current) {
Node tempnode;
enqueue(current);
run[current] = 1;
System.out.print("[" + current + "]");
while (front != rear) {
current = dequeue();
tempnode = Head[current].first;
while (tempnode != null) {
if (run[tempnode.x] == 0) {
enqueue(tempnode.x);
run[tempnode.x] = 1;
System.out.print("[" + tempnode.x + "]");
}
tempnode = tempnode.next;
}
}
}
|
生成树
一个图形的生成树以最少的边来连接图形中所有的顶点，且不造成回路(Cycle)的树状结构。
深度优先生成树、广度优先生成树。
MST 生成树，即在加权图（网络）上，计算路径成本最小的的生成树。有 Peim 算法和 Kruskal 算法等。
前面一直学习的数据结构，下面排序、查找属于算法的范畴了。
数据结构：https://www.wshunli.com/posts/850e5c53.html
算法：https://www.wshunli.com/posts/444e2c0f.html
参考资料
1、《图解数据结构-使用Java》
2、（数据结构）十分钟搞定时间复杂度（算法的时间复杂度） - 简书
https://www.jianshu.com/p/f4cca5ce055a
3、单链表反转的两种实现（Java） - CSDN博客
https://blog.csdn.net/acquaintanceship/article/details/73011169
4、data structures - Reversing a linked list in Java, recursively - Stack Overflow
https://stackoverflow.com/questions/354875/reversing-a-linked-list-in-java-recursively
5、【算法】如何判断链表有环 - CSDN博客
https://blog.csdn.net/u010983881/article/details/78896293
6、队列的实现(JAVA) - CSDN博客
https://blog.csdn.net/lcore/article/details/8868078
7、树和二叉树定义、基本术语和性质 - CSDN博客
https://blog.csdn.net/lsh_2013/article/details/43121373
8、java数据结构与算法之树基本概念及二叉树（BinaryTree）的设计与实现 - CSDN博客
https://blog.csdn.net/javazejian/article/details/53727333
9、data structures - Difference between “Complete binary tree”, “strict binary tree”,”full binary Tree”? - Stack Overflow
https://stackoverflow.com/questions/12359660/difference-between-complete-binary-tree-strict-binary-tree-full-binary-tre
10、数据结构 - 图的基本术语 - CSDN博客
https://blog.csdn.net/wangzi11322/article/details/45417081
11、《图论》——图的存储与遍历（Java） - CSDN博客
https://blog.csdn.net/Gamer_gyt/article/details/51498546
12、Java 与图 - 简书
https://www.jianshu.com/p/a47a147ec92c
13、DFS（深度优先搜索）和BFS(广度优先搜索) - 简书
https://www.jianshu.com/p/b086986969e6
