笔记 - 数据结构与算法分析

Data Structure and Algorithm Analysis in Java 3rd Edition

数据结构与算法分析，Java语言描述。

中文版译名为数据结构与算法分析，Java语言描述。本文对书中的核心内容进行记录和解析，并给出部分更通俗的补充资料，喜欢请点赞，(:з」∠)。

本书可能用到的在线资源

Pearson出版社提供的在线资源 https://www.pearson.com/us/higher-education/program/Weiss-Data-Structures-and-Algorithm-Analysis-in-Java-3rd-Edition/PGM324443.html?tab=resources
作者提供的参考代码电子版 http://users.cis.fiu.edu/~weiss/dsaajava3/code/
算法练习网站 LintCode 领扣
可视化数据结构网站，偏向于动画效果 https://visualgo.net
可视化数据结构网站偏向于自定义可视化代码 https://algorithm-visualizer.org/brute-force/insertion-sort

第一章引论

1.1 本书讨论的内容

在许多问题当中，我们要持有这样一个重要的观念：写出一个程序并不够。我们还要考虑，如果这个程序在巨大的数据集上运行，由运行时间造成的许多问题。

1.2 数学知识复习

1.2.1 指数

1.2.2 对数

除非特别规定，计算机科学中的对数都以2为底。

1.2.3 级数

这个公式在计算机科学中的使用非常频繁。其中，数 $H_n$ 称为调和数，其和称为调和和。这一近似式的误差趋向于 $\gamma \approx 0.57721566$

H_n=\sum_{i=1}^N{\frac{1}{i}}\approx \log _eN

1.2.4 模运算

1.2.5 证明的方法

数据结构中最常用的是归纳法和反证法。

1.3 递归简论

编写递归程序时，应牢记的四条规则：

基准情形
不断推进
设计法则
合成效益法则切忌在不同的递归调用中做重复性的工作。

1.4 泛型 Generic

如果不考虑对象的类型，而对象的实现方法是相同的，那么可以用泛型实现(Generic Implementation)来描述这种基本的方法。

要深入的理解泛型，参阅Java编程思想-第十五章。

1.4.1 使用Object类表示泛型

这种方法有两点要注意：

要使用超类对象的子类方法，需要将对象强制转换成子类。
不能使用基本类型，只有引用类型与Object相容。

1.4.2 基本类型的包装

8种基本类型与Object不相容，因此Java提供了基本类型的包装类。这些包装类的父类均为java.lang.Number。所有的Number类都存在缓存机制，只要是-128至127之间的数字都会被缓存，在这个范围之外的数据，则会生成新的对象。

包装类	包装类转基本类型	基本类型转包装类
Byte	Byte.valueOf(byte)	byteInstance.byteValue()
Short	Short.valueOf(short)	shortInstance.shortValue()
Integer	Integer.valueOf(int)	integerInstance.intValue()
Long	Long.valueOf(long)	longInstance.longValue()
Float	Float.valueOf(float)	floatInstance.floatValue()
Double	Double.valueOf(double)	doubleInstance.doubleValue()
Character	Character.valueOf(char)	charInstance.charValue()
Boolean	Boolean.valueOf(boolean)	booleanInstance.booleanValue()

1.4.3 使用接口类型表示泛型

考虑在由一些项组成的数组中找出最大项的问题。最简单的情况，数组的元素的类均相同，且实现了Comparable接口，使用compareTo方法即可。举一些特殊的例子来说，用compareTo比较String和Shape，这两个类都实现了Compareable接口

对于String来说返回值类型是int，分别有三种，小于0，等于0，大于0

如果字符串相等返回值0；
如果第一个字符和参数的第一个字符不等,结束比较,返回他们之间的差值（ascii码值）（负值前字符串的值小于后字符串，正值前字符串大于后字符串）；
如果第一个字符和参数的第一个字符相等，则以第二个字符和参数的第二个字符做比较，以此类推，直至比较的字符或被比较的字符有一方全比较完，这时就比较字符的长度。

对于Shape来说返回的是面积的差值。

注意，1.基本类型不能作为Comparable传递，但包装类可以，因为它实现了Comparable接口。2.如果Comparable数组有两个不相容的对象，那么compareTo方法会抛出异常ClassCastException,这是相当有用的性质。3.接口是不是标准的库接口倒不是必须的。4.这个方法并不总是可行的，比如一个类是Final类，或者这个类是库中的类，但接口是用户定义的接口。function object可用于处理这种情况。

1.4.4 数组类型的兼容性

语言设计中的困难之一是如何处理集合类型的继承问题。最容易的解决方法是指定这些数组不是类型兼容的。在Java中，数组是类型兼容的，这叫做协变数组类型(covariant array type)，每个数组都明了它所允许储存的对象类型。

如果类Base是类Sub的基类，那么Base[]就是Sub[]的基类。而泛型是不可变的(invariant)，List<Base>不会是List<Sub>的基类，更不会是他的子类。

数组支持协变，是因为Java 5 之前没有泛型，而又迫切需要泛型。但为什么数组设计成”协变“不会有大问题呢？这是基于数组的一个独有特性：

数组记得它内部元素的具体类型，并且会在运行时做类型检查。

Joshua J. Bloch在《Effective Java》中明确地指出过，Java 允许数组协变是 Java 的缺陷，他也没搞明白为什么要这样设计。

1.5 实现泛型构件

java 5 支持泛型类。本节将叙述编写泛型类和泛型方法的基础。

1.5.1 简单的泛型类和接口

在下面这个例子当中，AnyType可以改成任何一种具体的类名，我们可以使用泛型作为参数和返回值。

//这是一个泛型类的例子
public class GenericMemoryCell<AnyType> {
    public AnyType read() {
        return storedValue;
    }
    public void write(AnyType x) {
        storedValue = x;
    }
    private AnyType storedValue;
}

1.5.1-a

//这是一个泛型接口的例子
package java.lang
public interface Comparable<AnyType> {
    public int compareTo(AnyType other);
}

1.5.1-b

1.5.2 自动装箱/拆箱

在Java5以后，如果一个int被传递到了一个需要Integer的地方，那么编译器会在幕后插入一个对Integer构造方法的引用。如果一个Integer对象被放到需要int类型的地方，编译器会在幕后插入一个对intValue方法的调用。对于剩余七对基本对象，这同样会发生。装箱和拆箱指的就是包装类这个箱子。

