数据结构 Java版PDF电子书下载

1.1 本书内容 1

1.1.1 动态数组 1

第1章 类与对象 1

1.1.2 链表 2

1.1.3 关联数组 3

1.1.5 适配器结构 4

1.1.4 图 4

1.2 面向对象编程 5

1.1.7 数据结构与算法 5

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

1.3 理解类的概念 7

1.4.1 设计Time24类 8

1.4 Time24类 8

1.4.2 构造函数 9

1.4.3 toString方法 10

1.4.4 Accessor和mutator方法 11

1.5 对象的声明和使用 12

1.4.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.7 时间间隔 23

1.8.6 增加时间 23

1.8.5 格式化的对象描述 23

1.9 类的构造 24

1.10 String类 26

1.10.2 串合并 27

1.10.1 串索引 27

1.10.3 串比较 28

1.11 枚举类 29

1.12 总结 32

书面练习 33

编程练习 34

编程项目 36

第2章 类之间的关系 39

2.1.1 Integer对象的比较 40

2.1 wrapper类 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.4 Java中的继承 47

2.3.3 TimeCard类的UML图 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.1 throw语句 60

2.7 运行时错误的处理 60

2.7.2 处理异常的try/catch代码块 61

2.7.3 finally子句 62

2.7.5 Java异常的层次结构 63

2.7.4 异常传播 63

2.8 输入与输出 65

2.7.6 标准的异常 65

2.8.1 控制台I/O 66

2.8.3 使用Reader流的文本输入 67

2.8.2 文件I/O 67

2.8.4 输入串的分析 69

2.8.5 使用Writer流的文本输出 71

2.8.6 输出流的控制 72

2.9.2 输入流的读取 73

2.9.1 声明Scanner对象 73

2.9 Scanner类 73

2.9.4 Scanner类API 75

2.9.3 文件输入 75

2.9.5 应用程序：Scanner类的使用 76

2.10 总结 79

书面练习 80

编程练习 83

编程项目 87

3.1 Java接口 89

第3章 类的设计 89

3.2 作为模板的接口 91

3.2.1 使用接口类型 92

3.2.2 接口与继承 94

3.3 使用iavadoc创建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.1 选择排序 115

第4章 算法介绍 115

4.2.1 顺序搜索 119

4.2 简单的搜索算法 119

4.2.2 二叉搜索 121

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

4.3.1 系统／内存性能标准 126

4.3 算法的分析 126

4.3.3 Big-O符号 129

4.3.4 通用数量级 131

4.4 搜索算法的比较 133

书面练习 136

4.5 总结 136

编程练习 138

编程项目 141

第5章 泛型类与方法 143

5.1 Obiect超类 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.1 基本的泛型方法 155

5.4 泛型方法 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.1 递归的概念 171

第6章 递归 171

6.1.2 递归方法的实现 173

6.1.1 描述一个递归算法 173

6.1.3 递归的工作方式 175

6.1.4 多种基数表示法 176

6.2.1 构建一个刻度尺 179

6.2 递归的应用 179

6.2.2 Hanoi塔 181

6.3 递归的评价 185

6.3.1 Fibonacci方法 186

6.4 总结 189

6.3.2 使用递归的标准 189

书面练习 190

编程练习 192

编程项目 194

7.1 插入排序 195

第7章 排序算法 195

7.2.1 归并排序 198

7.2 分治排序算法 198

7.2.2 通用的排序方法 201

7.2.3 msort（）方法 202

7.2.4 归并排序的效率 205

7.3.1 使用基准值分割列表 206

7.3 快速排序 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.1 集合介绍 227

第8章 集合类型 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.5 总结 246

8.4.3 集合的toString（）方法 246

书面练习 247

编程练习 248

编程项目 249

9.1 列表集合 251

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

9.2 ArrayList类 255

9.2.1 调整ArrayList的大小 257

9.3.1 ArrayList的连接 259

9.3 ArrayList应用程序 259

9.2.2 ArrayList API 259

9.3.2 closest-pair问题 262

9.4.1 ArrayList类的设计 266

9.4 实现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.6 ArrayList集合的评价 279

9.5.4 克隆数组 279

书面练习 280

9.7 总结 280

编程练习 282

编程项目 285

第10章 链表 287

10.1.1 创建链表 289

10.1 单链表 289

10.1.3 定位列表位置 291

10.1.2 扫描链表 291

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

10.1.4 更新列表头 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.1 应用程序：选拔列表 304

