数据结构与问题求解 Java语言版 第4版PDF电子书下载

第1部分 Java教程 3

第1章 Java基础知识 3

1．1 通用环境 3

1．2 第一个程序 4

1．2．1 注释 4

1．2．2 main 5

1．2．3 终端输出 5

1．3 基本类型 5

1．3．1 概述 5

1．3．2 常量 6

1．3．3 基本类型的声明与初始化 6

1．3．4 终端输入与输出 7

1．4 基本运算符 7

1．4．1 赋值运算符 7

1．4．2 二元算术运算符 8

1．4．3 一元运算符 8

1．4．4 类型转换 9

1．5 条件语句 9

1．5．1 关系和相等运算符 10

1．5．2 逻辑运算符 10

1．5．3 if语句 11

1．5．4 while语句 12

1．5．5 for语句 13

1．5．6 do语句 13

1．5．7 break和continue 14

1．5．8 switch语句 15

1．5．9 条件运算符 15

1．6 方法 16

1．6．1 方法名重载 17

1．6．2 存储类 18

本章小结 18

重要概念 18

常见错误 20

网上资源 20

练习 20

简答题 20

理论题 21

实践题 21

程序设计题 22

参考文献 22

第2章 引用类型 23

2．1 什么是引用 23

2．2 对象和引用基础 24

2．2．1 点（．）运算符 25

2．2．2 对象的声明 25

2．2．3 垃圾回收 26

2．2．4 =的含义 26

2．2．5 参数传递 27

2．2．6 ==的含义 28

2．2．7 对象的无运算符重载 29

2．3 字符串 29

2．3．1 字符串处理基础 29

2．3．2 字符串连接 30

2．3．3 字符串比较 30

2．3．4 其他String方法 30

2．3．5 将其他类型转换成字符串 31

2．4 数组 31

2．4．1 声明、赋值与方法 32

2．4．2 动态数组扩展 34

2．4．3 ArrayList 36

2．4．4 多维数组 37

2．4．5 命令行参数 38

2．4．6 增强的for循环 39

2．5 异常处理 40

2．5．1 概述 40

2．5．2 finally子句 41

2．5．3 常见的异常 41

2．5．4 throw和throws子句 42

2．6 输入与输出 43

2．6．1 基本流操作 43

2．6．2 Scanner类型 44

2．6．3 顺序文件 46

本章小结 49

重要概念 49

常见错误 50

网上资源 51

练习 51

简答题 51

理论题 51

实践题 52

程序设计题 54

参考文献 56

第3章 对象与类 57

3．1 什么是面向对象编程 57

3．2 简单示例 58

3．3 javadoc 60

3．4 基本方法 62

3．4．1 构造函数 62

3．4．2 存取器和访问器 62

3．4．3 输出与toString 63

3．4．4 equals 64

3．4．5 main 64

3．5 示例：使用java.math.BigInteger 64

3．6 其他构造 66

3．6．1 this引用 66

3．6．2 用于构造函数的this缩写 67

3．6．3 instanceof运算符 67

3．6．4 实例成员与静态成员 68

3．6．5 静态字段与方法 68

3．6．6 静态初始化块 70

3．7 示例：实现BigRational类 71

3．8 包 74

3．8．1 import指令 75

3．8．2 package语句 76

3．8．3 CLASSPATH环境变量 77

3．8．4 包可见性规则 77

3．9 设计模式：组合（对） 78

本章小结 79

重要概念 80

常见错误 81

网上资源 82

练习 82

简答题 82

理论题 83

实践题 83

程序设计题 85

参考文献 87

第4章 继承 88

4．1 什么是继承 88

4．1．1 创建新类 89

4．1．2 类型兼容性 92

4．1．3 动态分配和多态性 93

4．1．4 继承层次结构 94

4．1．5 可见性规则 95

4．1．6 构造函数与super 95

4．1．7 final方法和类 96

4．1．8 重写方法 97

4．1．9 类型兼容性修正 99

4．1．10 数组类型的兼容性 100

4．1．11 协变返回类型 100

4．2 设计层次结构 101

4．2．1 抽象方法与抽象类 103

4．2．2 未来的设计 105

4．3 多重继承 106

4．4 接口 108

4．4．1 指定接口 108

4．4．2 实现接口 108

4．4．3 多接口 109

4．4．4 接口是抽象类 109

4．5 Java的基本继承 110

4．5．1 Object类 110

4．5．2 异常的层次结构 110

4．5．3 I／O装饰模式 110

4．6 使用继承实现泛型组件 114

4．6．1 使用Object的泛型 114

4．6．2 基本类型的包装 115

4．6．3 自动装包／拆包 117

4．6．4 适配器：改变接口 117

4．6．5 泛型所使用的接口类型 118

4．7 使用Java 5泛型实现泛型组件 120

