数据结构与问题求解:Java版

第一部分 java教程

第1章 java简介 2

1.1 通用环境 2

1.2 第一个程序 3

1.3 基本数据类型 4

1.4 基本运算符 5

1.5 条件语句 7

1.6 方法 11

1.7 小结 13

1.8 名词解释 13

1.9 常见错误 14

1.10 网上资源 14

习题 15

参考文献 16

第2章 引用类型 17

2.1 什么是引用 17

2.2 对象和引用的基本概念 18

2.3 字符串 21

2.4 数组 23

2.5 异常处理 30

.2.6 输入和输出 32

2.7 小结 35

2.8 名词解释 37

2.9 常见错误 38

2.10 网上资源 38

习题 38

参考文献 39

第3章 对象与类 40

3.1 何为面向对象编程 40

3.2 一个简单的例子 41

3.3 javadoc 42

3.4 基本方法 43

3.5 附加结构 46

3.6 包 49

3.7 设计模式：复合 52

3.8 小结 52

3.9 名词解释 53

3.10 常见错误 54

3.11 网上资源 55

习题 55

参考文献 57

第4章 继承 58

4.1 什么是继承 58

4.2 层次结构设计 68

4.3 多重继承 71

4.4 接口 72

4.5 java中的基础继承体系 74

4.6 通用实现组件 77

4.7 函数（函数对象） 82

4.8 动态绑定细节 87

4.9 小结 89

4.10 名词解释 90

4.11 常见错误 91

4.12 网上资源 91

习题 92

参考文献 95

第二部分 算法与程序构建

第5章 算法分析 98

5.1 什么是算法分析 98

5.2 算法运行时间举例 100

5.3 最大连续子序列之和的问题 101

5.4 通用big-oh规则 106

5.5 对数 108

5.6 静态搜索问题 109

5.7 检验算法分析 112

5.8 big-oh分析法的限制 113

5.9 小结 113

5.10 名词解释 113

5.11 常见错误 114

5.12 网上资源 114

习题 114

参考文献 118

第6章 应用程序接口集 119

6.1 简介 119

6.2 迭代器模式 120

6.3 应用程序接口集：容器和迭代器 123

6.4 通用算法 127

6.5 表接口 131

6.6 栈和队列 134

6.7 集合 137

6.8 映射 142

6.9 优先级队列 145

6.10 小结 148

6.11 名词解释 148

6.12 常见错误 149

6.13 网上资源 149

习题 150

参考文献 151

第7章 递归 152

7.1 什么是递归 152

7.2 背景：通过数学归纳法证明 153

7.3 基本递归 154

7.4 数值应用 163

7.5 分而治之算法 168

7.6 动态规划 174

7.7 回溯 177

7.8 小结 180

7.9 名词解释 181

7.10 常见错误 181

7.11 网上资源 181

习题 182

参考文献 184

第8章 排序算法 185

8.1 排序算法为什么重要 185

8.2 基础知识 186

8.3 插入排序算法和其他简单排序算法的分析 186

8.4 希尔排序 188

8.5 归并排序 190

8.6 快速排序 192

8.7 快速选择 202

8.8 排序的下限 203

8.9 小结 204

8.10 名词解释 204

8.11 常见错误 204

8.12 网上资源 205

习题 205

参考文献 208

第9章 随机化处理 209

9.1 为什么需要随机数字 209

9.2 随机数字发生器 209

9.3 非均匀分布的随机数字 213

9.4 产生随机排序 214

9.5 随机化算法 215

9.6 随机化初试 217

9.7 小结 219

9.8 名词解释 219

9.9 常见错误 220

9.10 网上资源 220

习题 220

参考文献 221

第三部分 应用

第10章 趣味游戏 224

10.1 迷宫索字游戏 224

10.2 tic-tac-toe游戏 230

10.3 小结 236

10.4 名词解释 236

10.5 常见错误 236

10.6 网上资源 236

习题 236

参考文献 238

第11章 栈和编译程序 239

11.1 平衡符校验器 239

11.2 一个简单的计算器 248

11.3 小结 258

11.4 名词解释 258

11.5 常见错误 259

11.6 网上资源 259

习题 259

参考文献 260

第12章 公用程序 261

12.1 文件压缩 261

12.2 交叉引用发生器 276

12.3 小结 279

12.4 名词解释 279

12.5 常见错误 280

