数据结构与算法分析 JAVA语言描述 第2版PDF电子书下载

第0章 引言 1

第1章　Java类 2

1.1　对象与类 2

1.2　在Java类中使用方法 5

1.3 定义Java类 7

1.3.1　方法定义 8

1.3.2　实参与形参 10

1.3.3　传递实参 11

1.3.4　Name类的定义 14

1.3.5　构造函数 16

1.3.6　toString方法 18

1.3.7　调用其他方法的方法 18

1.3.8　返回所属类实例的方法 20

1.3.9　静态域与静态方法 20

1.3.10　方法的重载 22

1.4　枚举类 23

1.5　包 26

本章小结 27

练习 28

项目设计 31

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

2.1 合成 35

2.1.1　通用类型 38

2.1.2　适配器 41

2.2　继承 42

2.2.1　从构造函数中调用构造函数 45

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

2.2.3　受保护的访问 47

2.2.4　方法的覆盖与重载 47

2.2.5　多重继承 52

2.3　类型兼容性与基类 53

2.3.1　Object类 54

2.3.2　抽象类与抽象方法 56

2.4　多态性 58

本章小结 63

练习 64

项目设计 68

第3章　类的设计 70

3.1　封装 70

3.2　方法的说明 72

3.3　接口 76

3.3.1 编写接口 76

3.3.2　实现接口 78

3.3.3　作为数据类型的接口 79

3.3.4　接口的通用类型 80

3.3.5　Comparable接口 80

3.3.6　扩展接口 82

3.3.7　接口与抽象类 83

3.3.8　符号常量 85

3.4　类的选择 86

3.4.1　类的确定 87

3.4.2　CRC卡片 88

3.5　类的复用 91

本章小结 91

练习 92

项目设计 93

第4章　线性表 96

4.1　ADT线性表说明 96

4.2　使用ADT线性表 103

4.3　像使用自动售货机一样使用线性表 107

4.4　Java类库：List接口 109

本章小结 109

练习 110

项目设计 112

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

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

5.1.1　类比 114

5.1.2　Java实现 116

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

5.2.1 扩展数组 125

5.2.2　线性表的新实现 127

5.3　Java类库：ArrayList与Vector类 128

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

本章小结 133

练习 134

项目设计 135

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

6.1 链表 136

6.1.1　在表头添加来创建链表 137

6.1.2　在表末添加来创建链表 138

6.1.3 在不同位置添加来创建链表 140

6.2　使用链表实现ADT线性表 142

6.2.1　私有类Node 142

6.2.2　数据域与构造函数 144

6.2.3　选择要实现的核心方法组 145

6.2.4　在线性表的末端插入元素 146

6.2.5 在线性表的指定位置插入元素 148

6.2.6　私有方法getNodeAt 152

6.2.7　断言与isEmpty方法 153

6.2.8　display方法 154

6.3　测试不完整的实现 155

本章小结 157

练习 158

项目设计 159

第7章　完成线性表的链表实现 160

7.1　从链表中删除一个元素 160

7.2　完成ADT线性表的链表实现 162

7.2.1　方法remove 162

7.2.2　方法replace 165

7.2.3　方法getEntry 165

7.2.4　方法contains 166

7.2.5　其他方法 166

7.3　使用具有设置与获取方法的Node类 167

7.4　表尾引用 170

7.5 用链表实现ADT线性表的优缺点 175

7.6　Java类库：LinkedList类 175

本章小结 176

练习 176

项目设计 177

第8章　迭代器 179

8.1　什么是迭代器 179

8.2　Iterator接口 180

8.3　独立类迭代器 186

8.4　内部类迭代器 189

8.4.1　基于链表实现 190

8.4.2　基于数组实现 194

8.5　迭代器方法为何在自己的类中 197

8.6　ListIterator接口 198

8.7 基于数组实现ListIterator接口 204

8.8　Java类库：Iterable接口 211

8.8.1　Iterable与for-each循环 212

8.8.2　重温List接口 212

本章小结 213

练习 213

项目设计 216

第9章　算法的效率 218

9.1　动机 218

9.2　度量算法的效率 220

9.3　形式化 226

9.4　效率的图形表示 229

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

9.5.1　基于数组实现 232

9.5.2　基于链表实现 234

9.5.3　比较上述实现 237

本章小结 238

练习 238

项目设计 240

第10章 递归 243

10.1　何谓递归 243

10.2　跟踪递归方法 248

10.3　有返回值的递归方法 250

10.4　递归处理数组 253

