数据结构（计算机科学与技术 Java版）

第1章  类与对象    1
1.1  本书内容    1
1.1.1  动态数组    1
1.1.2  链表    2
1.1.3  关联数组    3
1.1.4  图    4
1.1.5  适配器结构    4
1.1.6  数据结构与面向对象编程    5
1.1.7  数据结构与算法    5
1.2  面向对象编程    5
1.3  理解类的概念    7
1.4  Time24类    8
1.4.1  设计Time24类    8
1.4.2  构造函数    9
1.4.3  toString方法    10
1.4.4  Accessor和mutator方法    11
1.4.5  静态方法    12
1.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.5  格式化的对象描述    23
1.8.6  增加时间    23
1.8.7  时间间隔    23
1.9  类的构造    24
1.10  String类    26
1.10.1  串索引    27
1.10.2  串合并    27
1.10.3  串比较    28
1.11  枚举类    29
1.12  总结    32
书面练习    33
编程练习    34
编程项目    36
第2章  类之间的关系    39
2.1  wrapper类    40
2.1.1  Integer对象的比较    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.3.3  TimeCard类的UML图    47
2.4  Java中的继承    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  运行时错误的处理    60
2.7.1  throw语句    60
2.7.2  处理异常的try/catch
代码块    61
2.7.3  finally子句    62
2.7.4  异常传播    63
2.7.5  Java异常的层次结构    63
2.7.6  标准的异常    65
2.8  输入与输出    65
2.8.1  控制台I/O    66
2.8.2  文件I/O    67
2.8.3  使用Reader流的文本输入    67
2.8.4  输入串的分析    69
2.8.5  使用Writer流的文本输出    71
2.8.6  输出流的控制    72
2.9  Scanner类    73
2.9.1  声明Scanner对象    73
2.9.2  输入流的读取    73
2.9.3  文件输入    75
2.9.4  Scanner类API    75
2.9.5  应用程序：Scanner类
的使用    76
2.10  总结    79
书面练习    80
编程练习    83
编程项目    87
第3章  类的设计    89
3.1  Java接口    89
3.2  作为模板的接口    91
3.2.1  使用接口类型    92
3.2.2  接口与继承    94
3.3  使用javadoc创建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章  算法介绍    115
4.1  选择排序    115
4.2  简单的搜索算法    119
4.2.1  顺序搜索    119
4.2.2  二叉搜索    121
4.3  算法的分析    126
4.3.1  系统/内存性能标准    126
4.3.2  算法性能：运行时间分析    126
4.3.3  Big-O符号    129
4.3.4  通用数量级    131
4.4  搜索算法的比较    133
4.5  总结    136
书面练习    136
编程练习    138
编程项目    141
第5章  泛型类与方法    143
5.1  Object超类    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  泛型方法    155
5.4.1  基本的泛型方法    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章  递归    171
6.1  递归的概念    171
6.1.1  描述一个递归算法    173
6.1.2  递归方法的实现    173
6.1.3  递归的工作方式    175
6.1.4  多种基数表示法    176
6.2  递归的应用    179
6.2.1  构建一个刻度尺    179
6.2.2  Hanoi塔    181
6.3  递归的评价    185
6.3.1  Fibonacci方法    186
6.3.2  使用递归的标准    189
6.4  总结    189
书面练习    190
编程练习    192
编程项目    194
第7章  排序算法    195
7.1  插入排序    195
7.2  分治排序算法    198
7.2.1  归并排序    198
7.2.2  通用的排序方法    201
7.2.3  msort()方法    202
7.2.4  归并排序的效率    205
7.3  快速排序    206
7.3.1  使用基准值分割列表    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章  集合类型    227
8.1  集合介绍    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.4.3  集合的toString()方法    246
8.5  总结    246
书面练习    247
编程练习    248
编程项目    249
第9章  基于数组的列表集合    251
9.1  列表集合    251
9.2  ArrayList类    255
9.2.1  调整ArrayList的大小    257
9.2.2  ArrayList API    259
9.3  ArrayList应用程序    259
9.3.1  ArrayList的连接    259
9.3.2  closest-pair问题    262
9.4  实现ArrayList类    266
9.4.1  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.5.4  克隆数组    279
9.6  ArrayList集合的评价    279
9.7  总结    280
书面练习    280
编程练习    282
编程项目    285
第10章  链表    287
10.1  单链表    289
10.1.1  创建链表    289
10.1.2  扫描链表    291
10.1.3  定位列表位置    291
10.1.4  更新列表头    292
10.1.5  通用的插入和删除操作    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  使用LinkedList集合的
应用程序    304
10.4.1  应用程序：选拔列表    304
10.4.2  应用程序：回文列表    307
10.5  总结    309
书面练习    310
编程练习    313
编程项目    318
第11章  实现LinkedList类    321
11.1  双链表    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  实现LinkedList类    333
11.3.1  LinkedList类的私有
成员    333
11.3.2  LinkedList类的构造
函数    335
11.3.3  列表中基于索引的访问    335
11.3.4  搜索列表    336
11.3.5  修改列表    337
11.4  总结    339
书面练习    339
编程练习    340
编程项目    342
第12章  迭代器    345
12.1  迭代器的概念    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  迭代器的应用    358
12.4.1  有序列表    358
12.4.2  删除有序列表中的
重复值    360
12.5  OrderedList集合    361
12.5.1  OrderedList类方法    362
12.5.2  应用程序：确定字频    363
12.5.3  适配器设计模式    367
12.6  顺序集合的选择    367
12.7  总结    368
书面练习    369
编程练习    371
编程项目    373
第13章  迭代器的实现    375
13.1  迭代器实现设计    375
13.1.1  迭代器变量    376
13.1.2  迭代器接口方法    377
13.2  LinkedList迭代器    378
13.3  列表迭代器的实现    381
13.3.1  列表迭代器构造函数    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  中缀表达式的求解    412
14.5.1  中缀表达式属性    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  事件驱动的仿真    447
15.5.1  对银行的仿真    447
15.5.2  仿真设计模式    449
15.5.3  BankSimulation类    451
15.6  总结    457
书面练习    457
编程练习    460
编程项目    463
第16章  二叉树    465
16.1  树结构    465
16.1.1  树的相关术语    466
16.1.2  二叉树    468
16.2  二叉树节点    473
16.3  二叉树扫描算法    477
16.3.1  递归树遍历    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  树扫描算法的使用    489
16.4.1  树高度的计算    489
16.4.2  复制二叉树    491
16.4.3  清除树    494
16.4.4  显示二叉树    495
16.5  排序的下界(选读)    497
16.6  总结    499
书面练习    500
编程练习    503
编程项目    505
第17章  二叉树的应用    507
17.1  表达式树    507
17.2  迭代的树遍历    512
17.2.1  中序迭代遍历    513
17.2.2  InorderIterator类的实现    515
17.3  Euler回路遍历    518
17.4  绘制二叉树    521
17.4.1  影像树的构建    521
17.4.2  影像树的显示    523
17.5  总结    525
书面练习    526
编程练习    526
编程项目    529
第18章  二叉搜索树    531
18.1  二叉搜索树    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.3.5  二叉搜索树操作的
复杂度    551
18.4  STree迭代器    551
18.5  总结    556
书面练习    556
编程练习    558
编程项目    559
第19章  集与映射    561
19.1  集    563
19.1.1  TreeSet集合    563
19.1.2  简单的拼写检查器    565
19.2  集运算符    568
19.2.1  集运算符的实现    569
19.2.2  应用程序：计算机账号的
更新    572
19.2.3  使用有序集的操作    574
19.3  映射    577
19.3.1  Map接口    577
19.3.2  有序映射TreeMap    579
19.3.3  应用程序：一个学生时间
记录映射    581
19.3.4  应用程序：计算机软件
产品    583
19.4  映射集合视图    586
19.4.1  键集集合视图    586
19.4.2  条目集集合视图    588
19.4.3  应用程序：构建词汇
索引    591
19.5  总结    596
书面练习    596
编程练习    598
编程项目    602
第20章  有序集与映射的实现    603
20.1  TreeSet类的实现    603
20.2  TreeMap类的实现    604
20.2.1  TreeMap类的设计    607
20.2.2  使用键对条目进行访问    608
20.2.3  更新条目    609
20.2.4  删除条目    611
20.2.5  TreeSet和TreeMap类中
插入和删除操作的
复杂度    611
20.3  集合视图的实现    611
20.3.1  查看视图    612
20.3.2  实现视图    614
20.3.3  keySet集合视图    615
20.4  总结    617
书面练习    617
编程练习    618
编程项目    621
第21章  实现映射的散列法    625
21.1  散列法    625
21.2  散列函数的设计    627
21.2.1  Java方法hashCode()    627
21.2.2  自定义的散列函数    629
21.3  散列表的设计    631
21.3.1  线性探查法    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章  堆    661
22.1  基于数组的二叉树    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  使用堆进行排序    676
22.4.1  堆的产生    676
22.4.2  堆排序    679
22.4.3  静态堆方法概述    680
22.5  优先队列的实现    681
22.6  总结    684
书面练习    684
编程练习    687
编程项目    689
第23章  位数组与文件压缩    691
23.1  位数组    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.2  使类可序列化    718
23.4.3  反序列化对象    718
23.4.4  应用程序：对象的
序列化    718
23.4.5  定制序列化    721
23.5  总结    723
书面练习    724
编程练习    728
编程项目    729
第24章  图与路径    731
24.1  图的相关术语    731
24.1.1  有向图    733
24.1.2  带权图    734
24.2  图的创建和使用    735
24.2.1  Graph接口    735
24.2.2  DiGraph类    737
24.3  图遍历算法    741
24.3.1  广度优先搜索算法    741
24.3.2  深度优先访问算法    746
24.3.3  深度优先搜索算法    751
24.3.4  无环图    753
24.4  总结    755
书面练习    755
编程练习    758
编程项目    761
第25章  图算法    763
25.1  拓扑排序    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.2  Dijkstra算法的工作
原理    781
25.5.3  minimumPath()方法的
实现    781
25.5.4  无环图中的最小路径    784
25.6  最小生成树    787
25.6.1  Prim算法    788
25.6.2  minSpanTree()方法的
实现    790
25.7  总结    794
书面练习    794
编程练习    796
编程项目    798
第26章  图的实现    799
26.1  图的表示    799
26.2  DiGraph类的组件    800
26.2.1  顶点信息的表示    801
26.2.2  顶点映射与VertexInfo
数组列表    803
26.3  DiGraph类设计    806
26.4  DiGraph类方法    807
26.4.1  ArrayList的访问    808
26.4.2  邻接顶点的标识    808
26.4.3  入度和出度的求解    809
26.4.4  添加边    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.1  2-3-4树的搜索    836
27.3.2  2-3-4树中的插入操作    836
27.4  红-黑树    839
27.4.1  2-3-4树节点的表示    840
27.4.2  2-3-4树的红-黑树表示    841
27.4.3  在红-黑树中插入节点    844
27.4.4  4-节点的分割    844
27.4.5  红-黑树底部的插入
操作    848
27.4.6  红-黑树的构建    849
27.4.7  红-黑树的搜索运行
时间    850
27.4.8  在红-黑树中删除节点    851
27.5  RBTree类    852
27.6  总结    855
书面练习    855
编程练习    858
编程项目    859
第28章  数论与加密    861
28.1  基本的数论概念    861
28.1.1  Euclid GCD算法    862
28.1.2  模运算    863
28.1.3  Euler Φ函数    865
28.2  安全的消息传输    866
28.2.1  创建用于RSA加密的
密钥    867
28.2.2  使用用于RSA加密的
密钥    867
28.2.3  如何保护RSA通信    868
28.3  大整数的使用    868
28.4  RSA的客户-服务器模式    872
28.5  RSA算法(选读)    873
28.5.1  Euclid GCD算法的实现    873
28.5.2  RSA定理    876
28.6  总结    877
书面练习    878
编程练习    879
编程项目    880
第29章  杂类算法    881
29.1  组合学    881
29.1.1  组合的构建    882
29.1.2  查找所有子集    883
29.1.3  列出置换    885
29.1.4  旅行推销员问题    888
29.1.5  置换与TSP    889
29.2  动态编程    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  Java入门    923
A.1  Java程序的结构    923
A.1.1  注释    924
A.1.2  关键字与标识符    925
A.1.3  变量的声明和使用    925
A.1.4  控制台输出    925
A.2  Java编程环境    926
A.3  原始数据类型    927
A.3.1  数值类型    927
A.3.2  Java的char类型    929
A.3.3  命名常量的声明    930
A.4  运算符    930
A.4.1  算术运算符    930
A.4.2  赋值运算符    931
A.4.3 复合赋值运算符    931
A.4.4  增量运算符    932
A.4.5  运算符的优先顺序    932
A.5  类型之间的转换    933
A.6  选择语句    935
A.6.1  if语句    937
A.6.2  嵌套的if语句    938
A.6.3  多路if/else语句    939
A.6.4  条件表达式运算符    939
A.6.5  switch语句    940
A.6.6  boolean类型    941
A.7  循环语句    942
A.7.1  while语句    942
A.7.2  do/while语句    943
A.7.3  for语句    944
A.7.4  break语句    945
A.8  数组    946
A.8.1  数组的初始化    947
A.8.2  使用增强的for语句
扫描数组    947
A.8.3  二维数组    948
A.9  Java的方法    949
A.9.1  预定义的方法    949
A.9.2  自定义的方法    951
A.9.3  作为方法参数的数组    953
附录B  Java关键字    957
附录C  ASCII字符编码    959
附录D  Java操作符的优先顺序    961
附录E  EZJava集成开发环境    963
E.1  安装EZJava    963
E.2  启动EZJava    964
E.2.1  创建新文档    965
E.2.2  菜单选项    966
E.3  程序的编译和运行    966
E.4  项目的使用    968