Java程序设计 基础、编程抽象与算法策略PDF电子书下载

第1章 Java概览 1

1.1 你的第一个Java程序 1

1.2 Java的历史 2

1.2.1 编程语言 2

1.2.2 面向对象范型 3

1.2.3 Java编程语言 4

1.2.4 Java的演化 4

1.3 Java程序的结构 5

1.3.1 注释 6

1.3.2 包声明 6

1.3.3 导入语句 7

1.3.4 类定义 7

1.3.5 run方法 8

1.4 变量 11

1.4.1 变量声明 11

1.4.2 命名惯例 11

1.5 常量 12

1.6 数据类型 13

1.6.1 数据类型的概念 13

1.6.2 整数类型 14

1.6.3 浮点类型 14

1.6.4 布尔类型 15

1.6.5 字符 15

1.6.6 字符串 16

1.6.7 复合类型 16

1.7 表达式 16

1.7.1 优先级与结合性 17

1.7.2 表达式中的混用类型 18

1.7.3 整数除法和取余操作符 18

1.7.4 类型强制转换 19

1.7.5 赋值操作符 20

1.7.6 递增和递减操作符 21

1.7.7 布尔操作符 22

1.8 语句 24

1.8.1 简单语句 24

1.8.2 块 24

1.8.3 if语句 24

1.8.4 switch语句 25

1.8.5 while语句 26

1.8.6 for语句 29

1.9 类、对象和方法 31

1.10 总结 33

1.11 复习题 34

1.12 习题 35

第2章 方法 39

2.1 Java中的方法 39

2.1.1 Java方法的语法结构 40

2.1.2 静态方法 41

2.1.3 重载 42

2.2 方法和程序结构 43

2.3 方法调用的机制 44

2.3.1 调用方法的步骤 44

2.3.2 组合函数 45

2.3.3 跟踪组合函数 47

2.4 简单的递归函数 50

2.4.1 fact的递归方案 51

2.4.2 追踪递归过程 51

2.4.3 递归的信任飞跃 54

2.5 斐波那契函数 55

2.5.1 计算斐波那契数列中的项 55

2.5.2 在递归实现中收获自信 57

2.5.3 递归实现的效率 57

2.5.4 递归不应被指责 58

2.6 总结 60

2.7 复习题 60

2.8 习题 61

第3章 字符串 67

3.1 将字符串用作抽象值 67

3.2 字符串操作 68

3.2.1 在字符串中选择字符 70

3.2.2 抽取字符串的各个部分 70

3.2.3 字符串比较 71

3.2.4 在字符串内搜索 72

3.2.5 遍历字符串中的字符 72

3.2.6 通过连接来扩展字符串 73

3.2.7 使用递归操作字符串 74

3.2.8 对字符分类 74

3.3 编写字符串应用程序 75

3.3.1 识别回文 76

3.3.2 将英文翻译为隐语 77

3.4 总结 79

3.5 复习题 80

3.6 习题 81

第4章 文件 86

4.1 文本文件 86

4.2 读取文本文件 87

4.2.1 创建文件读取器 87

4.2.2 异常处理 88

4.2.3 逐个字符地读取文件 90

4.2.4 逐行地读取文件 92

4.3 编写文本文件 93

4.3.1 打开用于输出的文件 93

4.3.2 将输出写入文件中 93

4.4 格式化输出 95

4.5 格式化输入 100

4.6 使用文件对话框 102

4.7 总结 105

4.8 复习题 105

4.9 习题 106

第5章 数组 109

5.1 数组简介 109

5.1.1 数组声明 109

5.1.2 数组选择 110

5.2 数据表示和内存 112

5.2.1 位、字节和字 112

5.2.2 二进制和十六进制表示 113

5.2.3 表示其他数据类型 115

5.2.4 数组的表示 115

5.3 使用数组来制表 117

5.4 数组初始化 118

5.5 多维数组 119

5.6 可变长参数列表 120

5.7 总结 120

5.8 复习题 121

5.9 习题 122

第6章 集合 128

6.1 ArrayList类 128

6.1.1 指定ArrayList的元素类型 129

6.1.2 声明ArrayList对象 129

6.1.3 ArrayList的操作 129

6.1.4 ArrayList类的一个简单应用 130

6.2 包装器类 131

6.2.1 从基本类型创建对象 132

6.2.2 自动装箱 132

6.2.3 包装器类中的静态方法 133

6.3 栈抽象 134

6.3.1 Stack类的结构 135

6.3.2 栈和袖珍计算器 135

6.4 队列抽象 138

6.4.1 队列应用 140

6.4.2 仿真与模型 140

6.4.3 排队模型 140

6.4.4 离散时间 141

6.4.5 仿真时间中的事件 141

6.4.6 实现仿真 142

6.4.7 随机数 144

6.5 映射表抽象 145

6.5.1 Map接口的结构 145

6.5.2 在应用中使用映射表 147

6.6 集抽象 149

