《数据结构与STL》(Data Structures and the Standard Template Library)扫描版[PDF]

2019-03-11 05:31|来源: 网络

中文名: 数据结构与STL
原名: Data Structures and the Standard Template Library
作者: William J.Collins
译者: 周翔
图书分类: 网络
资源格式: PDF
版本: 扫描版
出版社: 机械工业出版社
书号: 7111139623
发行时间: 2004年4月8日
地区: 大陆
语言: 简体中文
简介:

评论处1楼有网盘链接
内容介绍:
   数据结构一直是计算机科学专业课程的核心内容,它是信息的组织方式。对于相同的算法,用不同的数据结构表示其中的抽象数据类型会造成不同的执行效率。
   本书从面向对象程序设计的角度,具体使用c++语言,讲述了数据结构及其算法。通过对方法接口、示例和应用的学习,引导学生逐渐理解和掌握如何高效地使用数据结构。
   本书与传统数据结构教材相比,除了保留系统、全面的风格之外,还具有重视与实际编程结合、侧重标准模板库的实现描述等特点;并配有丰富的习题及实验,是一本优秀的课堂和自学参考用书。
内容截图:



目录:
出版者的话
专家指导委员会
译者序
前言
第1章 c++中的类 1
1.1 类 1
1.1.1 方法接口 1
1.1.2 对象 2
1.1.3 数据抽象 4
1.1.4 构造器 6
1.1.5 一个employee类 7
1.1.6 employee类的定义 11
实验1:company项目 13
1.1.7 继承 13
1.1.8 受保护的访问 14
1.1.9 hourlyemployee类 15
实验2:关于继承的更多的细节 18
1.1.10 运算符的重载 19
1.1.11 友元 20
实验3:重载运算符“=”和运算符“]]” 21
.1.1.12 信息隐藏 21
总结 22
习题 22
编程项目1.1:一个sequence类 25
第2章 容器类的存储结构 27
2.1 指针 27
2.1.1 堆和堆栈的对比 29
2.1.2 引用参数 29
2.1.3 指针字段 30
2.1.4 数组和指针 30
实验4:指针变量赋值与动态变量
赋值的对比 31
2.1.5 动态变量的存储空间释放 31
2.2 数组 32
2.3 容器类 33
2.3.1 容器类的存储结构 33
2.3.2 链式结构 34
2.3.3 迭代器 37
2.3.4 iterator类的设计和实现 39
实验5:定义其他的迭代器运算符 40
2.3.5 pop_front方法 40
2.3.6 析构器 41
实验6:重载运算符operator = 42
2.3.7 通用型算法 42
实验7:更多关于通用型算法的知识 46
2.3.8 数据结构和标准模板库 46
总结 46
习题 47
编程项目2.1:扩展linked类 47
第3章 软件工程简介 49
3.1 软件开发生命周期 49
3.2 问题分析 49
3.3 程序设计 51
3.3.1 方法接口和字段 51
3.3.2 依赖关系图 53
3.4 程序实现 54
3.4.1 方法验证 55
实验8:驱动器 56
3.4.2 正确性实现的可行性 56
3.4.3 方法效率评估 56
3.4.4 大o表示法 57
3.4.5 快速获取大o估算 59
3.4.6 平衡折中 62
3.4.7 运行时间分析 63
3.4.8 随机性 65
实验9:计时和随机性 66
3.4.9 类型转换 66
3.5 程序维护 67
总结 67
习题 67
编程项目3.1:linked类的进一步扩充 69
第4章 递归 71
4.1 简介 71
4.2 阶乘 71
4.3 十进制到二进制的转换 75
实验10:斐波纳契数 78
4.4 汉诺塔 78
4.5 回溯 86
4.6 折半查找 97
实验11:迭代折半查找 106
4.7 生成置换 106
4.8 间接递归 114
4.9 递归的代价 115
总结 116
习题 116
编程项目4.1:汉诺塔的迭代版本 121
编程项目4.2:八皇后问题 122
编程项目4.3:马的遍历问题 123
第5章 向量和双端队列 127
5.1 标准模板库 127
5.2 向量 128
5.2.1 vector类的方法接口 129
5.2.2 向量迭代器 134
5.2.3 向量和其他容器的对比 136
5.2.4 vector类可能的字段 137
5.2.5 vector类的一个实现 137
实验12:vector类的更多的实现细节 142
5.3 向量的一个应用:高精度算法 142
5.3.1 very_long_int类的设计 143
5.3.2 very_long_int类的一个实现 144
实验13:扩展very_long_int类 147
5.4 双端队列 147
实验14:惠普的deque类实现的更多细节 154
5.5 双端队列的一个应用:非常长的整数 154
总结 154
习题 155
编程项目5.1:扩展very_long_int类 157
编程项目5.2:deque类的另一种实现 157
第6章 表 159
6.1 表 159
6.1.1 list类的方法接口 160
6.1.2 迭代器接口 163
6.1.3 链表方法和向量或双端队列
方法的差别 165
6.1.4 list类的字段和实现 166
6.1.5 list节点的存储 171
实验15:更多list类的实现细节 174
实验16:计时顺序容器 174
实验17:迭代器,第二部分 174
6.1.6 list类的其他实现 175
6.2 链表应用:一个行编辑器 177
6.2.1 editor类的设计 180
6.2.2 editor类的实现 182
总结 187
习题 187
编程项目6.1:扩展editor类 189
编程项目6.2:list类的另一种设计和实现 195
第7章 队列和堆栈 197
7.1 队列 197
7.1.1 queue类的方法接口 197
7.1.2 使用queue类 200
7.1.3 容器配接器 201
7.1.4 一个接近的设计 202
7.2 计算机仿真 204
7.3 队列应用:洗车仿真 205
7.3.1 程序设计 207
7.3.2 carwash类的实现 208
7.3.3 carwash方法的分析 212
7.3.4 随机化到达时间 212
实验18:随机化到达时间 214
7.4 堆栈 214
7.4.1 stack类的方法接口 214
7.4.2 使用stack类 215
7.4.3 stack类是一个容器配接器 216
7.5 堆栈应用1:递归是如何实现的 216
7.6 堆栈应用2:将中缀转换成后缀 222
7.6.1 后缀表示法 224
7.6.2 转换矩阵 226
7.6.3 记号 227
实验19:将中缀转化成后缀 228
7.6.4 前缀表示法 228
总结 230
习题 231
编程项目7.1:扩展洗车仿真 232
编程项目7.2:求一个条件的值 233
编程项目7.3:一个迭代的迷宫搜索 237
编程项目7.4:queue类的另一个设计 237
第8章 二叉树和折半查找树 239
8.1 定义和属性 239
8.1.1 二叉树定理 245
8.1.2 外部路径长度 247
8.1.3 二叉树的遍历 248
8.2 折半查找树 253
8.2.1 binsearchtree类 254
8.2.2 binsearchtree类的iterator类 255
8.2.3 binsearchtree类的字段和实现 257
8.2.4 递归方法 261
8.2.5 binsearchtree迭代器 269
实验20:binsearchtree的平均高度 270
总结 270
习题 271
编程项目8.1:binsearchtree类的
另一种实现 274
第9章 avl树 277
9.1 平衡的折半查找树 277
9.2 旋转 277
9.3 avl树 281
9.3.1 avl树的高度 282
9.3.2 函数对象 284
实验21:更多的函数对象的细节 286
9.3.3 avltree类 286
9.3.4 fixafterinsertion方法 289
9.3.5 insert方法的正确性 297
9.4 avl树的应用:一个简单的
拼写检查器 299
总结 302
习题 302
编程项目9.1:avltree类的erase方法 305
编程项目9.2:改进的spellchecker项目 305
第10章 红黑树 307
10.1 红黑树 307
10.1.1 红黑树的高度 310
10.1.2 惠普的rb_tree类 313
10.1.3 rb_tree类中的insert方法 315
实验22:使用全部三种情况的红黑树插入 320
10.1.4 erase方法 320
实验23:erase的调用,其中应用了全部
四种情况 331
10.2 标准模板库的关联容器 331
10.3 集合应用:再次讨论拼写检查器 334
10.3.1 multiset类 335
实验24:更多与set和multiset类相关的
知识 336
10.3.2 map类 336
10.3.3 multimap类 339
实验25:更多与map和multimap类
相关的知识 340
总结 340
习题 340
编程项目10.1:一个简单的辞典 343
编程项目10.2:创建一个词汇索引 343
第11章 优先队列和堆 347
11.1 介绍 347
11.1.1 priority_queue类 348
11.1.2 priority_queue类的字段和实现 350
11.1.3 堆 351
实验26:优先队列中的公平性 359
11.1.4 priority_queue类的另一种
设计及实现 359
11.2 优先队列的应用:霍夫曼编码 360
11.2.1 huffman类的设计 364
11.2.2 huffman类的实现 366
总结 371
习题 372
编程项目11.1:解码一个消息 374
第12章 排序 377
12.1 介绍 377
12.2 排序能有多快 380
12.3 快速排序 382
12.3.1 树排序 382
12.3.2 堆排序 383
12.3.3 归并排序 385
12.3.4 快速排序 390
12.3.5 分治法算法 395
实验27:排序算法的运行时间 396
总结 396
习题 397
编程项目12.1:排序一个文件 402
第13章 查找和散列类 405
13.1 分析查找的框架 405
13.2 查找方式复习 405
13.2.1 顺序查找 405
13.2.2 折半查找 406
13.2.3 红黑树查找 408
13.3 hash_map类 408
13.3.1 hash_map类中的字段 409
13.3.2 散列 409
13.3.3 链式 412
13.3.4 iterator类的字段和实现 419
13.3.5 hash_map类的实现 420
13.3.6 链式散列分析 423
13.3.7 value_type类 425
13.3.8 应用 425
实验28:hash_map计时 427
13.4 hash_set类 427
13.5 开放地址散列 427
13.5.1 erase方法 430
13.5.2 主聚类 434
13.5.3 双散列 435
13.5.4 开放地址散列分析 439
总结 441
习题 442
编程项目13.1:使用链式和双散列构造一个
符号表的运行时间比较 444
第14章 图、树和网络 445
14.1 无向图 445
14.2 有向图 447
14.3 树 448
14.4 网络 450
14.5 图算法 451
14.5.1 迭代器 451
14.5.2 连通性 457
14.5.3 产生最小生成树 458
14.5.4 寻找网络中的最短路径 462
14.6 开发一个网络类 465
14.7 network类 465
14.7.1 network类中的字段 467
14.7.2 network类的实现 469
14.7.3 与边相关的方法的实现 470
14.7.4 全局方法的实现 472
14.7.5 get_minimum_spanning_tree方法 475
14.7.6 get_shortest_path方法 476
14.7.7 网络方法的时间花费估算 478
实验29:货郎担问题 479
14.7.8 network类的另一种设计和实现 479
14.8 回溯通过网络 481
总结 483
习题 484
编程项目14.1:完成邻接矩阵的实现 486
编程项目14.2:回溯通过一个网络 486
附录1 数学背景 489
附录2 string类 501
附录3 多态性 511
参考文献 515
索引 517


