JAVA程序设计与数据结构 第2版PDF电子书下载

第1章　概述 1

1.1 集合 1

1.1.1　集合的分类 1

目录 1

1.1.2　关于集合的操作 2

1.2　抽象数据类型 3

1.3 算法分析 4

1.3.1 简单性和清晰度 4

1.3.2　空间效率 4

1.3.3 时间效率 4

1.4　算法类型 5

1.4.2　分治算法 6

1.4.3 回溯算法 6

1.4.1 贪婪算法 6

1.5　软件开发过程 7

1.5.1 复杂性 7

1.5.2　脆弱性 7

1.5.3 可扩展性 8

1.5.4 互连性 8

1.6　面向对象程序设计简介 8

1.6.1 过程式程序设计 8

1.6.2　函数式程序设计 8

1.6.3　面向对象程序设计（OOP） 9

1.6.4　面向对象程序设计的直观概括 9

1.7　软件开发生命周期 10

1.8 本书的软件开发方法 11

1.9　分析和设计阶段的测试 12

1.8.4 实现 12

1.8.2 分析 12

1.8.3 设计 12

1.8.1 需求 12

1.10　测试代码 13

1.10.1　单元、集成和验收测试 13

1.10.2　测试内容 13

1.10.3　如何设计测试数据 14

1.11 正确性的证明 15

1.12　软件开发过程的其他方面 15

1.12.1 编码约定 15

1.12.2　前置条件和后置条件 16

1.13　层次系统的开发 17

2.1 简介 20

第2章　面向对象程序设计和基本的输入输出功能 20

2.2 类和对象 21

2.2.1 示例：字符串对象 21

2.2.2　示例：终端输出 22

2.2.3　对象、类和计算机内存 22

2.2.4　对象的3个特征 23

2.2.5　客户端和服务器 23

2.3 Employee类 23

2.3.1 用户需求 23

2.3.2　类模板的结构 26

2.3.3 Employee类的设计和实现 27

2.3.4　构造函数和异常 28

2.3.5　this的使用 30

2.3.6　取值方法、赋值方法和toString方法 30

2.3.7　测试等同性 32

2.3.8　比较及接口Comparable 33

2.3.9　复制对象及接口Cloneable 34

2.3.10　对象序列化 35

2.3.11 finalize和dispose方法 36

2.3.12　使用对象时一些有用的提示 37

2.4　继承和多态 37

2.5 实现一个简单的图形层次结构 38

2.5.1　实现Shape类 38

2.5.2　实现Circle类 39

2.5.3　构造函数和super保留字 40

2.5.4　其他方法和super保留字 41

2.5.5 实现Rectangle类 41

2.5.6　保护型（protected）变量和方法 42

2.6 图形类的使用 43

2.5.7　实现、扩展、重写和终结 43

2.6.1 查找合适的方法 44

2.6.2 图形数组 45

2.7　将图形作为参数和返回值 47

2.7.1 示例：输入Retangle，输出Circle 47

2.7.2　示例：输入任意图形，输出Circle 48

2.7.3　示例：输入任意图形，输出任意图形 48

2.8　面向对象系统的分解 49

2.8.1 确定类 50

2.8.2　分配职责 51

2.8.3　确定数据属性 51

2.8.4　确定方法 52

2.8.5　类和对象模型之间的关系 52

2.9　基于字符的流输入、输出 53

2.9.1　介绍键盘读取器 54

2.9.2　扩展键盘读取器 56

2.9.3　文件读取器 57

2.9.4　格式化输出 59

2.9.5　使用支持类 62

第3章　基于GUI的Java应用程序 64

3.1 模型-视图-控制器模式 64

3.2　温度转换程序的代码 65

3.2.1 模型 65

3.2.2　视图 66

3.2.3　控制器 67

3.2.4　视图和控制器的完整代码 68

3.3 GridBagLayout类 70

3.4　EasyGridLayout类 72

3.5 IntegerField类和DoubleField类 74

3.6　弹出式消息 75

3.7　其他窗口组件 77

3.7.1　菜单和文本区 78

3.7.2　复选框和单选按钮 80

3.7.3 列表框 83

3.8　模式对话框的使用 88

3.9　多窗口应用程序 93

3.10　侦听器共享 96

3.11　方法一览表 98

第4章　复杂度 107

4.1　衡量算法的效率 107