class BoxingDemo {
    public static void main(String[] args) {
        GenericMemoryCell<Integer> m = new GenericMemoryCell<Integer>();
        m.write(37);
        int val = m.read();
        System.out.println("Contents are: " + val);
    }
}

1.5.2-a

1.5.3 菱形操作符

在1.5.2的例子中，第5行有些啰嗦，Java7增加了一种新的语法糖，菱形运算符。上述例子可以改写为

GenericMemoryCell<Integer> m = new GenericMemoryCell<>();

1.5.3-a

1.5.4 带限制的通配符

public static double totalArea(Shape [] arr) {
    double total = 0;

    for(Shape s : arr)
        if (s != null)
            total += s.area();
    return total;
}

1.5.4-a

代码1.5.4-a展示的是一个static方法，用于计算Shape数组的总面积。假设要重写成能支持Collection<Shape>的方法，这样就能使用For-in循环。

public static double totalArea(Collection<Shape> arr) {
    double total = 0;

    for(Shape s : arr)
        if (s != null)
            total += s.area();
    return total;
}

1.5.4-b

给1.5.4-b传参Collection<Shape>能正常运行，但是传Collection<Square>呢？(我们已经假设Circle和Square是继承Shape的类。) 答案取决于是否Collection<Square> IS-A Collection<Shape>，用技术术语来说就是是否有协变性。泛型集合(Collection<Type>)不是协变的。因此，我们不能把Collection<Square>作为1.5.4-b的参数。

协变性在带来潜在的问题的同时，也带来了灵活性。Java5使用通配符(wildcard)来弥补这个不足。通配符表示参数类型的子类或超类。

public static double totalArea(Collection<? extends Shape> arr) {
    double total = 0;

    for (shape s: arr)
        if (s != null)
            total += s.area();

    return total;
}

1.5.4.c

1.5.4.c将Collection<T>作为参数，其中T IS-A Shape，语法上写作Collection<? extends Shape>，?作为通配符

通配符的使用可以对泛型参数做出某些限制，使代码更安全，对于上边界和下边界限定的通配符总结如下：

