数据结构（计算机科学与技术 Java版）

第1章 类与对象 1

1.1 本书内容 1

1.1.1 动态数组 1

1.1.2 链表 2

1.1.3 关联数组 3

1.1.4 图 4

1.1.5 适配器结构 4

1.1.6 数据结构与面向对象编程 5

1.1.7 数据结构与算法 5

1.2 面向对象编程 5

1.3 理解类的概念 7

1.4 Time24类 8

1.4.1 设计Time24类 8

1.4.2 构造函数 9

1.4.3 toString方法 10

1.4.4 Accessor和mutator方法 11

1.4.5 静态方法 12

1.5 对象的声明和使用 12

1.5.1 对象方法的使用 13

1.5.2 引用与别名 14

1.6 一个使用Time24对象的

应用程序 15

1.7 类的表示 16

1.8 类的实现 18

1.8.1 Time24类声明 19

1.8.2 私有的工具方法 20

1.8.3 accessor与mutator方法 21

1.8.4 构造函数 22

1.8.5 格式化的对象描述 23

1.8.6 增加时间 23

1.8.7 时间间隔 23

1.9 类的构造 24

1.10 String类 26

1.10.1 串索引 27

1.10.2 串合并 27

1.10.3 串比较 28

1.11 枚举类 29

1.12 总结 32

书面练习 33

编程练习 34

编程项目 36

第2章 类之间的关系 39

2.1 wrapper类 40

2.1.1 Integer对象的比较 40

2.1.2 静态wrapper类成员 41

2.1.3 字符处理 42

2.2 自动装箱与自动拆箱 43

2.3 对象组合 44

2.3.1 TimeCard类 45

2.3.2 TimeCard类的实现 46

2.3.3 TimeCard类的UML图 47

2.4 Java中的继承 47

2.4.1 一个雇员层次结构 48

2.4.2 继承层次结构中成员的

可见性 49

2.4.3 Employee类的声明 50

2.4.4 SalaryEmployee子类 51

2.4.5 继承层次结构中的关键

字super 52

2.4.6 HourlyEmployee子类 53

2.5 多态性 55

2.6 抽象类 59

2.7 运行时错误的处理 60

2.7.1 throw语句 60

2.7.2 处理异常的try/catch

代码块 61

2.7.3 finally子句 62

2.7.4 异常传播 63

2.7.5 Java异常的层次结构 63

2.7.6 标准的异常 65

2.8 输入与输出 65

2.8.1 控制台I/O 66

2.8.2 文件I/O 67

2.8.3 使用Reader流的文本输入 67

2.8.4 输入串的分析 69

2.8.5 使用Writer流的文本输出 71

2.8.6 输出流的控制 72

2.9 Scanner类 73

2.9.1 声明Scanner对象 73

2.9.2 输入流的读取 73

2.9.3 文件输入 75

2.9.4 Scanner类API 75

2.9.5 应用程序：Scanner类

的使用 76

2.10 总结 79

书面练习 80

编程练习 83

编程项目 87

第3章 类的设计 89

3.1 Java接口 89

3.2 作为模板的接口 91

3.2.1 使用接口类型 92

3.2.2 接口与继承 94

3.3 使用javadoc创建API 96

3.4 设计模式 99

3.5 GUI应用程序设计 100

3.5.1 图形组件 101

3.5.2 GUI应用程序设计模式 102

3.5.3 事件侦听器与事件处理

程序 105

3.5.4 骰子投掷动作事件 106

3.6 总结 107

书面练习 108

编程练习 108

编程项目 112

第4章 算法介绍 115

4.1 选择排序 115

4.2 简单的搜索算法 119

4.2.1 顺序搜索 119

4.2.2 二叉搜索 121

4.3 算法的分析 126

4.3.1 系统/内存性能标准 126

4.3.2 算法性能：运行时间分析 126

4.3.3 Big-O符号 129

4.3.4 通用数量级 131

4.4 搜索算法的比较 133

4.5 总结 136

书面练习 136

编程练习 138

编程项目 141

第5章 泛型类与方法 143

5.1 Object超类 144

5.1.1 对象数组方法 145

5.1.2 通用的顺序搜索 146

5.2 Java泛型介绍 147

5.2.1 基于Object的Store类 148

5.2.2 泛型集合 149

5.2.3 泛型Store类 150

5.3 泛型接口 151

5.4 泛型方法 155

5.4.1 基本的泛型方法 155

5.4.2 为泛型类型使用绑定 156

