书籍《数据结构与算法》
数据结构与算法
第一章 引言
指针：指向某个块地址的指针。 int *p;
数据结构：相互之间存在一种或多种特定关系的数据元素的集合。
struct horse //声明结构体horse，定义Silver
{
int age;
int height;
} Silver;
typedef struct {
int age;
int height;
} Silver; //声明及定义Silver
第二章 数据结构导论
基本概念: 数据（总称）、数据元素（基本单位）、数据对象（元素集合）、数据结构（关系集合）
抽象数据类型：一个逻辑类型的数据集合以及这个集合上的一组数据。
算法性质：正确性、具体性、确定性、有限性、可终止性。
算法标准：正确性、可读性、健壮性、高效性、简洁性。
时间复杂度O(n)：定量描述了该算法的运行时间，输入为无穷大时的情况，是事前估算算法分析。
空间复杂度：运行完一个程序所需内存的大小。
第三章 线性表
线性表（List）：n个数据元素（同属一个集合）的有限序列。
基本操作：创建、销毁、清空、插入、删除、遍历；
判断是否为空表、返回表长、得到位序i的数据元素、返回首个数据元素e的位序、得到数据元素e的直接前驱或直接后继。
（1）顺序表：用顺序的存储方式实现线性表的存储，即数组形式。线性表长度应小于数组长度。
基本操作：创建、销毁、插入、删除、查找；
（2）链表：使用链式存储方式实现的线性表。通过指针指向其他元素。
注：p、s、prior、next都是指向一个结构块的指针，包括块中的数据和指针，而块中的指针指向的是下一个或上一个结构块，包括数据和指针。
单向链表的基本操作：创建、销毁、插入、删除，查找；
双向链表的基本操作：创建、销毁、插入、删除，查找；
单向循环链表
双向循环链表
有序表（顺序和链式）
线性表中的数据已经排序的表。
顺序表与链表的优缺点：顺序表读取、查找、赋值、替换比较方便，但删除、插入耗时；链表刚好相反。针对对象的不同性质使用不同的表。
第四章 栈与队列
（1）栈（stack）：限定只能在表的一端进行插入和删除操作的线性表。LIFO
基本操作：创建、销毁、清空、压栈Push、出栈PoP、遍历；判断是否为空栈、返回栈长、得到栈顶元素。
顺序栈：利用一组连续的存储单元（数组）依次存放自栈底到栈顶的所有元素。需要初始化时分配空间大小，及检查是否栈满。
链栈：用链式存储结构实现的栈。数据进栈时临时分配空间，是更好的栈。
（2）队列（Queue）：限定只能在表的一端插入、另一端删除的线性表。FIFO
基本操作：创建、销毁、清空、插入队尾、删除队首、遍历；判断是否为空队列、返回队列长度、得到队列首元素。
顺序队列：利用一组连续的存储单元（数组）依次存放自队首到队尾的所有元素。
链队列：用链式存储结构实现的队列。数据进队列时临时分配空间，是更好的队列。
（3）迭代与递归：
第五章 串与数组
（1）串（String）：字符串，由零个货多个字符组成的线性表。
基本操作：创建、复制、比较、连接、替换、删除、销毁；判断是否为空串、返回串长度、返回子串位置。
顺序存储字符串：利用一组连续的存储单元（数组）依次存放字符序列。
块链存储字符串：一个结点存储多个字符的链式存储字符序列。
模式匹配（在主串中查找子串）：BF算法、KMP算法
BF算法：从主串头部开始匹配，不匹配时，将子串在主串中向后移动一位，又从子串头部重新开始匹配，直到匹配成功。
KMP算法：先对子串进行分析，从主串头部开始匹配，不匹配时，将子串在主串中向后移动一位，从子串的某点开始匹配，直到匹配成功。
（2）数组：多维数组是一种线性表。
基本操作：创建、销毁、读取、赋值。
矩阵压缩：特殊形状矩阵的压缩存储（三角矩阵、条带矩阵、对称矩阵）、稀疏矩阵的压缩存储（三元组顺序表）
第六章 树与二叉树
（1）树（Tree）：n（n≥0）个结点的有限集。任意非空树中有且仅有一个根（Root）结点，其余结点称子树。
基本操作：构造空树、创建、销毁、清空、插入、删除、遍历；判断是否为空树、返回树的深度、返回根结点、返回双亲结点、返回左孩子、返回右孩子。
结点（Node）：包含一个数据元素及指向其子树的分支。
结点的度（Node Degree）：结点拥有子树的个数。
树的度（Tree Degree）：非空树中各结点度的最大值。
分支结点（Offshoot Node）：树中结点的度不等于0 的结点。
叶子结点（Leaf Node）：树中结点的度等于0 的结点。
孩子（Child）：结点的直接后继。
双亲（Parent）：结点的直接前驱。
兄弟（Sibling）：同一个双亲的结点之间互为兄弟。
祖先（Ancestry）：从树根到某结点所经分支上的所有结点。
子孙（Descendant）：某结点所有子树上的所有结点。
结点层次（Level）：非空树中根结点的层次是1，其余结点的层次是双亲层次加1。
树的深度（Height）：所有结点层次的最大值。
有序树与无序树（Ordered Treeand Unordered Tree）：树中结点的各个子树从左到右是否有次序的。
森林（Forest）：m棵互不相交的树组成。
（2）二叉树（Binary Tree）：每个结点的度都不超过2的树。
满二叉树：所有分支结点的度都等于2，且所有叶子结点都在同一层。
完全二叉树：从上到下、从左到右对树进行编号，如果树的结点编号与满二叉树的结点编号的位置完全相同，称为完全二叉树。
二叉树存储结构：顺序存储结构（以完全二叉树的形式顺序存储）、链式存储结构（以左孩子、数据、右孩子的结点结构通过指针指向实现）；下标为0的数组单元空闲不用，空指针用0表示。
二叉树的遍历：根据双亲的位置关系，每个结点的遍历方式
前序：双亲、左孩子、右孩子
中序：左孩子、双亲、右孩子
后序：左孩子、右孩子、双亲
层序：自上而下、自左向右逐层遍历。
线索二叉树：为了遍历序列中的前驱和后继，将二叉链表中的空指针指向结点的前驱和后继，又为了与左右孩子进行区分，引入左右标志，区分左右孩子与前驱后继。线索二叉树采用中序遍历的方式更实用。
lchild | ltag | data | rtag | rchild |
当ltag、rtag == 0时，lchild、rchild为左右指针，指向左右孩子；
当ltag、rtag == 1时，lchild、rchild为左右线索，指向前驱后继；
（3）树的存储结构：
双亲表示法
孩子链式表示法
孩子双亲表示法
孩子兄弟表示法
（4）树、森林与二叉树的转换：
树转换成二叉树
① 在所有兄弟结点之间加一连线；
② 对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。
森林转化成二叉树
① 将森林中的每棵树变为二叉树。
② 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。
二叉树转换成树、森林
若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，…，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。
（5）树与森林的遍历
先根遍历树（同于二叉树先序遍历）、后根遍历树（同于二叉树中序遍历）、层序遍历树；
先序遍历森林（同于二叉树先序遍历）：先访问第一棵树的根，而后第一棵树的子树，重复如此。中序遍历森林（同于二叉树中序遍历）：先访问第一棵树的子树，而后第一棵树的根，重复如此。
（6）哈夫曼树与哈夫曼编码
哈夫曼树，又称最优二叉树，运用于通信、数据压缩、决策与算法。
路径：两结点之间的分支。
结点的路径长度：根结点到该结点的分支数。
树的路径长度：树根到所有结点的路径长度之和。
结点的权值：除结点数据元素值之外，结点上有意思的数值（如频数）。
结点的带权路径长度：树根到某结点的路径长度与该结点权值的乘积。
树的带权路径长度：树中所有叶子结点的带权路径长度之和。
哈夫曼树：带权路径长度WPL最小的二叉树。
如下图中‘n’的路径长度是4，结点的带权路径长度是2*4，图中紫色方框内的数字与字母旁的数字都表示结点的权值，即不带路径长度的出现的次数。
前缀编码：一组不等长编码中的任一编码都不是其他编码的前缀；前缀编码能保证译码的唯一性；又称哈夫曼编码，最优前缀编码。
利用原始数据，统计出现的不同字符的个数、每种字符的频数，构造一棵哈夫曼树，坐分支代表0，右分支代表1，得到每个字符的编码，得到的编码方式是最短的数据编码方式，通过先序遍历方式遍历该树，或使用栈的方式记录路径序列，得到叶子结点值，即为编码前数据。
第七章 图
图（Graph）有顶点和边组成，即G = (V, E)；Vertex表示顶点，边分为无向边Edge (Vi, Vj) 与有向边<Vi, Vj>（弧Arc）。图中每条边都是有向边称为有向图，否则反之。
基本操作：创建图、销毁图、插入顶点、删除顶点、增加弧、删除弧；寻找顶点序号、寻找顶点值、返回第一个邻接点、返回下一个邻接点、深度遍历、广度遍历。
邻接点：若两顶点间存在边，则称两顶点互为邻接点。
完全图：n个顶点，无向完全图（n(n-1)/2条边）、有向完全图（n(n-1)条边）
稀疏图（边数小于）、稠密图（边数大于）。
顶点的度TD(V)、入度ID(V)、出度OD(V)，度为奇数的顶点为奇度顶点（奇点），同理偶点。
路径：顶点之间的边。
路径长度：边的数目。
回路（环）：第一个顶点与最后一个顶点相同。
子图：G1 = (V1, E1)，G2 = (V2, E2)，V1∈V2，E1∈E2，G1为子图。
连通图：无向图中任意两顶点之间都连通，为连通图。
连通分量：无向图中极大连通子图为连通分量。“极大”指的是包含互连的极大顶点和这些顶点的所有边。与连通子图的区别。
强连通图：有向图中顶点Vi到Vj，且顶点Vj到 Vi都有路径，为顶点的强连通；任意两顶点都是强连通，为强连通图。
强连通分量：有向图中极大强连通子图。
权和网：边带权值称为网，或带权网。
生成树：树中包含图的所有顶点，且树是连通图，无回路。
生成森林：连通分量的生成树构成生成森林。
图的存储：邻接矩阵表示法、邻接表表示法、十字链表。
邻接矩阵表示法：一个一维数组存储顶点，一个二维数组存储边。
邻接表表示法：把图中每个顶点把与其相连的所有顶点用单链表相连。
图的遍历：深度遍历、广度遍历。需借助一个辅助数组标记顶点是否被访问。
深度遍历DFS：类似于树的前序遍历；先选择一个出发点，对每一个可能的分支路径深入到不能再深入时才回溯，并另辟路径继续深入下去遍历；如果还有顶点未被访问，则另选一个出发点，重复上述过程，直到所有顶点被访问。
广度遍历BFS：类似于树的层序遍历；先选择一个出发点，接着依次访问与出发点邻接的所有顶点，然后再从这些顶点发出，依次访问与上述顶点邻接的所有顶点；如果还有顶点未被访问，则另选一个出发点，重复上述过程，直到所有顶点被访问。
最小生成树
生成树：所有顶点均由边连接在一起，但不存在回路的图。
最小生成树：生成树的每条边上的权值之和最小。
实例：在N个城市之间修路，总路线的总和最小问题。
Prim算法
Kruskal算法
拓扑排序
有向无环图：不存在回路的有向图。它是描述一项工程进度的有效工具。
AOV网：用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex network)
（1）在有向图中选一个没有前驱的顶点且输出之
（2）从图中删除该顶点和所有以它为尾的弧
（3）重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止
关键路径
AOE网：在有向无环图中，用有向边表示一个工程的各个活动，有向边上的权值表示活动的持续时间，用顶点表示事件，这样的有向图称为边表示活动的网络。
关键路径：在AOE网中，源点到汇点的最长路径。通过关键路径可以得到整个工程的工期，加快进度。
Ve(j)——表示事件Vj的最早发生时间
Vl(j)——表示事件Vj的最迟发生时间
e(i)——表示活动ai的最早开始时间
l(i)——表示活动ai的最迟开始时间
l(i)-e(i)——表示完成活动ai的时间余量
最短路径
最短路径：在有权图中，顶点之间路径上所有边的权值之和最小；在无权图中，顶点之间经过的边数最少的路径。
Dijkstra算法
Floyd算法
第八章 查找表
查找：确定一个具有特定值的元素是不是一个特定集合的成员。
静态查找表：对查找表只做查找不存在其他操作；
动态查找表：对查找表即做查找，也做其他操作，如插入和删除。
关键字：数据元素中某个数据项的值，用它标识一个数据元素。
（1）静态查找表
对象通常是顺序存储的线性表或有序表。方法是顺序查找、二分查找与索引查找，将三中方法相互结合使用更佳。
顺序查找：在顺序线性表中依次与给定值相比较直至相等或不存在。
二分查找：在顺序线性表中，通过指针top、bot、mid，其中mid=(top+bot)/2，三个指针在待查找表中二分式移动，匹配关键字。
索引查找：对关键字“分块有序”进行查找的算法，类似字典的查找。
（2）动态查找表：在程序运行过程中动态生成查找表
二叉查找树：动态生成、插入、删除二叉查找树。最终转化成平衡二叉树AVL树：左子树的深度减去右子树的深度，得到的平衡因子只能取-1、0、1。
键树：也叫数字查找树，树中的每个结点是关键字的一个字符，从根到叶子对应一个关键字。
哈希表（Hash Table）：也叫散列表
散列：通过把关键码值映射到表中的一个位置来访问记录的过程。大多数散列方法是根据地址计算需要的顺序把记录放在表中。也就是说，它通过计算一个关键字的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。
散列函数：把关键码值映射到位置的函数。
散列表：存放记录的数组。
槽Slot：散列表中的一个位置。
散列方法一般只适用于集合，不适用于允许多个记录有同样关键码值的应用程序，也不适用于范围检索。
但是散列过程中不可避免的会发生表中数据冲突的情况，即表中某位置已经存在数据，后又新加的数据怎么处理。
冲突解决技术：开散列方法、闭散列方法
开散列方法：在散列表不记录具体的数据，记录一个链表的表头，链表中记录所有与这个位置有关的数据。
闭散列方法：把所有记录直接存储在散列表中，若被占则调到下一个记录。
负载因子：描述填充程度，α=N/M，N表中当前记录数目，M表的总记录数目。
第九章 排序
简单排序：选择、冒泡、插入排序
选择排序：在记录中找最小，放第一个位置，找次小的，反复进行。
冒泡排序：每次从底部开始逐个向上比较，较小的数向上移，循环N个记录。
插入排序：比较第一个和第二个数，将较小的数插入前面，比较第三个数与第一二数，插入第三个数，插入的后面的数往后移。
希尔排序Shell Sort：也称递减增量排序算法，实质是分组插入排序。
基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更短了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。
组数 [ 13 14 94 33 82 25 59 94 65 23 45 27 73 2539 10 ]
5个步长划分，得5列 排序后结果
13 14 94 33 82 1314 73 25 23
25 59 94 65 23 2527 94 33 39
45 27 73 25 39 4559 94 65 82
3个步长划分，得3列 排序后结果
13 14 73 13 14 25
25 23 25 2523 33
27 94 33 2745 59
39 45 59 3965 73
94 65 82 9494 82
1步长一组，得1列完成排序
快速排序Quick Sort：快排采用了分治法的思想。
步骤：（1）从数列中挑出一个元素作为基准数。
（2）分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边。
（3）再对左右区间递归执行第二步，直至各区间只有一个数。
堆排序 Heap Sort：采用二叉堆的数据结构来实现的。虽然实质上还是一维数组，二叉堆是一个近似完全二叉树 。
二叉堆具有以下性质：
（1）父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
（2）每个节点的左右子树都是一个二叉堆（都是最大堆或最小堆）。
步骤：
（1）创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
（2）堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
（i给上述两个过程调用）最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
归并排序Merge Sort：归并排序的思想就是先递归分解数组，再合并数组。
先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
再考虑递归分解，基本思路是将数组分解成left和right，如果这两个数组内部数据是有序的，那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？可以再二分，直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序。然后合并排序相邻二个小组即可。
基数排序：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
稳定性：对于两个关键字相等的记录在经过排序后，不改变它们在排序之前在序列中的相对位置。
算法思想：穷举法、迭代法（递推法）、递归法、回溯法、贪心法、分治法、动态规划法（前轮的最优解来决定下一个解）、分支定界法。
参考文献：
http://student.zjzk.cn/course_ware/data_structure/web/gailun/gailun1.1.1.htm
google：维基百科