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

目录 1

第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.3 Name类的定义 12

1.3.4　构造函数 13

1.3.5 toString方法 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.3　类型兼容性与基类 36

2.2.5　多重继承 36

2.3.1 Object类 37

2.3.2　抽象类与抽象方法 39

2.4　多态性 40

第3章　类的设计 50

3.1 封装 50

3.2　方法的说明 52

3.3 Java接口 55

3.3.1　编写接口 55

3.3.2　实现接口 57

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

3.3.3　作为数据类型的接口 58

3.3.5　扩展接口 59

3.3.6　接口中的符号常量 60

3.3.7　接口与抽象类的比较 61

3.4　类的选择 63

3.4.1　类的确定 64

3.4.2 CRC卡片 64

3.5　类的复用 66

第4章　线性表 70

4.1　ADT线性表说明 70

4.2　使用ADT线性表 78

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

4.3 Java类库：List接口 82

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

5.1.1 类比 87

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

5.1.2 Java实现 89

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

5.2.1　扩展数组 97

5.2.2　线性表新的实现 98

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

5.5 Java类库 104

5.5.1 ArrayList类 104

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

5.5.2 Serializable接口 105

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

6.1　链表 108

6.1.1　创建一个链表 109

6.1.2　创建另一个链表 111

6.1.3　仍创建一个链表 113

6.2 Node类 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.6　Java类库：LinkedList类 136

7.1　迭代器是什么 139

第7章　迭代器 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.1 Iterator接口 160

8.2　实现Iterator接口 163

8.2.1　基于链表实现 163

8.2.2　基于数组实现 165

8.3 ListIterator接口 168

8.4　基于数组实现ListIterator接口 174

8.5 Java类库：重温ArrayList和LinkedList 181

第9章　算法的效率 184

9.1　动机 184

9.2　度量算法的效率 186

9.3　形式化 192

9.4　效率的图形表示 194

9.5 ADT线性表不同实现的效率 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.1 countDown的时间效率 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.4　链表的插入排序 248

11.2.3　插入排序的效率 248

11.3　希尔排序 251

11.3.1　Java代码 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.5　Java类库中的归并排序 264

12.1.4　迭代归并排序 264

12.2　快速排序 265

12.2.1　快速排序的效率 265

12.2.2　创建划分 266

12.2.3　快速排序的Java代码 268

12.2.4　Java类库中的快速排序 272

12.3　基数排序 272

12.3.1　基数排序的伪代码 274

12.3.2　基数排序的效率 274

12.4　算法比较 275

13.1 ADT有序表的说明 280

第13章　有序表 280

13.2　链表实现 284

13.2.1 add方法 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.3.1　顺序查找有序数组 338

16.2.3　顺序查找数组的效率 338

16.3　查找有序数组 338

16.3.2　折半查找有序数组 339

16.3.3　Java类库：方法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.6　查找方法的选择 348

16.5.2　折半查找有序链表 348

第17章　词典 352

17.1 ADT词典的说明 352

17.1.1 Java接口 355

17.1.2　迭代器 356

17.2　使用ADT词典 357

17.2.1 电话号码簿 357

17.2.2　词频 361

17.2.3　词的索引 363

17.3 Java类库：Map接口 365

18.1　基于数组的实现 368

第18章　词典的实现 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.1　计算散列码 388

19.2　散列函数 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.8 Java类库：类HashMap 416

第20章　栈 421

20.1 ADT栈的说明 421

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

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

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

20.2.3　后缀表达式求值 437

20.2.4　中缀表达式求值 439

20.3　程序栈 441

20.4　使用栈代替递归 443

20.5 Java类库：类Stack 445

第21章　栈的实现 449

21.1　基于链表的实现 449

21.2　基于数组的实现 452

21.3　基于向量的实现 456

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

22.1　ADT队列的说明 460

22.2　使用队列模拟排队 464

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

22.4 ADT双端队列的说明 473

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

22.6　ADT优先队列的说明 476

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

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

23.1　基于链表实现队列 481

23.2.1　循环数组 485

23.2　基于数组实现队列 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.1　二叉树的遍历 513

24.2　树的遍历 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.2 BinaryNode的实现 536

25.2 ADT二叉树的实现 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.7 ADT词典的实现 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.1 AVL树 606

28.1.1　单旋转 607

28.1.2　双旋转 608

28.1.3 实现细节 612

28.2 2-3树 615

28.2.1 2-3树的查找 616

28.2.2　向2-3树插入元素 617

28.2.3　插入期间分裂节点 619

28.3 2-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.3 Java类库：类TreeMap 629

28.5 B树 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.2　深度优先遍历 639

29.2.1　广度优先遍历 639

29.3　拓扑顺序 642

29.4　路径 644

29.4.1　寻找路径 644

29.4.2　无权图中的最短路径 644

29.4.3 带权图中的最短路径 647

29.5 ADT图的Java接口 650

第30章　图的实现 657

30.1 两种实现的概述 657

30.1.1　邻接矩阵 657

30.1.2　邻接表 658

30.2.1　说明类Vertex 659

30.2　顶点与边 659

30.2.2　类Edge 661

30.2.3　实现类Vertex 663

30.3 ADT图的实现 664

30.3.1 基本操作 665

30.3.2　图的算法 668

附录A Java基础 673

附录B　异常处理 723

附录C　文件输入与输出 732

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

附录E 自测题答案 754