数据结构与问题求解——Java语言描述(第3版)
0推荐 收藏
4.8K阅读
图灵计算机科学丛书

数据结构与问题求解——Java语言描述(第3版)

Mark Allen Weiss (作者) 翁惠玉 , 严骏 (译者)
终止销售
本书从讲解什么是数据结构开始,延伸至高级数据结构和算法分析,强调数据结构和问题求解技术。本书的目的是从抽象思维和问题求解的观点提供对数据结构的实用介绍,试图包含有关数据结构、算法分析及其Java实现的所有重要的细节。作者采用了独特的方法将数据结构分成说明和实现两部分,并充分利用了已有的数据结构库(Java集合类API)。本书分为四个部分:第一部分讨论适合大多数应用的集合类API的一个子集,并覆盖基本的算法分析技术、递归和排序算法;第二部分包含了一组集合类API的应用实例;第三部分讨论数据结构的实现;第四部分描述了高级的数据结构,如伸展树、偶堆和不相交集数据结构。
本书适合作为本科生数据结构课程或研究生算法分析课程的教材。教师可以灵活地选择本书的内容,选择最适合对应课程的内容授课。

今年618,图灵自有719种电子书参与以下两种优惠:

活动时间:6.18日

满减优惠码:618

每单满 99 减 50

满折优惠码:618+

每单满 299 即享5折

纸质书
¥49.00

其他购买方式?

出版信息

  • 书  名数据结构与问题求解——Java语言描述(第3版)
  • 系列书名图灵计算机科学丛书
  • 执行编辑关于本书的内容有任何问题,请联系 傅志红
  • 出版日期2006-08-07
  • 书  号7-115-14988-7
  • 定  价49.00 元
  • 页  数480
  • 开  本16开
  • 出版状态终止销售
  • 原书名Data Structures and Problem Solving Using Java
  • 原书号0-321-32213-4

同系列书

本书特色

采用独特的方法将数据结构分成说明和实现两部分,并充分利用现成的数据结构库(Java集合类API)。
讲述有关数据结构、算法分析以及其Java实现的所有重要细节。
结合了Java 5.0的许多新特性,包括泛型编程和泛型集合类的设计。
专门设计了RSA密码系统、简单编译器、文件压缩等结合实际的实例。
涵盖了许多实用的高级数据结构以及算法,反映了本领域的最新进展,并提供了集合类API的一个子集的实现。

目录

