数据结构、算法与应用（Java语言描述）
-
【作 者】[美]Sartaj Sahni（萨尔塔杰.萨
【I S B N 】978-7-5084-4568-7
【责任编辑】陈洁
【适用读者群】本科
【出版时间】2007-06-01
【开 本】16开本
【装帧信息】平装（光膜）
【版 次】第1版
【页 数】632
【千字数】
【印 张】
【定 价】￥65
【丛 书】暂无分类
【备注信息】
图书详情
简介
本书特色
前言
章节列表
精彩阅读
下载资源
相关图书
本书涵盖了“数据结构和算法”的核心知识，使用Java语言描述，并对每种数据结构和算法的设计提供了多个实际应用。
本书共由三部分组成。第1部分包括第1~4章，回顾了Java编程概念及分析和测量程序性能的方法。第2部分包括第5~17章，深入研究了主要的数据结构。其中，第5~7章是本书研究的主干，探讨了表示数据的各种方法─?数组、链表和模拟指针，其余章节论及了数据结构的其他表示方法。第3部分包括第18~22章，探讨了常见的算法设计方法。
本书条理清晰，内容翔实。书中的算法都有完整的Java程序，且程序结构清晰、构思精巧。本书是高等院校“数据结构”课程的理想教材，也是读者自学数据结构的极好读物。
本书第一版非常畅销，第二版在第一版的基础上增加了新内容。本书全面介绍了基本的数据结构，是高等院校“数据结构”课程的理想教材。本书作者Sartaj Sahni从简单介绍开始，提供了直观的讨论和实际的应用，因此本书非常适合于学生阅读。
实际应用是本书的特色。Sahni博士对所讨论的每种数据结构和算法设计方法都提供了几种应用，并采用了以下主题的例子：排序、压缩和编码以及图像处理。通过将概念与应用相结合，可激发学生的学习热情和兴趣。Sahni博士是一名优秀的对称理论和实践信息工作者，这就体现在本书的学术概念以及培养学生的兴趣上。
本书中的市场开发（market-developed）教学法补充了一些概念，并给学生提供了大量练习。书中约有1000道练习题，包括综合和简单的编程问题以及项目。此外，本书还有一个关联Web站点，其中包含了书中的所有程序、动画、示例数据、生成的输出、某些练习的答案和带答案的示例测试。
关于作者
Sartaj Sahni是美国佛罗里达大学的著名教授，也是计算机信息科学与工程系主任。他是欧洲科学院、IEEA、ACM、AAAS和美国明尼苏达州超级计算机学院的成员。Sahni博士是1997年IEEE Computer Society Taylor L. Booth Education Award、2003年 IEEE Computer Society W. Wallace McDowell Award和2003年ACM Karl Karlstorm Outstanding Educator Award的获得者。Sahni取得坎普尔印度理工学院的工科学士学位，以及美国康奈尔大学的计算机科学硕士和博士学位。Sahni已经发表了250多篇研究论文，并编著了15部书籍。他的研究出版物涉及高效算法的设计与分析、并行计算、互联网络、设计自动化和医学算法。
本书由孔芳（苏州大学）、高伟（清华同方）主译，沈金河审校。参与翻译工作的人员还有欧阳宇、杨中民、郭蓓、张波、谢君英、盛海燕、易磊、唐美艳、代菊容、李蕾、李秋霞、赵岗善。
译 者
2007年1月
前言
致谢
关于本书
第1章 Java综述 1
1.1 简介 2
1.2 Java程序结构 2
1.2.1 独立运行的程序和Applet 2
1.2.2 包 3
1.2.3 引入类和包 4
1.2.4 超类和子类 4
1.3 Java编译器和虚拟机 5
1.4 文档注释 6
1.5 数据类型 7
1.6 方法 8
1.6.1 参数 8
1.6.2 重载方法 9
1.7 异常 10
1.7.1 抛出一个异常 10
1.7.2 处理异常 11
1.8 自定义数据类型 12
1.8.1 Currency类 12
1.8.2 Currency的数据成员 13
1.8.3 Currency的方法成员 14
1.8.4 Currency的构造函数 14
1.8.5 创建Currency的实例 15
1.8.6 Currency的存取器（获取）方法 15
1.8.7 Currency的存取器（设置）方法 16
1.8.8 调用方法和访问数据成员 17
1.8.9 Currency的输出和算术方法 18
1.8.10 main方法 19
1.9 访问修饰符 21
1.10 继承和方法重写 21
1.11 重访Currency 23
1.12 定义一个异常类 25
1.13 泛型方法 26
1.13.1 Computable接口 26
1.13.2 泛型方法abc 27
1.13.3 java.lang.Comparable接口 28
1.13.4 Operable接口 28
1.13.5 Zero和CloneableObject接口 28
1.13.6 MyInteger封装类 29
1.13.7 使用数据类型和方法作为参数 29
1.14 垃圾收集 33
1.15 递归 33
1.15.1 递归函数 33
1.15.2 归纳 34
1.15.3 递归方法 35
1.16 测试和调试 39
1.16.1 什么是测试 39
1.16.2 设计测试数据 41
1.16.3 调试 43
1.17 参考资料和选择性读物 44
第2章 性能分析 45
2.1 什么是性能 45
2.2 空间复杂度 46
2.2.1 空间复杂度的组成 46
2.2.2 范例 49
2.3 时间复杂度 51
2.3.1 时间复杂度的组成 51
2.3.2 运算计数 52
2.3.3 最佳、最差和平均运算计数 56
2.3.4 步骤计数 61
第3章 渐近表示法 73
3.1 简介 73
3.2 渐近表示法 75
3.2.1 表示法 75
3.2.2 和Θ表示法 77
3.3 渐近数学（可选） 79
3.3.1 O表示法 79
3.3.2 表示法 81
3.3.3 Θ表示法 82
3.3.4 表示法 84
3.3.5 属性 84
3.4 复杂度分析范例 86
3.5 实用的复杂度 89
3.6 参考资料和选择性读物 91
第4章 性能测量 92
4.1 简介 92
4.2 选择实例规模 92
4.3 开发测试数据 93
4.4 建立试验 93
4.5 缓存管理 98
4.5.1 一个简单的计算机模型 98
4.5.2 遗漏缓存对运行时间的影响 99
4.5.3 矩阵乘法 99
4.6 参考资料和选择性读物 102
第5章 线性列表——数组表示形式 103
5.1 数据对象和结构 104
5.2 线性列表数据结构 105
5.2.1 抽象数据类型LinearList 105
5.2.2 LinearList接口 105
5.2.3 LinearListAsAbstractClass抽象类 106
5.3 数组表示形式 108
5.3.1 表示形式 108
5.3.2 改变一维数组的长度 109
5.3.3 类ArrayLinearList 110
5.3.4 ArrayLinearList的Iterator 114
5.4 矢量表示形式 121
5.5 在单个数组中的多个列表 124
5.6 性能测量 126
5.7 java.util.ArrayList类 128
5.8 参考资料和选择性读物 129
第6章 线性列表——链表表示 130
6.1 单向链表和链 131
6.1.1 表示形式 131
6.1.2 ChainNode类 132
6.1.3 Chain类 133
6.1.4 对ADT LinearList的扩展 137
6.1.5 ExtendedChain类 138
6.1.6 性能测量 139
6.2 循环列表和头节点 144
6.3 双向链表 146
6.4 链表术语表 147
6.5 应用 148
6.5.1 箱排序 148
6.5.2 基数排序 151
6.5.3 凸包 153
第7章 线性列表——模拟指针 158
7.1 需要模拟指针 158
7.2 模拟指针 159
7.3 内存管理 160
7.3.1 SimulatedSpace1类 161
7.3.2 SimulatedSpace2类 162
7.3.3 评价模拟内存管理 162
7.4 与垃圾收集比较 163
7.5 模拟链 164
7.5.1 SimulatedChain类 164
7.5.2 性能测量 165
7.6 内存管理链 167
7.7 应用程序——并查问题 168
7.7.1 等价类 168
7.7.2 应用程序 169
7.7.3 第一个并查解决方案 171
7.7.4 第二个并查解决方案 171
第8章 数组和矩阵 175
8.1 数组 175
8.1.1 抽象数据类型 175
8.1.2 对一个Java数组进行索引 176
8.1.3 行优先和列优先的映射 176
8.1.4 数组的数组表示形式 178
8.1.5 行优先和列优先的表示形式 178
8.1.6 不规则的二维数组 179
8.2 矩阵 180
8.2.1 定义和操作 180
8.2.2 Matrix类 182
8.3 特殊矩阵 186
8.3.1 定义和应用程序 186
8.3.2 对角线矩阵 188
8.3.3 三对角线矩阵 190
8.3.4 三角形矩阵 190
8.3.5 对称矩阵 191
8.4 稀疏矩阵 194
8.4.1 目的 194
8.4.2 使用单线性表的表示 195
8.4.3 使用多线性表的表示 202
8.4.4 性能测量 204
第9章 堆栈 208
9.1 定义和应用 208
9.2 抽象数据类型 210
9.3 数组表示 211
9.3.1 实现为子类 211
9.3.2 类arrayStack 213
9.3.3 性能测量 214
9.4 链式表示 217
9.4.1 类DerivedLinkedStack 217
9.4.2 类LinkedStack 217
9.4.3 性能测量 218
9.5 应用 219
9.5.1 括号匹配 219
9.5.2 汉诺塔 220
9.5.3 重排有轨电车 222
9.5.4 开关箱路由 227
9.5.5 离线等价类问题 229
9.5.6 迷宫中的老鼠 232
9.6 参考资料和选择性读物 241
第10章 队列 242
10.1 定义和应用 242
10.2 抽象数据类型 243
10.3 数组表示 244
10.3.1 表示方法 244
10.3.2 ArrayQueue类 246
10.4 链式表示 249
10.5 应用 252
10.5.1 有轨电车的重新安排 252
10.5.2 线路路由 254
10.5.3 图像组件编号 257
10.5.4 机械工厂模拟 260
10.6 参考资料和选择性读物 272
第11章 跳表和散列表 273
11.1 字典 273
11.2 抽象数据类型 275
11.3 线性表表示 276
11.4 跳表表示（可选） 278
11.4.1 理想情形 278
11.4.2 插入和删除 279
11.4.3 分配层级 280
11.4.4 类SkipNode 280
11.4.5 类SkipList 281
11.4.6 SkipList方法的复杂度 285
11.5 散列表表示 285
11.5.1 理想散列 285
11.5.2 散列函数和散列表 287
11.5.3 线性探查法 290
11.5.4 使用链表的散列 295
11.6 一个应用——文本压缩 300
11.6.1 LZW压缩 301
11.6.2 LZW压缩的实现 302
11.6.3 LZW解压缩 306
11.6.4 LZW解压缩的实现 306
11.6.5 性能评估 309
11.7 参考资料和选择性读物 311
第12章 二叉树和其他树 312
12.1 树 312
12.2 二叉树 315
12.3 二叉树的属性 316
习题 318
12.4 二叉树的表示 318
12.4.1 基于数组的表示 318
12.4.2 链接表示 319
12.5 常见的二叉树操作 320
12.6 二叉树遍历 320
12.7 ADT BinaryTree 325
12.8 类LinkedBinaryTree 326
12.9 应用 329
12.9.1 信号放大器的布置 329
12.9.2 并查（Union-Find）问题 334
12.10 参考资料和选择性读物 343
第13章 优先级队列 344
13.1 定义和应用 344
13.2 抽象数据类型 345
13.3 线性表 346
13.4 堆 347
13.4.1 定义 347
13.4.2 插入元素到最大堆 348
13.4.3 从最大堆中删除元素 348
13.4.4 最大堆的初始化 349
13.4.5 MaxHeap类 350
13.5 左倾树 354
13.5.1 基于高度和基于宽度的最小
和最大左倾树 354
13.5.2 插入到最大HBLT 356
13.5.3 从最大HBLT中删除 356
13.5.4 合并两棵最大HBLT 356
13.5.5 初始化 358
13.5.6 MaxHBLT类 358
13.6 应用 362
13.6.1 堆排序 362
13.6.2 机器调度 363
13.6.3 哈夫曼编码 366
13.7 参考资料和选择性读物 371
第14章 比赛树 373
14.1 优胜树及其应用 373
14.2 抽象数据类型WinnerTree 377
14.3 优胜树的实现 377
14.3.1 表示 377
14.3.2 初始化一棵优胜树 378
14.3.3 重新进行比赛 378
14.3.4 类CompleteWinnerTree 378
14.4 失败树 379
14.5 应用 381
14.5.1 使用首次适应法的容器装包 381
14.5.2 使用下一适应法的容器装包 385
14.6 参考资料和选择性读物 388
第15章 二叉搜索树 389
15.1 定义 390
15.1.1 二叉搜索树 390
15.1.2 可索引二叉搜索树 391
15.2 抽象数据类型 392
15.3 二叉搜索树的操作及其实现 393
15.3.1 BinarySearchTree类 393
15.3.2 搜索 393
15.3.3 插入一个元素 394
15.3.4 删除一个元素 395
15.3.5 二叉搜索树的高度 397
15.4 有重复记录的二叉搜索树 399
15.5 索引的二叉搜索树 400
15.6 应用 401
15.6.1 柱状图 401
15.6.2 最优容器装包 404
15.6.3 交叉分配 406
第16章 平衡搜索树 413
16.1 AVL树 414
16.1.1 定义 414
16.1.2 AVL树的高度 415
16.1.3 AVL树的表示 415
16.1.4 AVL搜索树的搜索 415
16.1.5 AVL搜索树的插入 415
16.1.6 从AVL搜索树中删除 418
16.2 红黑树 421
16.2.1 定义 421
16.2.2 红黑树的表示 423
16.2.3 红黑树的搜索 423
16.2.4 红黑树的插入 423
16.2.5 从红黑树中删除 427
16.2.6 实现的考虑和复杂度 430
16.3 伸展树 432
16.3.1 引言 432
16.3.2 伸展操作 432
16.3.3 分摊复杂度 434
16.4 B-树 436
16.4.1 索引顺序存取法（ISAM） 436
16.4.2 m-叉搜索树 436
16.4.3 m叉排序B-树 438
16.4.4 B-树的高度 439
16.4.5 搜索B-树 439
16.4.6 插入元素到B-树 440
16.4.7 从B-树中删除 442
16.4.8 节点结构 445
16.5 参考资料和选择性读物 446
第17章 图 447
17.1 定义 447
17.2 应用和更多的定义 449
习题 451
17.3 属性 452
17.4 ADT Graph 453
17.5 不带权值的图的表示 454
17.5.1 邻接矩阵 455
17.5.2 链式邻接表 456
17.5.3 数组邻接表 457
17.6 带权图的表示形式 458
17.7 类的实现 459
17.7.1 不同的类 459
17.7.2 邻接矩阵类 460
17.7.3 到类Chain的扩展 463
17.7.4 链表类 464
17.8 图的搜索方法 466
17.8.1 广度优先搜索 466
17.8.2 广度优先搜索的实现 468
17.8.3 Graph.bfs的复杂度分析 468
17.8.4 深度优先搜索 470
17.8.5 深度优先搜索的实现 471
17.8.6 Graph.dfs的复杂度分析 471
17.9 重访的应用 472
17.9.1 查找路径 472
17.9.2 连通图和连通分量 474
17.9.3 生成树 476
第18章 贪婪方法 479
18.1 最优化问题 479
18.2 贪婪方法 480
18.3 应用 483
18.3.1 集装箱装载 483
18.3.2 0/1背包问题 485
18.3.3 拓扑排序 487
18.3.4 二分覆盖 490
18.3.5 单源最短路径 493
18.3.6 最小生成树 497
18.4 参考资料和选择性读物 507
第19章 分而治之 508
19.1 方法 508
19.2 应用 515
19.2.1 缺陷棋盘 515
19.2.2 归并排序 517
19.2.3 快速排序 522
19.2.4 选择 528
19.2.5 最近顶点对 530
19.3 求解递归等式 538
19.4 复杂度下界 540
19.4.1 最小最大问题的下界 541
19.4.2 排序的下界 542
第20章 动态规划 544
20.1 方法 544
20.2 应用 546
20.2.1 0/1背包问题 546
20.2.2 矩阵乘法链 550
20.2.3 所有对最短路径 555
20.2.4 带负值的单源最短路径 558
20.2.5 不相交网子集 562
20.3 参考资料和选择性读物 568
第21章 回溯法 569
21.1 方法 569
21.2 应用 574
21.2.1 集装箱装载 574
21.2.2 0/1背包问题 581
21.2.3 最大集团 584
21.2.4 旅行售货员 587
21.2.5 电路板排列 589
第22章 分支限界法 595
22.1 方法 595
22.2 应用 598
22.2.1 集装箱装载 598
22.2.2 0/1背包问题 605
22.2.3 最大集团 607
22.2.4 旅行售货员 609
22.2.5 电路板排列 612本书涵盖了“数据结构和算法”的核心知识，使用Java语言描述，并对每种数据结构和算法的设计提供了多个实际应用。
本书共由三部分组成。第1部分包括第1~4章，回顾了Java编程概念及分析和测量程序性能的方法。第2部分包括第5~17章，深入研究了主要的数据结构。其中，第5~7章是本书研究的主干，探讨了表示数据的各种方法─?数组、链表和模拟指针，其余章节论及了数据结构的其他表示方法。第3部分包括第18~22章，探讨了常见的算法设计方法。
本书条理清晰，内容翔实。书中的算法都有完整的Java程序，且程序结构清晰、构思精巧。本书是高等院校“数据结构”课程的理想教材，也是读者自学数据结构的极好读物。
致谢
关于本书
第1章 Java综述 1
1.1 简介 2
1.2 Java程序结构 2
1.2.1 独立运行的程序和Applet 2
1.2.2 包 3
1.2.3 引入类和包 4
1.2.4 超类和子类 4
1.3 Java编译器和虚拟机 5
1.4 文档注释 6
1.5 数据类型 7
1.6 方法 8
1.6.1 参数 8
1.6.2 重载方法 9
1.7 异常 10
1.7.1 抛出一个异常 10
1.7.2 处理异常 11
1.8 自定义数据类型 12
1.8.1 Currency类 12
1.8.2 Currency的数据成员 13
1.8.3 Currency的方法成员 14
1.8.4 Currency的构造函数 14
1.8.5 创建Currency的实例 15
1.8.6 Currency的存取器（获取）方法 15
1.8.7 Currency的存取器（设置）方法 16
1.8.8 调用方法和访问数据成员 17
1.8.9 Currency的输出和算术方法 18
1.8.10 main方法 19
1.9 访问修饰符 21
1.10 继承和方法重写 21
1.11 重访Currency 23
1.12 定义一个异常类 25
1.13 泛型方法 26
1.13.1 Computable接口 26
1.13.2 泛型方法abc 27
1.13.3 java.lang.Comparable接口 28
1.13.4 Operable接口 28
1.13.5 Zero和CloneableObject接口 28
1.13.6 MyInteger封装类 29
1.13.7 使用数据类型和方法作为参数 29
1.14 垃圾收集 33
1.15 递归 33
1.15.1 递归函数 33
1.15.2 归纳 34
1.15.3 递归方法 35
1.16 测试和调试 39
1.16.1 什么是测试 39
1.16.2 设计测试数据 41
1.16.3 调试 43
1.17 参考资料和选择性读物 44
第2章 性能分析 45
2.1 什么是性能 45
2.2 空间复杂度 46
2.2.1 空间复杂度的组成 46
2.2.2 范例 49
2.3 时间复杂度 51
2.3.1 时间复杂度的组成 51
2.3.2 运算计数 52
2.3.3 最佳、最差和平均运算计数 56
2.3.4 步骤计数 61
第3章 渐近表示法 73
3.1 简介 73
3.2 渐近表示法 75
3.2.1 表示法 75
3.2.2 和Θ表示法 77
3.3 渐近数学（可选） 79
3.3.1 O表示法 79
3.3.2 表示法 81
3.3.3 Θ表示法 82
3.3.4 表示法 84
3.3.5 属性 84
3.4 复杂度分析范例 86
3.5 实用的复杂度 89
3.6 参考资料和选择性读物 91
第4章 性能测量 92
4.1 简介 92
4.2 选择实例规模 92
4.3 开发测试数据 93
4.4 建立试验 93
4.5 缓存管理 98
4.5.1 一个简单的计算机模型 98
4.5.2 遗漏缓存对运行时间的影响 99
4.5.3 矩阵乘法 99
4.6 参考资料和选择性读物 102
第5章 线性列表——数组表示形式 103
5.1 数据对象和结构 104
5.2 线性列表数据结构 105
5.2.1 抽象数据类型LinearList 105
5.2.2 LinearList接口 105
5.2.3 LinearListAsAbstractClass抽象类 106
5.3 数组表示形式 108
5.3.1 表示形式 108
5.3.2 改变一维数组的长度 109
5.3.3 类ArrayLinearList 110
5.3.4 ArrayLinearList的Iterator 114
5.4 矢量表示形式 121
5.5 在单个数组中的多个列表 124
5.6 性能测量 126
5.7 java.util.ArrayList类 128
5.8 参考资料和选择性读物 129
第6章 线性列表——链表表示 130
6.1 单向链表和链 131
6.1.1 表示形式 131
6.1.2 ChainNode类 132
6.1.3 Chain类 133
6.1.4 对ADT LinearList的扩展 137
6.1.5 ExtendedChain类 138
6.1.6 性能测量 139
6.2 循环列表和头节点 144
6.3 双向链表 146
6.4 链表术语表 147
6.5 应用 148
6.5.1 箱排序 148
6.5.2 基数排序 151
6.5.3 凸包 153
第7章 线性列表——模拟指针 158
7.1 需要模拟指针 158
7.2 模拟指针 159
7.3 内存管理 160
7.3.1 SimulatedSpace1类 161
7.3.2 SimulatedSpace2类 162
7.3.3 评价模拟内存管理 162
7.4 与垃圾收集比较 163
7.5 模拟链 164
7.5.1 SimulatedChain类 164
7.5.2 性能测量 165
7.6 内存管理链 167
7.7 应用程序——并查问题 168
7.7.1 等价类 168
7.7.2 应用程序 169
7.7.3 第一个并查解决方案 171
7.7.4 第二个并查解决方案 171
第8章 数组和矩阵 175
8.1 数组 175
8.1.1 抽象数据类型 175
8.1.2 对一个Java数组进行索引 176
8.1.3 行优先和列优先的映射 176
8.1.4 数组的数组表示形式 178
8.1.5 行优先和列优先的表示形式 178
8.1.6 不规则的二维数组 179
8.2 矩阵 180
8.2.1 定义和操作 180
8.2.2 Matrix类 182
8.3 特殊矩阵 186
8.3.1 定义和应用程序 186
8.3.2 对角线矩阵 188
8.3.3 三对角线矩阵 190
8.3.4 三角形矩阵 190
8.3.5 对称矩阵 191
8.4 稀疏矩阵 194
8.4.1 目的 194
8.4.2 使用单线性表的表示 195
8.4.3 使用多线性表的表示 202
8.4.4 性能测量 204
第9章 堆栈 208
9.1 定义和应用 208
9.2 抽象数据类型 210
9.3 数组表示 211
9.3.1 实现为子类 211
9.3.2 类arrayStack 213
9.3.3 性能测量 214
9.4 链式表示 217
9.4.1 类DerivedLinkedStack 217
9.4.2 类LinkedStack 217
9.4.3 性能测量 218
9.5 应用 219
9.5.1 括号匹配 219
9.5.2 汉诺塔 220
9.5.3 重排有轨电车 222
9.5.4 开关箱路由 227
9.5.5 离线等价类问题 229
9.5.6 迷宫中的老鼠 232
9.6 参考资料和选择性读物 241
第10章 队列 242
10.1 定义和应用 242
10.2 抽象数据类型 243
10.3 数组表示 244
10.3.1 表示方法 244
10.3.2 ArrayQueue类 246
10.4 链式表示 249
10.5 应用 252
10.5.1 有轨电车的重新安排 252
10.5.2 线路路由 254
10.5.3 图像组件编号 257
10.5.4 机械工厂模拟 260
10.6 参考资料和选择性读物 272
第11章 跳表和散列表 273
11.1 字典 273
11.2 抽象数据类型 275
11.3 线性表表示 276
11.4 跳表表示（可选） 278
11.4.1 理想情形 278
11.4.2 插入和删除 279
11.4.3 分配层级 280
11.4.4 类SkipNode 280
11.4.5 类SkipList 281
11.4.6 SkipList方法的复杂度 285
11.5 散列表表示 285
11.5.1 理想散列 285
11.5.2 散列函数和散列表 287
11.5.3 线性探查法 290
11.5.4 使用链表的散列 295
11.6 一个应用——文本压缩 300
11.6.1 LZW压缩 301
11.6.2 LZW压缩的实现 302
11.6.3 LZW解压缩 306
11.6.4 LZW解压缩的实现 306
11.6.5 性能评估 309
11.7 参考资料和选择性读物 311
第12章 二叉树和其他树 312
12.1 树 312
12.2 二叉树 315
12.3 二叉树的属性 316
习题 318
12.4 二叉树的表示 318
12.4.1 基于数组的表示 318
12.4.2 链接表示 319
12.5 常见的二叉树操作 320
12.6 二叉树遍历 320
12.7 ADT BinaryTree 325
12.8 类LinkedBinaryTree 326
12.9 应用 329
12.9.1 信号放大器的布置 329
12.9.2 并查（Union-Find）问题 334
12.10 参考资料和选择性读物 343
第13章 优先级队列 344
13.1 定义和应用 344
13.2 抽象数据类型 345
13.3 线性表 346
13.4 堆 347
13.4.1 定义 347
13.4.2 插入元素到最大堆 348
13.4.3 从最大堆中删除元素 348
13.4.4 最大堆的初始化 349
13.4.5 MaxHeap类 350
13.5 左倾树 354
13.5.1 基于高度和基于宽度的最小
和最大左倾树 354
13.5.2 插入到最大HBLT 356
13.5.3 从最大HBLT中删除 356
13.5.4 合并两棵最大HBLT 356
13.5.5 初始化 358
13.5.6 MaxHBLT类 358
13.6 应用 362
13.6.1 堆排序 362
13.6.2 机器调度 363
13.6.3 哈夫曼编码 366
13.7 参考资料和选择性读物 371
第14章 比赛树 373
14.1 优胜树及其应用 373
14.2 抽象数据类型WinnerTree 377
14.3 优胜树的实现 377
14.3.1 表示 377
14.3.2 初始化一棵优胜树 378
14.3.3 重新进行比赛 378
14.3.4 类CompleteWinnerTree 378
14.4 失败树 379
14.5 应用 381
14.5.1 使用首次适应法的容器装包 381
14.5.2 使用下一适应法的容器装包 385
14.6 参考资料和选择性读物 388
第15章 二叉搜索树 389
15.1 定义 390
15.1.1 二叉搜索树 390
15.1.2 可索引二叉搜索树 391
15.2 抽象数据类型 392
15.3 二叉搜索树的操作及其实现 393
15.3.1 BinarySearchTree类 393
15.3.2 搜索 393
15.3.3 插入一个元素 394
15.3.4 删除一个元素 395
15.3.5 二叉搜索树的高度 397
15.4 有重复记录的二叉搜索树 399
15.5 索引的二叉搜索树 400
15.6 应用 401
15.6.1 柱状图 401
15.6.2 最优容器装包 404
15.6.3 交叉分配 406
第16章 平衡搜索树 413
16.1 AVL树 414
16.1.1 定义 414
16.1.2 AVL树的高度 415
16.1.3 AVL树的表示 415
16.1.4 AVL搜索树的搜索 415
16.1.5 AVL搜索树的插入 415
16.1.6 从AVL搜索树中删除 418
16.2 红黑树 421
16.2.1 定义 421
16.2.2 红黑树的表示 423
16.2.3 红黑树的搜索 423
16.2.4 红黑树的插入 423
16.2.5 从红黑树中删除 427
16.2.6 实现的考虑和复杂度 430
16.3 伸展树 432
16.3.1 引言 432
16.3.2 伸展操作 432
16.3.3 分摊复杂度 434
16.4 B-树 436
16.4.1 索引顺序存取法（ISAM） 436
16.4.2 m-叉搜索树 436
16.4.3 m叉排序B-树 438
16.4.4 B-树的高度 439
16.4.5 搜索B-树 439
16.4.6 插入元素到B-树 440
16.4.7 从B-树中删除 442
16.4.8 节点结构 445
16.5 参考资料和选择性读物 446
第17章 图 447
17.1 定义 447
17.2 应用和更多的定义 449
习题 451
17.3 属性 452
17.4 ADT Graph 453
17.5 不带权值的图的表示 454
17.5.1 邻接矩阵 455
17.5.2 链式邻接表 456
17.5.3 数组邻接表 457
17.6 带权图的表示形式 458
17.7 类的实现 459
17.7.1 不同的类 459
17.7.2 邻接矩阵类 460
17.7.3 到类Chain的扩展 463
17.7.4 链表类 464
17.8 图的搜索方法 466
17.8.1 广度优先搜索 466
17.8.2 广度优先搜索的实现 468
17.8.3 Graph.bfs的复杂度分析 468
17.8.4 深度优先搜索 470
17.8.5 深度优先搜索的实现 471
17.8.6 Graph.dfs的复杂度分析 471
17.9 重访的应用 472
17.9.1 查找路径 472
17.9.2 连通图和连通分量 474
17.9.3 生成树 476
第18章 贪婪方法 479
18.1 最优化问题 479
18.2 贪婪方法 480
18.3 应用 483
18.3.1 集装箱装载 483
18.3.2 0/1背包问题 485
18.3.3 拓扑排序 487
18.3.4 二分覆盖 490
18.3.5 单源最短路径 493
18.3.6 最小生成树 497
18.4 参考资料和选择性读物 507
第19章 分而治之 508
19.1 方法 508
19.2 应用 515
19.2.1 缺陷棋盘 515
19.2.2 归并排序 517
19.2.3 快速排序 522
19.2.4 选择 528
19.2.5 最近顶点对 530
19.3 求解递归等式 538
19.4 复杂度下界 540
19.4.1 最小最大问题的下界 541
19.4.2 排序的下界 542
第20章 动态规划 544
20.1 方法 544
20.2 应用 546
20.2.1 0/1背包问题 546
20.2.2 矩阵乘法链 550
20.2.3 所有对最短路径 555
20.2.4 带负值的单源最短路径 558
20.2.5 不相交网子集 562
20.3 参考资料和选择性读物 568
第21章 回溯法 569
21.1 方法 569
21.2 应用 574
21.2.1 集装箱装载 574
21.2.2 0/1背包问题 581
21.2.3 最大集团 584
21.2.4 旅行售货员 587
21.2.5 电路板排列 589
第22章 分支限界法 595
22.1 方法 595
22.2 应用 598
22.2.1 集装箱装载 598
22.2.2 0/1背包问题 605
22.2.3 最大集团 607
22.2.4 旅行售货员 609
22.2.5 电路板排列 612本书涵盖了“数据结构和算法”的核心知识，使用Java语言描述，并对每种数据结构和算法的设计提供了多个实际应用。
本书共由三部分组成。第1部分包括第1~4章，回顾了Java编程概念及分析和测量程序性能的方法。第2部分包括第5~17章，深入研究了主要的数据结构。其中，第5~7章是本书研究的主干，探讨了表示数据的各种方法─?数组、链表和模拟指针，其余章节论及了数据结构的其他表示方法。第3部分包括第18~22章，探讨了常见的算法设计方法。
本书条理清晰，内容翔实。书中的算法都有完整的Java程序，且程序结构清晰、构思精巧。本书是高等院校“数据结构”课程的理想教材，也是读者自学数据结构的极好读物。
- 数据结构（Python语言描述） [曹岳辉 刘卫国 康松林 编著]
- 数据结构——C语言（微课版） [主编 梁海英]
- 数据结构（C语言版）习题解答及实训指导 [李根强 谢月娥]
- 数据结构（C语言版） [主编 李根强 刘浩 谢月娥]
- 数据结构（Java版） [主编 李云平]
- 数据结构 [主编 韩利凯 朱浩悦]
- 数据结构（C语言版）（第三版） [主编 库波 曹静]
- 数据结构（Java版） [孙琳 张宇]
- 数据结构 [许绘香 段明义]
- 数据结构（C语言描述） [李素若 陈万华 游明坤 编著]
- 数据结构习题解答及上机指导 [李素若 琚辉 严永松 编著]
- 数据结构（C++描述）习题解答及实习指导 [李根强 谢月娥 主编]
- 数据结构（C语言版）学习指导与习题解答 [赵坚 姜梅 主编]
- 数据结构 [陆勤 主编 ]
- 数据结构（C++描述） [李根强 主 编]
- 数据结构（C++版）--习题解答及实习指导 [李根强 主编]
- 数据结构算法--Visual C++ 6.0程序集 [侯识忠 等编著]
- 数据结构算法--C++ Builder 6.0程序集 [侯识忠 等编著]
- 数据结构（C语言版）学习指导与习题解答 [赵坚 姜梅 主编]
- 数据结构（C语言版） [赵坚 姜梅 主编]
- 数据结构（C语言描述） [斯庆巴拉 主编]
- 数据结构（C++版）（第二版） [李根强]
- 数据结构（C++版）（第二版）习题解答及实训指导 [李根强]
- 数据结构——用C语言描述 [蔡明志 编著]
- 数据结构（C++版） [李根强 主编]
- 数据结构--用C语言描述（第二版） [宁正元 易金聪 编著]
- 数据结构（C语言描述） [马秋菊 主编]
- 数据结构（C/C++描述） [阮宏一 主编]
- 数据结构--C语言描述（第二版） [王路群 主编]
- 数据结构实验程序 [智东杰 主 编]
关闭
打印
推荐
收藏
评论
相关分类
