数据结构与算法（Java版）

第I部分 面向对象程序设计

第1章 封装

1.1 软件开发 2

1.1.1 良好的程序 2

1.1.2 封装 3

1.1.3 软件开发周期 5

习题 6

1.2 类和对象 7

1.2.1 类 7

1.2.2 对象、字段和方法 8

1.2.3 构造函数 9

1.2.4 访问器、修改器和this 11

1.2.5 静态与非静态 12

1.2.6 完成Die类 13

习题 14

1.3 使用对象 14

1.3.1 Beetle类 14

1.3.2 toString()方法 15

1.3.3 BeetleGame类 19

习题 24

1.4 小结 24

1.5 术语 25

1.6 复习题 26

1.7 项目 27

第2章 多态性

2.1 引用类型 29

2.1.1 null 30

2.1.2 引用和相等性 30

2.1.3 多态类型对象 31

2.1.4 基本类型和包装器 33

2.1.5 String 33

习题 34

2.2 数组 34

2.2.1 声明、分配和初始化 34

2.2.2 多维数组 35

2.2.3 示例：Domineering 37

习题 42

2.3 接口 43

习题 47

2.4 重载 47

习题 48

2.5 小结 48

2.6 术语 49

2.7 复习题 50

2.8 项目 50

第3章 继承

3.1 扩展类 53

3.1.1 多态性和继承 55

3.1.2 继承链 57

3.1.3 is-a和has-a 58

习题 60

3.2 Object类 61

3.2.1 Object类的方法 61

3.2.2 隐式构造函数 62

习题 62

3.3 包和访问级别 63

访问级别 64

习题 65

3.4 小结 65

3.5 术语 66

3.6 复习题 66

3.7 项目 66

第Ⅱ部分 线 性 结 构

第4章 栈和队列

4.1 Stack接口 70

4.1.1 泛型 71

4.1.2 示例：Idiot's Delight 72

习题 77

4.2 调用栈 78

习题 80

4.3 异常 80

习题 86

4.4 Queue接口 86

习题 91

4.5 小结 91

4.6 术语 91

4.7 复习题 92

4.8 项目 93

第5章 基于数组的结构

5.1 收缩和加长数组 95

5.1.1 Card类 96

5.1.2 收缩数组 97

5.1.3 加长数组 100

习题 101

5.2 实现栈和队列 101

5.2.1 ArrayStack类 101

5.2.2 ArrayQueue类 103

习题 105

5.3 List接口 106

5.3.1 接口 106

5.3.2 ArrayList类 107

习题 110

5.4 迭代器 111

5.4.1 Iterator接口 111

5.4.2 Iterable接口 112

5.4.3 ArrayIterator类 112

5.4.4 示例：Go Fish 114

习题 120

5.5 初识Java集合框架 121

抽象类 121

习题 122

5.6 小结 123

5.7 术语 123

5.8 复习题 123

5.9 项目 124

第6章 链表结构

6.1 表节点 125

习题 128

6.2 栈和队列 128

6.2.1 LinkedStack类 128

6.2.2 LinkedQueue类 131

习题 133

6.3 LinkedList类 134

6.3.1 Predecessor接口 136

6.3.2 两指算法 138

6.3.3 ListIterator类 139

习题 140

6.4 再论Java集合框架 141

习题 142

6.5 小结 142

6.6 术语 142

6.7 复习题 143

6.8 项目 143

第Ⅲ部分 算法

第7章 算法分析

7.1 计时 146

习题 148

7.2 渐近表示法 148

习题 152

7.3 统计步骤数 153

习题 157

7.4 最好、最坏和平均情况 157

习题 158

7.5 平摊分析 159

习题 160

7.6 小结 160

7.7 术语 161

7.8 复习题 161

7.9 项目 162

第8章 查找和排序

8.1 线性查找 163

习题 164

8.2 折半查找 164

8.2.1 折半查找分析 165

8.2.2 假定n是2的幂 166

习题 167

8.3 插入排序 167

习题 169

8.4 Comparable接口 170

习题 173

8.5 排序链表 173

习题 174

8.6 小结 174

8.7 术语 175

8.8 复习题 175

8.9 项目 176

第9章 递归

9.1 递归地思考 177

习题 183

9.2 分析递归算法 183

习题 186

9.3 归并排序 186

归并排序分析 189

习题 189

9.4 快速排序 190

快速排序分析 192

习题 193

9.5 避免递归 193

9.5.1 尾部递归 194

9.5.2 动态规划 195

习题 197

9.6 小结 197

9.7 术语 198

9.8 复习题 198

9.9 项目 200

第Ⅳ部分 树和集合

第10章 树

10.1 二叉树 202