12.6 网上资源 280

习题 280

参考文献 282

第13章 仿真 283

13.1 josephus问题 283

13.2 事件驱动仿真 286

13.3 小结 292

13.4 名词解释 293

13.5 常见错误 293

13.6 网上资源 293

习题 293

第14章 图形和路径 295

14.1 定义 295

14.2 无权值最短路径问题 304

14.3 正权值最短路径问题 307

14.4 负权值最短路径问题 311

14.5 无环图中的路径问题 313

14.6 小结 318

14.7 名词解释 318

14.8 常见错误 319

14.9 网上资源 319

习题 319

参考文献 321

第四部分 实现

第15章 内部类和数组表的实现 324

15.1 迭代和嵌套类 324

15.2 迭代类和内部类 326

15.3 抽象集（abstractcollection）类 328

15.4 有迭代类的 arraylist的实现 330

15.5 小结 334

15.6 名词解释 334

15.7 常见错误 335

15.8 网络资源 335

习题 335

第16章 堆栈和队列 337

16.1 动态数组的实现 337

16.2 链表的实现 345

16.3 两种方法的对比 350

16.4 java.util.stack类 350

16.5 双端队列 351

16.6 小结 352

16.7 名词解释 352

16.8 常见错误 352

16.9 网上资源 352

习题 353

第17章 链表 354

17.1 基本概念 354

17.2 java 实现 357

17.3 双向链表和循环链表 361

17.4 排序链表 363

17.5 api类库集中的linkedlist 类的实现 364

17.6 小结 373

17.7 名词解释 373

17.8 常见错误 373

17.9 网上资源 373

习题 374

第18章 树 376

18.1 通用树 376

18.2 二叉树 381

18.3 递归和树 385

18.4 树的遍历：iterator类 387

18.5 小结 396

18.6 名词解释 396

18.7 常见错误 397

18.8 网上资源 397

习题 397

第19章 二叉查找树 400

19.1 基本思想 400

19.2 静态顺序 407

19.3 二叉查找树的操作分析 410

19.4 avl树 412

19.5 红-黑树 418

19.6 aa-树 427

19.7 api类库中的集treeset和treemap类的实现 434

19.8 b-树 446

19.9 小结 449

19.10 名词解释 450

19.11 常见错误 451

19.12 网上资源 451

习题 451

参考文献 453

第20章 哈希表 455

20.1 基本思想 455

20.2 哈希函数 456

20.3 线性探测 457

20.4 二次探测 460

20.5 单链哈希法 470

20.6 哈希表与二叉查找树 470

20.7 哈希法的应用 471

20.8 小结 471

20.9 名词解释 471

20.10 常见错误 472

20.11 网上资源 472

习题 472

参考文献 474

第21章 优先队列：二分堆 475

21.1 基本思想 475

21.2 基本操作的实现 479

21.3 buildheap操作：线性时间堆结构 482

21.4 高级操作：decreasekey和merge 484

21.5 内部排序：堆排序 485

21.6 外部排序 487

21.7 小结 491

21.8 名词解释 491

21.9 常见错误 492

21.10 网上资源 492

习题 492

参考文献 494

第五部分 高级数据结构

第22章 splay树 498

22.1 自动调整和分步偿付 498

22.2 基本的自下而上的splay树 500

22.3 基本的splay树操作 501

22.4 自底而上的splay树的分析 502

22.5 自顶而下的splay树的分析 505

22.6 自顶而下splay树的实现 508

22.7 splay树和其他查找树的比较 512

22.8 小结 512

22.9 名词解释 512

22.10 常见错误 512

22.11 网上资源 512

习题 513

参考文献 513

第23章 归并优先级队列 515

23.1 非对称堆 515

23.2 对称堆 518

23.3 小结 526

23.4 名词解释 527

23.5 常见错误 527

23.6 网上资源 527

习题 527

参考文献 528

第24章 不相交集合类 529

24.1 等价关系 529

24.2 动态等价及应用 529

24.3 快速查找算法 536

24.4 快速合并算法 536

24.5 java实现 539

24.6 根据层合并和路径压缩的最差情况 541

24.7 小结 545

24.8 名词解释 546

24.9 常见错误 546

24.10 网上资源 546

习题 546

参考文献 548

附录a 运算符 550

附录b 图形用户界面 551

附录 c 位运算符 569