使用 List<? extends C> list 这种形式，表示 list 可以引用一个 ArrayList ( 或者其它 List 的子类 ) 的对象，这个对象包含的元素类型是 C 的子类型 ( 包含 C 本身）的一种。使用 List<? super C> list 这种形式，表示 list 可以引用一个 ArrayList ( 或者其它 List 的子类 ) 的对象，这个对象包含的元素就类型是 C 的超类型 ( 包含 C 本身 ) 的一种。

1.5.5 泛型 static 方法

我们先前讨论的都是泛型类，这里讨论泛型方法。与1.5.4.c中的totalArea不太一样的是，下面这个例子可以用AnyType指代输入参数的类型。

public static <AnyType> boolean contains(AnyType [] arr, AnyType x) {

    for(AnyType val : arr)
        if(x.equals(val))
            return true;

    return false;

}

1.5.5

泛型方法特别像是泛型类，泛型方法中的类型参数位于返回类型前。什么情况下要用到这个显式的AnyType呢?

这个输入类型用于声明局部变量AnyType a = new AnyType();
这个输入类型用作返回类型return new AnyType();
该类型用在多于一个的参数类型中(?没看懂)

1.5.6 类型限界

由于对AnyType对象调用了compareTo方法，编译器不会通过。因为不能确定AnyType IS-A Comparable。

public static <AnyType> AnyType findMax(AnyType[] arr) {
    int maxIndex = 0;

    for(int i = 1; i < arr.length; i++)
        if(arr[i].compareTo(arr[maxIndex]) > 0)
        # 编译器无法确定AnyType是不是Comparable对象
            maxIndex = 0;

    return arr[maxIndex];
}

1.5.6-a

自然，我们会想到用下面这种形式

public static <AnyType extends Comparable> ...

1.5.6-b

AnyType 是 Comparable 的一个子类/本身。

因为Comparable接口是支持泛型的，有更好的写法。

public static <AnyType extends Comparable<AnyType>> ...

1.5.6-c

补充: <T extends Comparable> This means that the type parameter must support comparison with other instances of its own type, via the Comparable interface. 这个类型必须支持和自己同类的对象进行比较，这个比较过程通过Comparable接口进行。或者说，类型 T 必须实现 Comparable 接口，并且这个接口的类型是 T。只有这样，T 的实例之间才能相互比较大小。例如，在实际调用时若使用的具体类是 Square，那么 Square 必须 implements Comparable

这种写法仍然不能令人满意，我们来进一步分析：假设Shape实现Comparable<Shape>接口，Square继承Shape。则Square实现Comparable<Square>，因此，Square IS-A Comparable<Shape>，但它IS-NOT-A Comparable<Square>。或者说，Square实现Comparable时，是在Shape，即它的父类实现的。Square本身并不能使用compareTo方法。

应该说，AnyType IS-A Comparable，其中，T是AnyType的父类。因为我们明确知道类型T，因此可以使用通配符最终结果为

public static <AnyType extends Comparable<? super AnyType>>

1.5.6-d

类型 AnyType 必须实现 Comparable 接口，并且这个接口的类型是 AnyType 或 AnyType 的任一父类。这样声明后，AnyType 的实例之间，AnyType 的实例和它的父类的实例之间，可以相互比较大小。例如，在实际调用时若使用的具体类是 Square (假设 Square 有一个父类 Shape），Shape 可以从 Square 那里继承 Comparable<Square> ，或者自己 implements Comparable<Shape> 。

1.5.7 类型擦除

泛型很大程度上是Java语言的成分，而不是JVM中的结构。

编译器使用类型擦除将泛型类转变成原始类（raw class）在泛型类被类型擦除的时候，之前泛型类中的类型参数部分如果没有指定上限，如 <T>则会被转译成普通的 Object 类型，如果指定了上限如 <T extends String>则类型参数就被替换成类型上限。

1.5.8 对泛型的限制

由于类型擦除的存在，以下的限制都是必须遵守的

基本类型

基本类型不能用作类型参数。

instanceof

不能对泛型使用instanceof。T是一个参数化类型和存在的编译目的。由于类型擦除，它在运行时不存在。因此，obj instanceof T是不合法的。

static的语境

static域和方法不可引用类的类型变量，因为擦除后就不存在了。

实例化

下面这个程序是非法的，擦除后T由它的限界代替，这可能是Object，甚至抽象类。

T obj = new T();

1.5.8-a

泛型数组 以下语句是非法的

T[] arr = new t[10];

1.5.8-b

T将由它的限界代替，这很可能是Object T，这会导致Ojecet[] IS-NOT-A T[]

参数化类型的数组

参数化类型的数组的实例化是非法的

GenericMemoryCell<String>[] arr1 = new GenericMemoryCell<>[10];

1.5.8-c

你可以向这个arr存放任何GenericMemoryCell<>而不会报错，但在取出的时候，如果指定取出对象为String格式，而又存放了其他格式，会产生ClassCaseException异常。

1.6 函数对象 Funtion Object

一个函数将自己放在一个对象内部而被传递，这样的对象叫做函数对象。

下面的例子示意了函数对象的用法。

package com.masoniclab;

import java.util.Comparator;

public class generic {
    public static void main(String[] args) {
        String[] arr = {"ZEBRA", "alligator", "crocodile"};
        System.out.println(findMax(arr, new CaseInsensitiveCompare()));
    }

    private static <AnyType> AnyType findMax(AnyType[] arr, Comparator<? super AnyType> 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];
    }
}

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

1.6-a

以下是Comparator的源代码，任何实现这个接口的类必须有compare这个方法。

public interface Comparator<T> {
    int compare(T var1, T var2);

1.6-b

第二章算法分析

2.1 数学基础

大 $O$ 标记法(Big O Notation)

给定两个函数， $f(x)$ 和 $g(x)$ 。当 $x$ 趋近于无穷大时，当且仅当存在正常量 $M$ ，使得对于所有足够大的 $x$ ，都有 $f(x)\leq M\cdot g(x)$ ，那么我们可以说，对于 $x\rightarrow \infty$ 时，

f(x)=O(g(x))

这样一个公式指的是，我们保证 $f(x)$ 是以不快于 $g(x)$ 的速度增长。因此， $g(x)$ 是 $f(x)$ 的一个上界(Upper Bound)。

这是一些常用的函数阶

符号	名称
$O(1)$	常数
$O(log n)$	对数
$O[(log n)^c]$	多对数
$O(n)$	线性
$O(\log _{n})$	线性对数
$O(c^n)$	指数

2.2 模型

我们假设有一台无限内存，所有计算操作耗时都是一个单位的计算模型。

2.3 要分析的问题

要考虑的模型参数主要是 $T_{avg}(N)$ 和 $T_{worst}(N)$ 。

2.4 运行时间计算

2.4.1 一个简单的例子

2.4.2 一般法则

使用大O标记法估计算法的运行时间，是非常符合直觉的，有这样几个计算法则:

for 循环 循环内部语句用时*迭代次数

嵌套的 for 循环 循环内部语句用时*迭代次数*迭代次数

顺序语句 将各个语句的运行时间简单相加即可

if/else 语句

对于一般的程序语句

if (condition) {
    s1.run();
} else {
    s2.run();
}

2.4.2-a

这个语句的运行时间大致是判断的运行时间+s1/s2中较长的运行时间。

但是如果if/else内含递归，计算时间就不太一样了。

public static long factorial(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return n*factorial(n - 1)
    }
}

2.4.2-b

这是一段用if/else实现阶乘的代码，这个递归用的并不好，因为可以轻松地用for循环代替它。时间复杂度为 $O(N)$ 。

这是一段正规的递归语句

public static long fib(int n) {
    if (n <= 1) { // A
        return 1;
    else {
        return fib(n - 1) + fib(n - 2) // B
    }
}

2.4.2-c

初看好像写的很聪明，N=0或N=1时，运行时间T(N)是常数值k。

N>1的情形，以k为基准计算。

N=2时，T(N)=T(N-1) + T(N-2) + 2 = k+2，其中的2是A处if和B处调用方法的开销。

利用数学归纳法可以证明，对于N>4， $fib(N) \leq (\frac{2}{3})^N$ ，近似于指数级增长，这种算法效率极差。因为它违反了(合成效益法则)。

如果要改进，通过用一个数组来保存T(N)使用for循环，可以节省大量的时间。

2.4.3 解决最大子序列和问题

对于这个问题，有一个相对复杂的 $O(N logN)$ 解法。这个方法采用"分治"策略(divide-and-conquer)。

package com.masoniclab.lecture.two;

public class MaxSum {
    /**
     * Recursive maximum contiguous subsequence sum algorithm.
     * Finds maximum sum in subarray spanning a[left..right].
     * Does not attempt to maintain actual best sequence.
     */
    private static int maxSumRec( int [ ] a, int left, int right )
    {
        // base case
        if( left == right )
            return Math.max(a[left], 0);

        int center = ( left + right ) / 2;

        // recursion
        int maxLeftSum  = maxSumRec( a, left, center );
        int maxRightSum = maxSumRec( a, center + 1, right );

        int maxLeftBorderSum = 0, maxRightBorderSum = 0;
        int leftBorderSum = 0, rightBorderSum = 0;

        // for loop
        for( int i = center; i >= left; i-- )
        {
            leftBorderSum += a[ i ];
            if( leftBorderSum > maxLeftBorderSum )
                maxLeftBorderSum = leftBorderSum;
        }

        for( int i = center + 1; i <= right; i++ )
        {
            rightBorderSum += a[ i ];
            if( rightBorderSum > maxRightBorderSum )
                maxRightBorderSum = rightBorderSum;
        }

        return max3( maxLeftSum, maxRightSum,
                maxLeftBorderSum + maxRightBorderSum );
    }

    /**
     * Return maximum of three integers.
     */
    private static int max3( int a, int b, int c )
    {
        return a > b ? Math.max(a, c) : Math.max(b, c);
    }

}

2.4.3-a

对这个程序分析运行时间令T(N)是处理长度为N的序列的耗时。如果N=1，设算法处理 base case 处用时为一个时间单位，因此，T(1)=1。其他情况下，要处理两个 for loop ，用时计为 $\mathrm {O} (N)!$ ， recursion 处要处理两个大小为N/2的子序列，时间计为2T(N/2)，我们得到方程组:

T(1)=1

T(N)=2T(N/2)+O(N)

代入2的幂可以发现，设 $N=2^k$ ， $T(N)=N\*(k+1)=N logN + N$

这是另一个非递归的实现版本:

/**
 * Quadratic maximum contiguous subsequence sum algorithm.
 * seqStart and seqEnd represent the actual best sequence.
 */
public static int maxSubSum2( int [ ] a )
{
    int maxSum = 0;

    for( int i = 0; i < a.length; i++ )
    {
        int thisSum = 0;
        for( int j = i; j < a.length; j++ )
        {
            thisSum += a[ j ];

            if( thisSum > maxSum )
            {
                maxSum = thisSum;
                seqStart = i;
                seqEnd   = j;
            }
        }
    }

    return maxSum;
}

2.4.3-b 原始的递归实现

/**
 * Linear-time maximum contiguous subsequence sum algorithm.
 * seqStart and seqEnd represent the actual best sequence.
 */
public static int maxSubSum4( int [ ] a )
{
    int maxSum = 0;
    int thisSum = 0;

    for( int i = 0, j = 0; j < a.length; j++ )
    {
        thisSum += a[ j ];

        if( thisSum > maxSum )
        {
            maxSum = thisSum;
        }
        else if( thisSum < 0 )
        {
            i = j + 1;
            thisSum = 0;
        }
    }

    return maxSum;
}

2.4.3-c 改进的递归实现

其中，i代表当前序列的起点，q代表当前序列的终点。i在改进版的代码中不是必须的。

这是因为:

如果a[i]是负的，那它不可能是最优序列的起点，可以用a[i+1]作为新的起点
任何负的子序列不可能是最优序列的起点，如果a[i]到a[j]的子序列是负的，那可以推进a[i]到a[j]
结论: 我们可以把i推进到j+1

这个算法的附带优点:

只对数据进行一次扫描，如果数组在硬盘或互联网上，那么它可以被按顺序读入，内存中不需要储存数组的任何元素。具有这种特性的算法称为"联机算法"(on-line algorithm)。仅需要常量空间，并以线性时间运行的联机算法几乎是完美的。

2.4.4 运行时间中的对数

对数运行时间出现的规律可以概括为

如果算法用常数时间将问题的大小削减为其一部分(通常是1/2)，那么算法就是 $\mathrm {O} (\log N)\!$ 的。
如果算法用常数时间将问题的大小削减一个常数(通常是1)，那么算法就是 $\mathrm {O} (N)\!$ 的。

折半查找(binary search)

Given an array $A$ of $n$ elements with values or records $A_{0},A_{1},A_{2},\ldots ,A_{n-1}$ sorted such that $A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}$ , and target value $T$ , the following subroutine uses binary search to find the index of $T$ in $A$ .

核心思路是比对 $A$ 和数列居中的元素，以此将数列一分为二。

它提供了在 $\mathrm {O} (\log n)\!$ 时间内的contains操作。

欧几里得算法

又叫辗转相除法，迭代次数是 $\mathrm {O} (\log n)\!$

package com.masoniclab.lecture.two;

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

    // Test program
    public static void main( String [ ] args )
    {
        System.out.println( "gcd( 45, 35 ) = " + gcd( 45, 35 ) );
        System.out.println( "gcd( 1989, 1590 ) = " + gcd( 1989, 1590 ) );
    }
}