10.1.1 有关树的术语 203

10.1.2 实现二叉树 205

习题 208

10.2 树的遍历 210

习题 213

10.3 广义树 213

10.3.1 表示广义树 214

10.3.2 示例：智能的Tic Tac Toe玩家 215

习题 221

10.4 小结 221

10.5 术语 221

10.6 复习题 223

10.7 项目 223

第11章 集合

11.1 Set接口 224

习题 229

11.2 有序表 230

11.2.1 查找 232

11.2.2 插入 233

11.2.3 删除 233

习题 234

11.3 二叉查找树 234

11.3.1 查找 235

11.3.2 插入 236

11.3.3 删除 238

习题 241

11.4 散列表 242

11.4.1 直接定址法 242

11.4.2 散列函数和散列码 244

11.4.3 冲突解决方法 245

11.4.4 查找 248

11.4.5 插入 249

11.4.6 删除 250

习题 250

11.5 再论Java集合框架 251

映射 252

习题 252

11.6 小结 253

11.7 术语 253

11.8 复习题 254

11.9 项目 255

第Ⅴ部分 高 级 主 题

第12章 高级线性结构

12.1 位向量 258

BitSet 264

习题 264

12.2 稀疏数组 265

习题 267

12.3 多维数组的连续表示法 267

习题 271

12.4 高级查找和排序 271

12.4.1 插值查找 271

12.4.2 比较排序的下界 273

12.4.3 桶排序 273

习题 275

12.5 小结 275

12.6 术语 276

12.7 复习题 276

12.8 项目 276

第13章 字符串

13.1 String和StringBuilder 277

习题 280

13.2 字符串匹配 280

13.2.1 朴素的字符串匹配 282

13.2.2 RK指纹识别算法 283

13.2.3 KMP跳跃算法 285

习题 289

13.3 小结 289

13.4 术语 290

13.5 复习题 290

13.6 项目 291

第14章 高级主题

14.1 堆 292

14.1.1 优先级队列 294

14.1.2 堆排序 296

14.1.3 Java的PriorityQueue类 297

习题 298

14.2 不相交集合簇 298

14.2.1 按高度合并 300

14.2.2 路径压缩 301

习题 302

14.3 数字查找树 302

习题 308

14.4 红黑树 308

14.4.1 红黑树的性质 308

14.4.2 查找 309

14.4.3 插入 309

14.4.4 删除 311

14.4.5 实现 312

习题 320

14.5 小结 320

14.6 术语 321

14.7 复习题 321

14.8 项目 321

第15章 图

15.1 术语 323

习题 327

15.2 表示法 327

习题 332

15.3 图的遍历 332

习题 334

15.4 拓扑排序 335

习题 339

15.5 最短路径 339

15.5.1 Dijkstra的单源点算法 340

15.5.2 Floyd-Warshall所有顶点对算法 341

习题 342

15.6 最小生成树 342

习题 346

15.7 小结 346

15.8 术语 346

15.9 复习题 348

15.10 项目 348

第16章 内存管理

16.1 显式内存管理 350

16.1.1 自由表 352

16.1.2 使用节点池 356

习题 358

16.2 自动内存管理 358

16.2.1 引用计数 358

16.2.2 标记和清理无用单元收集 359

16.2.3 复制无用单元收集 359

习题 365

16.3 小结 366

16.4 术语 366

16.5 复习题 367

16.6 项目 367

第17章 输出到磁盘

17.1 与文件交互 368

17.1.1 文本文件 368

17.1.2 数据文件 372

习题 376

17.2 压缩 376

17.2.1 霍夫曼编码方式 376

17.2.2 Lempel-Ziv编码方式 381

习题 384

17.3 外部排序 384

习题 389

17.4 B树 389

17.4.1 查找 390

17.4.2 插入 390

17.4.3 删除 391

17.4.4 实现 392

习题 404

17.5 小结 405

17.6 术语 405

17.7 复习题 406

17.8 项目 406

第Ⅵ部分 附 录

附录A Java知识回顾

A.1 第一个程序 408

A.2 变量和类型 410

A.3 循环 412

A.4 与用户交互 414

A.5 分支 414

A.6 方法和中断 417

A.7 常量 418

A.8 运算符 420

A.9 调试 423

A.10 编码约定 424

附录B 统一建模语言

B.1 类图 428

B.2 实例图 431

附录C 求和公式

C.1 求和符号 433

C.2 常量求和 434

C.3 前n个整数之和 434

C.4 二等分与加倍之和 435

C.5 函数之和的上限 435

C.6 常数因子 436

附录D 进一步的阅读材料

D.1 数据结构和算法 437

D.2 Java 437

D.3 游戏 437