热门关键字:  听力密码  听力密码  新概念美语  单词密码  巧用听写练听力
图书信息

数据结构、算法与应用(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程序,且程序结构清晰、构思精巧。本书是高等院校“数据结构”课程的理想教材,也是读者自学数据结构的极好读物。





最新评论共有 0 位网友发表了评论
发表评论
评论内容:不能超过250字,需审核,请自觉遵守互联网相关政策法规。
用户名: 密码:
匿名?
注册