第1章 袋子

袋子

袋子的行为

袋子的规格说明

接口

ADT袋子的使用

像使用自动售货机一样使用ADT

Java类库：接口Set

第2章 使用数组实现袋子

使用固定大小的数组实现ADT袋子

一个类比

一组核心方法

核心方法的实现

核心方法的测试

更多方法的实现

删除物品的方法

使用可变大小的数组实现ADT袋子

调整数组的大小

袋子的一种新的实现

使用数组实现ADT袋子的优缺点

第3章 使用链表实现袋子

链表

通过添加节点到表头来创建链表

ADT袋子的链表实现

私有的类Node

类LinkedBag的概要

一些核心方法的定义

核心方法的测试

方法getFrequencyOf

方法contains

从链表中删除物品

方法remove和clear

具有方法set和get的类Node

使用链表实现ADT袋子的优缺点

第4章 算法的效率

动机

算法效率的度量

基本操作次数的统计

最好、最坏和平均情况

大O表示法

程序结构的复杂度

效率的图形化表示

ADT袋子不同实现的效率

基于数组的实现

基于链表的实现

两种实现方法的比较

第5章 栈

ADT栈的规格说明

利用栈处理代数表达式

应用问题：中缀代数表达式中括号平衡的检查

应用问题：中缀表达式向后缀表达式的转换

应用问题：后缀表达式的求值

应用问题：中缀表达式的求值

程序栈

Java类库：类Stack

第6章 栈的实现

基于链表的实现

基于数组的实现

基于向量的实现

Java类库：Vector类

使用向量实现ADT栈

第7章 递归

什么是递归

跟踪一个递归方法

有返回值的递归方法

递归地处理一个数组

递归地处理一个链表

递归方法的时间效率

countDown的时间效率

计算xn的时间效率

一个复杂问题的简单解决方案

一个简单问题的拙劣解决方案

尾递归

间接递归

使用栈代替递归

第8章 排序引论

组织Java对数组排序的方法

选择排序

迭代选择排序

递归选择排序

选择排序的效率

插入排序

迭代插入排序

递归插入排序

插入排序的效率

链表的插入排序

希尔排序

Java代码

希尔排序的效率

算法比较

第9章 快速排序方法

归并排序

数组的归并

递归的归并排序

归并排序的效率

迭代的归并排序

Java类库中的归并排序

快速排序

快速排序的效率

创建划分

快速排序的Java代码

Java类库中的快速排序

基数排序

基数排序的伪代码

基数排序的效率

算法比较

第10章 队列、双端队列和优先队列

ADT队列

解决问题：模拟排队

解决问题：计算出售股票时的资本增益（一）

Java类库：接口Queue

ADT双端队列

解决问题：计算出售股票时的资本增益（二）

Java类库：接口Deque

Java类库：ArrayDeque类

ADT优先队列

解决问题：跟踪你的作业

Java类库：类PriorityQueue

第11章 队列、双端队列和优先队列的实现

基于链表队列的实现

基于数组队列的实现

循环数组

有一个未使用存储单元的循环数组

基于向量队列的实现

基于循环链表队列的实现

由两部分构成的循环链表

Java类库：类AbstractQueue

基于双向链表双端队列的实现

实现优先队列的可用方法

第12章 线性表

ADT线性表的规格说明

使用ADT线性表

Java类库：List接口

Jave类库：ArraryList类

第13章 用数组实现线性表

用数组实现ADT线性表

一个类比

Java实现

用数组实现ADT线性表的效率

用Vector实现ADT线性表

第14章 用链表实现线性表

操作链表节点

在多种位置加入节点

在多种位置删除节点

私有方法getNodeAt

开始实现

数据域和构造函数

在列表结尾加入

在列表给定位置加入

方法isEmpty和toArray

测试核心方法

继续实现

一个更好的实现

尾引用

用链表实现ADT列表的效率

Java类库：类 LinkedList

第15章 迭代器