2.5 幂运算

即计算 $x^N$ ，最明显的想法是进行N-1次连乘。

有种递归算法更好，以1为基准情况，将数字分为奇数和偶数情况，分别折半计算。

最终的用时是 $\mathrm {O} (\log n)\!$

第三章表、栈和队列

3.1 抽象数据类型

抽象数据类型(Abstract Data Type ADT)是数学上的抽象，带有一组操作(add/remove/contain/[union/find])的一些对象的集合。

3.2 表 ADT

3.2.1 简单数组

对表的这些操作都可用数组来实现。使用数组可以使得printList以线性时间被执行。而findKth操作则花费常数时间。但是插入和删除操作的耗时取决于操作的位置。如果所有操作发生在数组前端，则耗时为 $\mathrm {O} (N)$ 。如果发生在后端，耗时为 $\mathrm {O} (1)$ 。如果要对表的前端进行，链表会是更好的选择。

3.2.2 简单链表

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

来自维基百科 https://zh.wikipedia.org/wiki/链表

3.2.2E 单链表

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记，另外在一个固定的位置保存指向第一个节点的指针，有的时候也会同时储存指向最后一个节点的指针。

一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接

从链表中删除元素 $A_n$ 只需要将 $A_{n-1}$ 的指针改到 $A_{n+1}$ 。插入元素同理。在单链表中，删除最后一项 $A_n$ 比较麻烦，要先找到第 $A_{n-1}$ 项，把它的next链改为Null。然后修改持有最后节点的链。在经典的链表中，每个节点均存储着到它下一节点的链，而拥有指向最后节点的链并不提供最后节点的前驱节点的任何信息，这时就要用到双向列表。 PS: 上面这句话请结合图片理解。

3.2.2E 双向链表

一种更复杂的链表是“双向链表”。每个节点有两个连接：一个指向前一个节点，（当此“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当此“连接”为最后一个“连接”时，指向空值或者空列表）。 双向链表也叫双链表。双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。由于另外储存了指向链表内容的指针，并且可能会修改相邻的节点，有的时候第一个节点可能会被删除或者在之前添加一个新的节点。这时候就要修改指向首个节点的指针。有一种方便的可以消除这种特殊情况的方法是在最后一个节点之后、第一个节点之前储存一个永远不会被删除或者移动的虚拟节点，形成一个循环链表。这个虚拟节点之后的节点就是真正的第一个节点。这种情况通常可以用这个虚拟节点直接表示这个链表，对于把链表单独的存在数组里的情况，也可以直接用这个数组表示链表并用第0个或者第-1个（如果编译器支持）节点固定的表示这个虚拟节点。

来自维基百科 https://zh.wikipedia.org/wiki/链表

一个双向链表有三个整数值: 数值, 向后的节点链接, 向前的节点链接

3.3 Java Collections API 中的表

3.3.1 Collection 接口

ADT是 Collections API 中实现的数据结构之一。这是 Collection 接口源码的一部分。

package java.util;

public interface Collection<E> extends Iterable<E> {
    int size();

    boolean isEmpty();

    boolean contains(Object var1);

    Iterator<E> iterator();

    boolean add(E var1);

    boolean remove(Object var1);