10.5　递归处理链表 255

10.6　递归方法的时间效率 257

10.6.1　countDown的时间效率 257

10.6.2　计算xn的时间效率 258

10.7　困难问题的简单解法 259

10.8　简单问题的拙劣解法 264

10.9　尾递归 266

10.10　协同递归 268

本章小结 268

练习 270

项目设计 271

第11章　排序入门 275

11.1　组织用于数组排序的Java方法 276

11.2　选择排序 277

11.2.1　迭代选择排序 278

11.2.2　递归选择排序 280

11.2.3　选择排序的效率 281

11.3　插入排序 282

11.3.1　迭代插入排序 283

11.3.2　递归插入排序 284

11.3.3　插入排序的效率 286

11.3.4　链表的插入排序 286

11.4　希尔排序 289

11.4.1　Java代码 291

11.4.2　希尔排序的效率 292

11.5　算法比较 293

本章小结 293

练习 293

项目设计 296

第12章　快速排序算法 298

12.1　归并排序 298

12.1.1　数组的归并 298

12.1.2　递归归并排序 299

12.1.3　归并排序的效率 302

12.1.4　迭代归并排序 303

12.1.5　Java类库中的归并排序 304

12.2　快速排序 304

12.2.1　快速排序的效率 305

12.2.2　创建划分 305

12.2.3　快速排序的Java代码 308

12.2.4　Java类库中的快速排序 311

12.3　基数排序 311

12.3.1　基数排序的伪代码 313

12.3.2　基数排序的效率 313

12.4　算法比较 314

本章小结 314

练习 315

项目设计 316

第13章　有序表 319

13.1 ADT有序表的说明 319

13.2　链表实现 323

13.2.1　add方法 324

13.2.2　链表实现的效率 331

13.3　使用ADT线性表的实现 331

本章小结 336

练习 336

项目设计 337

第14章　继承与线性表 339

14.1　使用继承实现有序表 339

14.2　设计一个基类 342

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

本章小结 349

练习 350

项目设计 350

第15章　可变对象、不可变对象与可克隆对象 352

15.1　可变对象与不可变对象 352

15.1.1　创建只读类 355

15.1.2　同伴类 356

15.2　可克隆对象 358

15.2.1　克隆数组 364

15.2.2　克隆链表 366

15.2.3　克隆体的有序表 370

本章小结 373

练习 373

项目设计 376

第16章 查找 377

16.1 问题描述 377

16.2　查找无序数组 378

16.2.1　迭代顺序查找无序数组 378

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

16.2.3　顺序查找数组的效率 381

16.3　查找有序数组 381

16.3.1　顺序查找有序数组 381

16.3.2　折半查找有序数组 382

16.3.3　Java类库：binarySearch方法 386

16.3.4　折半查找数组的效率 387

16.4　查找无序链表 388

16.4.1　迭代顺序查找无序链表 388

16.4.2　递归顺序查找无序链表 389

16.4.3　顺序查找链表的效率 390

16.5　查找有序链表 390

16.5.1　顺序查找有序链表 390

16.5.2　折半查找有序链表 391

16.6　查找方法的选择 391

本章小结 392

练习 392

项目设计 394

第17章　词典 396

17.1　ADT词典的说明 396

17.1.1　Java接口 399

17.1.2　迭代器 400

17.2　使用ADT词典 402

17.2.1　电话号码簿 402

17.2.2　词频 407

17.2.3　词的索引 411

17.3　Java类库：Map接口 414

本章小结 415

练习 415

项目设计 416

第18章　词典的实现 418

18.1　基于数组的实现 418

18.1.1　基于数组的无序词典 419

18.1.2　基于数组的有序词典 424

18.2　基于向量的实现 428

18.3　基于链表的实现 433

18.3.1　基于链表的无序词典 434

18.3.2　基于链表的有序词典 434

本章小结 438

练习 438

项目设计 439

第19章　散列概述 440

19.1　什么是散列 440

19.2　散列函数 442

19.2.1　计算散列码 443

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

19.3　处理冲突 446

19.3.1　线性探测开放定址 446

19.3.2　二次探测开放定址 451

19.3.3　双散列开放定址 451

19.3.4　开放定址的潜在问题 453

19.3.5　链地址 453

本章小结 456

练习 457

项目设计 458

第20章　用散列实现词典 459

20.1　效率 459

20.1.1　装填因子 460

20.1.2　开放定址的开销 460

20.1.3　链地址的开销 462

20.2　再散列 463

20.3　处理冲突的各方案比较 464

