数据结构复习
什么是软件的基础？万年不变的公式：数据结构+算法=软件设计。走过了11年的计算机生涯，还记得，那时第二年，在那本白色的，还有点蓝色的教科书上面，首次接触到了这个公式，从此，就再也没放手。遥想当年，c++没学好，很是头疼那本书中的这个结构那个结构，链表是啥？还有，递归怎么去想？好吧，那一年玩魔兽去了，根本也没想多少，科是一定挂了的。兜兜转转这些年，从考研死扣了严蔚敏，到后来入手了Java，从这个框架转站了那个框架，从学校到公司，从一个公司又到另一个公司，大理石的《算法与数据结构》已经刷2遍，橙色Java算法接触宝典《算法》也是看了一遍，就连《c++11 primer》都从头到尾看了一遍。记得研三看primer的时候，边看就边想：特么的C++就这么个语法，当年怎么就学不进去，没学好呢？相当悔恨。同理，再《数据结构》上面也是一样。如果再让我来一遍，特么绝壁完爆期末考试。可是，人生已经回不去了。人就是这样，往往失去了，才懂得珍惜。对于《数据结构》的情感，我一直是这种内心情景，这次也算是描述清了。
一、学习数据结构的意义
- 你要走技术路线，不是混吃等死的话，上升必须要有个好的数据结构功底
- 锻炼思维
- 所有底层框架和系统的基础，不要被整天的api调用和crud所迷惑
- 算法的基础
- 不要说工作中碰不到，我在前前后后的两个工作中都碰到了。碰到了，你不会和你会，效率是不一样的！
- 想走业务线、管理线、老板线、我党线、人生赢家线、产品线等请无视上面BB，下面的也不用看了！
- 最后安利一句：技术就是苦逼，借用网易游戏宣传片中的一句话：用职业、生意、市场定义游戏的人，永远不懂得热爱的意义。扪心自问：你热爱技术吗？
整个数据结构的过程，大概是这样的：先理解概念，甚至可以看一遍实现，然后自己不看源码自己实现一遍。这个文章我主要介绍一下各个结构主要的注意点，具体的实现，我会上传github，链接再文末发出来。
对于算法部分，我们主要使用大名鼎鼎的leetcode进行跟踪与学习。本文会涉及到几个，不过不多，以为会慢慢的补全，也会继续出文章解说，大家也可以一起刷题，然后放上来。
另外，针对多线程的考虑，本文暂不涉及，要涉及这一点，可能不适合数据结构的入门与深入，咱们要一步步来。
二、链表、栈
对链表和栈的抽象主要是下面的接口：
public interface List<E> {
int size();
void resize(int resizeNum);
boolean isEmpty();
boolean isContained(E e);
void addFirst(E e);
void addLast(E e);
void add(int index, E e);
void remove(E e);
E get(int index);
int find(E e);
}重点要注意点在于：
- 链表的存储结果，可以有两种：数组和链式
- 链表可以进行任意节点的插入、删除、访问
- 栈的插入必须要在第一个元素前进行插入（栈顶），删除也只能删除最上面的（出栈），正所谓的先进后出（LIFO）
- 注意对resize的实现，考虑好扩容的时机
- 链表（数组）具体的实现类为：struct.impl.ArrayList
- 链表（链式）具体的实现类为：struct.impl.LinkedList
三、 队列
对于队列的抽闲接口如下：
public interface Queue<E> {
int size();
boolean isEmpty();
void enQueue(E e);
E deQueue();
void resize(int num);
}重点的注意点在于：
- 我们实现的是循环队列，使用数组进行存储
- 有两个指向收尾的index标示指针：first，last
- 队列空的情况为：
first==last，队列为满的情况为：(last+1)%size==first - 队列的入队是将元素放到队尾，出队是将队头的元素出队，这就是(FIFO)
主要实现类为：struct.impl.ArrayQueue
四、优先队列（堆，重点）
对于堆的抽象接口如下：
public interface Queue<E> {
int size();
boolean isEmpty();
void enQueue(E e);
E deQueue();
void resize(int num);
}实现重点在：
- 注意堆的概念：一个树的树顶一定大于（小于）两个孩子，所以整个树，root就是最大（最小）的值
- 堆是一个完全二叉树，所以我们可以使用数组进行实现，按照层序遍历的序号，对应数组的具体index
- 实现难点在于删除与插入
- 插入：放到整个数组的最后一个元素里面，然后执行上浮（shiftUp）操作
- 删除：将最后一个元素与root交换，然后针对最新root元素进行下沉（shiftDown）操作
- 我们使用root编号为0，root的两个孩子节点编号为1、2，以此类推
- 获取当前index的孩子节点的操作为：index *2+1、index*2+2
- 获取当前index的父亲节点操作为：(index-1)/2
实现类为：struct.impl.PriorityQueue
五、二叉搜索树（BST）
基本实现接口为：
public class BST<E extends Comparable<E>> {
public void addValue(E value);
public E findMin();
public E findMax();
public E deleteMin();
public E deleteMax() ;
public void deleteNode(E value);
public void inOrder();
public void levelOrder();
}注意点在于：
- 搜索树是一颗完全二叉树
- 所有非叶子节点的数值，都大于左孩子，都小于右孩子
- 主要注意删除最小值和删除最大值操作，因为可能涉及到删除节点孩子的保存问题
- 删除任意节点操作是重点，麻蛋，被头条考了，让我写
实现类为：struct.impl.BST
六、 二叉平衡树（AVL）
基本实现接口为：
public class BST<E extends Comparable<E>> {
public void addValue(E value);
public E findMin();
public E findMax();
public E deleteMin();
public E deleteMax() ;
public void deleteNode(E value);
public void inOrder();
public void levelOrder();
}注意点：
- AVL本身是一个BST
- AVL对BST的优化点在于：所有节点的左右子树的高度差，不大于1，防止BST退化成链表的问题
- 重点来了，思考好左旋右旋：如果是左左的情况，要进行右旋；如果是右右的情况，要进行左旋；如果是左右的情况，要进行先左旋再右旋；如果是右左的情况，要进行先右旋再左旋
- 下面是四种不平衡情况的图例：1：左左；2：左右；3：右左；4：右右
具体的实现代码为：struct.impl.AVL
七、结尾
我的上传地址是：AlgorithmAndDataStruct