6.7 遍历集合 151

6.7.1 使用迭代器 151

6.7.2 迭代顺序 151

6.7.3 计算词频 152

6.8 总结 154

6.9 复习题 155

6.10 习题 156

第7章 类和对象 161

7.1 类和面向对象设计 161

7.2 定义一个简单的Point类 161

7.2.1 将点定义为一种记录类型 162

7.2.2 在Point类中包含方法 163

7.2.3 javadoc注释 165

7.2.4 让实例变量保持私有 166

7.3 有理数 168

7.3.1 定义新类的策略 169

7.3.2 站在客户的视角 169

7.3.3 指定Rational类的私有状态 170

7.3.4 定义Rational类的构造器 170

7.3.5 为Rational类定义方法 171

7.3.6 实现Rational类 172

7.4 设计一个符号扫描器类 175

7.4.1 客户希望从符号扫描器中得到什么 175

7.4.2 TokenScanner类 176

7.5 将对象链接起来 180

7.5.1 刚铎的烽火 180

7.5.2 在链表中迭代 183

7.6 枚举类型 183

7.7 单元测试 185

7.8 总结 189

7.9 复习题 190

7.10 习题 190

第8章 继承 197

8.1 继承的简单示例 197

8.1.1 指定参数化类中的类型 197

8.1.2 调用继承方法的规则 198

8.1.3 调用继承构造器的规则 200

8.1.4 控制对类内容的访问 200

8.1.5 继承之外的选择 201

8.2 定义Employee类 203

8.3 Java图形类概览 206

8.3.1 在屏幕上放置一个窗口 207

8.3.2 向窗口中添加图形 208

8.4 一种图形对象的层次结构 210

8.4.1 创建一个面向对象的图形包 211

8.4.2 实现GWindow和GCanvas类 216

8.4.3 演示GObject类 219

8.4.4 创建简单的动画 220

8.5 定义一个控制台界面 222

8.6 总结 227

8.7 复习题 228

8.8 习题 228

第9章 递归策略 233

9.1 递归地思考 233

9.1.1 一个分而治之算法的简单示例 233

9.1.2 保持大局观 235

9.1.3 避免常见的陷阱 235

9.2 汉诺塔 236

9.2.1 刻画汉诺塔问题 237

9.2.2 找到递归策略 238

9.2.3 验证递归策略 240

9.2.4 编码解决方案 240

9.2.5 跟踪递归过程 241

9.3 子集求和问题 245

9.3.1 探寻递归解决方案 245

9.3.2 包含／排除模式 246

9.4 生成排列 246

9.5 图形递归 249

9.5.1 一个计算机艺术实例 249

9.5.2 分形 252

9.6 总结 256

9.7 复习题 256

9.8 习题 256

第10章 回溯算法 267

10.1 迷宫中的递归回溯 267

10.1.1 右手规则 267

10.1.2 寻找递归方式 268

10.1.3 识别简单情况 269

10.1.4 编码迷宫解决算法 270

10.1.5 说服自己解决方案有效 271

10.2 回溯与游戏 273

10.2.1 Nim游戏 274

10.2.2 对弈游戏的通用程序 277

10.3 最小最大值算法 279

10.3.1 博弈树 279

10.3.2 对位置和奕法做评估 279

10.3.3 限制递归搜索的深度 281

10.3.4 实现最小最大值算法 282

10.4 总结 283

10.5 复习题 284

10.6 习题 285

第11章 算法分析 294

11.1 排序问题 294

11.1.1 选择排序算法 294

11.1.2 性能的经验度量 295

11.1.3 分析选择排序的性能 296

11.2 计算复杂度 297

11.2.1 大O标记法 298

11.2.2 大O的标准简化 298

11.2.3 选择排序的计算复杂度 298

11.2.4 从代码中降低计算复杂度 299

11.2.5 最坏情况复杂度与平均情况复杂度 300

11.2.6 大O的形式化定义 301

11.3 递归的救赎 302

11.3.1 分而治之策略的威力 302

11.3.2 合并两个数组 303

11.3.3 合并排序算法 304

11.3.4 合并排序的计算复杂度 304

11.3.5 比较N2与N log N的性能 306

11.4 标准的复杂度分类 307

11.5 快速排序算法 309

11.5.1 划分数组 310

11.5.2 分析快速排序的性能 311

11.6 数学归纳 313

11.7 总结 315

11.8 复习题 316

11.9 习题 317

第12章 效率与表示方式 323

12.1 用于文本编辑的软件模式 323

12.2 设计一个简单的文本编辑器 324

12.2.1 编辑器命令 324

12.2.2 考虑底层的表示方式 325

12.2.3 对编辑器应用编码 327

12.3 基于数组的实现 328

12.3.1 定义私有数据结构 329

12.3.2 实现缓冲的操作 329

12.3.3 基于数组的编辑器的计算复杂度 332

12.4 基于栈的实现 333

12.4.1 定义私有数据结构 333

