经典数据结构和算法回顾
最近想回过头来看看以前写的一些代码，可叹为何刚进大学的时候不知道要养成写博客的好习惯。现在好多东西都没有做记录，后面也没再遇到相同的问题，忘的都差不多了。只能勉强整理了下面写的一些代码，这些代码有的有参考别人的代码，但都是自己曾经一点点敲的，挂出来，虽然很基础，但希望能对别人有帮助。
链表
链表是一种非常基本的数据结构，被广泛的用在各种语言的集合框架中。
首先链表是一张表，只不过链表中的元素在内存中不一定相邻，并且每个元素都可带有指向另一个元素的指针。
链表有，单项链表，双向链表，循环链表等。
单项链表的数据结构
如下
对链表的操作
主要有增删查
仅仅只需要将尾指针指向头节点，就可以构成单项循环链表，即tail->link=head;，有的时候，可能需要将链表逆置，当然，如果需要逆置，最好一开始就做双向链表。
删除链表中所有值为x的节点，以及清除链表中重复的节点
对于双向链表，也就是在节点中再添加一个节点，让它与另一个指针指向的方向相反。当然，当节点有了两个节点之后，就可以构成更复杂的比如树图等复杂结构了，双向链表可像如下定义
对双向链表的操作也无外乎增删改
链表是个很基础的东西，后面一些复杂的算法或数据结构的本质也是一个链表。链表和顺序表（也就是数组）都可以再进一步抽象成更复杂的数据结构。
比如队列和栈，不过是在链表或顺序表的基础上限制单端操作而已。再比如，由链表和顺序表还可以构成二叉树堆，它们还可以组合使用构成邻接表，十字链表，邻接多重表等结构用来描述图，等等。
字符串相关算法
做里快两年web开发了，可以说字符串是用多最多的数据类型了，所以针对字符串的算法也非常的多。先从简单的慢慢来。
首先最基本的是对字符串的求长，连接，比较，复制等
字符串比较复杂一点的就是模式匹配和子序列（编辑距离）的问题。
首先是较为简单的BF算法，这种算法原理非常简单，比如连个串a（主串）和b（模式串），首先将a1和b1进行比较，如果相同，则将b2与a2进行比较，如果还相同，继续拿a3与b3比，直到b串匹配完，怎匹配完成，如果出现不同的，怎回到最初的状态，将b1与a2进行比较，将b2与a3比较，等等，如此反复直到失败或成功。
较为复杂的算法是kmp算法，KMP算法的关键是避免BF算法中的回朔。并且当匹配失败后向右滑动到一个能自左最大对齐的位置继续匹配。
若在ai,bj的位置匹配失败，所以已经匹配的串便是
B1 B2 … Bj-1 == Ai-j+1 Ai-j+2 … Ai-1;
假设滑动完后要让Bk与Ai对齐，则应该有
B1 B2 B3 … Bk-1 == Ai-k+1 A-k+2 … Ai-1;
因为是向右滑动，想一想i的位置不变，B向右滑动，很显然，k要小于j。
所以进一步可以得到k到j之间B的子串（Bj前面的k-1个字符）与Ai前的k-1个字符是相同的，即
Bj-k+1 Bj-k+2 … Bj-1 == Ai-k+1 Ai-k+2 … Ai-1;
所以有
B1 B2 B3 … Bk-1 == Bj-k+1 Bj-k+2 … Bj-1
可以看出来，这个有个特点，字符串 B1 B2 ….. Bj-1关于Bk有种对称的感觉，不过这个不是镜像对称，不过我还是喜欢这么记`对称`,这也是求next值的依据，这个next就是k，就是偏移值。
next(j) = 0 (j==1) || max{k|1<=k<j && B1 B2 B3 … Bk-1 == Bj-k+1 Bj-k+2 … Bj-1} || 1；
下面是完整的KMP算法
下面的问题是最长公共子序列，算法的思想是动态规划，核心是转义方程
，也就是当两个字符相等时取左上元素+1，不相等时取左和上中大的那个
很显然，这个算法的时间复杂度和空间复杂度为o(n*m)
二叉树
树这里主要以二叉树为例，二叉树算是一种特殊的树，一种特殊的图。
二叉树具备如下特征
- 第i层最多有2^(i-1)次方个节点
- 深度为k的树最多有2^i-1个节点，也就是满二叉树等比求和
- n0=n2+1，即叶子节点的数量恰好是度为2的节点数加1，主要原因是节点数总比度数多1，因为根节点没有入度，所以有 n0 + n1 + n2 -1 = n1 + 2*n2。
- 对于满二叉树，如果以有序表存储，根节点放在0的位置上，左右孩子放在1,2上，相当于从上到下，从左到右，从0开始对节点进行编号，则对于节点i，它的左孩子应该位于2*i+1上，右孩子位于2*i+2上
- 等等，暂时只记得这些了。
用数组和链表都可以存储二叉树，但我见过的算法大都用数组存储二叉树，想必链表虽然易于理解，但相比写起算法来未必好写。
对二叉树的操作
有增删查遍历等操作，代码如下。
很显然，这个算法的时间复杂度和空间复杂度为o(n*m)
二叉树
树这里主要以二叉树为例，二叉树算是一种特殊的树，一种特殊的图。
二叉树具备如下特征
- 第i层最多有2^(i-1)次方个节点
- 深度为k的树最多有2^i-1个节点，也就是满二叉树等比求和
- n0=n2+1，即叶子节点的数量恰好是度为2的节点数加1，主要原因是节点数总比度数多1，因为根节点没有入度，所以有 n0 + n1 + n2 -1 = n1 + 2*n2。
- 对于满二叉树，如果以有序表存储，根节点放在0的位置上，左右孩子放在1,2上，相当于从上到下，从左到右，从0开始对节点进行编号，则对于节点i，它的左孩子应该位于2*i+1上，右孩子位于2*i+2上
- 等等，暂时只记得这些了。
用数组和链表都可以存储二叉树，但我见过的算法大都用数组存储二叉树，想必链表虽然易于理解，但相比写起算法来未必好写。
对二叉树的操作
有增删查遍历等操作，代码如下。
哈夫曼树的测试数据
图相关算法
图是一种比较复杂的数据结构，图的定义就不在此复述了。
图的一些表示方法（存储结构）
- 邻接矩阵
- 对于一个又n个节点的图，邻接矩阵以一个n*n的二维数组a来描述图，对于不同的图，比如，有向图和无向图，带权图和无权图，a[i,j]表示的含义有所不同，但都是描述边的。
- 邻接表
- 邻接表组合使用数组和链表描述图，其中数组的每一个元素代表一个节点i，i由两部分组成，一部分代表节点的数据，另一部分为一个指向一链表，这个链表里存放着能从节点i出发能走到的所有节点。对于有向图和无向图会有不同的表示。邻接表一般要比领接矩阵更省空间，但它带来了求入度不便等问题。
- 十字链表
- 结合使用邻接表与逆邻接表，这种方式只能描述有向图。首先它也有一个数组，每个数据元素代表一个节点i，i由三部分组成，i在邻接表的基础上增加了一个指针，这个指针指向第一个以i为弧尾的及节点。这就很好的解决了求入度的问题。
- 邻接多重表
- 邻接多重表主要，它主要用来表描述无向图，在邻接表或十字链表中，数组元素的指针域指向的链表元素其实代表了边，如果用邻接表来存无向图，会使得一条边对应的两个节点分别位于两条链中，当我需要删除一条边时，总是需要找到另一个表示这条边的边节点，再删除。所以有了邻接多重表，邻接多重表就是只用一个边界点表示边，但是将它链接到两链表中（对，没有错，一个节点，同时存在于两个链表中）
下面是上面四种描述的代码表示
图相关操作
对图的操作有创建，增删查等等，其中查就是遍历，遍历分为深度优先搜索和广度优先搜索。
深度优先搜索类似于树的钟旭遍历，即遇到未范围的节点，马上访问，修改标记数组，然后沿着这个节点继续访问，直到访问完，然后在回朔，转向未访问的分支。直到节点被访问完，如果是连通图，只要访问进行一次深度搜索，如果是非连通的，就要搜索多次。
广度优先搜索就像金字塔从上向下的一层一层的搜索，广度优先搜索除了需要用标记数组记录状态以外，还需要用队列来将发现而未访问的节点记录下来。用队列是为了保证遍历顺序。
下面是一些图相关的操作算法
与图相关的还有很多算法，比如求最小生成树的prim算法和kruskal算法
prim算法初始化一个s集合，始终挑选与s集合相连最小的边连接的节点加到集合中，然后更新剩余节点到s的距离，直到所有的点添加进了s集合，prim算法代码如下
Kruskal算法不断选取最小的边i，只要biani加进来不构成回路，则加入到边的集合e中来，直到加入的边能连接所有的顶点，则结束算法
上面主要涉及的是一些数据结构，以及这些数据结构最基本的算法，下面进入算法部分
查找算法
树表查找
线索二叉树
线索二叉树要求任何几节点的左子树比该节点的值小，右子树的值比该节点大。二叉排序树，主要涉及的是插入和搜索
有序表查找
排序算法
冒泡排序
以升序为例，冒泡排序每次扫描数组，将逆序修正，每次恰好将最大的元素过五关斩六将推到最后，再在剩余的元素重复操作
可见，冒泡排序的平均时间复杂度为O(n^2)
选择排序
以升序为例，每次扫描数组，找到最小的元素直接挪到第一个来，再在剩余的数组中重复这样的操作
选择排序的平均时间复杂度也是O(n^2)
直接插入排序
直接插入排序不断在前面已经有序的序列中插入元素，并将元素向后挪。再重取一个元素重复这个操作
插入排序的平均时间复杂度也是O(n^2)
堆排序
堆排序也是一种插入排序，不过是向二叉堆中插入元素，而且以堆排序中的方式存储二叉堆，则二叉堆必定是一棵完全二叉树，堆排序设计的主要操作就是插入和删除之后的堆调整，使得堆保持为大底堆或者小底堆的状态。也就是根节点始终保持为最小或最大，每次删除元素，就将根节点元素与最后元素交换，然后将堆的大小减1，然后进行堆调整，如此反复执行这样的删除操作。很显然，大底堆最后会得到递增序列，小底堆会得到递减序列。
排序的平均时间复杂度为O(NLogN)
快速排序
说到快排，就想起了大一上学期肖老师（教我C语言的老师）与我讨论的问题，当时懵懂无知，后才才知道那就是快排。
快排的思想也很简单，以升序为例，在序列中选一标杆，一般讲第一个元素作为标杆，然后将序列中比标杆小的元素放到标杆左边，将比标杆大的放到标杆右边。然后分别在左右两边重复这样的操作。
快速排序的平均时间复杂度为O(NLogN)
合并排序
合并排序采用分治法的思想对数组进行分治，对半分开，分别对左右两边进行排序，然后将排序后的结果进行合并。按照这样的思想，递归做是最方便的。
行，先总结这么多吧。