    void clear();
}

Collection 接口扩展了 Iterable 接口。实现了 Iterable 接口的类可以使用增强的 for 循环。

3.3.2 Iterator 接口

对于每个实现Iterator接口的集合，通过iterator方法，可以返回一个对象，并将当前位置的概念在对象内部储存下来。

public interface Iterator<E> {
    boolean hasNext();

    E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);

        while(this.hasNext()) {
            action.accept(this.next());
        }

    }
}

Iterator接口的方法很少，除了简单遍历以外几乎不能做什么。但是，它的remove方法有着更高的效率，因为next()已经定位了要删除的对象的位置。

3.3.3 List接口、ArrayList类和LinkedList类

List接口继承了Collection接口，而且增加了一些方法，比如listIterator。 List ADT有两种实现方式，ArrayList和LinkedList。前者的get和set方法耗时短，insert和delete耗时长后者的insert和delete耗时短，还提供了addFirst,removeFirst,addLast,removeLast等操作首尾元素的方法，但是get的耗时长。 末端添加 对于ArrayList, LinkedList来说，在末端添加N个元素耗时都是O(N) 前端添加 对于LinkedList, 耗时是O(N)，对于ArrayList，耗时是 $O(n^2)$ 求和对于ArrayList,耗时是O(N)，对于ArrayList，耗时是 $O(n^2)$ ，因为对get的调用耗时为O(N) 使用增强的for循环求和 对于ArrayList, LinkedList来说，耗时都是O(N)

总结来说，ArrayList索引容易，末尾增删容易。LinkedList索引困难，增删容易。

public static void makeList1(List<Integer> lst, int N) {
    lst.clear();
    for (int i = 0; i < N; i++) {
        lst.add(i);
    }
}

对于ArrayList和LinkedList，上面这个在末端增加元素的程序耗时都是O(N) 如果这个程序改为在头部增加元素，ArrayList耗时 $O(N^2)$ ，LinkedList耗时O(N)。

如果用fori循环求和，ArrayList耗时O(N)，LinkedList耗时 $O(N^2)$ ，因为get操作耗时O(N)。但是如果用增强的for循环求和，耗时都是O(N)，数字指针只是简单的向后推进，切换到下一元素的耗时可看做O(1)。

3.3.4 remove方法对LinkedList类的使用

问题: 将一个数组中的偶数删除，只对这个数组进行操作，避免新建数组。使用ArrayList: 不可行，删除操作过于耗时。使用LinkedList: 以下是最优解，任何涉及get和remove的操作都会极大地影响耗时。

public static void removeEvensVer1(List<Integer> lst) {
    Iterator<Integer> itr = lst.iterator();
    while (itr.hasNext()) {
        if(itr.next() % 2 == 0) {
            itr.remove();
        }
    }
}

使用Lambda表达式的版本:

public static void removeEvensVer1(List<Integer> lst) {
    lst.removeIf(i -> i % 2 == 0);
}

3.3.5 关于ListIterator接口

ListIterator扩展了List的Iterator功能，增加了previous和hasPreviours方法，使得可以从后向前遍历。 Iterator对于LinkedList的重要意义是，他可以在遍历途中改变当前迭代器指向的元素，这代替了set操作，大大减少了操作时间。

3.4 ArrayList类的实现

概述: 自己写一个ArrayList泛型类，实现基本功能和方法。

3.4.1 基本类

public class MyArrayList<T> implements Iterable<T> {
    private static final int DEFAULT_CAPACITY = 10;

    private T[] theItems;
    private int theSize;

    private void doClear() {
        theSize = 0;
        ensureCapacity(DEFAULT_CAPACITY);
    }

    public MyArrayList() {
        doClear();
    }

    public int size() {
        return theSize;
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public T get(int idx) {
        if (idx < 0 || idx >= size())
            throw new ArrayIndexOutOfBoundsException("Index " + idx + "; size " + size());
        return theItems[idx];
    }

    public T set(int idx, T newVal) {
        if (idx < 0 || idx >= size())
            throw new ArrayIndexOutOfBoundsException("Index " + idx + "; size " + size());
        T old = theItems[idx];
        theItems[idx] = newVal;
        return old;
    }

    // 扩充容量
    public void ensureCapacity(int newCapacity) {
        if (newCapacity < theSize)
            return;

        T[] old = theItems;
        // java没有泛型数组，这个强制转换会造成编译器警告，但这不可避免。
        theItems = (T[]) new Object[newCapacity];
        for (int i = 0; i < size(); i++)
            theItems[i] = old[i];
    }

    // 在指定位置加入元素
    public void add(int idx, T x) {
        if (theItems.length == size())
            ensureCapacity(size() * 2 + 1);

        for (int i = theSize; i > idx; i--)
            theItems[i] = theItems[i - 1];

        theItems[idx] = x;
        theSize++;
    }

    public T remove(int idx) {
        T removedItem = theItems[idx];

        for (int i = idx; i < size() - 1; i++)
            theItems[i] = theItems[i + 1];
        theSize--;

        return removedItem;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder("[ ");

        for (T x : this)
            sb.append(x + " ");
        sb.append("]");

        return new String(sb);
    }
}

3.4.2 迭代器、Java嵌套类和内部类

ArrayListIterator使用了一个Java特性，叫内部类(inner class)，这个类在MyArrayList类内部声明。书中列举了三个版本的Iterator，他们都过于冗长，有的甚至不能使用，以下是最终版本的Iterator，使用内部类，它免去了传参，访问权限等方面可能造成的困扰。

内部类有static关键词就是嵌套类，无static关键词就是简单的内部类。

public java.util.Iterator<T> iterator() {
    return new ArrayListIterator();
}

private class ArrayListIterator implements java.util.Iterator<T> {
    private int current = 0;
    private boolean okToRemove = false;

    public boolean hasNext() {
        return current < size();
    }

    public T next() {
        if (!hasNext())
            throw new java.util.NoSuchElementException();

        okToRemove = true;
        return theItems[current++];
    }

