数据结构与STL

第1章 C+中的类 1
1.1 类 1
1.1.1 方法接口 1
1.1.2 对象 2
1.1.3 数据抽象 4
1.1.4 构造器 6
· · · · · · (更多)

第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 BinSearchIree迭代器 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
第4章 图、树和网络 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
· · · · · · (收起)