迭代器是什么

Iterator接口

使用Iterator接口

独立类迭代器

内部类迭代器

基于链表实现

基于数组实现

为什么迭代器方法在它们自己的类中

ListIterator接口

使用ListIterator接口

ListIterator接口基于数组的实现

内部类

Java类库：Iterable接口

lterable和for-each循环

修改版接口List

第16章 有序表

ADT有序表的规格说明

使用ADT有序表

链表实现

方法add

链表实现的效率

使用ADT线性表的实现

效率问题

第17章 继承及线性表

使用继承实现有序表

设计一个基类

创建一个抽象基类

有序表的一种高效实现

方法add

第18章 查找

问题引入

查找无序数组

无序数组的迭代式顺序查找

无序数组的递归式顺序查找

顺序查找数组的效率

查找有序数组

有序数组的顺序查找

有序数组的二分查找

Java类库：方法binarySearch

二分查找数组的效率

查找无序链表

无序链表的迭代式顺序查找

无序链表的递归式顺序查找

顺序查找链表的效率

查找有序链表

有序链表的顺序查找

二分查找有序链表

查找方法的选择

第19章 词典

ADT词典规格说明

Java接口

迭代器

使用ADT词典

问题解决：电话号码本

问题解决：词频

问题解决：词的索引

Java类库：Map接口

第20章 词典的实现

基于数组的实现

一个无序数组词典

一个有序数组词典

基于向量的实例

链式实例

一个无序链式词典

一个有序链式词典

第21章 散列概述

散列是什么

散列函数

计算散列码

将散列码压缩成散列表的索引

处理冲突

用线性探测实现开放定址

用二次探测实现开放定址

用双重散列实现开放定址

开放定址的潜在问题

链地址

第22章 用散列实现词典

散列的效率

容载分析

开放定址消耗分析

链地址消耗分析

再散列

不同冲突解决方案的对比

用散列实现词典的实例

散列表中的条目

数据域和构造函数

getValue，remove和add方法

迭代器

Java类库：HashMap类

Java类库：HashSet类

第23章 树

树的概念

层次化的数据组织

树的术语

树的遍历

遍历二叉树

一般树的遍历

树的Java接口

树的通用接口

二叉树的接口

二叉树的例子

表达式树

决策树

二叉查找树

堆

一般树的例子

语法分析树

游戏树

第24章 树的实现

二叉树的节点

节点的接口

二叉树节点的实现

ADT二叉树的实现

创建基本二叉树

privateSetTree方法

访问器与更改器方法

计算高度和节点数

遍历

表达式树的实现

一般树

一般树的节点

用二叉树表示一般树

第25章 二叉查找树的实现

开始

二叉查找树接口

重复的条目

开始类定义

查找和检索

遍历

添加条目

递归实现

迭代实现

删除条目

删除一个叶子节点的条目

删除节点有一个孩子的条目

删除节点有两个孩子的条目

删除为根的条目

递归实现

迭代实现

操作的效率

平衡的重要性

节点添加的顺序

ADT词典实现

第26章 堆的实现

再论ADT堆

用数组表／示堆

插入条目

删除根

创建堆

堆排序

第27章 平衡查找树

AVL树

单旋转

双旋转

实现细节

2-3树

查找2-3树

添加条目至2-3树

添加时分裂节点

2-4树

添加条目至2-3树

比较AVL，2-3和2-4树

红黑树

红黑树的性质

添加条目到红黑树

Java类库：TreeMap类

B树

第28章 图

一些示例和术语

公路线路图

航空线路图

迷宫

树

遍历

广度优先遍历

深度优先遍历

拓扑排序

路径

寻找路径

无权图的最短路径算法

加权图中的最短路径

ADT图的Java接口

第29章 图的实现

两种实现的概述

邻接矩阵

邻接表

顶点和边

类Vertex的规格说明

内部类Edge

实现Vertex类

ADT图的实现

基本操作

图算法