数据结构与抽象 Java语言描述PDF电子书下载

引言 组织数据 1

序言 设计类 3

P.1 封装 3

P.2 说明方法 5

P.2.1 注释 5

P.2.2 前置条件和后置条件 5

P.2.3 断言 6

P.3 Java接口 7

P.3.1 写一个接口 8

P.3.2 实现一个接口 9

P.3.3 接口作为数据类型 11

P.3.4 派生一个接口 12

P.3.5 接口内命名常量 13

P.4 选择类 14

P.4.1 标识类 15

P.4.2 CRC卡 15

P.4.3 统一建模语言 16

P.5 重用类 17

第1章 包 22

1.1 什么是包 22

1.2 说明一个包 23

1.3 使用ADT包 30

1.4 像使用自动贩卖机一样使用ADT 33

1.5 ADT集合 34

1.6 Java类库：接口Set 35

Java插曲1 泛型 39

第2章 使用数组实现包 43

2.1 使用固定大小的数组实现ADT包 43

2.1.1 类比 43

2.1.2 一组核心方法 44

2.1.3 实现核心方法 45

2.1.4 让实现安全 51

2.1.5 测试核心方法 54

2.1.6 实现更多的方法 56

2.1.7 删除项的方法 58

2.2 使用可变大小的数组实现ADT包 65

2.2.1 可变大小数组 65

2.2.2 包的新实现 68

2.3 使用数组实现ADT包的优缺点 70

Java插曲2 异常 75

第3章 使用链式数据实现包 82

3.1 链式数据 82

3.2 ADT包的链式实现 84

3.2.1 私有类Node 84

3.2.2 类LinkedBag的框架 85

3.2.3 定义一些核心方法 86

3.2.4 测试核心方法 89

3.2.5 方法getFrequencyOf 90

3.2.6 方法contains 91

3.3 从链中删除一项 92

3.4 有设置和获取方法的类Node 96

3.5 使用链实现ADT包的优缺点 98

第4章 算法的效率 102

4.1 动机 102

4.2 测量算法的效率 103

4.2.1 计数基本操作 105

4.2.2 最优、最差和平均情形 106

4.3 大O表示 107

4.4 描述效率 110

4.5 实现ADT包的效率 113

4.5.1 基于数组的实现 113

4.5.2 链式实现 114

4.5.3 两种实现的比较 115

第5章 栈 121

5.1 ADT栈的规格说明 121

5.2 使用栈来处理代数表达式 125

5.2.1 问题求解：检查中缀代数表达式中平衡的分隔符 125

5.2.2 问题求解：将中缀代数表达式转换为后缀表达式 129

5.2.3 问题求解：计算后缀表达式的值 133

5.2.4 问题求解：计算中缀表达式的值 134

5.3 程序栈 136

5.4 Java类库：类Stack 137

第6章 栈的实现 142

6.1 链式实现 142

6.2 基于数组的实现 144

6.3 基于向量的实现 148

6.3.1 Java类库：类Vector 148

6.3.2 使用向量实现ADT栈 149

第7章 递归 154

7.1 什么是递归 154

7.2 跟踪递归方法 158

7.3 返回一个值的递归方法 160

7.4 递归处理数组 162

7.5 递归处理链 165

7.6 递归方法的时间效率 166

7.6.1 countDown的时间效率 166

7.6.2 计算xn的时间效率 167

7.7 困难问题的简单求解方案 168

7.8 简单问题的低劣求解方案 172

7.9 尾递归 174

7.10 间接递归 176

7.11 使用栈来替代递归 177

Java插曲3 再谈泛型 185

第8章 排序简介 194

8.1 对数组进行排序的Java方法的组织 194

8.2 选择排序 195

8.2.1 迭代选择排序 196

8.2.2 递归选择排序 198

8.2.3 选择排序的效率 198

8.3 插入排序 199

8.3.1 迭代插入排序 199

8.3.2 递归插入排序 201

8.3.3 插入排序的效率 202

8.3.4 链式结点链的插入排序 203

8.4 希尔排序 205

8.4.1 算法 206

8.4.2 希尔排序的效率 207

8.5 算法比较 208

第9章 更快的排序方法 213

9.1 归并排序 213

9.1.1 归并数组 213

9.1.2 递归归并排序 214

9.1.3 归并排序的效率 216

9.1.4 迭代归并排序 217

9.1.5 Java类库中的归并排序 218

9.2 快速排序 218

9.2.1 快速排序的效率 219

9.2.2 创建划分 219

9.2.3 实现快速排序 221

9.2.4 Java类库中的快速排序 223

9.3 基数排序 223

