●Chapter1知识整理
1.1类、对象和应用程序
类
统一方法
对象
应用程序
1.2组织类
继承
包
1.3异常
处理异常状况
异常与类：实例
1.4数据结构
非独立实现的结构
独立实现结构
数据结构的含义？
1.5基本结构化机制
内存
引用
数组
1.6算法比较：增长阶分析
测算法的时间效率
情况复杂度
输入值的大小
算法比较66
增长顺序68
选择排序算法69
常见的增长阶72
小结73
习题74
Chapter2抽象数据类型—栈
2.1抽象
信息隐藏
数据抽象
数据层次
前置条件和后置条件
Java接口
基于接口的多态性
2.2栈
栈的操作
栈的用法
2.3集合元素
常用集合
2.4栈接口
异常情况
接口
应用实例
2.5基于数组的栈实现
ArrayBoundedstack类
栈操作的定义
ArrayListStack类
2.6应用程序：平衡表达式
平衡类
应用程序
软件架构
2.7链表
数组与链表
LLNode类
链表操作
2.8基于链接的栈
LinkedStack类
压栈操作
弹栈操作
其他栈操作
比较栈的实现方式
2.9应用程序：后缀表达式评估器
讨论
后缀表达式求值
后缀表达式求值算法
错误处理
tFixEvaluator类
PFixCLI类
2.10栈变体
重新审视栈抽象数据类型
Java栈类和集合框架
小结
习题
Chapter3递归
3.1递归定义、算法和程序
递归定义
递归计算
递归程序
阶乘的迭代解决方案
3.2三个问题
验证递归算法
确定输入
编写递归方法
调试递归方法
3.3数组的递归处理
二分查找
3.4链表的递归处理
链表的递归性质
链表遍历
链表转换
3.5塔
算法
方法
程序
3.6分形
丁字方形的分形
变体
3.7移除递归
递归的工作原理
尾调用消除
直接使用栈
3.8何时使用递归解决方案
递归开销
低效算法
清晰度
小结
习题
Chapter4抽象数据类型—队列
4.1队列
队列操作
使用队列
4.2队列接口
应用实例
4.3基于数组的队列实现
ArrayBoundedQueue类
ArrayUnboundedQueue类
4.4交互式测试驱动程序
一般方法
ArrayBoundedQueue类的测试驱动
使用测试驱动程序
4.5基于链接的队列实现
入队操作
出队操作
循环链表队列设计
比较队列实现
4.6应用程序：回文
回文类
应用程序
4.7队列变体
特殊情况
玻璃队列
双端队列
双向链表
Java库集合框架队列/双端队列
4.8应用程序：平均等待时间
问题讨论和示例
Customer类
模拟
测试
4.9并发、干扰和同步
Counter类
Java线程
干扰
同步
同步队列
并发与Java库集合类
小结
习题
Chapter5抽象数据类型—集合
5.1集合接口
集合的前提
接口
5.2实现基于数组的集合
5.3应用程序：词汇密度
5.4重新探讨比较对象
函数equals
Comparable接口
5.5基于排序数组的集合的实现
参比元素
实现
以“拷贝”或“引用”的方式实现抽象数据类型
示例程序
5.6基于链接的集合的实现
内部表示形式
运算
比较集合实现
5.7集合变体
Java集合框架
BagADT
SetADT
小结
习题
Chapter6抽象数据类型—列表
6.1列表接口
迭代
列表假设
接口
6.2列表实现
基于数组的实现
基于链表的实现
6.3应用程序：纸牌和游戏
Card类
CardDeck类
应用程序：排列CardHand
应用程序：HigherorLower
应用程序：一对牌有多罕见
基于数组的有序列表的实现
插入排序
不支持的操作
Comparator接口
构造函数
应用实例
6.5列表变体
Java库列表
链表变体
链表作为节点数组
6.6应用程序：大整数
大整数
内部表示
LargeIntList类
LargeInt类
加法和减法
LargeIntCLI程序
小结
习题
Chapter7抽象数据类型—二搜索树
7.1树
树的遍历
7.2二搜索树
二树
二搜索树
二树遍历
7.3二搜索树接口
接口449
7.4实现层级：基础级
7.5迭代法VS递归法的实现
size函数的递归法
size函数的迭代法
递归还是迭代
7.6实现层级：剩余的观察函数
contains和get函数
遍历
7.7实现层级：转换函数
add操作
remove操作
7.8二搜索树的功能
重新讨论文本分析实验
插入顺序和树形
平衡二搜索树
7.9应用程序：词频计数器
类WordFreq
应用程序
7.10树的变体
特定应用的变体4
平衡搜索树
小结
习题
Chapter8抽象数据类型—Map
8.1Map接口
8.2Map的实现
无序数组
有序数组
无序链表
有序链表
二搜索树
以基于ArrayList的方式实现
8.3应用程序：从字符串到字符串的Map
8.4哈希法
冲突
8.5哈希函数
数组大小
哈希函数
Java对哈希的支持
复杂度
8.6基于哈希的Map
实现
使用HMap类
8.7Map的变体
混合结构
Java对Map的支持
小结
习题
Chapter9抽象数据类型—优先级队列
9.1优先级队列接口
使用优先级队列
接口
9.2优先级队列的实现
无序数组
有序数组
有序链表
二搜索树
9.3堆
9.4堆的实现
二树的非链接表示
实现堆
Enqueue（入队）方法
Dequeue（出队）方法
应用实例
堆VS优先级队列的其他表示
小结
习题
Chapter10抽象数据类型—图
10.1图的介绍
10.2图的接口
10.3图的实现
基于数组的实现
链接实现
10.4应用程序：图的遍历
深度优先搜索
广度优先搜索
10.5应用程序：单源短路径问题
小结
习题
Chapter11排序和查找算法
11.1排序
测试工具
11.2简单排序
选择排序
冒泡排序
插入排序
11.3O(Nlog2N)排序
合并排序
快速排序
堆排序
11.4更多的排序思考
测试
效率
对象和引用
比较对象
稳定性
11.5查找
顺序查找
高概率排序
有序集合
哈希法
小结
习题
附录A
附录B
附录C
附录D
术语表
索引