顺序表链表的区别（存储空间/增删改查）、栈和队列的应用（栈是应用，队列会结合操作系统，如调度，说的有理即可）、数组删除元素过程、二叉树前中后序、图【重点】（主要是算法思想，深搜广搜，克鲁斯，prime，弗洛伊德等中文算法表述）
算法定义
- 是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作
算法的基本特性
有穷性
- 必须保证执行有限步之后结束
确定性
- 每一步骤必须有确定的定义
可行性
- 所有操作都必须通过已实现的基本操作进行运算，并在有限次内实现
输入
- 有0或多个输入
输出
- 有一个或多个输出
数据结构定义
数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。
逻辑结构
- 集合，线性结构，树形结构，图状结构
存储结构
- 顺序存储，链式存储，索引存储，散列存储
线性表的定义
- 线性表是具有相同特性数据元素的一个有限序列，只有一个表头，只有一个表尾，且表头没有前驱，表尾没有后继
顺序表和链表的比较
基于空间的比较
存储分配的方式
顺序表的存储空间是一次性分配的
链表的存储空间是多次分配的
存储密度（结点值域所占的存储量/结点结构所占的存储总量）
顺序表的存储密度为1
链表的存储密度小于1，因为结点中有指针域
基于时间的比较
存取方式
顺序表可以随机存取，也可以顺序存取
链表只能顺序存取
插入/删除时移动元素的个数
顺序表平均需要移动近一半元素
链表不需要移动元素，只需要修改指针
栈的定义
- 栈是一种只能在一端进行插入或删除操作的线性表，允许插入删除的那一端称为栈顶，另一端称为栈底，栈底固定不变，栈的特点是先进后出
栈的应用
括号匹配
表达式求值
后缀表达式
进制数之间转换
迷宫求解
队列定义
- 是一种操作受限的线性表，仅允许在表的一端进行插入，在表的另一端进行删除。可进行插入的一端称为队尾，可进行删除的一端称为队头。队列的特点是先进先出。
队的应用
和OS结合的任务调度算法
广度优先搜索
树的层次遍历
树的基本术语
层次
- 从根开始，根为第一层，根的孩子为第二层，根的孩子的孩子为第三层，以此类推
高度/深度
- 树中结点的最大层次
二叉树的主要性质
非空二叉树上叶子结点数等于双分支结点数加一
二叉树的第i层上最多有2的i-1次幂个结点
高度或深度为k的二叉树最多有2的k次幂-1个结点
二叉树的遍历算法
先序遍历
访问根结点
先序遍历左子树
先序遍历右子树
中序遍历
中序遍历左子树
访问根结点
中序遍历右子树
后序遍历
后序遍历左子树
后序遍历右子树
访问根结点
层次遍历
先建立一个循环队列
将二叉树头结点入队列，然后出队列，访问该结点
如果它有左子树，则将左子树的根结点入队
如果它有右子树，则将右子树的根结点入队
然后出队列，对出队列的结点进行访问
如此反复，直到队列为空为止
图的存储结构
邻接矩阵
邻接表
图的遍历算法
深度优先搜索遍历
- 首先访问出发点v，将其标记为已访问过，然后选取与v邻接的未被访问的任意一个顶点w，并访问它，再选取与w邻接的未被访问的任一顶点并访问，以此重复进行
广度优先搜索遍历
- 首先访问起始顶点v，然后选取与v邻接的全部顶点w1,w2,w2,,,,wn进行访问，再依此访问与w1,w2,w2,,,,wn邻接的全部顶点（已经访问过的除外）。以此类推，直到所有顶点都被访问过为止
普利姆算法
从图中任意取出一顶点，把它当成一棵树，然后从与这棵树相接的边中选取一条最短的边，并将这条边及其所连接的顶点也并入这棵树中，此时得到了一棵有两个顶点的树。然后从与这棵树相接的边中选取一条最短的边，并将这条边及其所连顶点并入当前树中，得到一棵有三个顶点的树。以此类推，直到图中所有顶点都被并入树中为止，此时得到的生成树就是最小生成树
时间复杂度O(顶点的平方)
克鲁斯卡尔算法
首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止
时间复杂度 O(边数eloge)
迪杰斯特拉算法
设有两个顶点集合S和T，集合S中存放图中已找到最短路径的顶点，集合T存放图中剩余顶点。初始状态时，集合S中只包含源点v0，然后不断从集合T中选取到顶点v0路径长度最短的顶点vu并入到集合S中。集合S每并入一个新的顶点vu，都要修改顶点v0到集合T中顶点的最短路径长度值。不断重复这个过程，直到集合T的顶点全部并入到S中为止
时间复杂度O(nxn)
排序
直接插入排序
将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过。
时间复杂度：最好O(n) 最坏O(nxn) 平均 O(nxn)
空间复杂度：O(1)
稳定
折半插入排序
折半插入排序是采用折半查找法来查找插入位置的。折半查找法的一个基本条件是序列已经有序。折半排序就是通过折半的方式去找到合适的位置，然后一次性进行移动，为插入的元素腾出位置。
时间复杂度：最好O(nlog2n) 最坏O(nxn) 平均 O(nxn)
空间复杂度：O(1)
稳定
希尔排序
其本质还是插入排序，将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。
平均时间复杂度： O(nlog2n)
空间复杂度：O(1)
不稳定
简单选择排序
从头至尾顺序扫描序列，找出最小的一个关键字，和第一个关键字交换，接着从剩下的关键字中继续这种选择和交换，最终使序列有序
时间复杂度： O(nxn)
空间复杂度：O(1)
不稳定
优化方向：
- 每次循环可以同时找到最大值和最小值，时间减少一半。冒泡排序也可以。
堆排序
将一个无序序列调整为一个大顶堆，就可以找出这个序列的最大值，然后将找出的这个值交换到序列的最后，这样，有序序列关键字增加一个，无序序列中关键字减少一个，对新的无序序列重复这样的操作，就实现了排序
时间复杂度： O(nlog2n)
空间复杂度：O(1)
不稳定
冒泡排序
直观上可以解释为小的元素像气泡一样浮到前面来，大的元素沉到后面去。算法设计思想是两层循环，外层循环每一次操作将最大元素沉底，内层循环每次处理的数据数量减一，沉底的元素就不考虑了。
时间复杂度： O(nxn)
空间复杂度：O(1)
稳定
优化方向
设置flag标记，可以减少比较次数
记录无序区，有序区无需比较
快速排序
每一趟选择当前所有子序列中的一个关键字作为枢轴，将子序列中比枢轴小的移到枢轴前边，比枢轴大的移到枢轴后边；当本趟所有子序列都被枢轴以上规则划分完毕后会得到新的一组更短的子序列，它们成为下一趟划分的初始序列集
时间复杂度：最好O(nlog2n) 最坏O(nxn) 平均 O(nlog2n)
空间复杂度：O(log2n)
不稳定
二路归并排序
将已有的子序列合并，达到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
时间复杂度： O(nlog2n)
空间复杂度：O(n)
稳定
查找
顺序查找法
从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值k比较，若当前扫描的关键字与k相等，则查找成功；若扫描结束，仍未发现关键字等于k的记录，则查找失败
时间复杂度/空间复杂度O(n)
折半查找法
首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上步骤，直到找到满足条件的结果为止，若找不到，则返回失败。
时间复杂度O(logn)
常见的Hash函数的构造方法
直接定址法
数字分析法
平方取中法
除留余数法
常见的Hash函数冲突处理方法
开放定址法
线性探查法