4．7．1 简单的泛型类和接口 121

4．7．2 通配符的绑定 121

4．7．3 泛型的静态方法 123

4．7．4 类型绑定 123

4．7．5 类型擦除 124

4．7．6 泛型的限制 125

4．8 函子（函数对象） 127

4．8．1 嵌套类 130

4．8．2 局部类 130

4．8．3 匿名类 132

4．8．4 嵌套类和泛型 132

4．9 动态分配细节 133

本章小结 135

重要概念 136

常见错误 138

网上资源 138

习题 139

简答题 139

理论题 140

实践题 142

程序设计题 144

参考文献 146

第2部分 算法与构件块 149

第5章 算法分析 149

5．1 什么是算法分析 149

5．2 算法运行时间的示例 152

5．3 最大连续子序列和的问题 153

5．3．1 简单O（N3）算法 154

5．3．2 改进的O（N2）算法 156

5．3．3 线性算法 157

5．4 一般的大O规则 159

5．5 对数 162

5．6 静态查找问题 164

5．6．1 顺序查找 164

5．6．2 二分查找 164

5．6．3 插值查找 167

5．7 检查算法分析 168

5．8 大O分析的局限性 169

本章小结 169

重要概念 170

常见错误 170

网上资源 171

练习 171

简答题 171

理论题 172

实践题 176

程序设计题 178

参考文献 179

第6章 集合类API 181

6．1 概述 181

6．2 迭代器模式 182

6．2．1 基本的迭代器设计 183

6．2．2 基于继承的迭代器和工厂方法 185

6．3 集合类API：容器和迭代器 186

6．3．1 Collection接口 187

6．3．2 Iterator接口 189

6．4 泛型算法 191

6．4．1 Comparator函数对象 192

6．4．2 Collections类 192

6．4．3 二分查找 194

6．4．4 排序 194

6．5 List接口 196

6．5．1 ListIterator接口 196

6．5．2 LinkedList类 197

6．5．3 Lists的运行时间 200

6．5．4 从List中间删除和插入 202

6．6 栈与队列 204

6．6．1 栈 204

6．6．2 栈与计算语言 205

6．6．3 队列 206

6．6．4 在集合类API中的栈与队列 207

6．7 集合 207

6．7．1 TreeSet类 208

6．7．2 HashSet类 209

6．8 映射 213

6．9 优先级队列 217

6．10 集合类API中的视图 219

6．10．1 List的subList方法 219

6．10．2 SortedSet的headSet、subSet和tailSet方法 220

本章小结 220

重要概念 221

常见错误 222

网上资源 222

练习 223

简答题 223

理论题 223

实践题 224

程序设计题 229

参考文献 231

第7章 递归 232

7．1 什么是递归 232

7．2 背景知识：数学归纳法证明 233

7．3 基本递归 235

7．3．1 以任意基数打印数 236

7．3．2 运行的原因 238

7．3．3 如何运行 239

7．3．4 太多的递归是危险的 240

7．3．5 树的预备知识 241

7．3．6 其他的例子 242

7．4 数值应用 245

7．4．1 模运算 246

7．4．2 模的幂运算 246

7．4．3 最大公约数和乘法逆元素 247

7．4．4 RSA密码系统 250

7．5 分治算法 252

7．5．1 最大连续子序列和的问题 252

7．5．2 基本分治循环的分析 254

7．5．3 分治运行时间的一般上界 257

7．6 动态规划 259

7．7 回溯 262

本章小结 265

重要概念 265

常见错误 266

网上资源 266

练习 267

简答题 267

理论题 267

实践题 269

程序设计题 270

参考文献 273

第8章 排序算法 274

8．1 排序为什么重要 274

8．2 预备知识 275

8．3 插入排序和其他简单排序的分析 275

8．4 希尔排序 278

8．4．1 希尔排序的性能 279

8．5 归并排序 281

8．5．1 以线性时间归并有序数组 281

8．5．2 归并排序算法 283

8．6 快速排序 284

8．6．1 概述 285

8．6．2 快速排序分析 287

8．6．3 选择支点 290

8．6．4 分割策略 291

8．6．5 键等于支点 292

8．6．6 三个元素的中值分割 293

8．6．7 小数组 294

8．6．8 Java的快速排序例程 294

8．7 快速选择 296

8．8 排序的下限 297

本章小结 298

重要概念 299

常见错误 299

网上资源 299

练习 300

简答题 300

理论题 300

实践题 301

程序设计题 302

参考文献 304

第9章 随机化 305

9．1 为什么需要随机数 305

9．2 随机数发生器 306

9．3 非均匀随机数 312

9．4 生成随机排列 313

9．5 随机算法 314

9．6 随机素性测试 316

本章小结 319

重要概念 319

常见错误 320

网上资源 320

练习 321

简答题 321

理论题 321

