#### 算法
算法：解决问题的方法
程序：用某种语言来诠释算法
算法基本特征：
1. 可行性：在特定环境中每一个步骤都能实现且最终可以达到预期目的
2. 有穷性：算法能在有限的时间内完成，执行有限步骤后能中止，有合理的执行时间
3. 确定性：每一步都是明确的，不能模棱两可也不能多义
4. 有足够的情报：初始化条件和输入足够
算法的基本要素：
1. 算法中对数据对象的运算和操作
2. 算法的控制语句
算法设计的基本方法：列举、归纳、递归、递推、减半递推、回溯
算法复杂度：两个复杂度之间**没有关系**
1. 时间复杂度：执行算法所需要的计算工作量（执行的基本运算次数），不等同于算法执行时间，不考虑硬件水平等 算法工作量=f(n)，n为问题规模 工作量分析方法：平均性态、最坏情况
2. 空间复杂度：执行算法所需要的内存空间：输入数据、程序本身、执行过程中所需的额外空间
#### 数据结构
数据结构研究内容：逻辑结构、存储结构、对各种数据结构进行的运算
数据结构：相互有关联的数据元素的集合或数据及其关系（线性、树状、网状、集合结构）
1. 逻辑结构：反应数据元素之间的逻辑关系的数据结构。通常有两个要素：数据元素的集合D，D上的前后件关系R，反应各数据元素之间的前后关系。一个数据结构可表示为：B=（D，R）
2. 存储结构：也称为数据的物理结构，是数据的逻辑结构在计算机存储空间的存放方式
3. 数据结构图形表示：根节点，终端节点（叶子节点），内部节点
```
把一日三餐看作数据结构，表示为B=(D,R)
D = {早餐，午餐，晚餐}
R = {（早餐，午餐），（午餐，晚餐）}
```
根节点：没有前件（董事长）叶子节点：没有后件（员工）内部节点：中间节点（总经理，经理，组长）
存在没有元素的空数据结构
1. 线性结构：一个非空的数据结构，有且只有一个根节点，每一个节点最多有一个前件和一个后件（每个元素都要出现）
2. 非线性结构：不满足线性结构条件的所有结构（树状，网状）
#### 线性表、栈和队列
线性表：最简单最常用的数据结构，节点个数n表示当前线性表长度
线性表的存储结构：连续性，插入删除时需要移动相应位置之后的大片数据
1. 栈（先进后出）：一端封闭（栈底）的特殊线性表，只能从另一端（栈顶）插入（入栈）和删除（出栈）
2. 队列（先进先出）：插入数据在队尾，删除数据在队首，循环队列中**无法确定队首和队尾的位置**关系，栈底指针指向的空间永远为空（实际能用的空间是n-1）
线性链表： 每个结点独立存在（动态内存分配，不连续）每个节点中至少有两个成员当插入或删除时只需要改变相关指针
* 是否带头结点：带头结点时头指针指向头结点，如果不带的话头指针直接指向第一个数据
1. 单链表：每个结点中包含数据和一个指向下一个结点的指针（最后一个为空指针）
2. 单向循环链表：最后一个指针指向第一个有效结点（有头结点则为头结点，否则就是第一个数据）
3. 双链表：每个结点中包含一个指向上一个结点的指针、数据和一个指向下一个结点的指针（最后一个为空指针）
4. 双向循环链表：最后一个尾指针指向第一个结点，第一个头指针指向最后一个结点
#### 树状结构
1. 父结点：A-B-C，A是B的父结点，B是C的父结点
2. 子节点：A-B-C，B是A的子结点，C是B的子结点
3. 叶子结点：没有子结点的结点
4. 度：一个结点所拥有的后续结点的个数（树的度：所有节点中最大的度）
5. 深度：根节点所在层次，A-B-C中C在第三层
6. 子树：以某结点为根结点构成的树
7. 二叉树：树中节点的度不大于2的有序树（链式存储）
8. 满二叉树：除了最后一层外每一层的所有结点都有两个子结点
9. **完全二叉树**：除了最后两层外每一层的所有结点都有两个子结点
设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，**第 h 层所有的结点都连续集中在最左边**
假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，则
①n= n0+n1+n2 （其中n为完全二叉树的结点总数）；又因为一个度为2的结点会有2个子结点，一个度为1的结点会有1个子结点，除根结点外其他结点都有父结点，
②n= 1+n1+2*n2 ；由①、②两式把n2消去得：n= 2*n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=n/2 或 n0=(n+1)/2。
1. 深度为k的二叉树最多有(2^k)-1个结点
2. 第k层最多有2^(k-1)个节点
3. 度为0的节点总比度为2的结点多一个
4. 有n个结点的二叉树，其深度**至少**为 [log2n]+1，其中log2n取整数，2是底数
5. 有n个结点的**完全**二叉树深度为 [log2n]+1
6. 设完全二叉树（或满二叉树）共n个结点。从根节点开始。按层序用自然数编号则有：
* 若结点编号为i=1则该节点为根节点，且该结点没有父节点
* 若结点编号为1>1则他的父结点为i/2，左子结点2i，右子结点为2i+1
#### 二叉树遍历：
1. 前序（先序）遍历：（根、左、右）A B D H E I C F G
2. 中序遍历：（左、根、右）H D B E I A C G F
3. 后序遍历：（左、右、根）H D I E B G F C A
4. 按层遍历：（逐层往下）A B C D E F H I G
给两个序列（前中或后中）倒推：
* 先确定根节点（前序是第一个，后续是最后一个）
* 再看中序，根结点左边是左子树，右边是右子树
* 然后根据中序的判断，在前（后）序中找到左右子树相关的组
* 若给的是前序，则相关组的开头就是第二层
* 若给的是后序，则相关组的结尾就是第二层
#### 查找和排序
* 顺序查找（查找效率低，但在元素没有规律的情况或使用链式存储结构下只能用顺序查找）：在有N个元素的线性表中，从线性表的第一个元素开始逐个和被查找的元素进行比较，理想情况下比较次数为一次，最坏的情况下比较次数为N次（包含线性表中没有该元素的可能），平均需比较N/2次，查找算法的时间复杂度为O(n)
* 二分法查找（折半查找，效率较高）：使用时需满足顺序存储结构且线性表是有序表，长度为N的有序线性表，在最坏的情况下二分查找需要的比较次数为 log2n 次
* 交换类排序法：
1. 冒泡排序法：通过相邻的两个数两两对比进行适当的交换逐步将表变得有序，长度为N的线性表，最坏情况需要经N/2遍的从前往后的扫描和N/2遍从后往前的扫描，需要比较n(n-1)/2次
2. 快速排序法：冒泡排序法的改进，目前所有排序算法中最快的，一次直接比较得出最大或最小的，时间效率最高为O(log2n)，最坏情况下时间效率为O(n^2)，需要比较n(n-1)/2次
* 插入类排序法：
1. 简单插入排序法：组织两个表，有序表和无序表，依次取无序表中的内容插入到有序表中的相应位置。最好情况下（初始排序序列就是有序的）比较次数为n-1次,移动0次，最坏情况下（初始排序序列完全逆序）比较次数n(n-1)/2，移动次数为n(n-1)/2，平均比较次数和移动次数都约为n^2/4，时间复杂度为O(n^2)
2. 希尔排序法：将整个无序序列分割成若干个小的子序列进行插入排序，最坏情况下所需要比较次数为O(n^1.5)
* 选择类排序法：
1. 简单选择排序法：直接从目前的排序范围内找最小的一个，放在第一个元素位置，其余以此类推，最坏情况下需要比较n(n-1)/2次
2. 堆排序法：对大量的数据元素很有效,通过将无序表转化为堆，可以直接找到表中最大值或者最小值，然后将其提取出来，令剩余的记录再重建一个堆，取出次大值或者次小值，如此反复执行就可以得到一个有序序列
#### 小结
循环队列是线性的并且属于顺序存储结构
某循环队列的存储空间为Q(1:m)，初始状态为front=rear=m。现经过一系列的入队操作和退队操作后，front=m-1，rear=m，则该循环队列中的元素个数为 1 个
除了希尔排序和堆排序其它排序最坏情况下都需要比较n(n-1)/2次
Comments NOTHING