本书是为数据结构入门课程（通常课号是CS-2）而编写的教材。作者FrankCarrano和Walter Savitch在编写过程自始至终特别考虑到了Java与对象，为教师和学生提供了一种精心设计并经过教学实验的方式藉助Java讲授ADT和对象。本书独特的设计将内容组织为相对较短的章。这种方式使学习更容易，并留出了教学的机动性。本书教给学生如何使用线性表、词典、栈、伫列等等来组织数据。利用这些数据组织方式，学生们将学到算法设计的相关技术。书中的“编程提示”给读者额外的编程建议；大量的插图使讲解更形象生动；自测题贯穿各章，书末还给出了答案。本书适合作为数据结构的教学用书。

第1章Java类 1

1.1对象与类 1

1.2在Java类中使用方法 3

1.2.1引用与别名 4

1.2.2实参与形参 5

1.3定义Java类 6

1.3.1方法定义 7

1.3.2传递实参 9

1.3.3Name类的定义 12

1.3.4构造函式 13

1.3.5toString方法 15

1.3.6静态的域与方法 16

1.4包 17

第2章从已有类创建新类 23

2.1合成 23

2.2继承 27

2.2.1在构造函式中调用构造函式 30

2.2.2基类的私有域与私有方法 31

2.2.3方法的覆盖与重载 32

2.2.4保护访问 35

2.2.5多重继承 36

2.3类型兼容性与基类 36

2.3.1Object类 37

2.3.2抽象类与抽象方法 39

2.4多态性 40

第3章类的设计 50

3.1封装 50

3.2方法的说明 52

3.3Java接口 55

3.3.1编写接口 55

3.3.2实现接口 57

3.3.3作为数据类型的接口 58

3.3.4接口实现中的类型转换 58

3.3.5扩展接口 59

3.3.6接口中的符号常量 60

3.3.7接口与抽象类的比较 61

3.4类的选择 63

3.4.1类的确定 64

3.4.2CRC卡片 64

3.5类的复用 66

第4章线性表 70

4.1ADT线性表说明 70

4.2使用ADT线性表 78

4.3Java类库：List接口 82

4.4使用线性表如同使用自动售货机 82

第5章用数组实现线性表 87

5.1使用定长数组实现ADT线性表 87

5.1.1类比 87

5.1.2Java实现 89

5.2使用动态扩展数组实现ADT线性表 96

5.2.1扩展数组 97

5.2.2线性表新的实现 98

5.3使用向量实现ADT线性表 100

5.4用数组实现ADT线性表的优缺点 104

5.5Java类库 104

5.5.1ArrayList类 104

5.5.2Serializable接口 105

第6章用鍊表实现线性表 108

6.1鍊表 108

6.1.1创建一个鍊表 109

6.1.2创建另一个鍊表 111

6.1.3仍创建一个鍊表 113

6.2Node类 116

6.3使用鍊表实现ADT线性表 118

6.3.1线上性表的末端插入元素 119

6.3.2线上性表的指定位置插入元素 122

6.3.3私有方法getNodeAt 125

6.3.4方法remove 126

6.3.5方法replace 128

6.3.6方法getEntry 129

6.3.7方法contains 130

6.3.8其余方法 130

6.3.9使用具有设定与获取方法的Node类 131

6.4表尾引用 131

6.5用鍊表实现ADT线性表的优缺点 136

6.6Java类库：LinkedList类 136

第7章叠代器 139

7.1叠代器是什幺 139

7.1.1基本叠代器 140

7.1.2对ADT进行修改的叠代器方法 143

7.2内部叠代器的实现 145

7.3将叠代器本身实现为一个类 150

7.3.1外部叠代器 153

7.3.2内部类叠代器 154

第8章Java的叠代器接口 160

8.1Iterator接口 160

8.2实现Iterator接口 163

8.2.1基于鍊表实现 163

8.2.2基于数组实现 165

8.3ListIterator接口 168

8.4基于数组实现ListIterator接口 174

8.5Java类库：重温ArrayList和LinkedList 181

第9章算法的效率 184

9.1动机 184

9.2度量算法的效率 186

9.3形式化 192

9.4效率的图形表示 194

9.5ADT线性表不同实现的效率 198

9.5.1基于数组实现 198

9.5.2基于鍊表实现 199

9.5.3比较上述实现 201

第10章递归 206

10.1何谓递归 206

10.2跟蹤递归方法 211

10.3有返回值的递归方法 213

10.4递归处理数组 216

10.5递归处理鍊表 218

