数据结构 Java语言描述 原书第3版

第1章　软件开发周期 1

1.1　规格说明、设计和实现 2

1.2　运行时间分析 10

1.3　测试和调试 17

本章小结 22

自测练习参考答案 23

第2章　Java类和信息隐藏 24

2.1　类及其成员 24

2.2　类的使用 32

2.3　包 38

2.4　参数、equals方法和clone 41

本章小结 58

自测练习参考答案 58

程序设计项目 59

第3章　集合类 64

3.1　Java数组简介 64

3.2　整数包的ADT 70

3.3　程序设计项目：序列ADT 90

3.4　程序设计项目：多项式 99

本章小结 100

自测练习参考答案 101

程序设计项目 103

第4章　链表 106

4.1　链表基础 106

4.2　操作结点的方法 108

4.3　操作整个链表 117

4.4　使用链表实现的包ADT 132

4.5　程序设计项目：使用链表实现的序列ADT 143

4.6　复杂链表 148

本章小结 150

自测练习参考答案 150

程序设计项目 152

第5章　通用程序设计 155

5.1 Java的Object类型 155

5.2 Object方法和通用方法 159

5.3　通用类 161

5.4　通用结点 174

5.5　接口和迭代器 176

5.6　实现Iterable接口的通用包类（选读） 182

5.7　Java中Collection和Map接口简介（选读） 184

本章小结 190

自测练习参考答案 191

程序设计项目 193

第6章　栈 194

6.1　栈简介 194

6.2　栈的应用 197

6.3　栈ADT的实现 206

6.4　更复杂的栈应用 213

本章小结 219

自测练习参考答案 219

程序设计项目 219

第7章 队列 222

7.1　队列简介 222

7.2　队列的应用 225

7.3　Queue类的实现 236

7.4　优先队列 247

本章小结 250

自测练习参考答案 250

程序设计项目 251

第8章　递归思想 254

8.1　递归方法 254

8.2　递归的研究：分形和迷宫 261

8.3　递归的推导 273

本章小结 278

自测练习参考答案 278

程序设计项目 279

第9章　树 283

9.1　树的简介 283

9.2　树的表示方法 286

9.3　二叉树结点类 289

9.4　树的遍历 302

9.5　二叉查找树 312

本章小结 322

自测练习参考答案 323

程序设计项目 324

第10章　树项目 327

10.1　堆 327

10.2　B树 331

10.3　Java对树的支持 346

10.4　树、日志和时间复杂度分析 350

本章小结 354

自测练习参考答案 354

程序设计项目 355

第11章　查找 356

11.1　顺序查找和二分查找 356

11.2　开型寻址散列 363

11.3　使用Java的Hashtable类 374

11.4　链式散列 375

11.5　散列的耗时分析 377

本章小结 379

自测练习参考答案 379

程序设计项目 380

第12章　排序 382

12.1　二次排序算法 382

12.2　递归排序算法 391

12.3　一个使用堆的O（n log n）算法 403

本章小结 409

自测练习参考答案 410

程序设计项目 410

第13章 使用扩展类实现软件重用 412

13.1　扩展类 412

13.2　通用类型参数和继承 419

13.3　模拟生态系统 420

13.4　抽象类和Game类 434

本章小结 442

进阶阅读 442

自测练习参考答案 443

程序设计项目 444

第14章 图 445

14.1 图的定义 445

14.2　图的实现 449

14.3　图遍历 458

14.4　路径算法 464

本章小结 472

自测练习参考答案 472

程序设计项目 473

附录A Java的基本类型和算术溢出 474

附录B Java输入和输出 476

附录C　抛出和捕获Java异常 479

附录D　ArrayList、Vector、Hashtable和HashMap类 482

附录E　用于链表的结点类 485

附录F　一个用于包对象的类 491

附录G　深入大O表示法 496

附录H　Javadoc 498

附录I　用于交互式测试的Applet 503