9.3.1 基数排序的伪代码 225

9.3.2 基数排序的效率 225

9.4 算法比较 226

Java插曲4 再谈异常 231

第10章 队列、双端队列和优先队列 238

10.1 ADT队列 238

10.1.1 问题求解：模拟排队 241

10.1.2 问题求解：计算出售股票的资本收益 246

10.1.3 Java类库：接口Queue 248

10.2 ADT双端队列 249

10.2.1 问题求解：计算出售股票的资本收益 251

10.2.2 Java类库：接口Deque 252

10.2.3 Java类库：类ArrayDeque 253

10.3 ADT优先队列 254

10.3.1 问题求解：跟踪任务分配 255

10.3.2 Java类库：类PriorityQueue 257

第11章 队列、双端队列和优先队列的实现 262

11.1 队列的链式实现 262

11.2 基于数组实现队列 265

11.2.1 循环数组 266

11.2.2 带一个不用位置的循环数组 267

11.3 队列的循环链式实现 272

11.4 Java类库：类AbstractQueue 277

11.5 双端队列的双向链式实现 277

11.6 优先队列的可能实现方案 281

第12章 线性表 285

12.1 ADT线性表的规格说明 285

12.2 使用ADT线性表 291

12.3 Java类库：接口List 294

12.4 Java类库：类ArrayList 294

第13章 使用数组实现线性表 299

13.1 使用数组实现ADT线性表 299

13.1.1 类比 299

13.1.2 Java实现 301

13.1.3 使用数组实现ADT线性表的效率 308

第14章 使用链式数据实现线性表 313

14.1 链式结点链上的操作 313

14.1.1 在不同的位置添加结点 313

14.1.2 从不同的位置删除结点 316

14.1.3 私有方法getNodeAt 317

14.2 开始实现 318

14.2.1 数据域和构造方法 319

14.2.2 添加到线性表的表尾 320

14.2.3 在线性表的给定位置添加 321

14.2.4 方法isEmpty和toArray 322

14.2.5 测试核心方法 324

14.3 继续实现 325

14.4 细化实现 328

14.5 使用链实现ADT线性表的效率 331

14.6 Java类库：类LinkedList 333

Java插曲5 迭代器 338

第15章 ADT线性表的迭代器 351

15.1 实现迭代器的方法 351

15.2 独立类迭代器 351

15.3 内层类迭代器 354

15.3.1 链式实现 355

15.3.2 基于数组的实现 358

15.4 为什么迭代器方法在它自己的类中 360

15.5 基于数组实现接口ListIterator 362

Java插曲6 可变及不可变对象 372

第16章 有序表 378

16.1 ADT有序表的规格说明 378

16.2 链式实现 382

16.2.1 方法add 383

16.2.2 链式实现的效率 388

16.3 使用ADT线性表实现 388

Java插曲7 继承和多态 396

第17章 继承和线性表 405

17.1 使用继承实现有序表 405

17.2 设计一个基类 407

17.3 有序表的高效实现 413

第18章 查找 417

18.1 问题 417

18.2 在无序数组中查找 417

18.2.1 无序数组上的迭代顺序查找 418

18.2.2 无序数组上的递归顺序查找 418

18.2.3 顺序查找数组的效率 420

18.3 有序数组上的查找 420

18.3.1 有序数组上的顺序查找 420

18.3.2 有序数组上的二分查找 421

18.3.3 Java类库：方法binarySearch 424

18.3.4 数组上的二分查找的效率 425

18.4 无序链上的查找 426

18.4.1 无序链上的迭代顺序查找 426

18.4.2 无序链上的递归顺序查找 427

18.4.3 链上查找的效率 427

18.5 有序链上的查找 428

18.5.1 有序链上的顺序查找 428

18.5.2 有序链上的二分查找 428

18.6 查找方法的选择 429

Java插曲8 再论泛型 434

第19章 字典 436

19.1 ADT字典的规格说明 436

19.1.1 Java接口 439

19.1.2 迭代器 440

19.2 使用ADT字典 441

19.2.1 问题求解：电话号码簿 441

19.2.2 问题求解：字的频度 445

19.2.3 问题求解：字的词汇索引 448

19.3 Java类库：接口Map 451

第20章 字典的实现 455

20.1 基于数组的实现 455

20.1.1 基于数组的无序字典 455

20.1.2 基于数组的有序字典 459

20.2 链式实现 463

20.2.1 无序链式字典 464

20.2.2 有序链式字典 464

第21章 散列简介 470

21.1 什么是散列 470

21.2 散列函数 472

21.2.1 计算散列码 473

21.2.2 将散列码压缩为散列表的下标 475

