书籍详情
数据结构(计算机科学与技术 Java版)
作者:福特
出版社:清华大学
出版时间:2006-11-01
ISBN:9787302135449
定价:¥118.00
购买这本书可以去
内容简介
本书从面向对象的角度讲述了数据结构的基本理论。总的来说,数据结构就是处理批量数据的存储处理机。数据结构又称为集合(collection),它可进行添加和删除数据项的操作,并且能够提供对集合中元素的访问。面向对象的编程方法将数据结构视为可对数据进行特定操作的对象。类声明定义了数据底层的存储结构和能高效执行操作的实现方法。数据结构在计算机科学的各个领域中都扮演着非常重要的角色。在几乎所有重要的计算机应用程序的设计和实现中,它都是一个关键的要素。所以大多数学生在回顾数据结构的课程时,都认为这是他们将计算机科学作为一种学科来认识和了解的第一步。在数据结构的学习中会介绍大量的重要概念。 数据结构在计算机科学的各个领域中都扮演着非常重要的角色。本书主要从面向对象的角度讲述了数据结构的基本理论。为了帮助读者更加深入全面地理解数据结构,全书贯穿了对算法的综合研究。.本书重要特色:◆使用大量的示例与图表阐明各种概念。 ◆大量的书面练习与编程练习覆盖了各种概念并探讨了一些理论(包含可扩充的项目)。◆使用UML图与简洁的API描述介绍各种集合类及其联系。..◆本书的附录与前三个章节讲述了所有Java语言技巧。◆详细地解释和论证了每个集合类的实现设计。◆本书后半部分出色地诠释了对算法的应用。这一部分所介绍的主题包括图、数据压缩、平衡树、密码术以及混合算法设计方法。◆简要描述了GUI编程,并且选择某些图形应用程序示例说明了如何使用数据结构。...
作者简介
本书提供作译者介绍William Ford和William Topp是University of Pacific计算机科学专业的教授。他们编写了大量关于数据结构、算法以及汇编语言编程的著作和软件系统,主要包括:《数据结构C++语言描述——应用标准模板库》、《使用C++和对象技术的计算导论》、《数据结构(C++语言描述)》、《M68000系列汇编语言与系统编程(第二版)》,以及EZJava集成开发系统、Macintosh汇编系统2.0版等。...
目录
第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
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
猜您喜欢