第一部分 算法和构件块
第1章 算法分析    2
1.1 什么是算法分析    2
1.2 算法运行时间的实例    5
1.3 连续子序列最大和的问题    6
1.3.1 简单的O(N3)算法    7
1.3.2 改进的O(N2)算法    8
1.3.3 线性算法    9
1.4 一般的大O规则    11
1.5 对数    14
1.6 静态查找问题    15
1.6.1 顺序查找    15
1.6.2 二分搜索    16
1.6.3 插值查找    18
1.7 算法分析的检查    18
1.8 大O分析的局限性    19
小结    20
关键概念    20
常见错误    21
网上资源    21
习题    21
参考文献    26
第2章 集合类API    27
2.1 引言    27
2.2 迭代器模式    28
2.2.1 基本的迭代器设计    29
2.2.2 基于继承的迭代器和工厂方法    30
2.3 集合类API:容器和迭代器    32
2.3.1 Collection接口    32
2.3.2 Iterator接口    35
2.4 泛型算法    36
2.4.1 Comparator函数对象    37
2.4.2 Collections类    37
2.4.3 二分搜索    39
2.4.4 排序    40
2.5 List接口    40
2.5.1 ListIterator接口    41
2.5.2 LinkedList类    42
2.6 栈和队列    44
2.6.1 栈    44
2.6.2 栈与计算机语言    45
2.6.3 队列    46
2.6.4 集合类API中的栈和队列    46
2.7 集合    47
2.7.1 TreeSet类    48
2.7.2 HashSet类    48
2.8 映射    52
2.9 优先级队列    55
小结    57
关键概念    57
常见错误    58
网上资源    58
习题    59
参考文献    61
第3章 递归    62
3.1 什么是递归    62
3.2 背景:数学归纳法证明    63
3.3 基本的递归    65
3.3.1 以任何数制打印数    66
3.3.2 为什么可行    67
3.3.3 原理解析    68
3.3.4 太多的递归可能是危险的    69
3.3.5 树的预习    70
3.3.6 其他实例    71
3.4 数值应用    74
3.4.1 模运算    74
3.4.2 模的幂运算    75
3.4.3 最大公因子和乘法逆元素    76
3.4.4 RSA密码系统    78
3.5 分治算法    79
3.5.1 连续子序列最大和的问题    80
3.5.2 对一个基本的分治情况的分析    82
3.5.3 分治算法运行时间的通用上界    84
3.6 动态规划    86
3.7 回溯    89
小结    92
关键概念    92
常见错误    93
网上资源    93
习题    94
参考文献    96
第4章 排序算法    97
4.1 排序为什么重要    97
4.2 预备知识    98
4.3 插入排序及其他简单排序算法的分析    98
4.4 谢尔排序    101
4.5 归并排序    103
4.5.1 有序数组的线性时间合并    103
4.5.2 归并排序算法    105
4.6 快速排序    106
4.6.1 快速排序算法    107
4.6.2 快速排序的分析    108
4.6.3 挑选中心点    111
4.6.4 一种划分策略    112
4.6.5 键等于中心点    113
4.6.6 三个元素的中值划分    114
4.6.7 小规模数组    114
4.6.8 Java快速排序程序    115
4.7 快速选择    117
4.8 排序的下界    118
小结    119
关键概念    119
常见错误    120
网上资源    120
习题    120
参考文献    123
第5章 随机化    124
5.1 为什么需要随机数    124
5.2 随机数生成器    125
5.3 非均匀分布随机数    129
5.4 产生随机排列    130
5.5 随机化算法    131
5.6 随机化素数检验    133
小结    135
关键概念    135
常见错误    136
网上资源    136
习题    136
参考文献    138
第二部分 应用
第6章 娱乐和游戏    140
6.1 单词搜索迷宫    140
6.1.1 理论    140
6.1.2 Java实现    142
6.2 Tic-Tac-Toe游戏    146
6.2.1 α—β剪枝    146
6.2.2 置换表    148
6.2.3 计算机象棋    151
小结    152
关键概念    152
常见错误    152
网上资源    152
习题    153
参考文献    154
第7章 栈和编译器    155
7.1 平衡符号检查器    155
7.1.1 基本算法    155
7.1.2 实现    156
7.2 简单计算器    163
7.2.1 后缀机    164
7.2.2 中缀到后缀的转化    165
7.2.3 实现    166
7.2.4 表达式树    172
小结    173
关键概念    173
常见错误    174
网上资源    174
习题    174
参考文献    175
第8章 实用程序    176
8.1 文件压缩    176
8.1.1 前缀编码    177
8.1.2 赫夫曼算法    178
8.1.3 实现    180
8.2 交叉引用生成器    191
8.2.1 基本思想    191
8.2.2 Java实现    191
小结    194
关键概念    194
常见错误    195
网上资源    195
习题    195
参考文献    197
第9章 模拟    198
9.1 约瑟夫问题    198
9.1.1 简单实现方案    199
9.1.2 更高效的算法    200
9.2 事件驱动模拟    202
9.2.1 基本思路    202
9.2.2 实例:调制解调器银行的模拟    203
小结    209
关键概念    209
常见错误    209
网上资源    209
习题    209
第10章 图和路径    211
10.1 图的定义    211
10.2 非加权的最短路径问题    221
10.2.1 理论    221
10.2.2 Java实现    223
10.3 非负权值的最短路径算法    224
10.3.1 理论:Dijkstra算法    224
10.3.2 Java实现    227
10.4 含负权值的最短路径问题    228
10.4.1 理论    228
10.4.2 Java实现    229
10.5 无环图的路径问题    230
10.5.1 拓扑排序    230
10.5.2 无环图最短路径算法的理论    232
10.5.3 Java实现    233
10.5.4 应用:关键路径分析    234
小结    236
关键概念    236
常见错误    237
网上资源    237
习题    238
参考文献    240
第三部分 实现
第11章 内部类和ArrayList的实现    242
11.1 迭代器与嵌套类     242
11.2 迭代器和内部类     244
11.3 AbstractCollection类    246
11.4 StringBuilder    249
11.5 使用迭代器的ArrayList的实现    250
小结    254
关键概念    254
常见错误    254
网上资源    254
习题    255
第12章 栈和队列    257
12.1 动态数组的实现    257
12.1.1 栈    257
12.1.2 队列    260
12.2 链表实现    265
12.2.1 栈    265
12.2.2 队列    267
12.3 两种实现方式的比较    270
12.4 java.util.Stack类    270
12.5 双向队列    271
小结    271
关键概念    272
常见错误    272
网上资源    272
习题    272
第13章 链表    273
13.1 基本思想    273
13.1.1 头结点    274
13.1.2 迭代器类    275
13.2 Java实现    276
13.3 双向链表和循环链表    281
13.4 有序链表    283
13.5 集合类API中LinkedList类的实现    284
小结    292
关键概念    292
常见错误    293
网上资源    293
习题    293
第14章 树    296
14.1 普通的树    296
14.1.1 定义    296
14.1.2 实现    297
14.1.3 应用:文件系统    298
14.2 二叉树    301
14.3 递归和树    306
14.4 树的遍历:迭代器类    307
14.4.1 后序遍历    310
14.4.2 中序遍历    313
14.4.3 前序遍历    314
14.4.4 层次遍历    316
小结    317
关键概念    317
常见错误    318
网上资源    318
习题    318
第15章 二叉查找树    321
15.1 基本思想    321
15.1.1 操作    322
15.1.2 Java实现    323
15.2 顺序统计量    329
15.3 二叉查找树操作的分析    332
15.4 AVL树    335
15.4.1 性质    335
15.4.2 单旋转    337
15.4.3 双旋转    339
15.4.4 AVL插入小结    341
15.5 红黑树    341
15.5.1 自下而上的插入    342
15.5.2 自上而下的红黑树    344
15.5.3 Java实现    345
15.5.4 自上而下的删除    350
15.6 AA树    352
15.6.1 插入    353
15.6.2 删除    354
15.6.3 Java实现    355
15.7 集合类API中TreeSet类和TreeMap类的实现    358
15.8 B树    371
小结    376
关键概念    376
常见错误    377
网上资源    377
习题    378
参考文献    379
第16章 散列表    382
16.1 基本概念    382
16.2 散列函数    383
16.3 线性探测法    385
16.3.1 线性探测法的直观分析    386
16.3.2 实际上所发生的:初始聚类    386
16.3.3 find操作的分析    387
16.4 二次探测法    388
16.4.1 Java实现    392
16.4.2 二次探测法的分析    398
16.5 分别链接散列    399
16.6 散列表与二叉查找树    399
16.7 散列表的应用    400
小结    400
关键概念    400
常见错误    401
网上资源    401
习题    401
参考文献    403
第17章 优先级队列:二叉堆    404
17.1 基本概念    404
17.1.1 结构性    405
17.1.2 堆的有序性    406
17.1.3 允许的操作    406
17.2 基本操作的实现    408
17.2.1 插入    408
17.2.2 deleteMin操作    410
17.3 buildHeap操作:线性时间的堆构造    411
17.4 高级操作:decreaseKey和merge    414
17.5 内排序:堆排序    414
17.6 外排序    416
17.6.1 为什么需要新的算法    417
17.6.2 外排序模型    417
17.6.3 简单算法    417
17.6.4 多路归并    418
17.6.5 多阶段归并    419
17.6.6 置换选择法    420
小结    421
关键概念    422
常见错误    422
网上资源    422
习题    422
参考文献    425
第四部分 高级数据结构
第18章 伸展树    428
18.1 自调整和均摊法的分析    428
18.1.1 均摊法时间限度    429
18.1.2 简单的自调整策略(并不管用)    429
18.2 基本的自底向上的伸展树    430
18.3 基本的伸展树操作    432
18.4 自底向上伸展的分析    432
18.5 自顶向下的伸展树    436
18.6 自顶向下伸展树的实现    439
18.7 伸展树与其他搜索树的比较    442
小结    442
关键概念    443
常见错误    443
网上资源    443
习题    443
参考文献    444
第19章 归并优先级队列    445
19.1 斜堆    445
19.1.1 归并是基本操作    445
19.1.2 满足堆有序性的树的简化归并    446
19.1.3 斜堆:一个简单的修改    446
19.1.4 斜堆的分析    447
19.2 偶堆    448
19.2.1 偶堆操作    449
19.2.2 偶堆的实现    450
19.2.3 应用:Dijkstra最短加权路径算法    455
小结    457
关键概念    457
常见错误    457
网上资源    457
习题    457
参考文献    458
第20章 不相交集类    459
20.1 等价关系    459
20.2 动态等价及应用    459
20.2.1 应用:生成迷宫    460
20.2.2 应用:最小生成树    462
20.2.3 应用:最近的共同祖先问题    463
20.3 快速查找算法    466
20.4 快速并算法    466
20.4.1 智能并算法    468
20.4.2 路径压缩    469
20.5 Java实现    470
20.6 按秩并和路径压缩的最坏情况    471
小结    476
关键概念    477
常见错误    478
网上资源    478
习题    478
参考文献    479
附录A 运算符    481
附录B 位运算符    482
暂无评论!