双向列表：两个哨兵：header trailer（-1 和 n） 列表的查找：没有高效方法，只能按位置依次向后找。
列表的排序： 选择排序
一直找当前最大的。 以及 插入排序
一次找一个，然后进行对比排序。 逆序对个数：可以决定插入排序的复杂度 设想，当一个元素前面有n个比他大的元素 则在插入排序的时候，会从后向前比较n次。 一次这时候设总逆序对为I，复杂度就为O(I+N)
____________________________________ 第四章：队列与栈
应用：进制转换
括号匹配
栈混洗：将A栈中元素移动到B栈中，通过中间栈S，规定：只能移动到S再全部移动到B 那么有多少种方法呢？打个比方，1先入栈，然后又入了一些，则此时让一些栈，则当1出栈时，假设前面已经进入了k个元素，则后面n-k个只能排列在B的后n-k个位置上 所以这样推算，也就得到了递推关系：S(N) = ∑S(K-1)S(N-K) 这样一个递推数叫做Catalan数，其结果为 (2n)!/(n!(n+1)!) 推导过程详见：
http://blog.sina.com.cn/s/blog_497689ad01000azu.html
判断是否是一个栈混洗
O（n)的算法：直接借助A,B,S模拟混洗过程，运用贪心的原则，如果每次S.pop()时候已经空了或者需要弹出的元素不在S最顶端，则是非法的。
栈混洗与括号的联系：
一个栈混洗的过程可以表示为一个合法的括号表达式：
每次push看作是(，pop看作是)
由此可以预见：有多少种栈混洗结果，n对括号可以构成的表达式（合法）也就有多少种。
中缀表达式求值：
将数字压入栈，并且当遇到运算符时，先判断之前是否有运算符的优先级比当前运算符更大，如果是则首先进行上一个运算符的运算，然后递推进行判断再前一个运算符（运算级相同也要运算），直到不成立，就接着压栈。直到最后到头（压尽元素）。 引入两个栈。
优先级操作符的比较：制表
遇到小于则入栈，遇到大于则计算（栈顶元素 < > = 当前元素）
》》》》》》》》》》》》》》》》》》 部分习题笔记：
1.归并排序的算法复杂度证明：O(nlogn)
2.归并排序的优化：
对于两段已经排好顺序并且合起来也已经有序的情况，我们只需要增加一条语句： if (a[mi-1] <= a[mi]) merge(lo,mi,hi);
3.链表访问的优化：
由于对数据结构的操作往往都限定于一个较小的子集，所以可以将每次查找的链表元素移到首元素。在这种情况下，经常被访问的元素将集中在前端，大大提高访问效率。
第四章 树 1 树的表示方法：
可以将各个节点组成数组结构，包含孩子节点数据集与父节点的标号，如果有某个节点孩子节点，那么此节点里面的孩子节点数据集（可以为列表或者向量）就存储又大到小的孩子。再存储此节点的父亲节点。这时候向下查找与孩子的数目线性相关，向上查找与深度有关。
改进：每个节点主需要记录两个引用：纵向的firstchild以及横向的nextsibling（相邻兄弟），这时候储存结构的规整性大大增加。
2 二叉树：
真二叉树：每个节点都是2个度或者0个度（如果不够则在下面补满2个孩子）。更加规整（实际操作其实是假想的，并不存在）。