引论

递归简论

基本法则

基准情形 base case
- 必须总要有某些基准的情形，其不用递归就能求解。
不断推进 making progress
- 对于要递归求解的情形，递归调用必须总能朝着一个基准情形推进。
设计法则
- 假设所有递归调用都能运行。
合成效益法则 compound interest rule
- 在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作。

代码实现

// 利用递归打印整数
public class PrintOut {
	public static void main(String[] args) {
		int n = 7654;
		printOuter(n);
	}
	public static void printOuter(int n){
		if ( n >= 10 )
			printOuter(n/10);
		System.out.print(n%10);
	}
}

泛型构件 pre-Java 5

面向对象目标：对代码重用的支持。
支持机制：泛型机制 generic mechanism

泛型表示方案

使用超类 Object

问题：
1. 需要强制转型，丢失类型信息
2. 不可使用基本类型
  - 只有引用类型与 Object 相容
解决 2：对基本类型进行包装（e.g., int -> Integer）

适用场景：使用 Object 类中已有的方法能够表示所执行的操作。
使用接口类型
- 只有实现了某接口的对象才能够作为某接口数组的元素传递。e.g., Comparable
- 数组内两个对象不相容时抛出异常 ClassCastException
- 不可使用基本类型，同 1.2
- 数组类型的兼容性（协变数组类型，如果类 Base 是类 Sub 的基类，那么 Base[] 就是 Sub[] 的基类）

利用 Java 5 泛型特性实现泛型构件

简单泛型类与接口
- e.g., Comparable
自动装箱
- e.g., int值放到需要Integer类型的情况时，编译器自动调用对Integer的构造方法进行包装。
菱形运算符 <>
- 创建对象时使用，简化代码。
- e.g., A < Type > m = new A<>();【√】； A < Type > m = new A < Type >();【x】
通配符
- 用以解决泛型（及泛型集合）非协变问题
泛型 static 方法
- 在返回类型之前指定类型参数
- 适用场景：
  1. 特定类型用于返回类型
  2. 特定类型用于多于一个的参数列表中
  3. 特定类型用于声明一个局部变量
类型限界与擦除
- 限界指定参数类型必须具有的性质，示例：

    public static < AnyType extends Comparable < ? super AnyType >

擦除：泛型转换为非泛型时类型信息被编译器擦除，编译器生成同名原始类。

限制
1. 基本类型
  - 包装
2. static 语境
  - static 方法与 static 域均不可引用类的类型变量（擦除）
  - static 域在该类的诸泛型实例之间是共享的（仅存在一个原始类）
3. 泛型类型的实例化
  - 泛型类型不可实例化，需要用限界代替泛型类型
4. 泛型数组对象
  - 不可创建泛型数组，同 7.4

代码实现

// 利用 Comparable 接口实现泛型

public class FindMaxDemo {
	public static void main(String[] args) {
		String[] st1 = {"Joe","Bob"};
		Integer[] in1 = {1,2,34};
		System.out.println(findMax(st1));
		System.out.println(findMax(in1));
	   }
	public static Comparable findMax(Comparable[] arr){
		int maxIndex = 0;
		for ( int i = 1; i < arr.length; i++ ) {
			if (arr[i].compareTo(arr[maxIndex]) > 0) {
				maxIndex = i;
			}
		}
		return arr[maxIndex];
	}
}

函数对象

定义：一个函数通过将其放在一个对象内部而被传递。

代码实现

   // 结合函数对象利用 Comparable 接口实现泛型

   class CaseInsensitiveCompare implements Comparator< String > {
      public int compare(String lhs, String rhs) {
         return lhs.compareToIgnoreCase(rhs);
      }
   }

   public class FindMaxDemoWithFuncObj {
      public static void main(String[] args) {
         String[] arr = {"Joe","Bob", "zEEE", "bbo"};
         Integer[] in1 = {1,2,34};
         String a = "A";
         String b = "B";
         String tmp = new String();
         tmp = tmp.
         System.out.println(findMax(arr, new CaseInsensitiveCompare()));
         }
      public static < T > T findMax( T []arr, Comparator<? super T> cmp){
         int maxIndex = 0;
         for ( int i = 1; i < arr.length; i++ ) {
            if ((cmp.compare(arr[ i ], arr[ maxIndex ])) > 0) {
               maxIndex = i;
            }
         }
         return arr[ maxIndex ];
      }
   }

算法分析

概念：为求解一个问题需要遵循的、被清楚指定的简单指令的集合。

数学基础

当 $T (N) = O (f (N))$ 时，保证函数 $T (N)$ 是在以不快于 $f (N)$ 的速度增长，继而 $f (N)$ 是 $T (N)$ 的上界，即 $f (N) = Ω (T (N))$ ， $T (N)$ 是 $f (N)$ 的下界。