    public void remove() {
        if (!okToRemove)
            throw new IllegalStateException();

        MyArrayList.this.remove(--current);
        okToRemove = false;
    }
}

总结来说，ArrayListIterator是隐式的泛型类，它依赖于MyArrayList，而后者是泛型的。

3.5 LinkedList类的实现

我们将LinkedList作为双链表实现，设计这个类要考虑的事情:

MyLinkedLisy类本身，它包含到两端的链，表的大小和一些方法。
Node类，他可能是一个私有的嵌套类。一个节点包含数据和到前后节点的链。
LinkedListIterator类，提供next, hasNext, remove方法的实现。

代码过长，在此只列出关键部分

Node嵌套类的实现代码

private static class Node<AnyType>
{
    public Node( AnyType d, Node<AnyType> p, Node<AnyType> n )
    {
        data = d; prev = p; next = n;
    }

    public AnyType data;
    public Node<AnyType>   prev;
    public Node<AnyType>   next;
}

清空链表的实现代码 所有涉及添加，删除的操作都有类似的思路，即改变其前后位置的链(prev, next)。

public void doClear( )
{
    beginMarker = new Node<>( null, null, null );
    endMarker = new Node<>( null, beginMarker, null );
    beginMarker.next = endMarker;

    theSize = 0;
    modCount++;
}

取得节点的实现代码 将链表一分为二以后进行遍历查找，能节省一点时间。

private Node<AnyType> getNode( int idx, int lower, int upper )
{
    Node<AnyType> p;

    if( idx < lower || idx > upper )
        throw new IndexOutOfBoundsException( "getNode index: " + idx + "; size: " + size( ) );

    if( idx < size( ) / 2 )
    {
        p = beginMarker.next;
        for( int i = 0; i < idx; i++ )
            p = p.next;
    }
    else
    {
        p = endMarker;
        for( int i = size( ); i > idx; i-- )
            p = p.prev;
    }

    return p;
}

在一些操作中，尤其是remove和iterator中，使用到了modCount这个变量，意即Modification Count，用于记录操作数，它的主要作用是错误检测。

It allows the internals of the list to know if there has been a structural modification made that might cause the current operation to give incorrect results.

If you’ve ever gotten ConcurrentModificationException due to modifying a list (say, removing an item) while iterating it, its internal modCount was what tipped off the iterator.

3.6 栈 STACK

3.6.1 栈模型

对栈的基本操作有pop/进栈和push/出栈。栈有时也叫LIFO(LIFO, Last In First Out)后进先出表。

3.6.2 栈的实现

栈常用一维数组或链表来实现。

3.6.3 应用

栈主要有以下几种应用

平衡符号，检查程序中的语法错误，比如补齐花括号。
方法调用
前缀\后缀表达法

共有前缀、中缀、后缀表达法三种，其中中缀表达法就是我们日常使用的表达法，如a*(b+c)。

中缀表示法 中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。对计算机来说，计算前缀或后缀表达式的值非常简单。

前缀表示法/波兰表示法 Polish Notation, PN 前缀表达式的运算符位于操作数之前。从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。例如前缀表达式“- × + 3 4 5 6”： (1) 从右至左扫描，将6、5、4、3压入堆栈； (2) 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素，注意与后缀表达式做比较），计算出3+4的值，得7，再将7入栈； (3) 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈； (4) 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。可以看出，用计算机计算前缀表达式的值是很容易的。

后缀表示法/逆波兰表示法 Reverse Polish notation, RPN 与前缀表达式类似，只是顺序是从左至右：从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。例如后缀表达式“3 4 + 5 × 6 -”： (1) 从左至右扫描，将3和4压入堆栈； (2) 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做比较），计算出3+4的值，得7，再将7入栈； (3) 将5入栈； (4) 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈； (5) 将6入栈； (6) 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。

这两种表示法都由波兰数学家扬·武卡谢维奇提出，因此被称为波兰表示法。

具体的内容请参考原文以及https://blog.csdn.net/Antineutrino/article/details/6763722 本质上是对栈进行操作。

3.7 队列 QUEUE

像栈一样，队列(queue)也是表。是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。在此略过。

3.E 总结

本章主要介绍了抽象数据类型ADT中常用的几种。根据Wiki的资料，ADT包含以下类型。容器, 集合, 关系数组 ,串列, 队列, 优先队列, 双端队列, 堆栈, 线性表, 字符串, 树状图, 图,广义表, 多重关连数组(multimap), multiset(bag)等

第四章树

https://blog.csdn.net/javazejian/article/details/53727333

4.1 预备知识

在计算机科学中，树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个节点都只有有限个子节点或无子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树；
树里面没有环路(cycle)

4.1.1 树的实现

可以在树的节点里储存链，将每个节点的所有子节点放在树节点的链表里。例如

class Treenode {
    Object element;
    TreeNode firstChild; // 第一个子节点
    TreeNode nextSibling; // 兄弟节点
}

树可以用链表和数组实现，参考https://blog.csdn.net/u011240877/article/details/53193877

4.1.2 树的遍历及应用

分为深度和广度优先遍历。参考 https://zh.wikipedia.org/wiki/树的遍历

4.2 二叉树

在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。二叉树的第 $i$ i层至多拥有 $2^{i-1}$ 个节点；深度为 $k$ 的二叉树至多总共有${\displaystyle 2^{\begin{aligned}k\end{aligned}}-1} $个节点（定义根节点所在深度 $k_{0}=0$ ，而总计拥有节点数符合的，称为“满二叉树”；深度为 $k$ 有 $n$ 个节点的二叉树，当且仅当其中的每一节点，都可以和同样深度 $k$ 的满二叉树，序号为1到 $n$ 的节点一对一对应时，称为完全二叉树。对任何一棵非空的二叉树 $T$ ，如果其叶片（终端节点）数为 $n_{0}$ ，分支度为2的节点数为 $n_{2}$ ，则 $n_{0}=n_{2}+1$ 。

4.2.1 实现

class BinaryNode {
    Object element;
    BinaryNode left;
    BinaryNode Right;
}

4.2.2 例子

表达式树

4.3 二叉查找树 Binary Search Tree

是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
任意节点的左、右子树也分别为二叉查找树；
没有键值相等的节点。二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为 $O(\log n)$ 。

4.3.1 contains方法

对节点遍历，如果要查找的值小于此节点，向左子树继续遍历，否则向右子树遍历。要注意先判断是否是空树。

4.3.2 findMin和findMax

可以用递归或者while，最小值应该在树的左子节点，循环到没有子节点即可。

4.3.3 insert方法

类似contain的思路，调用递归来找到元素应处的位置。

private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
{
    if( t == null )
        return new BinaryNode<>( x, null, null );

    int compareResult = x.compareTo( t.element );

    if( compareResult < 0 )
        t.left = insert( x, t.left );
    else if( compareResult > 0 )
        t.right = insert( x, t.right );
    else
        ;  // Duplicate; do nothing
    return t;
}

4.3.4 remove方法

最复杂的是remove操作，它有以下几种可能:

节点是树叶，直接删除
节点有一个子节点，可以调整父节点的链来删除
节点有两个子节点，这种比较复杂，一般用右子树的最小值替代要删除的节点。

private BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> t )
{
    if( t == null )
        return t;   // Item not found; do nothing

    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 ) // Two children
    {
        t.element = findMin( t.right ).element;
        t.right = remove( t.element, t.right );
    }
    else
        t = ( t.left != null ) ? t.left : t.right;
    return t;
}