10.6递归方法的时间效率 220

10.6.1countDown的时间效率 220

10.6.2计算xn的时间效率 222

10.7困难问题的简单解法 223

10.8简单问题的拙劣解法 228

10.9尾递归 230

10.10协同递归 232

第11章排序入门 238

11.1选择排序 239

11.1.1叠代选择排序 240

11.1.2递归选择排序 242

11.1.3选择排序的效率 243

11.2插入排序 243

11.2.1叠代插入排序 244

11.2.2递归插入排序 246

11.2.3插入排序的效率 248

11.2.4鍊表的插入排序 248

11.3希尔排序 251

11.3.1Java代码 253

11.3.2希尔排序的效率 254

11.4算法比较 255

第12章更快的排序算法 259

12.1归併排序 259

12.1.1数组的归併 259

12.1.2递归归併排序 260

12.1.3归併排序的效率 262

12.1.4叠代归併排序 264

12.1.5Java类库中的归併排序 264

12.2快速排序 265

12.2.1快速排序的效率 265

12.2.2创建划分 266

12.2.3快速排序的Java代码 268

12.2.4Java类库中的快速排序 272

12.3基数排序 272

12.3.1基数排序的伪代码 274

12.3.2基数排序的效率 274

12.4算法比较 275

第13章有序表 280

13.1ADT有序表的说明 280

13.2鍊表实现 284

13.2.1add方法 285

13.2.2鍊表实现的效率 291

13.3使用ADT线性表的实现 292

第14章继承与线性表 299

14.1使用继承实现有序表 299

14.2基类的设计 302

14.3有序表的一种高效实现 306

第15章可变对象、不可变对象及可克隆对象 310

15.1可变对象与不可变对象 310

15.1.1同伴类 313

15.1.2使用继承构建同伴类 315

15.2可克隆对象 317

15.3克隆体的有序表 323

15.4克隆数组 325

15.5克隆鍊表 327

第16章查找 334

16.1问题描述 334

16.2查找无序数组 335

16.2.1叠代顺序查找无序数组 335

16.2.2递归顺序查找无序数组 336

16.2.3顺序查找数组的效率 338

16.3查找有序数组 338

16.3.1顺序查找有序数组 338

16.3.2折半查找有序数组 339

16.3.3Java类库：方法binarySearch 343

16.3.4折半查找数组的效率 343

16.4查找无序鍊表 345

16.4.1叠代顺序查找无序鍊表 345

16.4.2递归顺序查找无序鍊表 346

16.4.3顺序查找鍊表的效率 347

16.5查找有序鍊表 347

16.5.1顺序查找有序鍊表 347

16.5.2折半查找有序鍊表 348

16.6查找方法的选择 348

第17章词典 352

17.1ADT词典的说明 352

17.1.1Java接口 355

17.1.2叠代器 356

17.2使用ADT词典 357

17.2.1电话号码簿 357

17.2.2词频 361

17.2.3词的索引 363

17.3Java类库：Map接口 365

第18章词典的实现 368

18.1基于数组的实现 368

18.1.1元素 369

18.1.2基于数组的无序词典 370

18.1.3基于数组的有序词典 371

18.2基于向量的实现 375

18.3基于鍊表的实现 377

18.3.1元素 377

18.3.2基于鍊表的无序词典 378

18.3.3基于鍊表的有序词典 379

第19章用散列实现词典 385

19.1什幺是散列 386

19.2散列函式 388

19.2.1计算散列码 388

19.2.2将散列码压缩为散列表的索引 391

19.3处理冲突 392

19.3.1线性探测开放定址 392

19.3.2二次探测开放定址 396

19.3.3双散列开放定址 397

19.3.4开放定址的潜在问题 398

19.3.5链地址 398

19.4效率 401

19.4.1装填因子 401

19.4.2开放定址的开销 402

19.4.3链地址的开销 403

19.5再散列 404

19.6处理冲突的各方案比较 405

19.7使用散列的词典实现 406

19.7.1散列表中的元素 406

19.7.2数据域与构造函式 407

19.7.3方法getValue、remove及add 408

19.7.4叠代器 415

19.8Java类库：类HashMap 416

第20章栈 421

20.1ADT栈的说明 421

20.2利用栈处理代数表达式 425

20.2.1检查中缀代数表达式中括弧是否平衡 425

20.2.2将中缀表达式转化为后缀表达式 430

20.2.3后缀表达式求值 437

20.2.4中缀表达式求值 439

20.3程式栈 441

20.4使用栈代替递归 443