重要结论

如果 $T_{1} (N) = O (f (N))$ 且 $T_{2} (N) = O (g (N))$ ，那么
1. $T_{1} (N) + T_{2} (N) = O (f (N) + g (N)) = m a x (O (f (N), g (N)))$
2. $T_{1} (N) * T_{2} (N) = O (f (N) * g (N))$
如果 $T (N)$ 是一个 $k$ 次多项式，则 $T (N) = Θ (N^{k})$
对于任意常数 $k$ ， $l o g^{k} N = O (N)$

在对于任何需要 $O$ 表示的任何分析中，低阶项与常数一般被忽略。
两个函数的相对增长率可通过 $l i m_{N \to \infty} f (N) / g (N)$ 计算得到。

运行时间计算

一般法则

for 循环

一个 for 循环的运行时间至多是该 for 循环内部语句（包括测试）的运行时间乘以迭代的次数，一般为 $O (N)$ 。

嵌套的 for 循环

从内向外进行分析。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有 for 循环的大小的乘积。

一般而言，有 $k$ 个 for 循环则运行时间为 $O (N^{k})$ 。

顺序语句

按各语句的运行时间求和即可，其中的最大值即所得的运行时间。

if/else 语句

两种情况下的语句运行时间长者即为所求。

运行时间中的对数

对数时间规律法则

如果一个算法用常数时间（ $O (1)$ ）将问题的大小削减为其一部分（通常是 $1 / 2$ ），那么该算法的运行时间则为 $O (l o g N)$ 。另一方面，如果使用常数时间紧急时将问题减少一个常数的数量（如将问题减少 $1$ ），那么这种算法就是 $O (N)$ 的。

实例

折半查找

给定一个整数 $X$ 和整数序列 $A_{0}, A_{1}, . . . A_{N - 1}$ ，后者已预先排序并在内存中，求得下标 $i$ 使得 $A_{i} = X$ ，如果 $X$ 不在序列中，则返回 $i = - 1$ 。

非递归实现：

private static int binarySearch(int[] a, int x) {
    int low = 0, high = a.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (a[mid] < x)
            low = mid + 1;
        else if (a[mid] > x)
            high = mid - 1;
        else return mid;
    }
    return -1;
}

递归实现：

public static int binarySearch(int[] a, int x, int start, int end) {
    if (start == end)
        return -1;
    int center = (start + end)/2;
    if ( a[center] > x) {
        return binarySearch(a, x, start, center);
    } else if ( a[center] < x ) {
        return binarySearch(a, x, center + 1, end);
    } else if ( a[center] == x)
        return center;
    return -1;
}

欧几里得算法计算最大公因数

public static long gcd( long m, long n ) {
    while ( n != 0 ) {
        long rem = m % n;
        m = n;
        n = rem;
    }
    return m;
}

幂运算

递归实现：

若 $N$ 是偶数： $X^{N} = X^{N / 2} * X^{N / 2}$
若 $N$ 是奇数：$ X^N = X^{(N-1)/2} *X^{(N-1)/2} * X$

public static long pow( long x, int n ) {
    if ( n == 0 )
        return 1;
    if ( n % 2 == 0) {
        return pow( x * x , n / 2 );
    } else return pow( x * x, n / 2 ) * x;
}

表、栈和队列

抽象数据类型

概念

抽象数据类型（ Abstract Data Type，ADT）是带有一组操作的一些对象的集合，是数学的抽象。

实例

表、图、集合以及他们各自的操作（添加、删除等）一起形成的对象。

表 ADT

数组实现

连续存储、固定容量
线性时间操作
- 打印
- 插入与删除
常数时间操作
- 查找

链表实现

不连续存储
线性时间操作
- 查找
- 打印
常数时间操作
- 插入与删除

* 删除最后一项时：

找到指向最后节点的项并将其 next 链修改为 null
更新持有最后节点的链

Java Collections API 中的表

Collection 接口

public interface Collection<T> extends Iterable<T> {
    int size();
    boolean isEmpty();
    void clear();
    boolean contains(T x);
    boolean add(T x);
    boolean remove(T x);
    java.util.Iterator<T> iterator();    
}

接口并不规定集合如何决定某一元素是否属于集合，需要由实现该接口的具体类来确定

Collection 接口扩展了 Iterable 接口，实现了该接口的类可以拥有增强的 for 循环，该循环施加于这些类之上以观察它们所有的项。

public static <T> void print(Collection<T> coll) {
    for ( T item : coll ) {
        System.out.println(item);
    }
}

Iterator 接口