4.4 AVL树

AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 $O(\log {n})$ 。

原文花费了大量篇幅介绍旋转调平的方法，参考 https://zh.wikipedia.org/wiki/AVL树 https://zh.wikipedia.org/wiki/树旋转

图形化演示: https://visualgo.net/zh/bst

4.5 伸展树

伸展树虽然有最坏运行时间 $O(N)$ ，但它保证从空树开始连续M次对树的操作最多花费 $O(M log N)$ 时间。要做到这一点，意味着每次访问节点的时候，节点都在移动。否则，耗时应该是 $O(M \cdot N)$ 一般来说，当M次最坏情形运行时间为 $O(M f(N))$ 时，我们就说它的摊还/平摊(Amortized)时间为 $O(f(N))$ 。

简而言之，伸展树根据节点被访问的频率调整树的结构，越频繁使用的节点越靠近根部，它能够自我平衡。缺点: 它有可能会变成一条链。

参考: https://blog.csdn.net/u014634338/article/details/49586689

4.6 再探树的遍历

遍历方式的命名，源于其访问节点的顺序。最简单的划分：是深度优先（先访问子节点，再访问父节点，最后是第二个子节点）？还是广度优先（先访问第一个子节点，再访问第二个子节点，最后访问父节点）？深度优先可进一步按照根节点相对于左右子节点的访问先后来划分。如果把左节点和右节点的位置固定不动，那么根节点放在左节点的左边，称为前序（pre-order）、根节点放在左节点和右节点的中间，称为中序（in-order）、根节点放在右节点的右边，称为后序（post-order）。对广度优先而言，遍历没有前序中序后序之分：给定一组已排序的子节点，其“广度优先”的遍历只有一种唯一的结果。

前序遍历 Pre-order Traversal

先访问根，再访问子树。图示顺序: F, B, A, D, C, E, G, I, H.

中序遍历 In-order Traversal

或者叫依序遍历，它的耗时是O(N)，它的顺序是先处理左节点(子树)，然后元素，然后右节点(子树)。