10.4 使用LinkedList集合的应用程序 304

10.4.2 应用程序：回文列表 307

10.5 总结 309

书面练习 310

编程练习 313

编程项目 318

11.1 双链表 321

第11章 实现LinkedList类 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.1 LinkedList类的私有成员 333

11.3 实现LinkedList类 333

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

11.3.2 LinkedList类的构造函数 335

11.3.4 搜索列表 336

11.3.5 修改列表 337

书面练习 339

11.4 总结 339

编程练习 340

编程项目 342

12.1 迭代器的概念 345

第12章 迭代器 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.1 有序列表 358

12.4 迭代器的应用 358

12.4.2 删除有序列表中的重复值 360

12.5 OrderedList集合 361

12.5.1 OrderedList类方法 362

12.5.2 应用程序：确定字频 363

12.6 顺序集合的选择 367

12.5.3 适配器设计模式 367

12.7 总结 368

书面练习 369

编程练习 371

编程项目 373

13.1 迭代器实现设计 375

第13章 迭代器的实现 375

13.1.1 迭代器变量 376

13.1.2 迭代器接口方法 377

13.2 LinkedList迭代器 378

13.3.1 列表迭代器构造函数 381

13.3 列表迭代器的实现 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.1 中缀表达式属性 412

14.5 中缀表达式的求解 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.1 对银行的仿真 447

15.5 事件驱动的仿真 447

15.5.2 仿真设计模式 449

15.5.3 BankSimulation类 451

书面练习 457

15.6 总结 457

编程练习 460

编程项目 463

16.1 树结构 465

第16章 二叉树 465

16.1.1 树的相关术语 466

16.1.2 二叉树 468

16.2 二叉树节点 473

16.3.1 递归树遍历 477

16.3 二叉树扫描算法 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.1 树高度的计算 489

16.4 树扫描算法的使用 489

16.4.2 复制二叉树 491

16.4.3 清除树 494

16.4.4 显示二叉树 495

16.5 排序的下界（选读） 497

16.6 总结 499

书面练习 500

编程练习 503

编程项目 505

17.1 表达式树 507

第17章 二叉树的应用 507

17.2 迭代的树遍历 512

17.2.1 中序迭代遍历 513

17.2.2 InorderIterator类的实现 515

17.3 Euler回路遍历 518

17.4.1 影像树的构建 521

17.4 绘制二叉树 521

17.4.2 影像树的显示 523

17.5 总结 525

编程练习 526

书面练习 526

编程项目 529

18.1 二叉搜索树 531

第18章 二叉搜索树 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.4 STree迭代器 551

18.3.5 二叉搜索树操作的复杂度 551

书面练习 556

18.5 总结 556

编程练习 558

编程项目 559

第19章 集与映射 561

19.1.1 TreeSet集合 563

19.1 集 563

19.1.2 简单的拼写检查器 565

19.2 集运算符 568

19.2.1 集运算符的实现 569

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

19.2.3 使用有序集的操作 574

19.3.1 Map接口 577

19.3 映射 577

19.3.2 有序映射TreeMap 579

19.3.3 应用程序：一个学生时间记录映射 581

19.3.4 应用程序：计算机软件产品 583

19.4.1 键集集合视图 586

19.4 映射集合视图 586

19.4.2 条目集集合视图 588

19.4.3 应用程序：构建词汇索引 591

书面练习 596

19.5 总结 596

编程练习 598

编程项目 602

20.1 TreeSet类的实现 603

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

20.2 TreeMap类的实现 604

20.2.1 TreeMap类的设计 607

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

20.2.3 更新条目 609

20.3 集合视图的实现 611

20.2.5 TreeSet和TreeMap类中插入和删除操作的复杂度 611

20.2.4 删除条目 611

20.3.1 查看视图 612

20.3.2 实现视图 614

20.3.3 keySet集合视图 615

书面练习 617

20.4 总结 617

编程练习 618

编程项目 621

21.1 散列法 625

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

21.2.1 Java方法hashCode（） 627

21.2 散列函数的设计 627

21.2.2 自定义的散列函数 629

21.3.1 线性探查法 631

21.3 散列表的设计 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.1 基于数组的二叉树 661

第22章 堆 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.1 堆的产生 676

22.4 使用堆进行排序 676

22.4.2 堆排序 679

22.4.3 静态堆方法概述 680

22.5 优先队列的实现 681

书面练习 684

22.6 总结 684