20.4　使用散列的词典实现 465

20.4.1　散列表中的元素 465

20.4.2　数据域与构造函数 466

20.4.3　方法getValue、remove和add 467

20.4.4　迭代器 473

20.5　Java类库：类HashMap 475

本章小结 475

练习 476

项目设计 476

第21章　栈 478

21.1 ADT栈的说明 478

21.2　利用栈处理代数表达式 481

21.2.1　检查中缀代数表达式的括号是否平衡 482

21.2.2　将中缀表达式转化为后缀表达式 487

21.2.3　后缀表达式求值 493

21.2.4　中缀表达式求值 495

21.3　程序栈 497

21.4　使用栈代替递归 498

21.5　Java类库：类Stack 501

本章小结 502

练习 502

项目设计 504

第22章　栈的实现 506

22.1　基于链表的实现 506

22.2　基于数组的实现 509

22.3　基于向量的实现 513

本章小结 515

练习 515

项目设计 516

第23章　队列、双端队列与优先队列 517

23.1　ADT队列的描述 517

23.2　使用队列模拟排队 521

23.3　使用队列计算股份销售的资本收益 527

23.4　Java类库：Queue接口 530

23.5　ADT双端队列的描述 530

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

23.7　ADT优先队列的描述 534

23.8　使用优先队列跟踪委派任务 535

本章小结 537

练习 537

项目设计 539

第24章 队列、双端队列与优先队列的实现 541

24.1　基于链表的队列实现 541

24.2　基于数组的队列实现 545

24.2.1　循环数组 546

24.2.2 含有一个未用位置的循环数组 547

24.3　基于向量的队列实现 552

24.4　基于循环链表的队列实现 554

24.5　Java类库：AbstractQueue类 560

24.6　基于双向链表的双端队列实现 560

24.7　实现优先队列的可用方法 564

24.8　Java类库：PriorityQueue类 564

本章小结 565

练习 566

项目设计 567

第25章　树 569

25.1　树的概念 569

25.1.1　层次化的组织 569

25.1.2　树的术语 571

25.2　树的遍历 574

25.2.1　二叉树的遍历 575

25.2.2　树的遍历 576

25.3　树的Java接口 577

25.3.1　所有树的接口 577

25.3.2　二叉树的接口 578

25.4　二叉树举例 579

25.4.1　表达式树 580

25.4.2　决策树 581

25.4.3　二叉查找树 585

25.4.4　堆 587

25.5　树举例 589

25.5.1　语法分析树 589

25.5.2　博弈树 590

本章小结 590

练习 591

项目设计 593

第26章　树的实现 595

26.1　二叉树的结点 595

26.1.1　结点的接口 596

26.1.2　BinaryNode的实现 597

26.2　ADT二叉树的实现 599

26.2.1　创建基本二叉树 599

26.2.2 方法privateSetTree 600

26.2.3　访问者与修改者方法 603

26.2.4　计算高度与统计结点 604

26.2.5　遍历 605

26.3　表达式二叉树的实现 610

26.4　树 612

26.4.1　树的结点 612

26.4.2　用二叉树表示树 613

本章小结 614

练习 614

项目设计 616

第27章　二叉查找树的实现 617

27.1　预备知识 617

27.1.1　二叉查找树接口 618

27.1.2　重复元素 620

27.1.3　开始类定义 621

27.2　查找与检索 622

27.3　遍历 624

27.4　插入元素 624

27.4.1　递归实现 625

27.4.2　迭代实现 628

27.5　删除元素 631

27.5.1　删除叶子结点中的元素 631

27.5.2　删除有一个孩子的结点中的元素 631

27.5.3　删除有两个孩子的结点中的元素 631

27.5.4　删除根结点中的元素 635

27.5.5　递归实现 635

27.5.6　迭代实现 639

27.6　操作的效率 643

27.6.1　平衡的重要性 644

27.6.2　插入结点的顺序 644

27.7　ADT词典的实现 645

本章小结 648

练习 649

项目设计 651

第28章　堆的实现 653

28.1　再论ADT堆 653

28.2　用数组表示堆 654

28.3　插入元素 656

28.4　删除根 659

28.5　创建堆 662

28.6　堆排序 664

本章小结 667

练习 668

项目设计 669

第29章　平衡查找树 670

29.1　AVL树 670

29.1.1　单旋转 671

29.1.2　双旋转 673

29.1.3　实现细节 676

29.2　2-3树 681

29.2.1　2-3树的查找 681

29.2.2　往2-3树插入元素 682