public void printTree() {
    if(isEmpty())
        System.out.println("Empty Tree");
    else
        printTree(root);
private void printTree(BinaryNode<T> t) {
    if(t != null) {
        printTree(t.left);
        System.out.println(t.element);
        printTree(t.right);
    }
}

图示顺序: A, B, C, D, E, F, G, H, I.

后序遍历 Post-Order Traversal

它的耗时也是O(N)，因为每个节点的运行时间是常数时间，它的顺序是先处理子树，再处理根(节点数据)。比如下面这个计算高度的例子，这个例子声明树叶的高度为0。

private int height(BinaryNode<T> t) {
    if(t == null)
        return -i;
    else
        return 1 + Math.max(height(t.left), height(t.right));
}

图示顺序: A, C, E, D, B, H, I, G, F.

4.7 B树

B树是多叉树，又名平衡多路查找树，B可能指Balanced。 B树（B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。 B树，概括来说是一个一般化的二叉查找树（binary search tree）一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘，常被应用在数据库和文件系统的实现上。

提出背景

对一个有N条记录的已排序表进行二叉查找，可以在 $O(\log_2{n})$ 内完成。如果表有1,000,000笔记录,那么查找其中一条记录，将在20次查找内完成。 log2(1,000,000) = 19.931… 但是这样大的数据库常常被放在机械硬盘上，考虑到机械盘的寻址时间，这可能要花费0.2秒，这个耗时已经相当大了，需要进行优化。

优化

我们知道，二叉查找树的find方法耗时不会低于 $O(\log_2{n})$ ，这个数值取决于树的高度。而如果有更多的分支，树就会有更低的高度，耗时也会更少。

一棵有N个节点的完全二叉树的高度是 $\log_2{N}$ ，而一棵有N个节点的完全M叉树的高度大约是 $\log_M{N}$

要进一步了解B树的设计理念，参阅https://zh.wikipedia.org/wiki/B树

定义

根据 Knuth 的定义，一个 M 阶的B+树是一个有以下属性的树：

每一个非叶子节点有 M/2 到 M 个子节点。
根节点可以是叶子，否则它至少有两个子节点。
有 k 个子节点的非叶子节点拥有 k − 1 个键(数据项)
所有的叶子节点都在同一层，并且有 L/2 到 L 个键(数据项)

每个节点代表一个磁盘区块，我们根据所储存的项的大小选择M和L。举例来说，德州有1000万条驾驶员记录，每个关键字(非叶节点)有32字节，代表名字。每个记录有256个字节，代表驾驶员的详细信息。

设一个区块能储存8192字节，一棵M阶B树有M-1个关键字，共占用32(M-1)字节，再加上M个分支。假设分支占用4个字节，因此一个非叶节点总内存需求为36M-32字节。把一个非叶节点放入一个区块中，那么36M-32=8192,得M=228。每个数据记录是256字节，也可以把32条记录放入一个区块，因此L=8192/256=32。

目前为止，一个区块可以装32条256字节长度的记录，也可以装228个非叶节点。 M=32，因此一个树叶可以装M/2-M即16-32条数据记录。每个内部节点以114-228种方式分叉。由于有1000万条记录，因此最多存在625,000片树叶。

最坏的情况下，树叶在第四层上。这个数字由 $\log_{M/2}{N}$ 近似的给出，去掉根节点的层数， $114^4=168,896,016$ 。

关于B树的插入，删除另请参阅其他资料，比如维基百科。 PS: 1位/比特(bit)=1 binary digit=1个0或1 1字节(Byte)=8bit 字/字长(word)在不同操作系统下意义不同。64位系统1word=64bit=8Byte 小写b指bit,大写B指Byte。

4.8 标准库中的集合与映射

前面说过，List容器的查找效率很低，因此Collections API提供了两个附加容器，Set和Map，用于修补这些问题。

4.8.1 关于 Set 接口

Set是Collection的一个接口，它储存未排序且不重复的元素。 Set被HashSet，LinkedHashSet和TreeSet继承，其中TreeSet允许元素以有序状态储存。

4.8.2 关于 Map 接口

HashMap是一个Map接口的一个实现。

boolean containsKey(KeyType key)
ValueType get(KeyType key)
ValueType put(KeyType key, VauleType value)

Map不提供迭代器，要用间接的方式，比如KeySet()，values()。

4.8.3 TreeSet类和TreeMap类的实现

Java要求TreeSet和TreeMap支持基本的add, remove和contains方法，且以对数时间完成。一般我们用自顶向下的红黑树实现。

另一个核心问题是迭代器的实现。

4.8.4 使用多个映射的实例

4.E 小结

树在操作系统，编译器设计以及查找中用处广泛。其中: 分析树是编译器设计中的核心数据结构。查找树在算法设计中非常重要，其所有操作开销都比较小。 AVL树要求所有节点的左右子树高度相差最多1。伸展树的节点可达任意深度，在每次访问后调整节点的结构。 B树是平衡M叉树，能很好地适应磁盘系统的操作。

简单二叉查找树的插入和删除操作比任何平衡树方案都要快。

第五章散列

散列表(Hash Table)的实现常常被叫做散列(hashing)或哈希表。

5.1 一般想法

查找通常是对项的某个部分进行的，这部分叫做关键字。每个关键字被映射到[0, TableSize-1]这个范围.并且应当保证任何两个不同的关键字映射到不同的单元。这些就是散列的基本想法，此外还要解决映射函数和映射冲突这两个问题。

5.2 散列函数

设计散列函数是一门学问，原文提供了多个算法范例，呈现一种逐渐改进的态势。关键字如果是整数，可以用key mod Tablesize 作为函数。如果是字符串，下面是一个使用 Horner Rule 的例子。

这个散列函数涉及所有的元素，而且分布的很好。

public static int hash( String key, int tableSize ) {
    int hashVal = 0;

    for( int i = 0; i < key.length(); i++ )
        hashVal = 37 * hashVal + key.charAt(i);
        // 这里使用了霍纳法则，免于一个一个将元素相加。

    hashVal %= tableSize;

    if( hashVal < 0 )
        hashVal += tableSize;
    // 允许溢出，并附加了处理负数的机制。

    return hasVal;
}

参考资料

java.lang.Number分析 https://blog.csdn.net/springcsc1982/article/details/8788345
重新认识基本类和包装类https://blog.csdn.net/xialei199023/article/details/63251295
协变数组和类型擦除https://blog.csdn.net/xsc_c/article/details/18010499
为什么数组支持协变https://www.zhihu.com/question/21394322
Java泛型总结https://segmentfault.com/a/1190000005337789
如何理解<T extends Comparable<T>> https://www.cnblogs.com/xiaomiganfan/p/5390252.html
https://stackoverflow.com/questions/8537500/java-the-meaning-of-t-extends-comparablet
大O符号 https://zh.wikipedia.org/wiki/%E5%A4%A7O%E7%AC%A6%E5%8F%B7
折半查找https://en.wikipedia.org/wiki/Binary_search_algorithm

笔记 - 数据结构与算法分析

第一章 引论 #

1.1 本书讨论的内容 #

1.2 数学知识复习 #

1.2.1 指数 #

1.2.2 对数 #

1.2.3 级数 #

1.2.4 模运算 #

1.2.5 证明的方法 #

1.3 递归简论 #

1.4 泛型 Generic #

1.4.1 使用Object类表示泛型 #

1.4.2 基本类型的包装 #

1.4.3 使用接口类型表示泛型 #

1.4.4 数组类型的兼容性 #

1.5 实现泛型构件 #

1.5.1 简单的泛型类和接口 #

1.5.2 自动装箱/拆箱 #

1.5.3 菱形操作符 #

1.5.4 带限制的通配符 #

1.5.5 泛型 static 方法 #

1.5.6 类型限界 #

1.5.7 类型擦除 #

1.5.8 对泛型的限制 #

1.6 函数对象 Funtion Object #

第二章 算法分析 #

2.1 数学基础 #

大OOO标记法(Big O Notation) #

2.2 模型 #

2.3 要分析的问题 #

2.4 运行时间计算 #

2.4.1 一个简单的例子 #

2.4.2 一般法则 #

2.4.3 解决最大子序列和问题 #

2.4.4 运行时间中的对数 #

折半查找(binary search) #

欧几里得算法 #

2.5 幂运算 #

第三章 表、栈和队列 #

3.1 抽象数据类型 #

3.2 表 ADT #

3.2.1 简单数组 #

3.2.2 简单链表 #

3.2.2E 单链表 #

3.2.2E 双向链表 #

3.3 Java Collections API 中的表 #

3.3.1 Collection 接口 #

3.3.2 Iterator 接口 #

3.3.3 List接口、ArrayList类和LinkedList类 #

3.3.4 remove方法对LinkedList类的使用 #

3.3.5 关于ListIterator接口 #

3.4 ArrayList类的实现 #

3.4.1 基本类 #

3.4.2 迭代器、Java嵌套类和内部类 #

3.5 LinkedList类的实现 #

3.6 栈 STACK #

3.6.1 栈模型 #

3.6.2 栈的实现 #

3.6.3 应用 #

3.7 队列 QUEUE #

3.E 总结 #

第四章 树 #

4.1 预备知识 #

4.1.1 树的实现 #

4.1.2 树的遍历及应用 #

4.2 二叉树 #

4.2.1 实现 #

4.2.2 例子 #

4.3 二叉查找树 Binary Search Tree #

4.3.1 contains方法 #

4.3.2 findMin和findMax #

4.3.3 insert方法 #

4.3.4 remove方法 #

4.4 AVL树 #

4.5 伸展树 #

4.6 再探树的遍历 #

前序遍历 Pre-order Traversal #

中序遍历 In-order Traversal #

后序遍历 Post-Order Traversal #

4.7 B树 #