编程练习 687

编程项目 689

23.1 位数组 691

第23章 位数组与文件压缩 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.4 应用程序：对象的序列化 718

23.4.3 反序列化对象 718

23.4.2 使类可序列化 718

23.4.5 定制序列化 721

23.5 总结 723

书面练习 724

编程练习 728

编程项目 729

24.1 图的相关术语 731

第24章 图与路径 731

24.1.1 有向图 733

24.1.2 带权图 734

24.2.1 Graph接口 735

24.2 图的创建和使用 735

24.2.2 DiGraph类 737

24.3.1 广度优先搜索算法 741

24.3 图遍历算法 741

24.3.2 深度优先访问算法 746

24.3.3 深度优先搜索算法 751

24.3.4 无环图 753

书面练习 755

24.4 总结 755

编程练习 758

编程项目 761

25.1 拓扑排序 763

第25章 图算法 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.3 minimumPath（）方法的实现 781

25.5.2 Dijkstra算法的工作原理 781

25.5.4 无环图中的最小路径 784

25.6 最小生成树 787

25.6.1 Prim算法 788

25.6.2 minSpanTree（）方法的实现 790

书面练习 794

25.7 总结 794

编程练习 796

编程项目 798

26.1 图的表示 799

第26章 图的实现 799

26.2 DiGraph类的组件 800

26.2.1 顶点信息的表示 801

26.2.2 顶点映射与VertexInfo数组列表 803

26.3 DiGraph类设计 806

26.4 DiGraph类方法 807

26.4.2 邻接顶点的标识 808

26.4.1 ArrayList的访问 808

26.4.4 添加边 809

26.4.3 入度和出度的求解 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.2 2-3-4树中的插入操作 836

27.3.1 2-3-4树的搜索 836

27.4 红－黑树 839

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

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

27.4.4 4－节点的分割 844

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

27.4.5 红－黑树底部的插入操作 848

27.4.6 红－黑树的构建 849

27.4.7 红－黑树的搜索运行时间 850

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

27.5 RBTree类 852

书面练习 855

27.6 总结 855

编程练习 858

编程项目 859

28.1 基本的数论概念 861

第28章 数论与加密 861

28.1.1 Euclid GCD算法 862

28.1.2 模运算 863

28.1.3 Euler φ函数 865

28.2 安全的消息传输 866

28.2.2 使用用于RSA加密的密钥 867

28.2.1 创建用于RSA加密的密钥 867

28.3 大整数的使用 868

28.2.3 如何保护RSA通信 868

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

28.5.1 Euclid GCD算法的实现 873

28.5 RSA算法（选读） 873

28.5.2 RSA定理 876

28.6 总结 877

书面练习 878

编程练习 879

编程项目 880

29.1 组合学 881

第29章 杂类算法 881

29.1.1 组合的构建 882

29.1.2 查找所有子集 883

29.1.3 列出置换 885

29.1.4 旅行推销员问题 888

29.2 动态编程 889

29.1.5 置换与TSP 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.1 Java程序的结构 923

附录A Java入门 923

A.1.1 注释 924

A.1.4 控制台输出 925

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

A.1.2 关键字与标识符 925

A.2 Java编程环境 926

A.3.1 数值类型 927

A.3 原始数据类型 927

A.3.2 Java的char类型 929

A.4.1 算术运算符 930

A.4 运算符 930

A.3.3 命名常量的声明 930

A.4.3 复合赋值运算符 931

A.4.2 赋值运算符 931

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

A.4.4 增量运算符 932

A.5 类型之间的转换 933

A.6 选择语句 935

A.6.1 if语句 937

A.6.2 嵌套的if语句 938

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

A.6.3 多路if/else语句 939

A.6.5 switch语句 940

A.6.6 boolean类型 941

A.7.1 while语句 942

A.7 循环语句 942

A.7.2 do/while语句 943

A.7.3 for语句 944

A.7.4 break语句 945

A.8 数组 946

A.8.2 使用增强的for语句扫描数组 947

A.8.1 数组的初始化 947

A.8.3 二维数组 948

A.9.1 预定义的方法 949

A.9 Java的方法 949

A.9.2 自定义的方法 951

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

附录B Java关键字 957

附录C ASCII字符编码 959

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

E.1 安装EZJava 963

附录E EZJava集成开发环境 963

E.2 启动EZJava 964

E.2.1 创建新文档 965

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

E.2.2 菜单选项 966

E.4 项目的使用 968