29.2.3　插入期间分裂结点 683

29.3　2-4树 685

29.3.1　往2-4树插入元素 685

29.3.2　比较AVL树、2-3树和2-4树 686

29.4　红黑树 687

29.4.1　红黑树的特性 688

29.4.2　往红黑树插入元素 689

29.4.3　Java类库：类TreeMap 693

29.5　B树 693

本章小结 694

练习 695

项目设计 696

第30章　图 697

30.1　一些例子与术语 697

30.1.1　公路地图 697

30.1.2　航线 700

30.1.3　迷宫 700

30.1.4　先修课程 701

30.1.5　树 701

30.2　遍历 701

30.2.1　广度优先遍历 702

30.2.2　深度优先遍历 704

30.3　拓扑顺序 705

30.4　路径 707

30.4.1　寻找路径 708

30.4.2　无权图的最短路径 708

30.4.3　加权图的最短路径 710

30.5 ADT图的Java接口 714

本章小结 717

练习 718

项目设计 720

第31章　图的实现 722

31.1　两种实现的概述 722

31.1.1　邻接矩阵 722

31.1.2　邻接表 723

31.2　顶点与边 724

31.2.1　说明类Vertex 724

31.2.2　内部类Edge 726

31.2.3　实现Vertex类 727

31.3　ADT图的实现 731

31.3.1　基本操作 731

31.3.2 图的算法 735

本章小结 737

练习 738

项目设计 739

附录A　Java基础 741

A.1 引言 741

A.1.1　应用程序和小程序 741

A.1.2　对象和类 741

A.1.3　第一个Java应用程序 741

A.2　Java基础 744

A.2.1　标识符 744

A.2.2　保留字 744

A.2.3　变量 745

A.2.4　基本类型 745

A.2.5　常量 746

A.2.6　赋值语句 746

A.2.7　赋值兼容性 747

A.2.8　类型转换 748

A.2.9　算术运算符和表达式 749

A.2.10　括号和优先规则 750

A.2.11 自增和自减运算符 751

A.2.12　特殊赋值运算符 752

A.2.13　符号常量 752

A.2.14　Math类 753

A.3 用键盘和屏幕进行简单的输入和输出 754

A.3.1　屏幕输出 754

A.3.2 用Scanner类进行键盘输入 755

A.4　if-else语句 757

A.4.1　布尔表达式 758

A.4.2　嵌套语句 761

A.4.3　多重if-else语句 763

A.4.4　条件运算符（可选） 764

A.5　switch语句 764

A.6　枚举 766

A.7　作用域 768

A.8　循环 769

A.8.1　while语句 769

A.8.2　for语句 770

A.8.3　do-while语句 772

A.8.4　关于循环的其他信息 773

A.9　String类 774

A.9.1　字符串中的字符 775

A.9.2　字符串的联接 776

A.9.3　String方法 777

A.10　StringBuilder类 779

A.11 使用Scanner抽取字符串的一部分 780

A.12　数组 783

A.12.1　数组形参和返回值 785

A.12.2　初始化数组 786

A.12.3　数组索引出界 786

A.12.4 对数组使用＝与＝＝ 786

A.12.5　数组与for-each循环 788

A.12.6　多维数组 788

A.12　封装类 790

附录B　异常处理 796

B.1　基本的异常处理 796

B.2　Java类库的异常类 799

B.3　定义自己的异常类 800

B.4　复合catch代码块 802

B.5　finally代码块 803

B.6　抛出但不捕获异常的方法 804

B.7　不需要捕获的异常 805

附录C　文件输入与输出 807

C.1　概述 807

C.1.1　数据流 807

C.1.2　文件的优点 807

C.1.3　文件的类型 808

C.1.4　文件名 809

C.1.5　包java.io 809

C.2　使用PrintWriter写文本文件 809

C.3　读取文本文件 812

C.3.1　使用Scanner读取文本文件 812

C.3.2　使用BufferedReader读取文本文件 814

C.3.3　定义打开数据流的方法 816

C.4　二进制文件的I/O 817

C.4.1　使用DataOutputStream写二进制文件 817

C.4.2　使用DataInputStream读取二进制文件 821

C.5　File类 823

C.6　对象串行化 824

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

D.1　命名变量与类 828

D.2　缩排 828

D.3　注释 829

D.3.1　单行注释 829

D.3.2　注释块 830

D.3.3　何时写注释 830

D.3.4　Java文档注释 830

D.3.5　运行javadoc 832

附录E　自测题答案 833