5.5 泛型与继承 157

5.5.1 被绑定的泛型类型 158

5.5.2 泛型与通配符 160

5.6 泛型搜索/排序算法 161

5.7 总结 164

书面练习 165

编程练习 166

编程项目 168

第6章 递归 171

6.1 递归的概念 171

6.1.1 描述一个递归算法 173

6.1.2 递归方法的实现 173

6.1.3 递归的工作方式 175

6.1.4 多种基数表示法 176

6.2 递归的应用 179

6.2.1 构建一个刻度尺 179

6.2.2 Hanoi塔 181

6.3 递归的评价 185

6.3.1 Fibonacci方法 186

6.3.2 使用递归的标准 189

6.4 总结 189

书面练习 190

编程练习 192

编程项目 194

第7章 排序算法 195

7.1 插入排序 195

7.2 分治排序算法 198

7.2.1 归并排序 198

7.2.2 通用的排序方法 201

7.2.3 msort()方法 202

7.2.4 归并排序的效率 205

7.3 快速排序 206

7.3.1 使用基准值分割列表 206

7.3.2 快速排序递归下降 209

7.3.3 pivotIndex()方法 211

7.3.4 quicksort()方法 213

7.3.5 快速排序的运行时间 215

7.3.6 排序算法的比较 216

7.4 第k大元素的查找 219

7.5 总结 221

书面练习 222

编程练习 223

编程项目 225

第8章 集合类型 227

8.1 集合介绍 227

8.2 集合的概述 229

8.2.1 List集合 230

8.2.2 Set集合 232

8.2.3 Map集合 233

8.2.4 适配器集合 234

8.2.5 Graph集合 235

8.2.6 Java Collections Framework 236

8.3 Bag集合 237

8.3.1 创建和使用一个Bag集合 238

8.3.2 应用：Eratosthenes筛选法 240

8.4 Bag类的实现 243

8.4.1 私有的remove()方法 244

8.4.2 插入和访问方法 245

8.4.3 集合的toString()方法 246

8.5 总结 246

书面练习 247

编程练习 248

编程项目 249

第9章 基于数组的列表集合 251

9.1 列表集合 251

9.2 ArrayList类 255

9.2.1 调整ArrayList的大小 257

9.2.2 ArrayList API 259

9.3 ArrayList应用程序 259

9.3.1 ArrayList的连接 259

9.3.2 closest-pair问题 262

9.4 实现ArrayList类 266

9.4.1 ArrayList类的设计 266

9.4.2 准备更大的容量 267

9.4.3 添加和删除元素 268

9.4.4 实现索引访问 272

9.5 Cloneable对象 273

9.5.1 克隆Time24对象 274

9.5.2 克隆引用变量 275

9.5.3 克隆ArrayList对象 277

9.5.4 克隆数组 279

9.6 ArrayList集合的评价 279

9.7 总结 280

书面练习 280

编程练习 282

编程项目 285

第10章 链表 287

10.1 单链表 289

10.1.1 创建链表 289

10.1.2 扫描链表 291

10.1.3 定位列表位置 291

10.1.4 更新列表头 292

10.1.5 通用的插入和删除操作 292

10.1.6 删除目标节点 294

10.2 双链表 298

10.3 LinkedList集合 299

10.3.1 LinkedList类 300

10.3.2 基于索引的LinkedList

方法 301

10.3.3 访问列表尾 302

10.4 使用LinkedList集合的

应用程序 304

10.4.1 应用程序：选拔列表 304

10.4.2 应用程序：回文列表 307

10.5 总结 309

书面练习 310

编程练习 313

编程项目 318

第11章 实现LinkedList类 321

11.1 双链表 321

11.1.1 DNode对象 322

11.1.2 使用DNode对象 323

11.2 循环双链表 325

11.2.1 声明双链表 326

11.2.2 更新双链表 327

11.2.3 应用程序：词汇杂乱 330

11.3 实现LinkedList类 333

11.3.1 LinkedList类的私有

成员 333

11.3.2 LinkedList类的构造

函数 335

11.3.3 列表中基于索引的访问 335

11.3.4 搜索列表 336

11.3.5 修改列表 337

11.4 总结 339

书面练习 339

编程练习 340

编程项目 342

第12章 迭代器 345

12.1 迭代器的概念 345

12.2 集合迭代器 346

12.2.1 迭代器扫描方法 347

12.2.2 通用的迭代器方法 350

12.2.3 使用增强的for语句

进行迭代 351

