数据结构与算法经典问题解析
图书馆最近在上新书，看到了这本书，就借回去看了。虽然书中也有少许错误，但是讲解还是通俗易懂的。
每章小结
第一章 绪论
变量，数据类型，数据结构（data structure，线性与非线性），抽象数据类型（ADT）。
什么是算法：解决问题的方法与步骤，不需要严格的证明。
算法分析：确定在时间和空间上比较有效的算法。
增长率：近似，忽略微不足道的。
分析算法：最好（下界），平均时间，最差（上界）
大O表示法（上界），大Ω表示法（下界），大Θ表示法（平均）。
渐近分析（循环，嵌套循环，循环执行时间，if-then-else语句，级数时间复杂度），性质，常见公式。
分治法主定理：T(n)=mT(n/p)+O(n)。
算法分析经典例题。
递归，数组，动态数组，链表，栈，队列，树，图，排序，查找，选择，散列，字符串
第二章 递归和回溯
递归：任何调用自身的函数称为递归。递归算法必然需要是收敛的。递归比迭代代码更加简洁，而且在编译或者解释时，循环灰转化为递归函数。所以，递归往往使得处理更加简单高效。比如，排序，搜索，遍历。
函数不再递归时为基本情形（base case），调用时称为递归情形（recursive case）。
范例：阶乘。
递归在内存里的情况：递归函数每次的再调用会产生副本（准确讲只是一些返回变量），函数均结束时会逐个返回。
记住递归不能出现无穷递归，递归基于栈操作。
迭代和递归。
递归算法经典用例：
斐波那契数列、阶乘
归并排序，快速排序
二分查找
树的遍历：比如中序遍历，前序遍历，后序遍历
图的遍历：深度优先搜索，广度优先搜索
动态规划例子
分治算法
汉诺塔
回溯算法
回溯是一种采用分治策略进行穷举搜索的方法。
最笨但最有效的方法是：尝试所有的可能性
回溯算法经典用例：
二进制串：产生所有的二进制串
生成k进制串
背包问题
广义字符串
哈密顿回路
图着色问题
递归算法和回溯具体的实现不一定要想的特别明白，只要思路能用递归实现就好，比如想简单的情况，一般是n=2-3，再计算他的特性。
测试中可以把数据设为char，然后表示top,front,rear等“指针”可以表示成下一位空的元素，也可以表示成当前元素，哪个方便用哪一种。
第三章 链表
链表：相邻之间指针相连，最后一个元素的后续指针值为NULL，链表长度可增可减比较方便（注意不能无穷无尽，避免内存耗尽），空间浪费较少。
链表的主要操作：插入，删除。计数，查找，清空链表。
数组：在一整个连续内存块中，访问时基于首地址的偏移量以及数组元素的大小。
数组简单易用，访问元素在常数时间上较快。但是数组大小分配后即固定，基于数组的插入操作比较复杂。
动态数组：大小自动调整的线性数据结构。固定化一个数组初始大小，而后一旦满了就扩展两倍于原始数组大小的新数组，若元素个数不足数组大小的一般，则数组大小减少一半。
数组的再次更改大小其实是重新划分一个数组，再将元素全部复制过去，这样速度较慢，不如链表方便。链表的缺点主要在于访问单个元素的时间开销问题，数组可以随机读取，而链表顺序读取。时间开销在O(1)~O(n)。链表的增加删除工作也比较麻烦，也需要额外的内存空间来存储指针。
单向链表：每个结点有指向后一个元素的next指针。
链表基本操作：遍历，插入，删除
链表的遍历：头结点开始，依次遍历，当next指针的值为null时结束遍历。
单向链表的插入：在表头插入，在表尾插入，中间位置随机插入
单向链表的删除：删除表头，删除表尾，删除中间的结点
单向链表的清空：从头结点开始逐个删除，利用临时变量（对象），auxilaryNode
双向链表：首尾均可访问整个链表。缺点是需要再增加一个指针。结点插入或删除会更耗时。
双向链表操作要比单向链表多一个previous“指针”变量
循环链表：尾结点指向头结点。此时不能通过null判断是否是尾结点或者头结点。
循环链表可以用于管理计算机的计算资源，可以用于实现循环缓冲区，栈，队列。
改进的存储高效的双向链表：
1 ptrdiff=后继结点的地址 异或 前驱结点的地址
2 松散链表，链表的查找O比数组大，可以将链表分组。比如4个是一个小链表的串联。
练习：
链表实现栈
倒数找链表
散列表
判断是循环链表还是单向链表
求整数的无穷级数的中位数
交换链表的相邻结点
判断回文数
二叉树转双向链表
删除链表中重复的字符
第四章 栈
可以把栈（stack）比喻成餐馆里叠着的盘子，需要时从顶端取（入栈），洗干净后再放在顶端（出栈）。
栈是一个有序线性表，栈顶（top）执行插入和删除操作。后入先出（LIFO）或者先入后出（FILO）。
入栈（push）和出栈（pop）。空栈执行出栈为下溢（underflow），满栈执行入栈为溢出（overflow）。通常，将下溢和溢出认为错误异常。
栈在计算机程序中做执行其他任务时的保存现场的执行地址的功能。
栈的主要操作：压栈，出栈，栈长，为空，为满
栈的应用：
符号匹配
中缀表达式转化为后缀表达式
计算后缀表达式
实现函数调用（包括递归调用）
求范围误差（极差）
网页浏览中的浏览记录
文本编辑器中的撤销功能
HTML和XML文件中的标签匹配
数的遍历算法等
栈的实现方式比较多，常用的方法：
基于（动态）数组的简单实现（数组倍增技术，执行n次push操作约需logn次倍增操作，倍增太多可能导致内存溢出）
基于链表的实现（headNode）
栈的练习
匹配括号等对称符号
中缀表达式转化为后缀表达式
判断回文
逆置栈的内容
栈实现队列
123456通过出入栈得到特定的内容
对栈中元素进行排序
删除栈中重复的字符
第五章 队列
队列好比排队买票，排队打饭等等
队列只能在一端插入，另一端删除的有序线性表
队列是先入先出（FIFO）或后入后出(LILO)
入队（EnQueue），出队（DeQueue）
空队列执行出列操作会导致下溢（underflow），对满队列执行入队会导致溢出（overflow）
队列的常用操作：
入队enQueue，出队deQueue，返回队首的元素front，返回队尾的元素rear，队列元素个数，容量大小，是否为空
队列的应用
模拟系统的任务调度
模拟现实生活中的购票行为
多道程序设计
异步数据传输
客户等待
队列的实现：
（动态）循环数组，链表
队列的相关问题
逆置队列元素
两个栈实现队列
两个队列实现栈
反向输出元素
第六章 树
树是一种类似链表的结构，不同的是树的一个结点可以指向多个子结点
树是一种典型的非线性结构，具有层次特性的图结构的一种方法。
相关术语：
根节点：根节点是一个没有双亲结点的结点，树中最多只有一个根节点
边：双亲结点到孩子结点的连接
叶子结点：没有孩子结点的结点
兄弟结点：拥有相同双亲结点的所有孩子结点
祖先结点：从根节点出发，一条路径到某结点，则这条路径上经过的结点
结点的大小：子孙结点的个数，包括自身
树的层：相同深度所有结点的集合为树的层，根节点为0层
结点的深度：根节点到该结点的路径长度
结点的高度：该结点到最深子孙结点的路径长度
树的高度：所有结点高度的最大值。对于一棵树而言，它的高度和深度一样，但对一个结点而言，深度 和高度不一定一样
斜树：除叶子结点为，每个结点都只有一个孩子结点，全只有右孩子结点叫右斜树，全只有左孩子结点叫左斜树
二叉树：
如果每个结点最多有两个孩子结点，则称为二叉树
严格二叉树：每个结点2个或0个孩子结点
满二叉树：每个结点有2个孩子结点，且所有叶子结点都在同一层
完全二叉树：二叉树本身的高度h，所有叶子结点的深度为h或h-1
满二叉树的结点个数：2^(h+1)-1
完全二叉树的结点个数：2^h~2^(h+1)-1
满二叉树的叶子结点个数:2^h
n个结点的完全二叉树，空指针的个数：n+1
二叉树的操作
插入，删除，查找，遍历
获取树的大小，树的高度，其和最大的层，找出最近的公共祖先结点
二叉树的应用
编译器表达式树
数据压缩算法中的赫夫曼编码树
优先队列
二叉树的遍历
前序遍历（DLR），中序遍历（LDR），后续遍历（LRD），层次遍历
递归与非递归遍历
递归是利用系统栈
非递归是自己自定义栈
层次遍历：利用队列实现
二叉树问题：
找出最大元素（递归、非递归）
找出某个元素（递归、非递归）
插入一个元素
获取二叉树结点的个数
删除一个元素
查找最深结点
比较二叉树结构
列出二叉树的根结点到某结点路径
镜像二叉树
已知中序遍历和前序遍历求树或后序遍历
…
通用树（N叉树）
线索二叉树（无需栈或队列的遍历）
leftp ltag data rtag rightp
如果ltag==0 指向中序序列的左结点
如果ltag==1 指向左孩子的左结点
如果rtag==0 指向中序序列的右结点
如果rtag==1 指向右孩子的右结点
表达式树
用来组合表达式的树，计算机根据优先级处理表达式的过程
异或树，二叉搜索树，平衡搜索二叉树，AVL树
红黑树，伸展树，增强树，替罪羊树，区间树等
第七章 优先队列和堆
优先队列ADT也是队列，但是不是按先到先服务，而是按照优先级高低处理。
常用于计算机的作业调度
优先队列的操作：
优先队列是元素的容器，每个元素有一个相关的键值
insert(key,data)
deleteMin/Max()
getMin/Max()
队列的大小，堆的排序
优先队列的应用：
数据压缩，最短路径算法（Dijkstra），最小生成树算法（Prim），顾客排队算法，查找第k个最小元素
优先队列的实现：
无序链表，无序数组，有序数组，有序链表，二叉平衡树，平衡二叉搜索树的实现，二叉堆
这几种实现的优缺点
堆：堆是具有特定性质的二叉树，是一个完全二叉树，且结点的值必须均大于等于其孩子结点的值（或均小于等于孩子结点的值）
二叉堆
第八章 并查集ADT
集合，无需考虑顺序
第九章 图
两个对象之间的路径问题
从一个城市到另一个城市的路径多样
图可以表示为（V，E），v是结点的集合，称为顶点，e是顶点对的集合，称为边
顶点和边代表位置和存储元素
有向边：有序顶点对<u,v>，u->v，单向道（单行道）
无向边：无序顶点对(u,v)，u<->v，双向道（火车线）
有向图：所有的边都是有向边（路由网络）
无向图：所有的边都是无向边（飞行航班）
无环图：树的变形
自环：自身指向自身
平行边：连接相同顶点对的边
顶点的度：关联该顶点的边的数量
子图：图的子集
简单路径：不包含重复顶点的路径
环路：简单路径基础上的收尾相同结点
连通图：每对顶点都有路径可达
有向无环图：不包含环的有向图
有权图：每条边有一个整数表示的权重来代表距离或者花费
完全图：包含所有边的图
稀疏图，稠密图
有向有权图：网络
图的应用：
电子线路之间的组件关系
交通网络
计算机网络
数据库
图的表示：
边的列表，邻接矩阵，邻接表，邻接集
图的遍历：
深度优先搜索（DFS）：类似树的前序遍历，使用栈实现，一个顶点开始走遍所有的路径，遍历所有的其他顶点。访问中有是否访问标记。
广（宽）度优先搜索（BFS）：类似树的层次遍历，使用队列实现，从一个顶点出发，逐层遍历一遍。访问中有是否访问标记。
拓扑排序：无环图中对顶点的排序
入度，出度
解决课程选修的先决条件，检测死锁，计算作业的流水线，检查符号的链接环，解析电子表格中的公式
最短路径算法：
无权图，有权图，带负边的有权图中的最短路径
应用：找出一个地方到另一个地方的最快最短路径
Dijkstra算法，Bellman-Ford算法等
最小生成树：图生成树 Prim算法，Kruscal算法
图算法相关问题：
n顶点的无向简单图具有的最大边数
n个顶点和e条边的图有多少不同的邻接矩阵，邻接表，判断是否有孤立点
判断指定两个顶点是否路径可达
DFS应用
四着色问题
反转图
哈密顿环
第十章 排序
排序是按某种顺序进行排列元素的一种算法
排序是计算机中重要算法，可以显著降低问题的复杂度
排序的分类：
比较的次数
交换的次数
内存的使用
递归
稳定性
适应性
内部排序，外部排序
冒泡排序(bubble sort)
算法：迭代的对输入序列中的第一个元素到最后的元素按两两交换方法。逐渐将键值较小的元素如同气泡一样浮在序列的顶端。
冒泡排序时间复杂度高O(n^2)，算法实现简单。
冒泡排序可用来检测是否已经是排序的
改进版：增加一个附加标记，判断是否已经排序好，时间复杂度最好O(n)，最差O(n^2)
选择排序(selection sort)
算法：寻找序列中的最小值，用当前位置实现最小值，重复过程，分区（partition）操作。
时间复杂度最坏O(n^2)，最好O(n)
插入排序(insertion sort)
算法：每次从输入数据拿出一个元素，插入到另一个已经排好序的序列正确位置
时间复杂度O(n^2)
希尔排序(shell sort)
泛化的插入排序，适合序列已经几乎有序的情况
归并排序(merge sort)
将序列分成两部分并递归处理每一部分，之后将子问题解合并
堆排序(heap sort)
基于比较的算法，也是选择排序
快速排序(quick sort)
分治算法技术的实例，分区交换排序，基于比较排序的著名算法
树排序
二叉搜索树
算法比较：
线性排序算法：
计数排序，桶排序，基数排序
拓扑排序
外部排序
第十一章 查找
查找是一个从项目的集合中寻找某个具有特定属性的项目的过程。
项目可以是数据库的记录，数组中简单数据元素，文件中的文本，树中的结点，图中的边和顶点等。
查找是计算机中的核心算法。
查找的类型：
无序的线性查找
排序/有序线性查找
二分查找
符号表和散列
字符串查找算法：键值，三叉搜索树，后缀树
第十二章 选择算法（中位数）
选择算法是指在某个列表中寻找第k个最小/最大的数字。包括最小值，最大值，中位数。
基于排序的选择算法
基于划分的选择算法
中位数算法
第十三章 符号表
字典，关键字与键值的一种数据结构
应用：
拼写检查工具
数据库应用的数据字典
加载器(loader)，汇编器(assembler)，编译器(complier)产生的符号表
路由器（DNS查找）
第十四章 散列
散列是一种用以实现信息存储和快速检索的技术
执行优化搜索和符号表的实现
平衡二叉树的插入删除检索的操作时间复杂度是O(logn)
但实际应用中，这些操作仍然太慢
散列可以提供平均时间复杂度为O(1)，最坏情况为O(n)的操作
散列表ADT:
CreateHashTable
HashSearch
HashInsert
HashDelete
DeleteAll
散列的例子：
给定字符串，查找是否存在重复的符号，比传统的线性扫描要快的多
散列的组成：
散列表：数组的一种推广，关键字分配数组中的位置
散列函数：将关键字转为索引
负载因子：散列函数是否将关键字均匀分布
冲突：两个记录的存储位置相同
冲突解决算法：直接连接法（分离链接法），开放地址法（线性探测法，二次探测法，双重散列法）
散列达到O(1)的时间复杂度
静态散列、动态散列
布鲁姆过滤器（Bloom filter）
第十五章 字符串算法
自动完成，字符串匹配
蛮力法，Robin-Karp算法，基于有限自动机的字符串匹配算法，KMP算法，Boyce-Moore算法，后缀树等
第十六章 算法设计技术
待解决问题与已解决问题的相似
递归或迭代
过程式（C,PHP,PERL）或声明式(SQL)
串行或并行或分布式
确定性和不确定性
精确或相似
贪婪法：问题化为多个阶段，每个阶段找出最佳方案，不考虑后续决策的影响
分治法：原问题分成多个子问题，子问题与原问题类型相同规模较小，再分别递归求解，最终合理整合
动态规划法（DP）：备忘录技术
线性规划法：不等式约束下，最大化（或最小化）输入变量的线性函数
归约（转化求解）：复杂问题转化为一个已解决问题
复杂度，随机算法，分支定界、枚举、回溯等
第十七章 贪婪算法
第十八章 分治算法
第十九章 动态规划算法
第二十章 复杂度类型
随着问题规模大变化，其复杂度的增长速率
简单问题，难问题
用计算机解决问题
（终）