数据结构
- 线性结构
数组、链表、栈、队列
- 非线性
多维数组、树、图
1. 栈
后进先出，可以处理递归调用
实际应用：字符串求值，前、中、后缀表达式，中与后缀表达式的转化，
2. 队列
先进先出
实际应用：约瑟夫问题
3. 树
- 二叉树：前、中、后、广度、深度遍历
广度优先（BFS）：利用队列的特性
深度优先（DFS）：递归，非递归（栈特性） - 顺序二叉树，以数组为基础，构建虚拟的二叉树
左节点 ：2n +1
右节点：2n +2 - 最优二叉树（赫夫曼树）带权路径最短
将权重递增排序，构建局部权重最小树，然后将构建的节点加入，再次排序，重复，知道集合中只有一个节点，
实际应用：赫夫曼编码，构建好赫夫曼树后，向左为0，右为1，构建各个节点的编码，形成，各个编码开始都不重复的编码。 - 线索二叉树
为了遍历或是其他更快，将单子节点的节点设置前驱或是后继（当前的前驱指向前一个节点，前一个节点的后继，指向当前节点） - 二叉树搜索树（BST）
所有的节点值大于左节点，小于右节点，中序遍历为有序 - 平衡二叉树（AVL）
前提是BST，并且左右子树的高度差不超过1，保证该特点在添加节点时，判断高度，进行左、右、双旋操作；
4. 图
邻接矩阵，深度、广度优先遍历、
算法
1. 排序（内、外部排序）
1.1 冒泡
比较、交换，将最值放到最后，O(n^2),稳定
1.2 选择
每次选择最小的与前的交换 ，O(n^2),不稳定
1.3 插入
将后面无序表中的元素、插入有序表中的正确位置， O(n^2),稳定
1.4 希尔
插入排序的升级版，逐步减少步长，达到局部有序，减少交换，局部使用插入排序,O(nlog^2 n),不稳定
1.5 快排
根据取得的基准值，分为大于、小于该值的俩部分、然后再对这俩部分做前面的操作，知道只有一个数 O(nlog^2 ），不稳定
1.6 归并
递归将排序数分为最小单位，然后局部排序，向上合并，达到整体有序 O(nlog^2 n),稳定
1.7 基数排序
将数据从低位开始，分成0-9组，按照低位，放入到不同的分组中，按该顺序，根据次低位分组，依次类推
1.8 堆排序
首先通过最后一个非叶子节点开始，自底向上调整成为大顶堆（或小顶堆），然后交换顶端节点与最后一个元素，调整堆，继续获取，直到结束
2. 具体算法
- 二分搜索（递归、非递归）
- 分治算法
汉诺塔 - 动态规划
背包问题 - KMP
- 贪心算法
- 最小生成树
普里姆
克鲁斯卡 - 最短路径
迪杰斯特拉
弗洛伊德 - 马踏棋盘（+贪心）