实践题 321

程序设计题 321

参考文献 322

第3部分 应用 327

第10章 娱乐与游戏 327

10．1 纵横找单词 327

10．1．1 理论 327

10．1．2 Java实现 329

10．2 井字游戏 334

10．2．1 α-β剪枝 334

10．2．2 置换表 336

10．2．3 计算机下棋 339

本章小结 340

重要概念 340

常见错误 341

网上资源 341

练习 341

简答题 341

理论题 342

实践题 342

程序设计题 342

参考文献 343

第11章 栈与编译器 344

11．1 平衡符号检查器 344

11．1．1 基本算法 344

11．1．2 实现 345

11．2 简单的计算器 353

11．2．1 后缀机 354

11．2．2 中缀到后缀的转换 354

10．2．3 实现 357

10．2．4 表达式树 363

本章小结 364

重要概念 364

常见错误 365

网上资源 365

练习 365

简答题 365

理论题 366

实践题 366

程序设计题 366

参考文献 367

第12章 实用程序 368

12．1 文件压缩 368

12．1．1 前缀码 369

12．1．2 霍夫曼算法 370

12．1．3 实现 372

12．2 交叉引用生成器 384

12．2．1 基本思想 384

12．2．2 Java实现 384

本章小结 387

重要概念 388

常见错误 388

网上资源 388

练习 388

简答题 388

理论题 389

实践题 389

程序设计题 390

参考文献 392

第13章 模拟 393

13．1 约瑟夫问题 393

13．1．1 简单的解决方案 394

13．1．2 更高效的算法 395

13．2 事件驱动模拟 397

13．2．1 基本思想 397

13．2．2 示例：电话银行模拟 398

本章小结 404

重要概念 405

常见错误 405

网上资源 405

练习 405

简答题 405

理论题 405

实践题 406

程序设计题 406

第14章 图与路径 407

14．1 图的定义 407

14．1．1 图的表示 409

14．2 无权最短路径问题 417

14．2．1 理论 418

14．2．2 Java实现 420

14．3 非负权值的最短路径问题 421

14．3．1 理论：dijkstra算法 421

14．3．2 Java实现 424

14．4 负权值的最短路径问题 425

14．4．1 理论 426

14．4．2 Java实现 426

14．5 在无环图中的路径问题 427

14．5．1 拓扑排序 428

14．5．2 无环图最短路径算法的理论 429

14．5．3 Java实现 430

14．5．4 应用：关键路径分析 432

本章小结 434

重要概念 434

常见错误 435

网上资源 435

练习 435

简答题 435

理论题 436

实践题 437

程序设计题 437

参考文献 438

第4部分 实现 443

第15章 内部类和ArrayList的实现 443

15．1 迭代器和嵌套类 443

15．2 迭代器和内部类 445

15．3 AbstractCollection类 447

15．4 StringBuilder 450

15．5 使用迭代器的ArrayList的实现 451

本章小结 456

重要概念 456

常见错误 456

网上资源 456

练习 456

简答题 456

理论题 457

实践题 457

程序设计题 457

第16章 栈与队列 459

16．1 动态数组实现 459

16．1．1 栈 459

16．1．2 队列 462

16．2 链表实现 467

16．2．1 栈 467

16．2．2 队列 469

16．3 两种方法的比较 473

16．4 java.util.Stack类 473

16．5 双端队列 474

本章小结 475

重要概念 475

常见错误 475

网上资源 475

练习 475

简答题 475

实践题 476

程序设计题 476

第17章 链表 477

17．1 基本思想 477

17．1．1 头结点 478

17．1．2 迭代器类 479

17．2 Java实现 480

17．3 双链表和循环链表 485

17．4 有序链表 487

17．5 集合类AIP LinkedList类的实现 488

本章小结 498

重要概念 498

常见错误 498

网上资源 498

练习 499

简答题 499

理论题 499

实践题 499

程序设计题 500

第18章 树 502

18．1 一般树 502

18．1．1 定义 502

18．1．2 实现 503

18．1．3 应用：文件系统 504

18．2 二叉树 507

18．3 递归与树 512

18．4 树的遍历：迭代器类 514

18．4．1 后序遍历 516

18．4．2 中序遍历 520

18．4．3 前序遍历 521

18．4．4 层序遍历 523

本章小结 524

重要概念 524

常见错误 525

网上资源 525

练习 526

简答题 526

理论题 527

实践题 527

程序设计题 527

第19章 二叉查找树 529

19．1 基本思想 529

19．1．1 操作 530

19．1．2 Java实现 531

19．2 顺序统计量 537

19．2．1 Java实现 538

19．3 二叉查找树操作的分析 541

19．4 AVL树 543

19．4．1 性质 544

19．4．2 单旋转 546

19．4．3 双旋转 548

19．4．4 AVL插入总结 550