相关问答

更多
  • 我不确定你为什么会得到那个特定的错误(不知怎的,它认为他们使用<<运算符被定义为对std :: ostream进行rvalue引用),但看起来推荐的方式可能是专门化在TestAssert.h中看到的CppUnit :: assertion_traits模板。 像这样的东西: namespace CppUnit{ template struct assertion_traits>{ static bool equ ...
  • 我建议使用Closure Library(特别是关闭编译器)。 这里你有一个数据结构图书馆goog.structs 。 图书馆包含: goog.structs.AvlTree goog.structs.CircularBuffer goog.structs.Heap goog.structs.InversionMap goog.structs.LinkedMap goog.structs.Map goog.structs.PriorityQueue goog.structs.Set 例如,您可以使用单元测 ...
  • 他正在描述实施中给出的原子操作,“以某种方式”。 这是用硬件实现的一些伪代码。 He is describing an atomic operation which is given by the implementation, "somehow." That is pseudo-code for something implemented in hardware.
  • C标准不提供链表和堆栈等数据结构。一些编译器实现可能会提供自己的版本,但它们的使用在不同的编译器之间是不可移植的。 所以是的,你必须自己写。 The C Standard does not provide data structures like linked list and stack.Some compiler implementations might provide their own versions but their usage will be non portable across dif ...
  • 在C ++中编写复杂的数据结构时,我遵循了几条准则: 避免原始指针; 使用智能指针。 如果您的数据结构是循环的还是非循环的,请尽早弄清楚。 如果数据结构中存在循环,则无法在不创建泄漏的情况下在任何地方使用share_ptr。 在循环结构中的某个点上,您希望使用weak_ptr中断循环,以便可以释放对象。 如果我的对象保留在其他对象上,并且我希望它是一个容器,我会在需要它时实现适当的迭代器,而不是之前的一秒 。 当我想在容器上使用其中一个STL算法时,我通常需要迭代器支持。 当然,我可以实现与我自己使用的ST ...
  • Guava还有一些额外的数据结构,以及Apache Commons Collections库 。 Guava has a number of additional data structures, as well as the Apache Commons Collections library.
  • 快速回答 这是一个类比的快速回答。 松弛结构与正常的 0并发结构相当,这与正常的并发结构与正常的非并发结构相当。 应用程序中数据结构的大多数用法都是普通的非流动用途,要么是因为它们不共享,要么是因为某种类型的粗粒度锁定足以共享它们。 它们提供了一个简单的API,并且易于推理,即使在使用粗粒度锁定时存在并发访问也是如此。 举一个具体的例子,你可能会发现每次使用ConcurrentMap使用普通Map实现20到100次。 这并不能使ConcurrentMap变得无用! 在使用它的5%的地方,可能没有真正的替代品 ...
  • 这个问题似乎已经解决了 。 我实际上写了一个有点冗长的回复(推荐Glib,并提到Lua自5.0以来是麻省理工学院,而不是BSD),但是我的机器在中途坠毁:( This question already seems to be addressed here. I actually wrote a somewhat lengthy response (recommending Glib and mentioning that Lua since 5.0 is MIT, not BSD), however my ...
  • STL分为三个部分: 集装箱 迭代器 算法 您显然已经找到了容器部分,并且您可能已经使用了与容器关联的迭代器。 但是你所发现的迭代器还有更多。 算法部分通过迭代器链接到容器。 但是还包含零件手柄仿函数和相关的粘合剂。 我最喜欢的网站是: http ://www.sgi.com/tech/stl/table_of_contents.html 除了标准库之外,您还应该看一下boost库: 另见: Boost Library The STL is divided into three parts: Contain ...
  • 好吧,有GLib库,库,用于实现GTK +小部件集。 GLib使用GObject作为在C中进行OOP的一种方式。但GObjectified C以非常冗长而着称。 Well, there's the GLib library, library, which is what is used to implement the GTK+ widget set. GLib uses GObject as a way to do OOP in C. But GObjectified C is famous for be ...