4.1.1　测量算法的执行时间 107

4.1.2　对指令计数 109

4.1.3　用代数方法推导增长率 111

4.2 比较增长率 112

4.2.1　使用代数方法比较增长率 112

4.1.4　测量算法使用的内存 112

4.2.2　大O表示法 114

4.2.3　最佳、最差和平均性能 115

4.3 查找算法 116

4.3.1 数组的线性查找法 116

4.3.2　数组的二分查找法 117

4.4　排序算法 119

4.4.1　选择排序 119

4.4.2 冒泡排序 120

4.4.3　插入排序 121

4.5　案例分析：记录运行时间以及对指令计数 122

4.5.1 要求 122

4.5.4　Algorithms类的实现 123

4.5.2　分析 123

4.5.3　Algorithms类的设计 123

4.5.5　AlgorithmProfiler类的设计和实现 125

第5章　数组和链表 130

5.1　数组的特性 130

5.1.1 随机访问和连续地址内存 130

5.1.2　静态内存和动态内存 131

5.1.3　物理大小和逻辑大小 132

5.2　数组操作 133

5.2.1　增加数组的大小 133

5.2.2　减小数组大小 134

5.2.3　向数组中插入数据项 134

5.2.4　从数组中移除数据项 135

5.2.6　复杂度的权衡：查找和修改数组 136

5.2.5　数组方法的测试程序 136

5.3　链表 137

5.3.1 单链表和双向链表 137

5.3.2　不连续地址内存和节点 138

5.3.3　定义单链节点类 139

5.3.4　使用单链节点类 140

5.4　单链表的操作 142

5.4.1 遍历 142

5.4.2　查找（对象或第i项） 143

5.4.3　替换（对象或第i项） 144

5.4.4　在首端插入 144

5.4.5　在尾端插入 145

5.4.6　在首端移除 146

5.4.7　在尾端移除 147

5.4.8　插入（对象或第i项） 148

5.4.9　移除（对象或第i项） 149

5.4.10　复杂度的权衡：时间、空间和单链表 150

5.5　链表的各种变体 150

5.5.1　带有虚头节点的循环链表 150

5.5.2　双向链表 151

第6章　集合概述 155

6.1 简介 155

6.1.1　本书中集合的概述 156

6.1.2　Tiny集合 158

6.2　多种实现 158

6.3　集合和强制类型转换 159

6.4　集合和串行化 161

6.5.1　迭代器的使用 162

6.5　迭代器 162

6.5.2　实现Tiny和iterator方法 163

6.6　集合和集合视图 166

6.6.1 两个例子 167

6.6.2　Collection接口中的方法 168

6.6.3　collectionView方法的实现（可选内容） 169

6.6.4　AbstractCollection实现（可选内容） 170

6.7　集合的原型和专门版本 172

6.7.1　Tiny专门版本的概述（可选内容） 172

6.7.2　Tiny接口的扩展（可选内容） 173

6.7.3　将Tiny方法分配给类（可选内容） 174

6.7.4　编写代码的细节（可选内容） 175

6.8　本章向导 179

7.1 栈概述 182

第7章　栈 182

7.2 栈原型 183

7.3　栈的使用 184

7.4　栈原型的实现 186

7.4.1 数组实现 186

7.4.2　链表实现 188

7.4.3　两个实现的时间和空间分析 191

7.5　栈的3个应用 192

7.5.1　算术表达式求值 192

7.5.2　回溯算法 195

7.5.3　内存管理 196

7.6　专门版本的接口 200

7.7　专门版本的实现 201

7.8.1　要求 204

7.8　案例分析：后缀表达式求值 204

7.8.2　分析 205

7.8.3　设计 207

7.8.4　实现 210

第8章　队列 216

8.1 队列概述 216

8.2　队列的原型 217

8.3 队列原型的实现 219

8.3.1　链表实现 219

8.3.2　数组实现 220

8.3.3　两种实现的时间和空间分析 222

8.4　队列的两个应用 223

8.4.1 模拟 223

8.4.2　CPU循环调度 224

8.5　专门版本的接口 225

8.6　专门版本的实现 226

8.7　案例分析1：模拟超市结账流程 228

8.7.1　要求 228

8.7.2　分析 228

8.7.3　总体设计 230

8.7.4 MarketModel类的设计 230

8.7.5 MarketModel类的实现 231

8.7.6 Cashier类的设计 232