19．5 红黑树 550

19．5．1 自底而上的插入 551

19．5．2 自顶而下的红黑树 553

19．5．3 Java实现 554

19．5．4 自顶而下的删除 560

19．6 AA树 561

19．6．1 插入 562

19．6．2 删除 564

19．6．3 Java实现 565

19．7 集合类API中TreeSet类和TreeMap类的实现 569

19．8 B树 582

本章小结 587

重要概念 588

常见错误 588

网上资源 589

练习 589

简答题 589

理论题 589

实践题 590

程序设计题 590

参考文献 593

第20章 散列表 595

20．1 基本思想 595

20．2 散列函数 596

20．2．1 在java.1ang.String中的hashCode 598

20．3 线性探测法 599

20．3．1 线性探测法的简单分析 600

20．3．2 真的发生了什么：初始聚类 601

20．3．3 find操作的分析 602

20．4 二次探测法 603

20．4．1 Java实现 606

20．4．2 二次探测法的分析 613

20．5 分离链接散列 614

20．6 散列表与二叉查找树的比较 616

20．7 散列的应用 616

本章小结 616

重要概念 617

常见错误 617

网上资源 618

练习 618

简答题 618

理论题 618

实践题 619

程序设计题 619

参考文献 620

第21章 优先级队列：二叉堆 622

21．1 基本思想 622

21．1．1 结构性质 623

21．1．2 堆序性质 624

21．1．3 允许的操作 624

21．2 基本操作的实现 627

21．2．1 插入 627

21．2．2 deleteMin操作 628

21．3 buildHeap操作：线性时间的堆构造 630

21．4 高级操作：decreaseKey和merge 633

21．5 内部排序：堆排序 634

21．6 外部排序 636

21．6．1 为什么需要新算法 636

21．6．2 外部排序的模型 636

21．6．3 简单算法 636

21．6．4 多路归并 638

21．6．5 多相归并 639

21．6．6 置换选择 640

本章小结 641

重要概念 642

常见错误 642

网上资源 642

练习 643

简答题 643

理论题 643

实践题 645

程序设计题 645

参考文献 646

第5部分 高级数据结构 649

第22章 伸展树 649

22．1 自调整和平摊分析 649

22．1．1 平摊时间限定 650

22．1．2 简单的自调整策略（不能运行） 650

22．2 基本自底向上的伸展树 652

22．3 基本伸展树的操作 653

22．4 自底向上伸展树的分析 654

22．4．1 伸展限定的证明 656

22．5 自顶向下的伸展树 658

22．6 自顶向下伸展树的实现 661

22．7 伸展树与其他查找树的比较 665

本章小结 665

重要概念 665

常见错误 666

网上资源 666

练习 666

简答题 666

理论题 666

实践题 667

程序设计题 667

参考文献 667

第23章 归并优先级队列 668

23．1 斜堆 668

23．1．1 归并是一种基本操作 668

23．1．2 具有堆有序性树的简化归并 669

23．1．3 斜堆：一个简单的修改 669

23．1．4 斜堆的分析 670

23．2 偶堆 672

23．2．1 偶堆操作 672

23．2．2 偶堆的实现 674

23．2．3 应用：dijkstra的最短加树路径算法 679

本章小结 681

重要概念 681

常见错误 681

网上资源 681

练习 682

简答题 682

理论题 682

实践题 682

程序设计题 682

参考文献 683

第24章 不相交集类 684

24．1 等价关系 684

24．2 动态等价与应用 685

24．2．1 应用：生成迷宫 686

24．2．2 应用：最小生成树 687

24．2．3 应用：最近共同祖先问题 689

24．3 快速查找算法 692

24．4 快速并算法 693

24．4．1 智能并算法 694

24．4．2 路径压缩 696

24．5 Java实现 697

24．6 按秩并和路径压缩的最坏情况 699

24．6．1 并／查找算法的分析 699

本章小结 704

重要概念 704

常见错误 705

网上资源 705

练习 705

简答题 705

理论题 706

实践题 706

程序设计题 706

参考文献 707

附录A 运算符 709

附录B 图形化用户界面 710

B．1 抽象窗口工具包和Swing 710

B．2 在Swing中的基本对象 711

B．2．1 组件 712

B．2．2 容器 713

B．2．3 顶级容器 713

B．2．4 JPanel 714

B．2．5 重要的I／O组件 715

B．3 基本原理 719

B．3．1 布局管理器 719

B．3．2 图 722

B．3．3 事件 724

B．3．4 事件处理：适配器和匿名内部类 726

B．3．5 总结：将所有片段组合起来 728

B．3．6 是否需要明白Swing的所有内容 728

小结 728

重要概念 729

常见错误 730

网上资源 731

练习 731

简答题 731

实践题 731

程序设计题 731

参考文献 732

附录C 位运算符 733