数据结构与算法分析——C++描述(第3版)
5推荐 收藏
11.6K阅读
图灵计算机科学丛书

数据结构与算法分析——C++描述(第3版)

Mark Allen Weiss (作者) 张怀勇 (译者)
终止销售
本书是数据结构和算法分析的经典教材,书中使用主流的程序设计语言C++作为具体的实现语言。书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。本书适合作为计算机相关专业本科生的数据结构课程和研究生算法分析课程的教材。本科生的数据结构课程可以使用本书第1章~第9章,多学时课程还可以讲解第10章;研究生算法分析课程可以使用第6章~第12章。
纸质书
¥49.00

其他购买方式?

出版信息

  • 书  名数据结构与算法分析——C++描述(第3版)
  • 系列书名图灵计算机科学丛书
  • 执行编辑关于本书的内容有任何问题,请联系 傅志红
  • 出版日期2006-12-15
  • 书  号978-7-115-13923-8
  • 定  价49.00 元
  • 页  数448
  • 开  本16开
  • 出版状态终止销售
  • 原书名Data Structures and Algorithm Analysis in C++
  • 原书号0-321-37531-9

同系列书

本书特色

更新并测试了所有代码,确保与ANSI/ISO C++标准兼容。
STL(标准模板库)完全融合在全书之中。
完全修订了列表、栈和队列的内容。
简化了源代码,避免了与类模板的分离编译有关的复杂语法。
每章结尾都提供了丰富的习题,按难度划分,强调了各章的关键概念。

目录