12.3 列表迭代器 352

12.3.1 ListIterator方法set() 353

12.3.2 列表的后向扫描 354

12.3.3 ListIterator方法add() 356

12.3.4 迭代器设计模式 357

12.4 迭代器的应用 358

12.4.1 有序列表 358

12.4.2 删除有序列表中的

重复值 360

12.5 OrderedList集合 361

12.5.1 OrderedList类方法 362

12.5.2 应用程序：确定字频 363

12.5.3 适配器设计模式 367

12.6 顺序集合的选择 367

12.7 总结 368

书面练习 369

编程练习 371

编程项目 373

第13章 迭代器的实现 375

13.1 迭代器实现设计 375

13.1.1 迭代器变量 376

13.1.2 迭代器接口方法 377

13.2 LinkedList迭代器 378

13.3 列表迭代器的实现 381

13.3.1 列表迭代器构造函数 381

13.3.2 列表迭代器的公共方法 382

13.4 快速失效迭代器 385

13.5 总结 386

书面练习 387

编程练习 388

编程项目 390

第14章 堆栈 391

14.1 堆栈集合 392

14.2 堆栈的应用 396

14.2.1 多种基数 397

14.2.2 符号对的平衡 400

14.3 递归与运行时堆栈 403

14.4 后缀表达式 405

14.4.1 后缀表达式的求解 406

14.4.2 PostfixEval类 408

14.4.3 evaluate()方法 410

14.5 中缀表达式的求解 412

14.5.1 中缀表达式属性 412

14.5.2 中缀-后缀转换 413

14.6 总结 416

书面练习 417

编程练习 419

编程项目 422

第15章 队列与优先队列 425

15.1 Queue接口 426

15.1.1 创建一个队列集合类 427

15.1.2 应用：队列的调度 428

15.2 基数排序 430

15.3 有界队列 436

15.3.1 BQueue类的设计实现 438

15.3.2 BQueue类的声明 440

15.4 优先队列 441

15.4.1 优先队列接口 442

15.4.2 应用程序：支持服务库 444

15.5 事件驱动的仿真 447

15.5.1 对银行的仿真 447

15.5.2 仿真设计模式 449

15.5.3 BankSimulation类 451

15.6 总结 457

书面练习 457

编程练习 460

编程项目 463

第16章 二叉树 465

16.1 树结构 465

16.1.1 树的相关术语 466

16.1.2 二叉树 468

16.2 二叉树节点 473

16.3 二叉树扫描算法 477

16.3.1 递归树遍历 477

16.3.2 中序扫描算法 478

16.3.3 扫描方法的设计 480

16.3.4 迭代的层序扫描 482

16.3.5 Visitor设计模式 484

16.3.6 Visitor设计模式的使用 486

16.4 树扫描算法的使用 489

16.4.1 树高度的计算 489

16.4.2 复制二叉树 491

16.4.3 清除树 494

16.4.4 显示二叉树 495

16.5 排序的下界(选读) 497

16.6 总结 499

书面练习 500

编程练习 503

编程项目 505

第17章 二叉树的应用 507

17.1 表达式树 507

17.2 迭代的树遍历 512

17.2.1 中序迭代遍历 513

17.2.2 InorderIterator类的实现 515

17.3 Euler回路遍历 518

17.4 绘制二叉树 521

17.4.1 影像树的构建 521

17.4.2 影像树的显示 523

17.5 总结 525

书面练习 526

编程练习 526

编程项目 529

第18章 二叉搜索树 531

18.1 二叉搜索树 531

18.1.1 构建二叉搜索树 532

18.1.2 在二叉搜索树中定位

对象 533

18.1.3 删除二叉搜索树节点 535

18.2 STree：一种二叉搜索树类 536

18.3 STree类的实现 540

18.3.1 STree类的私有成员与

构造函数 541

18.3.2 插入和定位节点 542

18.3.3 删除节点 544

18.3.4 其他操作 550

18.3.5 二叉搜索树操作的

复杂度 551

18.4 STree迭代器 551

18.5 总结 556

书面练习 556

编程练习 558

编程项目 559

第19章 集与映射 561

19.1 集 563

19.1.1 TreeSet集合 563

19.1.2 简单的拼写检查器 565

19.2 集运算符 568

19.2.1 集运算符的实现 569

19.2.2 应用程序：计算机账号的

更新 572

19.2.3 使用有序集的操作 574

19.3 映射 577

19.3.1 Map接口 577

19.3.2 有序映射TreeMap 579

