数据结构和Java集合框架PDF电子书下载

第1章　Java语言的重要特性 1

1.1 类 1

1.1.1　方法描述 2

1.1.2　数据抽象 4

1.1.3　Employee类 6

1.1.4　局部变量和字段 8

1.1.5　构造函数 8

1.1.6　实例变量和静态变量 9

1.1.7　可见性修饰符 10

1.1.8　图形用户接口 10

1.1.9　Company类 11

1.1.10　继承 12

1.1.11　可见性修饰符protected 13

1.1.12　继承和构造函数 15

1.1.13　多态性（Polymorphism） 19

1.1.14　信息隐藏 21

1.1.15　异常处理 22

1.1.16　异常传送 24

1.2 小结 26

1.3 练习 27

第2章　接口和集合类 31

2.1　抽象方法和抽象类 31

2.2　接口 33

2.3 数组 36

2.4　集合类 38

2.5　集合类的存储结构 39

2.5.1 链接结构 39

2.5.2　LinkedCollection类 39

2.5.3　LinkedCollection类中的字段和方法定义 42

2.5.4　迭代器 45

2.5.5　数据结构和Java Collections Framework 47

2.7　练习 48

2.6 小结 48

第3章　软件工程介绍 51

3.1　软件开发生命期 51

3.2 问题分析 52

3.3　程序设计 53

3.3.1 方法描述和字段 54

3.3.2　依赖性图表 55

3.4　程序实现 57

3.4.1 方法验证 57

3.4.2　修正是否可行 58

3.4.3　评估方法的效率 58

3.4.4　大O符号 59

3.4.5　快速获取大O估计时间 61

3.4.6　平衡 64

3.4.7　运行时分析 65

3.4.8　Random类 66

3.5　程序维护 67

3.6　小结 68

3.7　练习 68

第4章　递归 73

4.1 绪论 73

4.2　阶乘 74

4.3　十进制转换成二进制 77

4.4　汉诺塔 80

4.5 回溯 88

4.6　二叉树搜索 96

4.7 间接递归 105

4.8　递归的开销 105

4.9　小结 106

4.10　练习 107

第5章　数组列表 119

5.1　List接口 119

5.2　ArrayList类 120

5.2.1　ArrayList类的方法描述 122

5.2.2　ArrayList类标题 127

5.2.3　ArrayList类中的字段 128

5.2.4　ArrayList对象可串行化性 128

5.2.5　ArrayList对象的可克隆性 129

5.3 实现ArrayList类 130

5.3.1　定义add方法 131

5.3.2　分摊时间 133

5.3.3　clone方法和copy构造函数 134

5.3.4　Fail-Fast迭代器 135

5.4　高精度算法 136

5.4.1　设计VeryLongInt类 137

5.4.2　实现VeryLongInt类 138

5.6　小结 141

5.7　练习 141

5.5　VECTOR类 141

第6章　链表 149

6.1　LinkedList类 149

6.1.1 比较LinkedList类和ArrayList类 151

6.1.2　LinkList迭代器 153

6.1.3　LinkedList类的字段和实现方法 158

6.1.4　ListItr类的字段和实现 164

6.1.5　LinkedList类的其他设计和实现方法 167

6.1.6　循环链表 169

6.2　行编辑器 171

6.2.1　设计Editor类 174

6.2.2　实现Editor类 176

6.2.3　Editor类方法的大O分析 179

6.2.4　EditorDirver类 179

6.3 小结 181

6.4　练习 181

7.1 队列 187

第7章　队列和堆栈 187

7.1.1　Queue类的设计与实现 188

7.1.2　Queue类可选择的设计和实现 190

7.2　计算机模拟 194

7.3　应用：模拟洗车 195

7.3.1　CarWash类的设计 196

7.3.2　CarWash类的实现 197

7.3.3　CarWash方法分析 200

7.3.4　随机到达时间 200

7.4　堆栈 201

7.4.1　Stack类的设计和实现 202

7.4.2　Java集合框架中的Stack类 202

7.4.3　Stack类可选的设计和实现 203

7.5　应用：如何编译实现递归 203

7.6　应用：中缀表达式到后缀表达式的转换 207

7.6.1　后缀表示 208

7.6.2　转换矩阵 210

7.6.3　标记 211

7.6.4　前缀表达式 212

7.7 小结 214

7.8　练习 215

第8章　二叉树和二叉搜索树 225

8.1　二叉树的定义和属性 226

8.1.1　二叉树定理 232

8.1.2　外部路径长度 234

8.1.3　对二叉树的遍历 235

8.2　二叉搜索树 240

8.2.1 BinSearchTree类 241

8.2.2　BinSearchTree类的字段及内置类 243

