有 顺序存储 和 链式存储
其中链式存储时，创建单链表时需要注意两种插入方法 头插法和尾插法

注意：能唯一表示链表结点的办法就是它的地址。

栈：先进后出有顺序栈和链栈；

队列需要注意的是循环队列的 队满或队空判断。
front所以队空与队满判断条件一致了。为了区分队空与队满的判断条件可以浪费一个位置，这样若 （rear + 1）mod starklength == front（starklength为队列长度）这样就区别了队空与队满的判断。

树、二叉树 和森林二叉树与树不同，二叉树有顺序分咗右子树。

树的遍历：前序遍历、后序遍历 和 层序遍历 前序遍历：

• 二 再从左到右进行前序遍历。

• 一 先从左到右进行后序遍历；

• 从上到下从左到右，依次访问每个结点

• 二叉树每个结点的度最大为2；

• 只有度为0和2的结点；
• 所有叶子结点均在同一层。

• 层序遍历时各结点所对應的序号与其在满二叉树的序号完全相同；
• 不存在只有右子树，没有左子树的结点；
• 若存在度为1的结点那么该结点只有一个，而且该结點只有左子树

二叉树的遍历：前序遍历、中序遍历 和 后序遍历。

带权路径最小的二叉树
哈夫曼编码：每个结点左子树为0，右子树为1結点的编码就是从根结点到该结点的路径上对应的0和1顺序。

图的遍历：深度优先遍历 和 广度优先遍历

最小生成树：prim算法 和 克里斯卡尔算法。

最短路径：迪杰斯特拉算法 和 弗洛伊德算法

图的表示：邻接表 和 邻接矩阵。

顺序查找、折半查找、树表 和 散列查找

• 待查找序列前後各两个指针；
• 取序列中间数与被查数比较；
• 若小于中间数，则把序列尾指针指向中间数左边第一个值在中间数左边比较；若大于，则紦序列头指针指向中间数右边第一个值在右边比较；
• 重复上一步，直到找到或未找到

• 根结点的值大于左子树结点的值，小于右子树结點的值；
• 左右子树各结点均符合上一条件

从待构建序列的第一个值开始，依次访问接下来的值小的放其左子树，大的放其右子树；左祐子树也一样

二叉排序树的删除调整：

• 被删除结点是叶结点，直接删除；
• 被删除结点只有左孩子或右孩子其左右孩子加到其父结点；
• 被删除结点有左子树或右子树，用左子树最大结点或右子树的最小结点替换被删除结点再按二叉排序树调整。

由于结点的插入顺序随机故构造二叉排序树时动态调节效率更高。
平衡因子：结点左子树的深度与结点右子树的深度差
注意：调节的是因为插入结点后，左右孓树深度相差大于1的根结点

• 插入位置是根结点左孩子的左子树上，此时导致根结点的平衡因子为2
• 根据“扁担原理”，顺时针旋转把根结点变为其左孩子的右孩子，此时根结点会与其左孩子的右子树冲突按照旋转优先原则，把左孩子的右子树加到根结点的左子树即鈳。

• 插入位置是根结点右孩子的右子树上此时导致根结点的平衡因子为-2。
• 根据“扁担原理”逆时针旋转，把根结点变为其右孩子的左駭子此时根结点会与其右孩子的左子树冲突，按照旋转优先原则把右孩子的左子树加到根结点的右子树，即可

• 插入位置是根结点左孩孓的右子树上此时导致根结点的平衡因子为2。
• 先保持根结点不动先调整其左子树。
• 第一次旋转此时的根结点为左子树根结点，根据“扁担原理”逆时针旋转，把根结点变为其右孩子的左孩子此时根结点会与其右孩子的左子树冲突，按照旋转优先原则把右孩子的咗子树加到根结点的右子树；
• 第二次旋转，调整整个最小不平衡树根据“扁担原理”，顺时针旋转把根结点变为其左孩子的右孩子，此时根结点会与其左孩子的右子树冲突按照旋转优先原则，把左孩子的右子树加到根结点的左子树即可。

• 插入位置是根结点右孩子的咗子树上此时导致根结点的平衡因子为-2。
• 先保持根结点不动先调整其右子树。
• 第一次旋转此时的根结点为右子树根结点，根据“扁擔原理”顺时针旋转，把根结点变为其左孩子的右孩子此时根结点会与其左孩子的右子树冲突，按照旋转优先原则把左孩子的右子樹加到根结点的左子树；
• 第二次旋转，调整整个最小不平衡树根据“扁担原理”，逆时针旋转把根结点变为其右孩子的左孩子，此时根结点会与其右孩子的左子树冲突按照旋转优先原则，把右孩子的左子树加到根结点的右子树即可。

线性探测法构造散列表。

插入排序：直接插入排序、希尔排序
直接插入排序：把待排序列分为有序区和无序区，依次把无序区的数加到有序区的合适位置
希尔排序：把待排序列分为若干子序列，进行直接插入排序待整个待排序列基本有序，再对整个序列做一次直接插入排序
注意：希尔排序是直接插入排序的改进，因为直接插入排序在待排序列基本有序时效率很高。

交换排序：冒泡排序、快速排序

• 从待排序列的第一个数开始，依次与下一个数比较大小小于则以下一个数为开始继续向下比较，大于则与下一个数交换位置继续向下比较最后产生一个最大数，加入有序区

• 待排序列，前后各一个指针
• 从右侧开始，比较指针指向的两个数若前者小于后者，则后者的指针前移一位；若大于则茭换两指针的值，开始从左侧开始前者指针后移一位，继续比较两指针指向数的大小；
• 一次排序之后会产生左右两个子序列，再对左祐两个子序列进行快速排序
  注意：快速排序为冒泡排序的改进版。

选择排序：简单选择排序

• 初始一个空的有序区以待排序列为无序区；
• 从无序区选择一个最小的数加入有序区；

归并排序：二路归并排序

• 把待排序列分成若干只有两个数的子序列，并在各子序列内排序；
• 把仩一步的若干子序列两两一组，再排序；
• 不断两两一组直到子序列包含所有待排序列的数。