8.7.7 Cashier类的实现 233

8.7.8 Customer类的设计 234

8.7.9 Customer类的实现 234

8.8 优先队列 236

8.9.2 分析 237

8.9.1 要求 237

8.9　案例分析2：急诊室调度 237

8.9.3　推荐界面 238

第9章　列表 240

9.1 列表概述 240

9.2 列表原型 241

9.3 列表的使用 244

9.4　列表原型的实现 247

9.4.1　静态数组实现 247

9.4.2　双向链表实现 250

9.4.3 两种实现的时间和空间分析 256

9.5　列表的3个应用 258

9.5.1　堆存储管理 258

9.5.2　对磁盘文件的组织 259

9.5.3　其他ADT实现 260

9.6　专门版本的接口 261

9.7　专门版本的实现 263

9.8　案例分析：维护任务列表（to-do列表） 267

9.8.1 要求 268

9.8.2 分析 268

9.8.3　设计 269

9.8.4　实现 270

第10章　递归、查找、排序和回溯 279

10.1 递归概述 279

10.1.1 实现递归 280

10.1.2　跟踪递归调用 281

10.1.3　编写递归方法的准则 282

10.1.4　递归方法的运行支持 283

10.1.5　两种递归方法的分析 284

10.1.6　两种递归方法的空间分析 286

10.2　递归和查找 287

10.2.1　数组的线性查找 287

10.2.2　数组的二分查找 288

10.3　递归和排序 290

10.3.1　快速排序 291

10.3.2　归并排序 295

10.4　递归和回溯 299

10.5　采用递归的理由 301

10.5.1 消除递归 302

10.5.2　尾递归 303

10.6.1 要求 304

10.6.2 分析 304

10.6　案例分析1：迷宫解决方案 304

10.6.3 类 306

10.6.4　MazeView的实现 306

10.6.5　MazeModel的实现 308

10.7　递归下降及其编程语言 310

10.7.1 语法介绍 310

10.7.2　识别、解析和解释语言中的语句 312

10.7.3　词汇分析和扫描器 312

10.7.4　解析策略 313

10.8　案例分析2：递归下降解析器 313

10.8.1 要求 313

10.8.2　分析 314

10.8.3　推荐的用户界面 314

10.8.4　Parser的实现 315

11.1　树的概述 319

第11章　树 319

11.1.1　树的讨论 321

11.1.2　普通树和二叉树的正式定义 322

11.2　树的表示 322

11.2.1　链表表示 322

11.2.2 完全二叉树的数组表示 324

11.3 二叉树的操作 325

11.3.1 二叉树的原型 326

11.3.2 BinaryTreePT的测试程序 328

11.3.3 BinaryTreePT类的实现 330

11.4　案例分析1：解析表达式树 335

11.4.1　要求 335

11.4.2　用户界面 336

11.4.3　ExpressionTree类的分析和设计 336

11.4.4　Parser类的分析、设计和实现 337

11.5　普通树操作 339

11.5.1　树的接口 339

11.5.2　TreeIterator接口 342

11.6　普通树类的实现（可选内容） 345

11.6.1 实现中的类职责 345

11.6.2　AbstractTree类的设计和实现 346

11.6.3　LinkedTree类的设计和实现 349

11.6.4　树迭代器的设计和实现 351

11.7　案例分析2：技能数据库 353

11.7.1　要求 353

11.7.2　分析 354

11.7.3　模型类的设计和实现 355

11.7.4　视图类的设计和实现 358

12.1.1 二叉树的形状 361

第12章　特殊树 361

12.1 堆 361

12.1.2　可比对象 362

12.1.3　Heap接口 362

12.1.4　Heap实现 363

12.1.5　堆排序的实现 364

12.1.6　add方法和pop方法的实现 365

12.1.7　分析堆排序 367

12.1.8　迭代器的实现 367

12.1.9　使用堆实现优先队列 368

12.2 二叉搜索树 372

12.2.1 排序集合抽象数据类型及其接口 372

12.2.2　排序集合抽象数据类型的实现 373

12.2.3 二分查找 374

12.2.4 二叉搜索树的实现 375

12.2.5　分析二叉搜索树 378

12.3 “更好的”二叉搜索树（可选内容） 379

12.3.1　2-3树 379

12.3.2　AVL树 380

第13章　无序集合：集、映射和包 385