实现 Iterator 接口的集合需要提供 iterator 方法，通过该方法，每个集合均可创建并返回给用户一个实现了 Iterator 接口的对象并将当前位置的概念在对象内部存储下来。

public interface Iterator <T> {
    boolean hasNext();	// 判断下一项是否存在
	T next();			// 调用集合的下一项
    void remove();		// 删除由 next() 最新返回的项
}

remove() 在调用一次后不可再调用直至下一次调用 next() 完成。该方法与 Collection 接口的 remove() 方法相比，效率更高。
若不使用该接口的 remove() 方法而是自定义操作使得集合结构改变则会导致迭代器不再合法，若继续使用则会抛出并发修改异常。

public static <T> void print(Collection<T> coll) {
    Iterator<T> itr = coll.iterator();
    while ( itr.hasNext() ) {
        T item = itr.next();
        System.out.println(item);
    }
}

List 接口及其具体实现类

public interface List<T> extends Collection<T> {
    T get(int index);
    T set(int index, T newVal);
    void add(int index, T x);
    void remove(int index);
    ListIterator<T> listIterator(int pos);
}

ArrayList 类

提供了 List ADT 一种可增长数组的实现，可在需要时自动增加基础数组的容量。

优点：对 get 与 set 操作花费常数时间
缺点：新项的插入与现有项的删除代价昂贵

LinkedList 类

提供了 List ADT 的双链表实现

优点：假定变动项位置已知，新项的插入与现有项的删除均开销很小，常数时间
缺点：不易作索引，对 get 的调用代价昂贵

对于搜索而言，Collection 的 contains() 与 remove() 方法对于上述两种实现均花费线性时间，低效。

ListIterator 接口

public interface ListIterator<T> extends Iterator<T> {
	boolean hasPrevious();
    T previous();
    void add(T x);
    void set(T newVal);
}

栈 ADT

概念

栈（stack）是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，记作栈顶（top），又称作后进先出表（LIFO）。

栈顶元素是整个模型中唯一可见的元素。

基本操作：

进栈（push）：插入元素
出栈（pop）：删除并返回最后插入的元素

实现

任何实现表的方法都能实现栈，其中多用 ArrayList 与 LinkedList。

链表实现：利用单链表
数组实现：模仿 ArrayList 实现

基于上述实现的操作可以非常快的常数时间运行

应用

平衡符号（括号的开闭）、后缀表达式、中缀到后缀的转换、方法调用（方法调用与方法返回基本上类似于开括号和闭括号）

队列 ADT

概念

队列也是表，使用时插入在一端进行而删除则在另一端进行，先进先出（FIFO）。

基本操作：

入队（enqueue）：在表的末端（队尾 rear）插入元素
出队（dequeue）：删除并返回在表的开头（队头 front）的元素

实现

与栈的情形类似。

数组实现

潜在问题：数组前部可能已经有元素出列，数据并未满位，此时 back 标识可能移动到数组的最后一个下标位置，下一次入队的元素则会存放失败。

解决：循环数组实现，只要 front 或是 back 到达数组的尾端则又将其放回开头。

应用

文件服务器：使用其他计算机的用户是按照先到先得的原则访问文件，因此其数据结构是一个队列。
树

概念

构成

一棵树是一些节点的集合
- 可为空集
- 若非空，则树由称作根（root）的节点 r 以及 0 个或多个非空的（子）树 T 组成。这些子树中每一棵的根都被来自根 r 的一条有向边所连结。
没有儿子的节点称作树叶（leaf）

实现、遍历及应用

利用链表实现：将每个节点的所有儿子都放在树节点的链表中，声明如下：

class TreeNode {
	Object element;
	TreeNode right;
	TreeNode left;
	}

遍历顺序：
- 先序遍历：根、左、右
- 中序遍历：左、根、右
- 后序遍历：左、右、根
应用

常用操作系统目录结构等

二叉树

每个节点不可拥有多于两个的儿子
平均深度（ $O (\sqrt{N})$ ）比节点个数 $N$ 小得多

二叉查找树

概念

平均深度： $O (l o g N)$
对于树中的每个节点 X，其左子树中所有项的值均小于 X 中的项，而其右子树中的所有项的值均大于 X 中的项

排序实现

方法一：定义树的类实现 Comparable 接口

public class BinarySearchTree extends Comparable{
	...
	}

方法二：利用 Comparator 函数对象

public class BinarySearchTree {
	private BinaryNode root;
	private Comparator cmp;
	
	public BinarySearchTree() {
		this(null);
		}
	
	public BinarySearchTree(Comparator c) {
		cmp = c;
		root = null;
		}
	