21.3 解决冲突 476

21.3.1 开放地址的线性探查 476

21.3.2 开放地址的二次探查 480

21.3.3 开放地址的双散列 480

21.3.4 开放地址的潜在问题 482

21.3.5 拉链法 482

第22章 使用散列实现字典 488

22.1 散列的效率 488

22.1.1 装填因子 488

22.1.2 开放地址法的代价 489

22.1.3 拉链法的代价 490

22.2 再散列 491

22.3 冲突解决方案的比较 492

22.4 字典的散列实现 492

22.4.1 散列表中的项 492

22.4.2 数据域和构造方法 493

22.4.3 方法getValue/remove和add 495

22.4.4 迭代器 500

22.5 Java类库：类HashMap 501

22.6 Java类库：类HashSet 501

第23章 树 504

23.1 树的概念 504

23.1.1 层次结构 504

23.1.2 树的术语 505

23.2 树的遍历 509

23.2.1 二叉树的遍历 510

23.2.2 一般树的遍历 511

23.3 树的Java接口 512

23.3.1 所有树的接口 512

23.3.2 二叉树的接口 512

23.4 二叉树的示例 514

23.4.1 表达式树 514

23.4.2 决策树 515

23.4.3 二叉查找树 518

23.4.4 堆 520

23.5 一般树的示例 522

23.5.1 语法树 522

23.5.2 游戏树 523

第24章 树的实现 530

24.1 二叉树中的结点 530

24.2 ADT二叉树的实现 532

24.2.1 创建基本二叉树 532

24.2.2 方法privateSetTree 534

24.2.3 访问方法和赋值方法 536

24.2.4 计算高度和结点个数 536

24.2.5 遍历 537

24.3 表达式树的实现 541

24.4 一般树 543

24.5 使用二叉树表示一般树 543

Java插曲9 克隆 549

第25章 二叉查找树的实现 562

25.1 开始 562

25.1.1 二叉查找树的接口 563

25.1.2 重复项 564

25.1.3 开始定义类 565

25.2 查找和获取 566

25.3 遍历 567

25.4 添加一项 567

25.4.1 递归实现 568

25.4.2 迭代实现 571

25.5 删除一项 572

25.5.1 删除叶子结点中的项 573

25.5.2 删除仅有一个孩子的结点中的项 573

25.5.3 删除有两个孩子的结点中的项 574

25.5.4 删除根中的项 576

25.5.5 递归实现 576

25.5.6 迭代实现 579

25.6 操作效率 582

25.6.1 平衡的重要性 583

25.6.2 结点按什么次序添加 583

25.7 ADT字典的实现 584

第26章 堆的实现 594

26.1 再论：ADT堆 594

26.2 使用数组表示堆 594

26.3 添加项 597

26.4 删除根 599

26.5 创建堆 602

26.6 堆排序 603

第27章 平衡查找树 611

27.1 AVL树 611

27.1.1 单旋转 612

27.1.2 双旋转 614

27.1.3 实现细节 617

27.2 2-3树 620

27.2.1 在2-3树中进行查找 621

27.2.2 向2-3树中添加项 621

27.2.3 添加过程中分裂结点 623

27.3 2-4树 624

27.3.1 向2-4树中添加项 624

27.3.2 AVL树、2-3树和2-4树的比较 626

27.4 红黑树 626

27.4.1 红黑树的特性 627

27.4.2 向红黑树中添加项 628

27.4.3 Java类库：类TreeMap 632

27.5 B树 632

第28章 图 639

28.1 一些示例及术语 639

28.1.1 公路图 639

28.1.2 航空公司的航线 641

28.1.3 迷宫 642

28.1.4 先修课程 642

28.1.5 树 642

28.2 遍历 643

28.2.1 广度优先遍历 643

28.2.2 深度优先遍历 644

28.3 拓扑序 646

28.4 路径 648

28.4.1 寻找路径 648

28.4.2 无权图中的最短路径 648

28.4.3 带权图中的最短路径 651

28.5 ADT图的Java接口 654

第29章 图的实现 662

29.1 两个实现概述 662

29.1.1 邻接矩阵 662

29.1.2 邻接表 663

29.2 顶点和边 663

29.2.1 说明类Vertex 664

29.2.2 内部类Edge 666

29.2.3 类Vertex的实现 666

29.3 ADT图的实现 669

29.3.1 基本操作 669

29.3.2 图算法 672

附录A 文档和程序设计风格 678

附录B Java基础（在线） 682

附录C Java类（在线） 684

附录D 从其他类创建类 685

附录E 文件输入和输出（在线） 701

索引 702