《数据结构与算法分析——C++语言描述（第四版）》 - [美]Mark Allen Weiss[M. A. 韦斯] - 电子工业出版社 - 香港大書城

	登入帳戶　 \|　訂單查詢　 \|　購物車/收銀台(0)　\|　在線留言板　 \|　付款方式　 \|　運費計算　 \|　聯絡我們　 \|　幫助中心　\|　加入書簽
		會員登入新用戶登記

HOME

新書上架

暢銷書架

好書推介

2023年度TOP

臺灣用戶

品種：超過100萬種各類書籍/音像和精品，正品正價，放心網購，悭钱省心

服務：香港／台灣／澳門／海外

送貨：速遞／郵局／服務站

新書上架：簡體書繁體書
暢銷書架：簡體書繁體書
好書推介：簡體書繁體書

『簡體書』数据结构与算法分析——C++语言描述（第四版）

書城自編碼： 2886027
分類：簡體書→大陸圖書→教材→研究生/本科/专科教材
作者： [美]Mark Allen Weiss[M. A. 韦斯]
國際書號(ISBN)： 9787121290572
出版社：电子工业出版社
出版日期： 2016-08-01
版次： 1 印次： 1
頁數/字數： 508/
書度/開本： 16开釘裝：平塑

售價：HK$ 133.5

我要買件

** 我創建的書架 **
未登入.

新書推薦：

《现代无人机鉴赏（珍藏版）》
售價：HK$ 78.2

《汗青堂丛书·晚清风云（4册套装）：帝国的切口清朝与中华传统文化太平天国运动史冲击与回应》
售價：HK$ 427.8

《穿在身上的历史：世界服饰图鉴（增订珍藏版）》
售價：HK$ 557.8

《历史的严妆：解读道学阴影下的南宋史学（中华学术·有道）》
售價：HK$ 109.8

《海外中国研究·江南：中国文雅的源流》
售價：HK$ 76.2

《迟缓的巨人：“大而不能倒”的反思与人性化转向》
售價：HK$ 77.3

《我们去往何方：身体、身份和个人价值》
售價：HK$ 67.0

《大学问·批判的武器：罗莎·卢森堡与同时代思想者的论争》
售價：HK$ 98.6

建議一齊購買：

HK$ 133.5
《照明设计基础（第2版）》

HK$ 236.8
《Adobe After Effects CC完全剖析》

HK$ 150.8
《骑行宝典——单车维修保养完全手册》

HK$ 182.9
《Go语言程序设计》

HK$ 180.2
《AP生物5分制胜（久经考验的美国课堂教材，助考生斩获AP考试》

編輯推薦：

本版特色如下：
*书中的阐述和算法均用C 新标准C 11的代码实现。
*unordered_map两个类模板的简要讨论。
*增加了基数排序和与选择相关问题下界的证明。增加了对AVL树删除算法的实现。使用新的unionfind分析同时改进此前各版的较弱的OMlog*N界。

內容簡介：

本书是数据结构和算法分析的经典教材，书中使用主流的程序设计语言C++作为具体的实现语言。书中内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。本书把算法分析与C++程序的开发有机地结合起来，深入分析每种算法，内容全面、缜密严格，并细致讲解精心构造程序的方法。

關於作者：

冯舜玺，天津师范大学数学科学学院退休教授，曾任天津市计算数学学会常务理事，主要教学及研究方向为数值代数，组合数学，数据结构与算法分析。 Mark Allen Weiss，佛罗里达国际大学计算与信息科学学院教授、副院长，本科教育主任和研究生教育主任。他于1987年获得普林斯顿大学计算机科学博士学位，师从Bob Sedgewick。他曾经担任全美APAdvanced Placement考试计算机学科委员会的主席2000-2004。Weiss教授在数据结构和算法分析方面卓有建树，他的数据结构和算法分析的著作尤其畅销，并受到广泛好评．已被世界500余所大学用作教材。