13.1　集、映射和包概述 385

13.1.1　集 385

13.1.2　映射 386

13.1.3 包 387

13.1.4　无序集合的迭代器 387

13.1.5 一个简短的例子 387

13.2　实现的考虑事项 389

13.2.1　散列 389

13.2.3　其他散列策略 390

13.2.2　散列链表方法的分析 390

13.3　映射原型类 391

13.3.1　HashMapPT类的接口 391

13.3.2　HashMapPT类的设计 392

13.4　集原型类 396

13.4.1　HashSetPT类的接口 396

13.4.2　设计和实现 397

13.5　包原型类 399

13.5.1　HashBagPT类的接口 399

13.5.2　设计和实现 400

13.6　Java集合框架中的Map类和Set类 401

13.6.1　映射 401

13.6.2　Set接口 404

13.7.1　Bag接口 405

13.7　将Bag ADT添加到集合框架 405

13.7.2　Bag实现 406

13.8　案例分析1：文件索引系统 409

13.8.1 要求 409

13.8.2 分析 409

13.8.3　设计和实现 410

13.9　案例分析2：信贷批准系统 417

13.9.1 要求 417

13.9.2　分析 417

13.9.3 类 417

13.9.4　设计和实现 418

第14章　图 426

14.1 概述 426

14.2 术语 427

14.3.1　邻接矩阵 429

14.3 图的表示 429

14.3.2　邻接表 430

14.3.3　两种表示的分析 431

14.3.4　运行时间的进一步分析 431

14.4 图的遍历 432

14.4.1　连通图的一般遍历算法 432

14.4.2　深度优先遍历和广度优先遍历 432

14.4.3 图的分量 434

14.5 图中的树 435

14.5.1 生成树和生成森林 435

14.5.2　最小生成树 435

14.5.3　最小生成树算法 435

14.6　拓扑排序 437

14.7.1　Dijkstra算法 438

14.7　最短路径问题 438

14.7.2　初始化 439

14.7.3　计算 439

14.7.4　分析 440

14.8　图原型 440

14.8.1 使用图原型的例子 440

14.8.2　LinkedGraphPT类 441

14.8.3 LinkedVertexPT类 448

14.8.4　LinkedEdgePT类 451

14.9 一个专门的图实现（可选内容） 453

14.9.1　Graph接口 454

14.9.2　权值 456

14.9.3 实现 457

14.9.4　关于性能的提示 460

14.10.1 要求 461

14.10.2　分析 461

14.10.3　GraphDemoView类 461

14.10　案例分析：测试图的算法 461

14.10.4　GraphDemoModel类 466

第15章　多线程、网络和客户端／服务器编程 470

15.1　线程和进程 470

15.1.1　线程 471

15.1.2　休眠线程 472

15.1.3　生产者、消费者和同步 474

15.2　网络、服务器和客户端 479

15.2.1　IP地址 479

15.2.3　套接字和一个日期／时间客户端程序 481

15.2.2　端口、服务器和客户端 481

15.2.4　服务器套接字和一个日期／时间服务器端程序 483

15.2.5　客户端和服务器端之间的双向会话 485

15.2.6　使服务器处理多个客户端 485

15.2.7　使用服务器守护进程 486

15.2.8　使用客户端处理器 489

15.2.9　模型-视图-控制器模式 491

15.3　案例分析：校园电话目录 491

15.3.1 要求 491

15.3.2　分析 492

15.3.3 设计 493

15.3.4　实现 493

A.1 保留字 499

A.2　数据类型 499

附录A　Java语言特性回顾 499

A.3　变量、作用域和生命周期 501

A.4 表达式 502

A.5　控制语句 503

A.5.1 复合语句 503

A.5.2　if和if-else语句 503

A.5.3　while和do-while语句 504

A.5.4　for语句 504

A.5.5　switch语句 504

A.6　混合模式运算和强制类型转换 505

A.7　字符串 505

A.8　数组 507

A.9　方法和参数 508

A.10　引用类型 509

A.13　接口 510

A.11 包装器类 510

A.12　类 510

A.14　适配器 511

A.15　异常 511

A.16　程序包 512

A.17　文本文件 513

附录B　层次结构、接口及类 516

B.1 层次结构 516

B.2　接口 516

B.3 类 516

附录C　安装指令 518

C.1　使用JDK 518

C.2　使用JGrasp 519

术语表 520