第1章 引论    1
1.1 本书讨论的内容    1
1.2 数学知识复习    2
1.2.1 指数    2
1.2.2 对数    2
1.2.3 级数    3
1.2.4 模运算    4
1.2.5 证明方法    4
1.3 递归的简单介绍    6
1.4 C++类    9
1.4.1 基本class语法    9
1.4.2 特别的构造函数语法与访问函数    10
1.4.3 接口与实现的分离    11
1.4.4 vector和string    13
1.5 C++细节    14
1.5.1 指针    14
1.5.2 参数传递    15
1.5.3 返回值传递    16
1.5.4 引用变量    16
1.5.5 三大函数:析构函数、复制构造函数和operator=    17
1.5.6 C风格的数组和字符串    20
1.6 模板    21
1.6.1 函数模板    22
1.6.2 类模板    22
1.6.3 Object、Comparable和例子    24
1.6.4 函数对象    25
1.6.5 类模板的分离编译    26
1.7 使用矩阵    27
1.7.1 数据成员、构造函数和基本访问函数    27
1.7.2 operator[]    28
1.7.3 析构函数、复制赋值和复制构造函数    29
小结    29
练习    29
参考文献    30
第2章 算法分析    32
2.1 数学基础    32
2.2 模型    34
2.3 要分析的问题    34
2.4 运行时间计算    36
2.4.1 一个简单的例子    37
2.4.2 一般法则    37
2.4.3 最大子序列和问题的解    39
2.4.4 运行时间中的对数    44
2.4.5 检验你的分析    46
2.4.6 分析结果的准确性    47
小结    48
练习    48
参考文献    52
第3章 表、栈和队列    53
3.1 抽象数据类型(ADT)    53
3.2 表ADT    53
3.2.1 表的简单数组实现    54
3.2.2 简单链表    54
3.3 STL中的向量和表    55
3.3.1 迭代器    56
3.3.2 示例:对表使用erase    57
3.3.3 const_iterator    58
3.4 向量的实现    59
3.5 表的实现    63
3.6 栈ADT    71
3.6.1 栈模型    71
3.6.2 栈的实现    72
3.6.3 应用    72
3.7 队列ADT    78
3.7.1 队列模型    78
3.7.2 队列的数组实现    78
3.7.3 队列的应用    80
小结    81
练习    81
第4章 树    85
4.1 预备知识    85
4.1.1 树的实现    86
4.1.2 树的遍历及应用    87
4.2 二叉树    90
4.2.1 实现    90
4.2.2 一个例子——表达式树    91
4.3 查找树ADT——二叉查找树    93
4.3.1 contains    94
4.3.2 findMin和findMax    96
4.3.3 insert    97
4.3.4 remove    98
4.3.5 析构函数和复制赋值操作符    99
4.3.6 平均情况分析    99
4.4 AVL树    102
4.4.1 单旋转    104
4.4.2 双旋转    106
4.5 伸展树    111
4.5.1 一个简单的想法(不能直接使用)    112
4.5.2 伸展    113
4.6 树的遍历    118
4.7 B树    119
4.8 标准库中的set和map    123
4.8.1 set    123
4.8.2 map    124
4.8.3 set和map的实现    125
4.8.4 使用几个map的例子    126
小结    130
练习    130
参考文献    135
第5章 散列    137
5.1 基本思想    137
5.2 散列函数    137
5.3 分离链接法    139
5.4 不使用链表的散列表    142
5.4.1 线性探测    142
5.4.2 平方探测    144
5.4.3 双散列    148
5.5 再散列    148
5.6 标准库中的散列表    150
5.7 可扩散列    151
小结    153
练习    154
参考文献    156
第6章 优先队列(堆)    158
6.1 模型    158
6.2 一些简单的实现    159
6.3 二叉堆    159
6.3.1 结构性质    159
6.3.2 堆序性质    160
6.3.3 基本的堆操作    161
6.3.4 堆的其他操作    164
6.4 优先队列的应用    167
6.4.1 选择问题    167
6.4.2 事件模拟    168
6.5 d堆    169
6.6 左式堆    170
6.6.1 左式堆性质    170
6.6.2 左式堆操作    171
6.7 斜堆    175
6.8 二项队列    177
6.8.1 二项队列结构    177
6.8.2 二项队列操作    178
6.8.3 二项队列的实现    180
6.9 标准库中的优先队列    183
小结    185
练习    185
参考文献    189
第7章 排序    191
7.1 预备知识    191
7.2 插入排序    192
7.2.1 算法    192
7.2.2 插入排序的STL实现    192
7.2.3 插入排序的分析    194
7.3 一些简单排序算法的下界    194
7.4 谢尔排序    195
7.5 堆排序    198
7.6 归并排序    200
7.7 快速排序    204
7.7.1 选取枢纽元    206
7.7.2 分割策略    206
7.7.3 小数组    208
7.7.4 实际的快速排序例程    208
7.7.5 快速排序的分析    209
7.7.6 选择问题的线性期望时间算法    213
7.8 间接排序    213
7.8.1 vector<Comparable*>不运行    215
7.8.2 智能指针类    216
7.8.3 重载operator<    217
7.8.4 使用“*”解引用指针    217
7.8.5 重载类型转换操作符    217
7.8.6 随处可见的隐式类型转换    217
7.8.7 双向隐式类型转换会导致歧义    218
7.8.8 指针减法是合法的    218
7.9 排序算法的一般下界    218
7.10 桶排序    220
7.11 外部排序    220
7.11.1 为什么需要新算法    220
7.11.2 外部排序模型    221
7.11.3 简单算法    221
7.11.4 多路合并    222
7.11.5 多相合并    223
7.11.6 替换选择    223
小结    224
练习    225
参考文献    229
第8章 不相交集类    231
8.1 等价关系    231
8.2 动态等价性问题    231
8.3 基本数据结构    233
8.4 灵巧求并算法    235
8.5 路径压缩    237
8.6 按秩求并和路径压缩的最坏情形    239
8.7 一个应用    243
小结    245
练习    245
参考文献    246
第9章 图论算法    248
9.1 若干定义    248
9.2 拓扑排序    250
9.3 最短路径算法    252
9.3.1 无权最短路径    254
9.3.2 Dijkstra算法    257
9.3.3 具有负边值的图    262
9.3.4 无环图    263
9.3.5 所有顶点对的最短路径    265
9.3.6 最短路径举例    266
9.4 网络流问题    267
9.5 最小生成树    271
9.5.1 Prim算法    272
9.5.2 Kruskal算法    273
9.6 深度优先搜索的应用    275
9.6.1 无向图    276
9.6.2 双连通性    276
9.6.3 欧拉回路    279
9.6.4 有向图    282
9.6.5 查找强分支    283
9.7 NP完全性介绍    284
9.7.1 难与易    285
9.7.2 NP类    286
9.7.3 NP完全问题    286
小结    288
练习    288
参考文献    293
第10章 算法设计技巧    296
10.1 贪心算法    296
10.1.1 一个简单的调度问题    297
10.1.2 赫夫曼编码    299
10.1.3 近似装箱问题    303
10.2 分治算法    310
10.2.1 分治算法的运行时间    310
10.2.2 最近点问题    312
10.2.3 选择问题    315
10.2.4 一些算术问题的理论改进    317
10.3 动态规划    320
10.3.1 用表代替递归    320
10.3.2 矩阵乘法的顺序安排    322
10.3.3 最优二叉查找树    325
10.3.4 所有点对最短路径    327
10.4 随机化算法    329
10.4.1 随机数生成器    330
10.4.2 跳跃表    333
10.4.3 素性测试    335
10.5 回溯算法    337
10.5.1 公路收费点重建问题    337
10.5.2 博弈    341
小结    346
练习    346
参考文献    351
第11章 摊还分析    355
11.1 一个无关的智力问题    355
11.2 二项队列    356
11.3 斜堆    359
11.4 斐波那契堆    361
11.4.1 切除左式堆中的结点    362
11.4.2 二项队列的懒惰合并    364
11.4.3 斐波那契堆操作    366
11.4.4 时间界的证明    367
11.5 伸展树    368
小结    371
练习    371
参考文献    372
第12章 高级数据结构及其实现    374
12.1 自顶向下伸展树    374
12.2 红黑树    379
12.2.1 自底向上插入    380
12.2.2 自顶向下红黑树    381
12.2.3 自顶向下删除    385
12.3 确定性跳跃表    387
12.4 AA树    392
12.5 treap树    396
12.6 k-d树    399
12.7 配对堆    401
小结    405
练习    406
参考文献    408
附录 类模板的分离编译    411
索 引    414