第1章程序设计：综述1
1.1 本书讨论的内容1
1.2 数学知识复习2
1.2.1 指数exponent2
1.2.2 对数logarithm2
1.2.3 级数series3
1.2.4 模运算modular arithmetic4
1.2.5 证明方法5
1.3 递归简论7
1.4 C++类10
1.4.1 基本的class语法10
1.4.2 构造函数的附加语法和访问
函数11
1.4.3 接口与实现的分离13
1.4.4 vector类和string类16
1.5 C++细节17
1.5.1 指针pointer18
1.5.2 左值、右值和引用19
1.5.3 参数传递21
1.5.4 返回值传递23
1.5.5 std::swap和std::move25
1.5.6 五大函数：析构函数，拷贝构造
函数，移动构造函数，拷贝赋值
operator=，移动赋值operator=26
1.5.7 C风格数组和字符串30
1.6 模板31
1.6.1 函数模板31
1.6.2 类模板32
1.6.3 Object、Comparable和一个
例子33
1.6.4 函数对象34
1.6.5 类模板的分离式编译37
1.7 使用矩阵37
1.7.1 数据成员、构造函数和基本访问
函数38
1.7.2 operator[]38
1.7.3 五大函数39
小结39
练习39
参考文献41
第2章算法分析42
2.1 数学基础42
2.2 模型44
2.3 要分析的问题44
2.4 运行时间计算47
2.4.1 一个简单的例子47
2.4.2 一般法则47
2.4.3 最大子序列和问题的求解49
2.4.4 运行时间中的对数54
2.4.5 最坏情形分析的局限性57
小结58
练习58
参考文献63
第3章表、栈和队列64
3.1 抽象数据类型ADT64
3.2 表ADT64
3.2.1 表的简单数组实现65
3.2.2 简单链表65
3.3 STL中的vector和list67
3.3.1 迭代器68
3.3.2 例子：对表使用erase69
3.3.3 const_iterators70
3.4 vector的实现72
3.5 list的实现76
3.6 栈ADT86
3.6.1 栈模型86
3.6.2 栈的实现86
3.6.3 应用87
3.7 队列ADT93
3.7.1 队列模型93
3.7.2 队列的数组实现93
3.7.3 队列的应用95
小结96
练习96
第4章树100
4.1 预备知识100
4.1.1 树的实现101
4.1.2 树的遍历及应用102
4.2 二叉树105
4.2.1 实现105
4.2.2 一个例子——表达式树105
4.3 查找树ADT——二叉查找树108
4.3.1 contains110
4.3.2 findMin和findMax111
4.3.3 insert112
4.3.4 remove113
4.3.5 析构函数和拷贝构造函数115
4.3.6 平均情况分析115
4.4 AVL树118
4.4.1 单旋转119
4.4.2 双旋转121
4.5 伸展树128
4.5.1 一个简单的想法不能直接
使用128
4.5.2 展开130
4.6 树的遍历134
4.7 B树135
4.8 标准库中的集合与映射140
4.8.1 集合set140
4.8.2 映射map141
4.8.3 set和map的实现142
4.8.4 使用多个映射map的例142
小结147
练习147
参考文献153
第5章散列155
5.1 一般想法155
5.2 散列函数155
5.3 分离链接法157
5.4 不用链表的散列表161
5.4.1 线性探测法161
5.4.2 平方探测法163
5.4.3 双散列166
5.5 再散列167
5.6 标准库中的散列表169
5.7 以最坏情形O1访问的散列表170
5.7.1 完美散列170
5.7.2 杜鹃散列172
5.7.3 跳房子散列181
5.8 通用散列184
5.9 可扩散列186
小结188
练习189
参考文献193
第6章优先队列堆196
6.1 模型196
6.2 一些简单的实现197
6.3 二叉堆197
6.3.1 结构性质197
6.3.2 堆序性质198
6.3.3 基本的堆操作199
6.3.4 其他的堆操作203
6.4 优先队列的应用206
6.4.1 选择问题206
6.4.2 事件模拟207
6.5 d堆208
6.6 左式堆209
6.6.1 左式堆的性质209
6.6.2 左式堆操作210
6.7 斜堆215
6.8 二项队列216
6.8.1 二项队列构建216
6.8.2 二项队列操作217
6.8.3 二项队列的实现219
6.9 标准库中的优先队列224
小结225
练习225
参考文献229
第7章排序232
7.1 预备知识232
7.2 插入排序233
7.2.1 算法233
7.2.2 插入排序的STL实现233
7.2.3 插入排序的分析235
7.3 一些简单排序算法的下界235
7.4 希尔排序236
7.4.1 希尔排序的最坏情形分析237
7.5 堆排序239
7.5.1 堆排序的分析241
7.6 归并排序242
7.6.1 归并排序的分析245
7.7 快速排序247
7.7.1 选取枢纽元249
7.7.2 分割策略250
7.7.3 小数组252
7.7.4 实际的快速排序例程252
7.7.5 快速排序的分析254
7.7.6 选择问题的线性期望时间
算法256
7.8 排序算法的一般下界258
7.8.1 决策树258
7.9 选择问题的决策树下界260
7.10 对手下界adversary lower
bounds262
7.11 线性时间排序：桶式排序和
基数排序265
7.12 外部排序269
7.12.1 为什么需要一些新的算法269
7.12.2 外部排序模型269
7.12.3 简单算法269
7.12.4 多路合并270
7.12.5 多相合并271
7.12.6 替换选择272
小结273
练习题273
参考文献278
第8章不相交集类281
8.1 等价关系281
8.2 动态等价性问题281
8.3 基本数据结构283
8.4 灵巧求并算法286
8.5 路径压缩288
8.6 按秩求并和路径压缩的最坏
情形289
8.6.1 缓慢增长的函数289
8.6.2 通过递归分解进行的分析290
8.6.3 一个OM log*N界295
8.6.4 一个OMαM, N界296
8.7 一个应用297
小结299
练习299
参考文献301
第9章图论算法303
9.1 若干定义303
9.1.1 图的表示304
9.2 拓扑排序305
9.3 最短路径算法308
9.3.1 无权最短路径309
9.3.2 Dijkstra算法312
9.3.3 具有负边值的图317
9.3.4 无圈图318
9.3.5 所有顶点对间的最短路径320
9.3.6 最短路径的例320
9.4 网络流问题322
9.4.1 一个简单的最大流算法323
9.5 最小生成树326
9.5.1 Prim算法327
9.5.2 Kruskal算法329
9.6 深度优先搜索的应用330
9.6.1 无向图331
9.6.2 双连通性332
9.6.3 欧拉回路335
9.6.4 有向图338
9.6.5 查找强分支339
9.7 NP完全性介绍340
9.7.1 难与易341
9.7.2 NP类341
9.7.3 NP完全问题342
小结344
练习344
参考文献350
第10章算法设计技巧353
10.1 贪婪算法353
10.1.1 一个简单的调度问题354
10.1.2 哈夫曼编码355
10.1.3 近似装箱问题359
10.2 分治算法366
10.2.1 分治算法的运行时间367
10.2.2 最近点问题369
10.2.3 选择问题371
10.2.4 一些算术问题的理论改进374
10.3 动态规划377
10.3.1 用表代替递归377
10.3.2 矩阵乘法的顺序安排379
10.3.3 最优二叉查找树382
10.3.4 所有点对最短路径384
10.4 随机化算法386
10.4.1 随机数发生器387
10.4.2 跳跃表392
10.4.3 素性测试393
10.5 回溯算法396
10.5.1 收费公路重建问题396
10.5.2 博弈400
小结405
练习406
参考文献413
第11章摊还分析418
11.1 一个无关的智力问题418
11.2 二项队列419
11.3 斜堆423
11.4 斐波那契堆425
11.4.1 切除左式堆中的节点425
11.4.2 二项队列的懒惰合并427
11.4.3 斐波那契堆操作429
11.4.4 时间界的证明430
11.5 伸展树432
小结436
练习436
参考文献437
第12章高级数据结构及其实现439
12.1 自顶向下伸展树439
12.2 红黑树445
12.2.1 自底向上的插入446
12.2.2 自顶向下红黑树447
12.2.3 自顶向下删除452
12.3 treap树453
12.4 后缀数组和后缀树456
12.4.1 后缀数组456
12.4.2 后缀树458
12.4.3 后缀数组和后缀树的线性
时间构建461
12.5 k-d树471
12.6 配对堆474
小结479
练习479
参考文献483
附录A 类模板的分离式编译486
索引489

