Steven Guan 讲的顺序真的迷 我还是老老实实按教材来吧
第一章略
第二章 算法分析
2.1 数学基础
定义2.1 如果存在正常数c和n0使得当N≥n0时T(N)≤cf(N),则记为TN=O(fN).
定义2.2 如果存在正常数c和n0是使得当N≥n0时T(N)≥cg(N),则记为TN=Ω(gN).
定义3.3
定义3.4
最大子序列和 欧几里得算法
第三章 表，栈和队列
3.1 抽象数据类型
抽象数据类型（abstract data type, ADT）是带有一组操作的一些对象的集合。对于集合ADT，可以有像添加（add），删除（remove）以及包含（contain）这样一些操作，
3.2 表ADT
我们将处理形如A0,A1,A2,….,An-1 的一般的表。我们说这个表的大小是N。将大小为0的特殊表称为空表。
表的数组的简单实现：
- int [] arr = new int [ 10 ];
- //下面我们决定扩大arr
- int [] newArr = new int[ arr.length * 2 ];
- for ( int i = 0; i < arr.length; i++ )
- newArr[ i ] = arr[ i ];
- arr = newArr;
3.3 简单链表
为了避免插入和删除的线性开销，我们需要保证表可以不连续储存，否则表的每个部分都可能需要整体移动。
链表由一系列节点组成，这些节点不必在内存中相连。每个节点均含有表元素和到包含该元素后继元的节点的链（link）。我们称之为next链。最后一个单元的next链引用null。
双链表
3.4 Java Collections API 中的表
在类库中，Java语言包中有一些普通数据结构的实现。该语言的这一部分通常叫做Collections API。表ADT是在Collection API中实现的数据结构之一。
Collection接口
Collection API 位于 java.util 包中。集合collection的概念在collection接口中得到抽象，它储存一组类型相同的对象。
该接口的一些最重要的部分（一些方法未被显示）
- public interface Collection extends Iterable
- {
- int size();
- boolean isEmpty();
- void clear();
- boolean contains( AnyType x);
- boolean add(AnyType x);
- java.util.Iterator iterator();
- }
在Iterable类型上使用增强的for循环
- public static void print(Collection col1){
- for(AnyType item: col1)
- System.out.println(item);
- }
- }
Iterator接口
实现Iterator接口的集合必须提供一个称为iterator的方法，该方法返回一个Iterator类型的对象。该Iterator是一个在java.util包中定义的接口。
- public interface Iterator{
- boolean hasNext();
- AnyType next();
- void remove();
- }
Iterator接口的思路是通过iterator方法，每个集合均可创建并返回给客户一个实现Iterator接口的对象，并将当前位置的概念在对象内部储存下来。每次对next的调用都给出集合的（尚未见到的）下一项，因此第一次调用next给出第一项，第二次调用给出第二项，…。hasNext用来告诉是否存在下一项。Iterator接口还包含一个方法remove，该方法可以删除由next最新返回的项（此后，我们不能再调用remove，直到对next再一次调用后）。虽然Collection接口也包含一个remove方法，但是使用Iterator的remove方法可能更有优点。
Iterator的remove方法优点在于，Collection的remove方法必须首先找出要被删除的项。P43
List接口，ArrayList类和linkedList类
List由java.util包中的List接口指定。List接口继承了Collection接口，因此它包含Collection接口中的所有方法，外加一些其他方法。
- public interface List extends Collection{
- Anytype get( int idx );
- Anytype set( int idx, Anytype newVal );
- void add( int idx, Anytype x );
- void remove( int idx );
- ListIterator listIterator( int pos );
- }
get和set使得用户可以访问或改变通过由位置索引idx给定的表中指定位置上的项。索引0位于表的前端，索引size() – 1代表表中的最后一项，而索引size() 则表示新添加的项可以是被放置的位置。add使得在位置idx处置入一个新的项（并把其后的项向后推移一个位置）