    private int myCompare(T left, T right) {
        if (cmp != null)
            return cmp.compare(left, right);
        else
            return ((Comparable)left).cpmpareTo(right);
	    }
    ...
	}

contains()

private boolean contains(T x, BinaryNode t) {
    if (t == null) 
        return false;
    
    int compareResult = x.compareTo(t.element);  // 方法一
 // int compareResult = myCompare(x, t.element); // 方法二
 
    if (compareResult < 0)
        return contains(x, t.left);
    else if (compareResult > 0)
        return contains(x, t.right);
    else 
        return true;
}

remove()

一般删除策略
- 叶子节点：直接删除
- 拥有一个儿子的节点：该节点可在其父节点调整自己的链以绕过该节点（指向其子节点）后被删除
- 拥有两个儿子的节点：用其右子树的最小数据代替该节点数据并递归地删除那个节点（此时为空的原最小数据点，其无左儿子，删除较为容易）

private BinaryNode remove(T x, BinaryNode t) {
    if (t == null)
        return t;
    
     int compareResult = x.compareTo(t.element); 
 
    if (compareResult < 0)
        t.left = remove(x, t.left);
    else if (compareResult > 0)
        t.right = remove(x, t.right);
    else if (t.left != null && t.right != null) {
        t.element = findMin(t.right).element;
        t.right = remove(t.element, t.right);
    }
    else 
        t = (t.left != null) ? t.left : t.right;
    return t;
}

惰性删除：

当一个元素要被删除时，仍留在树中，仅被标记为删除

AVL 树

非 AVL 树：

平衡后的 AVL 树：

带有平衡条件的二叉查找树
其每个节点的左子树和右子树高度最多差 1
插入或删除操作导致树不满足平衡条件时通过旋转操作来修复（针对插入值所在的那条边（两个节点之间的值）进行）
- 单旋转：改变发生在外边时（即左 - 左、右 - 右）
- 双旋转：改变发生在内部时（即左 - 右、右 - 左）

伸展树

保证从空树开始连续 M 次对树的操作最多花费 $O (M l o g N)$ 次时间
基本思想：当一个节点被访问后，其需要经过一系列的 AVL 树旋转操作被推到根上

伸展

**zig：**当 p 为根节点时进行。Zig 通常只在伸展操作的最后一步进行。

zig-zig 与 zag-zag：当 p 不为根节点且 x 和 p 都为左儿子或都为右儿子时进行。下图为 x 和 p 都为左儿子时的情况（即 Zig-zig），需先将 p 右旋到 g 的位置，再将 x 右旋到 p 的位置。

zig-zag 与 zag-zig：当 p 不为根节点且 x 为左儿子而 p 为右儿子时进行，反之亦然。下图为前述情况（即 Zig-zag），需先将 x 左旋到 p 到的位置，再将 x 右旋到 g 的位置。

连接

给出两棵树 S 和 T，且 S 的所有元素都比 T 的元素要小。连接步骤：

伸展 S 中最大的节点。现在这个节点变为 S 的根节点，且没有右儿子
令 T 的根节点变为其右儿子

B 树

是一种自平衡的树，能够保持数据有序
适用于读写相对大的数据块的存储系统，例如磁盘
减少定位记录时所经历的中间过程，从而加快存取速度

在 B 树中，内部（非叶子）节点可以拥有可变数量的子节点（数量范围预先设定）。当数据被插入或从一个节点中移除，它的子节点数量发生变化。为了维持在预先设定的数量范围内，内部节点可能会被合并或者分离。因为子节点数量有一定的允许范围，所以 B 树不需要像其他自平衡查找树那样频繁地重新保持平衡，但是由于节点没有被完全填充，可能浪费了一些空间。子节点数量的上界和下界依特定的实现而设置。

参考：
《数据结构与算法分析 —— Java 语言描述》

数据结构学习笔记：基础知识梳理

引论

递归简论

基本法则

代码实现

泛型构件 pre-Java 5

泛型表示方案

利用 Java 5 泛型特性实现泛型构件

代码实现

函数对象

代码实现

算法分析

数学基础

重要结论

运行时间计算

一般法则

for 循环

嵌套的 for 循环

顺序语句

if/else 语句

运行时间中的对数

对数时间规律法则

实例

表、栈和队列

抽象数据类型

概念

实例

表 ADT

数组实现

链表实现

Java Collections API 中的表

Collection 接口

Iterator 接口

List 接口及其具体实现类

ArrayList 类

LinkedList 类

ListIterator 接口

栈 ADT

概念

实现

应用

队列 ADT

概念

实现

数组实现

应用

树

概念

构成

实现、遍历及应用

二叉树

二叉查找树

概念

排序实现

contains()

remove()

AVL 树

伸展树

伸展

连接

B 树