20.5Java类库：类Stack 445

第21章栈的实现 449

21.1基于鍊表的实现 449

21.2基于数组的实现 452

21.3基于向量的实现 456

第22章伫列、双端伫列及优先伫列 460

22.1ADT伫列的说明 460

22.2使用伫列模拟排队 464

22.3使用伫列计算股份销售的资本收益 470

22.4ADT双端伫列的说明 473

22.5使用双端伫列计算股份销售的资本收益 475

22.6ADT优先伫列的说明 476

22.7使用优先伫列计算股份销售的资本收益 477

第23章伫列、双端伫列及优先伫列的实现 481

23.1基于鍊表实现伫列 481

23.2基于数组实现伫列 485

23.2.1循环数组 485

23.2.2含有一个不用位置的循环数组 488

23.3基于向量实现伫列 493

23.4基于循环鍊表实现伫列 495

23.5基于双向鍊表实现双端伫列 500

23.6实现优先伫列可用方法 504

第24章树 507

24.1树的概念 507

24.1.1层次化的组织 507

24.1.2树的术语 509

24.2树的遍历 513

24.2.1二叉树的遍历 513

24.2.2树的遍历 515

24.3树的Java接口 516

24.3.1所有树的接口 516

24.3.2二叉树接口 517

24.4二叉树举例 519

24.4.1表达式树 519

24.4.2决策树 521

24.4.3二叉查找树 524

24.4.4堆 526

24.5树举例 528

24.5.1语法分析树 528

24.5.2博弈树 530

第25章树的实现 534

25.1二叉树的节点 534

25.1.1节点的接口 535

25.1.2BinaryNode的实现 536

25.2ADT二叉树的实现 537

25.2.1创建基本二叉树 537

25.2.2方法privateSetTree 539

25.2.3访问者与修改者方法 542

25.2.4计算高度与统计节点 543

25.2.5遍历 544

25.3表达式二叉树的实现 549

25.4树 550

25.4.1树的节点 550

25.4.2用二叉树表示树 551

第26章二叉查找树的实现 555

26.1预备知识 555

26.1.1二叉查找树接口 556

26.1.2相同的元素 558

26.1.3开始类定义 559

26.2查找与提取 560

26.3遍历 561

26.4插入元素 561

26.4.1叠代实现 562

26.4.2递归实现 564

26.5删除元素 569

26.5.1删除叶子节点中的元素 569

26.5.2删除有一个孩子的节点中的元素 570

26.5.3删除有两个孩子的节点中的元素 570

26.5.4删除根节点中的元素 573

26.5.5叠代实现 574

26.5.6递归实现 579

26.6操作的效率 582

26.6.1平衡的重要性 583

26.6.2插入节点的顺序 584

26.7ADT词典的实现 585

第27章堆的实现 591

27.1再论ADT堆 591

27.2用数组表示堆 592

27.3插入元素 594

27.4删除根 597

27.5创建堆 600

27.6堆排序 602

第28章平衡查找树 606

28.1AVL树 606

28.1.1单旋转 607

28.1.2双旋转 608

28.1.3实现细节 612

28.22-3树 615

28.2.12-3树的查找 616

28.2.2向2-3树插入元素 617

28.2.3插入期间分裂节点 619

28.32-4树 620

28.3.1向2-4树插入元素 620

28.3.2比较AVL树、2-3树及2-4树 622

28.4红黑树 623

28.4.1红黑树的特性 624

28.4.2向红黑树插入元素 625

28.4.3Java类库：类TreeMap 629

28.5B树 629

第29章图 633

29.1一些例子与术语 633

29.1.1公路地图 633

29.1.2航线 636

29.1.3迷宫 636

29.1.4先修课程 637

29.1.5树 637

29.2遍历 638

29.2.1广度优先遍历 639

29.2.2深度优先遍历 639

29.3拓扑顺序 642

29.4路径 644

29.4.1寻找路径 644

29.4.2无权图中的最短路径 644

29.4.3带权图中的最短路径 647

29.5ADT图的Java接口 650

第30章图的实现 657

30.1两种实现的概述 657

30.1.1邻接矩阵 657

30.1.2邻接表 658

30.2顶点与边 659

30.2.1说明类Vertex 659

30.2.2类Edge 661

30.2.3实现类Vertex 663

30.3ADT图的实现 664

30.3.1基本操作 665

30.3.2图的算法 668

附录AJava基础 673

附录B异常处理 723

附录C档案输入与输出 732

附录D文档与程式设计风格 748

附录E自测题答案 754