內容試閱：

前言
目的目标
本书是《数据结构与算法分析C语言描述》的第四版，论述组织大量数据的方法数据结构，以及算法运行时间的估计算法分析。随着计算机的速度越来越快，对于能够处理大量输入数据的程序需求变得日益急迫。可是，由于在输入量很大时程序的低效率显得非常突出，因此又要求对效率问题给予更加严密的关注。通过在实际编程之前对算法进行分析，学生们可以确定一个特定的解决方案是否可行。例如，在本书中学生可查阅一些特定的问题并看到精心的实现怎样能够把处理大量数据的时间限制从若干个世纪减至不到一秒。因此，若无运行时间的阐释，就不会有算法和数据结构的提出。在某些情况下，对于影响实现的运行时间的一些微小细节都需要认真的探究。
一旦解法被确定，接着就要编写程序。随着计算机功能的日益强大，它们必须解决的问题就变得更加庞大和复杂，这就要求开发更加复杂的程序。本书的目标是同时教授学生良好的程序设计技巧和算法分析能力，使他们开发的程序能够具有最高的效率。
本书适合于高等数据结构课程或是算法分析第一年的研究生课程。学生应该具有中等程度的程序设计知识，包括指针、递归以及面向对象程序设计这样一些内容，此外还要具有一些离散数学的基础。
处理方法
虽然本书的内容大部分都与语言无关，但是，程序设计还是需要使用某种特定的语言。正如书名指出的，我们为本书选择了C。
C已经成为主流系统编程语言。除修复C语言的许多语法漏洞之外，C还提供一些直接结构类和模板来实现作为抽象数据类型的泛型数据结构。
编写本书最困难的部分是决定C所占的篇幅。使用太多C的特性将使本书难以理解，使用太少又会使读者得不到比支持类的C语言教材更多的收获。
我们所采取的做法是以一种基于对象的处理方式展示书中的内容。这样，本书几乎不存在对继承的使用。书中以类模板描述泛型数据结构。一般我们避免深奥的C特性，但是使用了vector类和string类，如今它们已是C标准的一部分。本书以前各版通过把类模板接口从其实现中分离出来已经做到了对类模板的实现。虽然这是有争议的首选方式，但它揭示出编译器使读者难以具体使用代码的一些问题。因此，这一版中联机代码把类模板作为一个独立的单元来介绍，无需接口与实现的分离。第1章提供了用于全书的C特性的综述，并描述了我们对类模板的处理方式。附录A阐述如何能够重写类模板以使用分离式编译。
以C和Java二者描述的数据结构的完全版可在互联网上获得。我们使用类似的编码约定以使得这两种语言间平行的结构表现得更加明显。
第四版最重要的变化概述
本书第四版吸收了大量对错误的修正，书中许多部分经过修订以增加表述的清晰度。此外：
? 第4章包含AVL树删除算法的实现，它是一个常常被读者提出的论题。
? 第5章已被广泛修订和扩展，现已包含两个更新的算法：杜鹃散列和跳房子散列。此外，还添加了论述通用散列的新的一节。对C中引入的unordered_set和unordered_ map两个类模板的简要讨论也是新加的内容。
? 第6章基本没有变化，不过，二叉堆的实现用到了C11版引入的移动操作move operation。
? 现在的第7章增加了基数排序的内容，并添加了新的一节，论述下界的证明。排序的程序用到C11版中引入的移动操作。
? 第8章使用由Seidel和Sharir所作的新的unionfind分析，并证明了OM?M, N的界以代替前面各版较弱的OM log*N界。
? 第12章添加了论述后缀树和后缀数组的材料，包括Karkkainen和Sanders的后缀数组线性时间构建算法及其实现。删除了讨论确定性跳跃表和AA树的两节。
? 全书所出现的代码均用C11作了更新。值得注意的是，这意味着C11新特性的使用，包括auto关键字、范围for循环、移动构造和赋值，以及统一初始化uniform initialization。
内容提要
第1章包含离散数学和递归的一些复习材料。我相信熟练处置递归唯一的办法是反复不断地研读一些好的用法。因此，除第5章外，递归遍及本书每一章的例子之中。另外，第1章还介绍了一些材料，作为对基本C的回顾，包括在C类设计中对模板和一些重要结构的讨论。
第2章处理算法分析。这一章阐述渐近分析和它的主要弱点。这里提供了许多例子，包括对对数运行时间的深入解释。通过直观地把一些简单递归程序转变成迭代程序而对它们进行分析。介绍了更复杂的分治程序，不过有些分析求解递推关系将推迟到第7章再详细阐述。
第3章包括表、栈和队列。这一章包括对STL中vector类和list类的讨论，其中涉及到迭代器的一些材料，并提供对STL中vector类和list类的重要子集的实现。
第4章讨论树，重点在查找树，包括外部查找树B树。UNIX文件系统和表达式树是作为例子来使用的。本章还介绍了AVL树和伸展树。关于查找树实现细节的更详细的处理放在第12章介绍。树的另外一些内容，如文件压缩和博弈树，推迟至第10章讨论。外部媒体上的数据结构作为几章中的最后论题来考虑。STL中set类和map类的讨论也在本章进行，其中包括一个重要的例子，该例使用3个分离的映射高效地解决一个问题。
第5章讨论散列表，包括诸如分离链接法以及线性探测法和平方探测法这样一些经典算法，此外还有几个新算法，即杜鹃散列和跳房子散列。通用散列也在这里讨论，而对可扩散列的讨论则放在本章末尾进行。
第6章是关于优先队列的。二叉堆也安排在这里，还有些额外的材料论述优先队列某些理论上有趣的实现。斐波那契堆在第11章讨论，配对堆在第12章讨论。
第7章是排序。它是关于编程细节和分析的非常特殊的一章。所有重要的通用排序算法均被讨论并进行了比较。详细分析了4种算法：插入排序，希尔排序，堆排序，以及快速排序。本版新增加了基数排序和一些与选择相关问题的下界证明。外部排序的讨论安排在本章的末尾进行。
第8章讨论不相交集算法并证明其运行时间。这是短小且特殊的一章，如果不讨论Kruskal算法则该章可以跳过。
第9章讲授图论算法。图论算法的趣味性不仅因为它们在实践中经常发生，而且还因为它们的运行时间强烈地依赖于数据结构的恰当使用。实际上，所有标准算法都是和相应的数据结构、伪代码以及运行时间的分析一起介绍的。为把这些问题放在一个适当的上下文环境下，本章对复杂性理论包括NP完全性和不可判定性进行了简要的讨论。
第10章通过考查一些常见问题的求解技巧来讨论算法设计。这一章通过大量实例而得到强化。这里及后面各章使用的伪代码使得学生对一个算法实例的理解不至于被实现的细节所困扰。
第11章处理摊还分析。对来自第4章和第6章的3种数据结构以及本章介绍的斐波那契堆进行了分析。
第12章讨论查找树算法、后缀树和后缀数组、k-d树、配对堆。不同于其他各章，本章为查找树和配对堆提供了完全和审慎的实现。材料的安排使得教师可以把一些内容整合到其他各章的讨论中。例如，第12章中的自顶向下红黑树可以和AVL树第4章的一起讨论。
第1章～第9章为大多数一学期的数据结构课程提供了足够的材料。如果时间允许，那么第10章也可以包括进来。研究生的算法分析课程可以使用第7章～第11章的内容。在第11章所分析的高级数据结构可以容易地在前面各章中查到。第9章中对NP完全性的讨论太过简单，以至于不足以用于这样的一门算法分析课程。读者将会发现，参阅一些论述NP完全性的著述对深化本书内容大有裨益。
练习
在每章末尾提供的练习与正文中讲授内容的顺序相匹配。最后的一些练习是把一章作为一个整体来处理而不是针对特定的某一节来考虑的。难做的练习标以一个星号，更难的练习标注两个星号。
参考文献
参考文献列于每章的最后。一般说来，这些参考文献或者是历史性质的，代表着书中材料的原始来源，或者阐述对正文中给出结果的扩展和改进。有些文献提供一些练习的解法。
补充材料
所有读者均可从网站http：cssupport.pearsoncmg.com上获取下列补充资料：
? 例子程序的源代码
? 勘误表
此外，下列材料只提供给Pearson Instructor Resource Center www.pearsonhighered.comirc上有资格的教师。如欲获取这些资料，可访问IRC或你的Pearson Education销售代表。
? 书中挑选的一些练习的解答
? 本书中的一些图示
? 勘误表
致谢
在该丛书几部著作的准备过程中作者得到了许许多多朋友的帮助，有些人在本书的其他版本中列出。谢谢所有诸位。
如同往常一样，Pearson专家们的努力使得本书的写作过程更加轻松。我愿意借此机会感谢我的编辑Tracy Johnson，以及制作编辑Marilyn Lloyd。贤妻Jill因其所做的每一件工作应该得到我特别的感谢。
最后，我还要感谢广大的读者，他们发送E-mail信息并指出较早各版的错误和矛盾之处。我的网站www.cis.fiu.edu~weiss也将包含更新后C和Java的源代码，一个勘误表，以及到提交问题报告的一个链接。
M．A．W．
Miami，Florida

書城介紹　 \|　合作申請　\|　索要書目　 \|　新手入門　\|　聯絡方式　 \|　幫助中心　\|　找書說明　 \|　送貨方式　\|　付款方式	香港用户　 \|　台灣用户　\|　海外用户

	megBook.com.hk
Copyright © 2013 - 2024 （香港）大書城有限公司　 All Rights Reserved.