12.4.2 实现缓冲的操作 333

12.4.3 比较计算复杂度 335

12.5 基于表的实现 336

12.5.1 链表缓冲中的插入操作 338

12.5.2 链表缓冲中的删除操作 340

12.5.3 链表表示方式中的光标移动 341

12.5.4 完成缓冲的实现 343

12.5.5 链表缓冲区的计算复杂度 345

12.5.6 双向链表 345

12.5.7 时空权衡 346

12.6 总结 346

12.7 复习题 347

12.8 习题 347

第13章 线性结构 351

13.1 泛型 351

13.1.1 Java中泛型的实现 351

13.1.2 泛型的限制 353

13.1.3 GenericArray类 354

13.2 实现栈 355

13.2.1 用数组结构实现栈 355

13.2.2 用链表实现栈 357

13.3 实现队列 361

13.3.1 用数组实现队列 362

13.3.2 用链表实现队列 366

13.4 实现列表 369

13.5 翻倍策略的分析 372

13.6 总结 373

13.7 复习题 374

13.8 习题 374

第14章 映射表 377

14.1 用数组实现映射表 378

14.2 在表中查找 379

14.3 散列 382

14.3.1 设计数据结构 382

14.3.2 理解字符串的散列函数 384

14.3.3 跟踪散列表的实现 385

14.3.4 调整桶元数量 386

14.3.5 实现你自己的散列函数 388

14.4 实现HashMap类 389

14.5 总结 392

14.6 复习题 393

14.7 习题 393

第15章 树 396

15.1 家族树 396

15.1.1 用于描述树的术语 397

15.1.2 树的递归属性 397

15.1.3 用Java表示家族树 397

15.2 二叉搜索树 398

15.2.1 二叉搜索树幕后的动机 399

15.2.2 在二叉搜索树中查找结点 400

15.2.3 在二叉搜索树中插入新结点 401

15.2.4 移除结点 404

15.2.5 树的遍历 405

15.3 平衡树 406

15.3.1 树的平衡策略 408

15.3.2 可视化AVL算法 408

15.3.3 单旋转 410

15.3.4 双旋转 411

15.3.5 实现AVL算法 412

15.4 用二叉搜索树实现映射表 414

15.5 偏序树 417

15.6 总结 419

15.7 复习题 420

15.8 习题 422

第16章 集 428

16.1 作为数学抽象的集 428

16.1.1 隶属关系 428

16.1.2 集的操作 429

16.1.3 集的恒等式 430

16.2 集的实现策略 431

16.3 扩展集的模型 432

16.4 优化由小整数构成的集 435

16.4.1 特征向量 435

16.4.2 由位构成的压缩数组 436

16.4.3 位操作 437

16.4.4 实现特征向量 438

16.4.5 定义CharSet类 439

16.5 总结 443

16.6 复习题 443

16.7 习题 444

第17章 图 447

17.1 图的结构 447

17.1.1 有向图和无向图 448

17.1.2 路径和环 449

17.1.3 连通性 449

17.2 表示策略 450

17.2.1 使用邻接表表示连接 450

17.2.2 使用邻接矩阵表示连接 451

17.2.3 使用弧集表示连接 452

17.3 基于集的图抽象 452

17.4 图的遍历 458

17.4.1 深度优先搜索 458

17.4.2 广度优先搜索 461

17.5 查找最小代价路径 463

17.6 泛化Graph类 467

17.6.1 在图抽象中使用参数化类型 468

17.6.2 添加额外的操作 469

17.7 搜索Web的算法 469

17.7.1 Google的PageRank算法 470

17.7.2 PageRank计算的一个微型实例 470

17.8 总结 472

17.9 复习题 473

17.10 习题 474

第18章 表达式树 481

18.1 解释器概览 481

18.2 表达式的结构 483

18.2.1 表达式的递归定义 483

18.2.2 二义性 484

18.2.3 表达式树 485

18.2.4 实现Expression的子类 488

18.2.5 对表达式绘图 491

18.2.6 跟踪计算过程 492

18.3 解析表达式 495

18.3.1 解析和语法 495

18.3.2 考虑优先级 496

18.3.3 递归下推解析器 496

18.4 总结 501

18.5 复习题 502

18.6 习题 502

第19章 将函数作为数据使用 507

19.1 交互式程序 507

19.1.1 Java事件模型 507

19.1.2 事件驱动的简单应用 508

19.1.3 匿名内部类 511

19.2 命令分派表 512

19.2.1 使用层叠if语句的命令分派 513

19.2.2 使用命令表的命令分派 514

19.2.3 用lambda表达式实现命令分派 516

19.3 lambda表达式 516

19.3.1 Java中lambda表达式的语法 516

19.3.2 函数式接口 517

19.3.3 一个lambda函数的简单应用 518

19.4 绘制函数 519

19.5 映射函数 520

19.6 总结 522

19.7 复习题 523

19.8 习题 523

索引 529