8.2.3　BinSearchTree类的实现 244

8.2.4　remove方法 249

8.2.5　TreeIterator类 256

8.3　小结 258

8.4　练习 259

第9章　平衡二叉搜索树 265

9.1　二叉搜索树的一个问题 265

9.2　旋转 266

9.3　AVL树 270

9.3.1　AVL树的高度 271

9.3.2　AVLTree类 272

9.3.3　fixAfterInsertion方法 274

9.3.4　add方法的正确性 282

9.4 RED-BLACK树 284

9.5　小结 290

9.6　练习 290

第10章　TreeMap和TreeSet 295

10.1　TreeMap类 295

10.1.1　TreeMap类的方法介绍 296

10.1.2　TreeMap类的字段 298

10.1.3　Comparator接口和Comparable接口 299

10.1.4　Entry类 300

10.1.5　TreeMap类的实现 300

10.1.6　fixAfterInsertion方法 302

10.1.7　Insertion的三种情况 303

10.1.8　TreeMap类的其他方法 307

10.1.9　fixAfterDeletion方法 311

10.1.10　entrySet方法 318

10.2　TREEMAP对象：一个简单的辞典 318

10.2.1　Thesaurus类的设计和实现 319

10.2.2　ThesaurusDriver类的设计和实现 320

10.3　TreeSet类 322

10.4　一个简单的拼写检查器 326

10.4.1　SpellChecker类的设计和实现 327

10.4.2 SpellCheckerDriver类的设计与实现 328

10.5 小结 330

10.6　练习 331

第11章　优先级队列 337

11.1 简介 337

11.2　PriorityQueue接口的定义 338

11.3　PriorityQueue接口的实现 339

11.3.1　Heap类 340

11.3.2　Heap类中的字段 344

11.3.3　Heap类的实现 344

11.3.4　percolateUp方法 345

11.3.5　percolateDown方法 349

11.4　应用：Huffman编码 351

11.4.1　Huffman树 353

11.4.2　贪婪算法 356

11.4.3　Huffman类 356

11.5　小结 361

11.6　练习 362

第12章　排序 367

12.1 简介 367

12.2　插入排序 368

12.3　排序能有多快 370

12.4　快速排序法 371

12.4.1　归并排序 372

12.4.2　树排序 377

12.4.3　堆排序 379

12.4.4　快速排序 383

12.5　小结 391

12.6　练习 391

第13章　检索和散列类 401

13.1　检索的分析框架 401

13.2　检索概述 402

13.2.1　顺序检索 402

13.2.3　red-black树检索 403

13.2.2　二分法检索 403

13.3　HashMap类 404

13.3.1　HashMap类的方法描述 404

13.3.2　HashMap类的字段 406

13.3.3　散列设计 406

13.3.4　hashCode方法 409

13.3.5　均匀散列假设 410

13.3.6　链 411

13.3.7　HashMap类的实现 412

13.3.8　链式散列分析 416

13.3.9　HashIterator类 418

13.4　HashSet类 419

13.5　开放地址散列 419

13.5.1　remove方法 421

13.5.2　主簇 425

13.5.3　双散列 426

13.5.4　开放地址散列分析 429

13.6　小结 432

13.7　练习 432

第14章　图、树和网络 437

14.1　无向图 437

14.2　有向图 440

14.3　树 441

14.4 网络 442

14.5 图的算法 443

14.5.1　迭代器 444

14.5.2　连通性 449

14.5.3　产生最小生成树 450

14.5.4　在网络中寻找最短路径 454

14.6　开发Network类 457

14.6.1　Network类的方法描述 458

14.6.2　Network类的字段 460

14.6.3　实现Network类 462

14.6.4　Network类的另一种设计和实现 469

14.7　突破网络 471

14.8　小结 473

14.9　练习 474

附录A　数学背景知识 481

A.1 简介 481

A.2　函数和数列 481

A.3 求和与求积 482

A.4　对数 483

A.5　数学归纳法 485

A.6　练习 492

附录B　GUI和GUIListener类 495

B.1 简介 495

B.2　线程 496

B.3 实现Process接口 497

B.4　GUI类 499

B.4.1　GUI构造函数 500

B.4.2　GUI类中的其他方法 501

B.5　GUIListener类 502

B.6　综合应用 503

附录C　Java集合框架 505

C.1 简介 505

C.2　Collection接口 505

C.3　List接口 507

C.4　ListIterator接口 509

C.5　Set接口 511

C.6　Map接口 513

C.7　ArrayList类 516

C.8　LinkedList类 527

C.9　TreeSet类 543

C.10　TreeMap类 555

C.11　HashSet类 567

C.12　HashMap类 575