相关文章

  • lt 8推荐

    算法书也可以写得很好玩

    Algorithms Copyright c 2006 S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani July 18, 2006 第13页写道 Let's be a little more conc…...

  • 被搁浅的鱼 4推荐

    写在离开之前(二)

    我为即将要来的面试,提前这半年要做的准备,写出来,一为提高自己,另一个则是给自己的硬性规定! 操作系统方面,需要阅读的书籍: 《现代操作系统第三版》、《操作系统精髓与设计原理》操作系统是所有技术的根基,里面包括了所有技术的基本思想,这两本书我准备相互印证的死磕! Java…...

  • 难道个人的读者就不是人吗?
    不是每个买书的人都是教师!!
    但我也是其中一个购书者!
    下载习题答案有什么不应该的!!!!!
    liming376  发表于 2009-03-29 10:34:38
    推荐
  • 顶楼上的,买书的一定是教师吗?国家鼓励学校用自己老师编写的教材,买书籍基本是读者自己买,自学,却下载不到答案,跟《c和指针》一样我做完课后习题却发现没课后参考答案对比自己写的答案!!!
    return  发表于 2012-03-29 21:18:29
    推荐
  • 才买了来,不知好不好
    tw  发表于 2007-08-09 21:39:14
    推荐
  • Very good!
    经典! 拜读中...
    Stark  发表于 2013-08-12 17:23:36
    推荐
  • 非常经典的书
    wking4  发表于 2015-09-29 23:35:33
    推荐
  • 没得卖了?
    Even_Geooc  发表于 2019-04-04 10:03:54
    推荐