19.3.3 应用程序：一个学生时间

记录映射 581

19.3.4 应用程序：计算机软件

产品 583

19.4 映射集合视图 586

19.4.1 键集集合视图 586

19.4.2 条目集集合视图 588

19.4.3 应用程序：构建词汇

索引 591

19.5 总结 596

书面练习 596

编程练习 598

编程项目 602

第20章 有序集与映射的实现 603

20.1 TreeSet类的实现 603

20.2 TreeMap类的实现 604

20.2.1 TreeMap类的设计 607

20.2.2 使用键对条目进行访问 608

20.2.3 更新条目 609

20.2.4 删除条目 611

20.2.5 TreeSet和TreeMap类中

插入和删除操作的

复杂度 611

20.3 集合视图的实现 611

20.3.1 查看视图 612

20.3.2 实现视图 614

20.3.3 keySet集合视图 615

20.4 总结 617

书面练习 617

编程练习 618

编程项目 621

第21章 实现映射的散列法 625

21.1 散列法 625

21.2 散列函数的设计 627

21.2.1 Java方法hashCode() 627

21.2.2 自定义的散列函数 629

21.3 散列表的设计 631

21.3.1 线性探查法 631

21.3.2 具有不同列表的拉链法 633

21.3.3 再散列 635

21.4 作为集合的散列表 636

21.5 Hash类的实现 637

21.5.1 Hash类的add()和

rehash()方法 639

21.5.2 Hash类的remove()方法 641

21.5.3 Hash类迭代器的实现 642

21.6 无序映射集合 645

21.6.1 访问HashMap类中的

条目 646

21.6.2 更新HashMap类中的

条目 647

21.7 无序集集合 649

21.8 散列表的性能 650

21.9 总结 652

书面练习 653

编程练习 655

编程项目 657

第22章 堆 661

22.1 基于数组的二叉树 661

22.2 Comparator接口 663

22.2.1 通用比较对象 664

22.2.2 通用的数组排序 665

22.3 堆 667

22.3.1 堆的插入操作 668

22.3.2 堆的删除操作 670

22.3.3 堆的显示 674

22.4 使用堆进行排序 676

22.4.1 堆的产生 676

22.4.2 堆排序 679

22.4.3 静态堆方法概述 680

22.5 优先队列的实现 681

22.6 总结 684

书面练习 684

编程练习 687

编程项目 689

第23章 位数组与文件压缩 691

23.1 位数组 691

23.1.1 BitArray类 694

23.1.2 BitArray类的实现 696

23.2 二进制文件 699

23.3 Huffman压缩 703

23.3.1 Huffman树的构建 707

23.3.2 Huffman压缩的实现 708

23.3.3 Huffman解压的实现 714

23.4 序列化 716

23.4.1 对象的序列化 717

23.4.2 使类可序列化 718

23.4.3 反序列化对象 718

23.4.4 应用程序：对象的

序列化 718

23.4.5 定制序列化 721

23.5 总结 723

书面练习 724

编程练习 728

编程项目 729

第24章 图与路径 731

24.1 图的相关术语 731

24.1.1 有向图 733

24.1.2 带权图 734

24.2 图的创建和使用 735

24.2.1 Graph接口 735

24.2.2 DiGraph类 737

24.3 图遍历算法 741

24.3.1 广度优先搜索算法 741

24.3.2 深度优先访问算法 746

24.3.3 深度优先搜索算法 751

24.3.4 无环图 753

24.4 总结 755

书面练习 755

编程练习 758

编程项目 761

第25章 图算法 763

25.1 拓扑排序 763

25.1.1 拓扑排序的目的 764

25.1.2 topologicalSort()方法

的实现 765

25.2 强连通组件 766

25.2.1 强连通组件算法的工作

原理 768

25.2.2 strongComponents()方法

的实现 769

25.3 图最优化算法 771

25.4 最短路径算法 772

shortestPath()方法的实现 774

25.5 Dijkstra最小路径算法 777

25.5.1 Dijkstra算法的设计 778

25.5.2 Dijkstra算法的工作

原理 781

25.5.3 minimumPath()方法的

实现 781

25.5.4 无环图中的最小路径 784

25.6 最小生成树 787

25.6.1 Prim算法 788

25.6.2 minSpanTree()方法的

实现 790

25.7 总结 794

书面练习 794

编程练习 796

编程项目 798

第26章 图的实现 799

26.1 图的表示 799

26.2 DiGraph类的组件 800

26.2.1 顶点信息的表示 801

