目　录Programming Abstractions in Java出版者的话译者序前言第1章　Java概览11.1　你的第一个Java程序11.2　Java的历史21.2.1　编程语言21.2.2　面向对象范型31.2.3　Java编程语言41.2.4　Java的演化41.3　Java程序的结构51.3.1　注释61.3.2　包声明61.3.3　导入语句71.3.4　类定义71.3.5　run方法81.4　变量111.4.1　变量声明111.4.2　命名惯例111.5　常量121.6　数据类型131.6.1　数据类型的概念131.6.2　整数类型141.6.3　浮点类型141.6.4　布尔类型151.6.5　字符151.6.6　字符串161.6.7　复合类型161.7　表达式161.7.1　优先级与结合性171.7.2　表达式中的混用类型181.7.3　整数除法和取余操作符181.7.4　类型强制转换191.7.5　赋值操作符201.7.6　递增和递减操作符211.7.7　布尔操作符221.8　语句241.8.1　简单语句241.8.2　块241.8.3　if语句241.8.4　switch语句251.8.5　while语句261.8.6　for语句291.9　类、对象和方法311.10　总结331.11　复习题341.12　习题35第2章　方法392.1　Java中的方法392.1.1　Java方法的语法结构402.1.2　静态方法412.1.3　重载422.2　方法和程序结构432.3　方法调用的机制442.3.1　调用方法的步骤442.3.2　组合函数452.3.3　跟踪组合函数472.4　简单的递归函数502.4.1　fact的递归方案512.4.2　追踪递归过程512.4.3　递归的信任飞跃542.5　斐波那契函数552.5.1　计算斐波那契数列中的项552.5.2　在递归实现中收获自信572.5.3　递归实现的效率572.5.4　递归不应被指责582.6　总结602.7　复习题602.8　习题61第3章　字符串673.1　将字符串用作抽象值673.2　字符串操作683.2.1　在字符串中选择字符703.2.2　抽取字符串的各个部分703.2.3　字符串比较713.2.4　在字符串内搜索723.2.5　遍历字符串中的字符723.2.6　通过连接来扩展字符串733.2.7　使用递归操作字符串743.2.8　对字符分类743.3　编写字符串应用程序753.3.1　识别回文763.3.2　将英文翻译为隐语773.4　总结793.5　复习题803.6　习题81第4章　文件864.1　文本文件864.2　读取文本文件874.2.1　创建文件读取器874.2.2　异常处理884.2.3　逐个字符地读取文件904.2.4　逐行地读取文件924.3　编写文本文件934.3.1　打开用于输出的文件934.3.2　将输出写入文件中934.4　格式化输出954.5　格式化输入1004.6　使用文件对话框1024.7　总结1054.8　复习题1054.9　习题106第5章　数组1095.1　数组简介1095.1.1　数组声明1095.1.2　数组选择1105.2　数据表示和内存1125.2.1　位、字节和字1125.2.2　二进制和十六进制表示1135.2.3　表示其他数据类型1155.2.4　数组的表示1155.3　使用数组来制表1175.4　数组初始化1185.5　多维数组1195.6　可变长参数列表1205.7　总结1205.8　复习题1215.9　习题122第6章　集合1286.1　ArrayList类1286.1.1　指定ArrayList的元素类型1296.1.2　声明ArrayList对象1296.1.3　ArrayList的操作1296.1.4　ArrayList类的一个简单应用1306.2　包装器类1316.2.1　从基本类型创建对象1326.2.2　自动装箱1326.2.3　包装器类中的静态方法1336.3　栈抽象1346.3.1　Stack类的结构1356.3.2　栈和袖珍计算器1356.4　队列抽象1386.4.1　队列应用1406.4.2　仿真与模型1406.4.3　排队模型1406.4.4　离散时间1416.4.5　仿真时间中的事件1416.4.6　实现仿真1426.4.7　随机数1446.5　映射表抽象1456.5.1　Map接口的结构1456.5.2　在应用中使用映射表1476.6　集抽象1496.7　遍历集合1516.7.1　使用迭代器1516.7.2　迭代顺序1516.7.3　计算词频1526.8　总结1546.9　复习题1556.10　习题156第7章　类和对象1617.1　类和面向对象设计1617.2　定义一个简单的Point类1617.2.1　将点定义为一种记录类型1627.2.2　在Point类中包含方法1637.2.3　javadoc注释1657.2.4　让实例变量保持私有1667.3　有理数1687.3.1　定义新类的策略1697.3.2　站在客户的视角1697.3.3　指定Rational类的私有状态1707.3.4　定义Rational类的构造器1707.3.5　为Rational类定义方法1717.3.6　实现Rational类1727.4　设计一个符号扫描器类1757.4.1　客户希望从符号扫描器中得到什么1757.4.2　TokenScanner类1767.5　将对象链接起来1807.5.1　刚铎的烽火1807.5.2　在链表中迭代1837.6　枚举类型1837.7　单元测试1857.8　总结1897.9　复习题1907.10　习题190第8章　继承1978.1　继承的简单示例1978.1.1　指定参数化类中的类型1978.1.2　调用继承方法的规则1988.1.3　调用继承构造器的规则2008.1.4　控制对类内容的访问2008.1.5　继承之外的选择2018.2　定义Employee类2038.3　Java图形类概览2068.3.1　在屏幕上放置一个窗口2078.3.2　向窗口中添加图形2088.4　一种图形对象的层次结构2108.4.1　创建一个面向对象的图形包2118.4.2　实现GWindow和GCanvas类2168.4.3　演示GObject类2198.4.4　创建简单的动画2208.5　定义一个控制台界面2228.6　总结2278.7　复习题2288.8　习题228第9章　递归策略2339.1　递归地思考2339.1.1　一个分而治之算法的简单示例2339.1.2　保持大局观2359.1.3　避免常见的陷阱2359.2　汉诺塔2369.2.1　刻画汉诺塔问题2379.2.2　找到递归策略2389.2.3　验证递归策略2409.2.4　编码解决方案2409.2.5　跟踪递归过程2419.3　子集求和问题2459.3.1　探寻递归解决方案2459.3.2　包含/排除模式2469.4　生成排列2469.5　图形递归2499.5.1　一个计算机艺术实例2499.5.2　分形2529.6　总结2569.7　复习题2569.8　习题256第10章　回溯算法26710.1　迷宫中的递归回溯26710.1.1　右手规则26710.1.2　寻找递归方式26810.1.3　识别简单情况26910.1.4　编码迷宫解决算法27010.1.5　说服自己解决方案有效27110.2　回溯与游戏27310.2.1　Nim游戏27410.2.2　对弈游戏的通用程序27710.3　最小最大值算法27910.3.1　博弈树27910.3.2　对位置和奕法做评估27910.3.3　限制递归搜索的深度28110.3.4　实现最小最大值算法28210.4　总结28310.5　复习题28410.6　习题285第11章　算法分析29411.1　排序问题29411.1.1　选择排序算法29411.1.2　性能的经验度量29511.1.3　分析选择排序的性能29611.2　计算复杂度29711.2.1　大O标记法29811.2.2　大O的标准简化29811.2.3　选择排序的计算复杂度29811.2.4　从代码中降低计算复杂度29911.2.5　最坏情况复杂度与平均情况复杂度30011.2.6　大O的形式化定义30111.3　递归的救赎30211.3.1　分而治之策略的威力30211.3.2　合并两个数组30311.3.3　合并排序算法30411.3.4　合并排序的计算复杂度30411.3.5　比较N2与N log N的性能30611.4　标准的复杂度分类30711.5　快速排序算法30911.5.1　划分数组31011.5.2　分析快速排序的性能31111.6　数学归纳31311.7　总结31511.8　复习题31611.9　习题317第12章　效率与表示方式32312.1　用于文本编辑的软件模式32312.2　设计一个简单的文本编辑器32412.2.1　编辑器命令32412.2.2　考虑底层的表示方式32512.2.3　对编辑器应用编码32712.3　基于数组的实现32812.3.1　定义私有数据结构32912.3.2　实现缓冲的操作32912.3.3　基于数组的编辑器的计算复杂度33212.4　基于栈的实现33312.4.1　定义私有数据结构33312.4.2　实现缓冲的操作33312.4.3　比较计算复杂度33512.5　基于表的实现33612.5.1　链表缓冲中的插入操作33812.5.2　链表缓冲中的删除操作34012.5.3　链表表示方式中的光标移动34112.5.4　完成缓冲的实现34312.5.5　链表缓冲区的计算复杂度34512.5.6　双向链表34512.5.7　时空权衡34612.6　总结34612.7　复习题34712.8　习题347第13章　线性结构35113.1　泛型35113.1.1　Java中泛型的实现35113.1.2　泛型的限制35313.1.3　GenericArray类35413.2　实现栈35513.2.1　用数组结构实现栈35513.2.2　用链表实现栈35713.3　实现队列36113.3.1　用数组实现队列36213.3.2　用链表实现队列36613.4　实现列表36913.5　翻倍策略的分析37213.6　总结37313.7　复习题37413.8　习题374第14章　映射表37714.1　用数组实现映射表37814.2　在表中查找37914.3　散列38214.3.1　设计数据结构38214.3.2　理解字符串的散列函数38414.3.3　跟踪散列表的实现38514.3.4　调整桶元数量38614.3.5　实现你自己的散列函数38814.4　实现HashMap类38914.5　总结39214.6　复习题39314.7　习题393第15章　树39615.1　家族树39615.1.1　用于描述树的术语39715.1.2　树的递归属性39715.1.3　用Java表示家族树39715.2　二叉搜索树39815.2.1　二叉搜索树幕后的动机39915.2.2　在二叉搜索树中查找结点40015.2.3　在二叉搜索树中插入新结点40115.2.4　移除结点40415.2.5　树的遍历40515.3　平衡树40615.3.1　树的平衡策略40815.3.2　可视化AVL算法40815.3.3　单旋转41015.3.4　双旋转41115.3.5　实现AVL算法41215.4　用二叉搜索树实现映射表41415.5　偏序树41715.6　总结41915.7　复习题42015.8　习题422第16章　集42816.1　作为数学抽象的集42816.1.1　隶属关系42816.1.2　集的操作42916.1.3　集的恒等式43016.2　集的实现策略43116.3　扩展集的模型43216.4　优化由小整数构成的集43516.4.1　特征向量43516.4.2　由位构成的压缩数组43616.4.3　位操作43716.4.4　实现特征向量43816.4.5　定义CharSet类43916.5　总结44316.6　复习题44316.7　习题444第17章　图44717.1　图的结构44717.1.1　有向图和无向图44817.1.2　路径和环44917.1.3　连通性44917.2　表示策略45017.2.1　使用邻接表表示连接45017.2.2　使用邻接矩阵表示连接45117.2.3　使用弧集表示连接45217.3　基于集的图抽象45217.4　图的遍历45817.4.1　深度优先搜索45817.4.2　广度优先搜索46117.5　查找最小代价路径46317.6　泛化Graph类46717.6.1　在图抽象中使用参数化类型46817.6.2　添加额外的操作46917.7　搜索Web的算法46917.7.1　Google的PageRank算法47017.7.2　PageRank计算的一个微型实例47017.8　总结47217.9　复习题47317.10　习题474第18章　表达式树48118.1　解释器概览48118.2　表达式的结构48318.2.1　表达式的递归定义48318.2.2　二义性48418.2.3　表达式树48518.2.4　实现Expression的子类48818.2.5　对表达式绘图49118.2.6　跟踪计算过程49218.3　解析表达式49518.3.1　解析和语法49518.3.2　考虑优先级49618.3.3　递归下推解析器49618.4　总结50118.5　复习题50218.6　习题502第19章　将函数作为数据使用50719.1　交互式程序50719.1.1　Java事件模型50719.1.2　事件驱动的简单应用50819.1.3　匿名内部类51119.2　命令分派表51219.2.1　使用层叠if语句的命令分派51319.2.2　使用命令表的命令分派51419.2.3　用lambda表达式实现命令分派51619.3　lambda表达式51619.3.1　Java中lambda表达式的语法51619.3.2　函数式接口51719.3.3　一个lambda函数的简单应用51819.4　绘制函数51919.5　映射函数52019.6　总结52219.7　复习题52319.8　习题523索引529