26.2.2 顶点映射与VertexInfo

数组列表 803

26.3 DiGraph类设计 806

26.4 DiGraph类方法 807

26.4.1 ArrayList的访问 808

26.4.2 邻接顶点的标识 808

26.4.3 入度和出度的求解 809

26.4.4 添加边 809

26.4.5 删除顶点 810

26.4.6 图算法支持方法 813

26.4.7 图集合视图 814

26.5 总结 815

书面练习 816

编程练习 817

编程项目 819

第27章 平衡的搜索树 821

27.1 AVL树 822

27.2 AVLTree类的实现 824

27.2.1 AVLTree类的add()

方法 825

27.2.2 私有的addNode()方法 831

27.2.3 add()方法 832

27.3 2-3-4树 835

27.3.1 2-3-4树的搜索 836

27.3.2 2-3-4树中的插入操作 836

27.4 红-黑树 839

27.4.1 2-3-4树节点的表示 840

27.4.2 2-3-4树的红-黑树表示 841

27.4.3 在红-黑树中插入节点 844

27.4.4 4-节点的分割 844

27.4.5 红-黑树底部的插入

操作 848

27.4.6 红-黑树的构建 849

27.4.7 红-黑树的搜索运行

时间 850

27.4.8 在红-黑树中删除节点 851

27.5 RBTree类 852

27.6 总结 855

书面练习 855

编程练习 858

编程项目 859

第28章 数论与加密 861

28.1 基本的数论概念 861

28.1.1 Euclid GCD算法 862

28.1.2 模运算 863

28.1.3 Euler Φ函数 865

28.2 安全的消息传输 866

28.2.1 创建用于RSA加密的

密钥 867

28.2.2 使用用于RSA加密的

密钥 867

28.2.3 如何保护RSA通信 868

28.3 大整数的使用 868

28.4 RSA的客户-服务器模式 872

28.5 RSA算法(选读) 873

28.5.1 Euclid GCD算法的实现 873

28.5.2 RSA定理 876

28.6 总结 877

书面练习 878

编程练习 879

编程项目 880

第29章 杂类算法 881

29.1 组合学 881

29.1.1 组合的构建 882

29.1.2 查找所有子集 883

29.1.3 列出置换 885

29.1.4 旅行推销员问题 888

29.1.5 置换与TSP 889

29.2 动态编程 889

29.2.1 由顶向下动态编程 890

29.2.2 使用动态编程的组合 893

29.2.3 由底向上动态编程 894

29.2.4 背包问题 896

29.2.5 Knapsack类 899

29.3 回溯：八皇后问题 903

29.3.1 问题分析 905

29.3.2 程序设计 907

29.3.3 显示棋盘 911

29.4 总结 913

书面练习 914

编程练习 915

编程项目 920

附录A Java入门 923

A.1 Java程序的结构 923

A.1.1 注释 924

A.1.2 关键字与标识符 925

A.1.3 变量的声明和使用 925

A.1.4 控制台输出 925

A.2 Java编程环境 926

A.3 原始数据类型 927

A.3.1 数值类型 927

A.3.2 Java的char类型 929

A.3.3 命名常量的声明 930

A.4 运算符 930

A.4.1 算术运算符 930

A.4.2 赋值运算符 931

A.4.3 复合赋值运算符 931

A.4.4 增量运算符 932

A.4.5 运算符的优先顺序 932

A.5 类型之间的转换 933

A.6 选择语句 935

A.6.1 if语句 937

A.6.2 嵌套的if语句 938

A.6.3 多路if/else语句 939

A.6.4 条件表达式运算符 939

A.6.5 switch语句 940

A.6.6 boolean类型 941

A.7 循环语句 942

A.7.1 while语句 942

A.7.2 do/while语句 943

A.7.3 for语句 944

A.7.4 break语句 945

A.8 数组 946

A.8.1 数组的初始化 947

A.8.2 使用增强的for语句

扫描数组 947

A.8.3 二维数组 948

A.9 Java的方法 949

A.9.1 预定义的方法 949

A.9.2 自定义的方法 951

A.9.3 作为方法参数的数组 953

附录B Java关键字 957

附录C ASCII字符编码 959

附录D Java操作符的优先顺序 961

附录E EZJava集成开发环境 963

E.1 安装EZJava 963

E.2 启动EZJava 964

E.2.1 创建新文档 965

E.2.2 菜单选项 966

E.3 程序的编译和运行 966

E.4 项目的使用 968