绪言——致成长中的程序员们 1
一、为什么要使用C++? 1
第一部分 理论基础 1
二、为什么要使用STL? 3
三、编程的一些规范 4
四、应当使用什么开发环境? 7
第1章 数据结构导论 11
1.1 数据结构与算法 11
1.1.1 数据结构 11
1.1.2 算法 13
1.2 数据结构的抽象形式——抽象数据类型 13
1.2.1 抽象数据类型 13
1.2.2 应用程序编程接口(API) 14
1.3 C++类和抽象数据类型 15
1.3.1 C++类 15
1.2.3 维护程序和文档 15
1.3.2 继承性 16
1.3.3 多态性 17
1.3.4 泛型设计和模板 18
1.4 运算与算法 19
1.4.1 运算 19
1.4.2 算法 20
1.5 算法分析 21
1.5.1 时空性能 21
1.5.2 时间复杂度分析 21
1.5.3 空间复杂度分析 25
1.5.4 算法分析与代码优化调整 26
第2章 C++语言概述 27
2.1 C++语言的演化和标准化历程 27
2.2 C++支持的程序设计风格 30
2.2.1 基于过程的程序设计 31
2.2.2 基于对象的程序设计 32
2.2.3 面向对象的程序设计 33
2.2.4 泛型程序设计 34
2.3 模块化程序设计 34
2.3.1 函数 34
2.3.2 类和封装机制 40
2.4 类的构造、析构和赋值 40
2.4.1 构造函数和析构函数 40
2.4.2 类的赋值 41
2.5 类层次结构——继承和多态 43
2.5.1 访问控制:public、private和protected继承 43
2.5.2 虚函数与多态 45
2.6 异常处理 46
2.6.1 异常处理的应用情况 46
2.6.2 异常处理基础知识 46
2.7 推荐的编程习惯和风格 48
2.6.3 其他错误处理技术 48
第3章 C++模板编程入门 52
3.1 类模板 53
3.1.1 如何定义类模板 53
3.1.2 如何实现类模板的成员函数 53
3.1.3 如何使用类模板 55
3.2 函数模板 56
3.2.1 如何定义函数模板 56
3.3 模板实例化 57
3.2.2 如何使用函数模板 57
3.4 模板的特化 61
3.4.1 类模板的特化 61
3.4.2 函数模板的特化 65
3.5 模板参数 66
3.6 静态成员和变量 69
3.7 模板和friend 71
3.8.2 函数对象的使用 72
3.8.1 如何定义函数对象 72
3.8 函数对象(仿函数) 72
3.8.3 模板函数对象 73
3.8.4 标准库中的函数对象 73
第4章 泛型设计、STL库与数据结构 75
4.1 标准C++与STL 76
4.1.1 模板——现代C++风格的基础 76
4.1.2 STL的发展历程 77
4.1.3 STL与C++标准程序库 78
4.1.4 STL的实现版本 80
4.1.5 准标准程序库:Boost库 81
4.1.6 泛型算法与STL的应用展示 83
4.2 泛型程序设计与多态 89
4.2.1 面向对象程序设计中的多态 89
4.2.2 泛型程序设计中的多态 90
4.2.3 GP与OOP的对比 91
4.3.1 STL库的设计:容器、算法与迭代器 93
4.3 泛型程序设计与STL 93
4.3.2 Accumulate函数示例 95
4.4 概念与模型 96
4.4.1 必要条件集合 96
4.4.2 示例:迭代器 97
4.5 关联类型与特性类 98
4.5.1 函数模板中需要的关联类型 98
4.5.2 类中的typedef嵌套 98
4.5.3 特性类的定义 99
4.5.4 部分特化 100
4.5.5 标签分派 101
4.6 STL中的核心concept:迭代器剖析 102
4.6.1 迭代器概述 102
4.6.2 迭代器与索引的比较 103
4.6.3 STL的迭代器分类 103
4.6.4 STL中迭代器种类的选择 109
4.7 STL的其他组件 111
4.7.1 STL的数据结构:容器 111
4.7.2 STL算法 113
4.7.3 函数对象 114
4.7.4 适配器 115
4.7.5 分配器 117
第二部分 基础数据结构 118
第5章 线性表 118
5.1 线性表概述 118
5.1.1 线性表基础知识 118
5.1.2 线性表类ADT 119
5.2 顺序存储结构——顺序表 120
5.2.1 顺序表的定义及特点 120
5.2.2 顺序表的遍历与查找 120
5.2.3 顺序表的其他操作 122
5.2.4 顺序表类ADT以及类定义 123
5.3 链式存储结构——链表 125
5.3.1 单链表 126
5.3.2 双向链表 128
5.3.3 循环链表 130
5.3.4 链表类ADT以及类定义 130
5.4 vector的基本操作及应用 133
5.4.1 vector迭代器 133
5.4.2 vector的基本操作 133
5.5 list的基本操作及应用 145
5.5.1 list迭代器 145
5.5.2 list的基本操作 145
5.6 slist的基本操作及应用 152
5.6.1 slist的迭代器 152
5.6.2 slist的基本操作 152
5.7 线性表的应用案例 154
5.7.1 稀疏多项式的加法和乘法 154
5.7.2 大整数加法 160
第6章 栈与队列 167
6.1 双端队列 167
6.1.1 deque概况 167
6.1.2 操作与应用 168
6.2 堆栈基础 169
6.2.1 堆栈的定义 169
6.2.2 堆栈ADT 170
6.3 栈的使用 171
6.3.1 进制转换 171
6.3.2 列车调度 172
6.4 表达式计算 174
6.4.1 中缀表达式转换为后缀表达式 174
6.4.2 后缀表达式的计算 178
6.4.3 测试 180
6.5.1 队列的定义 181
6.5 队列和优先队列 181
6.5.2 队列ADT 182
6.5.3 队列的实现 183
6.5.4 优先队列 184
6.6 使用队列 185
6.6.1 时间驱动的模拟 185
6.6.2 基数排序法 189
6.7 栈与队列的综合实例 192
6.7.1 农夫过河问题 192
6.7.2 深度优先搜索算法 195
6.7.3 广度优先搜索算法 197
第7章 递归 199
7.1 递归基础 199
7.1.1 递归的概念 199
7.1.2 使用递归的情况 200
7.2.2 问题的递归求解 202
7.2.1 问题的提出 202
7.2 汉诺塔问题 202
7.2.3 Hanoi类 205
7.3 迷宫问题 206
7.3.1 问题的提出 207
7.3.2 迷宫的回溯分析 207
7.3.3 Maze类 209
7.4 八皇后问题 212
7.4.1 问题的描述 212
7.4.2 八皇后问题的回溯分析 213
7.4.3 QueenChess类的设计 214
7.5 递归算法的评价 217
7.5.1 递归工作栈 217
7.5.2 递归算法的复杂度 218
7.5.3 递归与迭代的比较 219
8.1.1 序列容器与有序关联容器 221
8.1 树和二叉树基础知识 221
第8章 树和二叉树 221
8.1.2 广义树结构 222
8.1.3 二叉树的定义与性质 223
8.1.4 二叉树遍历算法 225
8.1.5 二叉树遍历算法的应用 226
8.2 二叉搜索树基础知识 228
8.2.1 二叉搜索树的定义 228
8.2.2 二叉搜索树的操作 229
8.2.3 二叉搜索树类ADT 230
8.2.4 二叉搜索树的结构 231
8.2.5 二叉搜索树的实现要点 232
8.2.6 二叉搜索树的迭代器 232
8.3 二叉树类算法的实现代码分析 233
8.3.1 二叉树类的声明与接口 233
8.3.2 二叉树的遍历操作实现 234
8.3.3 树遍历算法的应用 235
8.3.4 二叉树相关算法的测试程序 239
8.4 二叉搜索树类的实现代码分析 242
8.4.1 二叉搜索树节点和树类的声明 242
8.4.2 构造函数、析构函数和赋值运算符 245
8.4.3 二叉搜索树的查找与更新操作 247
8.4.4 二叉搜索树的测试程序 251
8.5 二叉搜索树应用案例 256
8.5.1 消除重复项 256
8.5.2 音像商店事务管理系统 258
第9章 图 266
9.1 图的抽象 267
9.1.1 图的描述 267
9.1.2 图的数据结构 270
9.2 图的算法 272
9.2.1 图搜索算法 272
9.2.2 拓扑排序 275
9.2.3 连通分量算法 277
9.2.4 最短路径问题 278
9.2.5 最小生成树问题 282
9.3 Boost图库介绍 285
9.3.1 STL中的泛型 285
9.3.2 BGL中的泛型 286
9.3.3 BGL中的图算法 287
9.3.4 BGL实现的数据结构 287
9.3.5 BGL的历史 288
9.4 图类的实现与应用 289
9.4.1 图的概念(Concepts) 289
9.4.2 图类的实现 293
9.4.3 图类应用示例 298
9.5 图算法的实现和应用 302
9.5.1 访问器 302
9.5.2 图遍历算法的应用 306
9.5.3 拓扑排序的应用 309
9.5.4 最短路径算法的应用 310
9.5.5 最小生成树算法的应用 314
9.6 图的建模与可视化——Graphviz软件与DOT语言 317
9.6.1 核心绘图引擎 318
9.6.2 图文件描述语言——DOT语言 319
9.6.3 Graphviz应用示例 322
第三部分 综合应用 329
第10章 综合应用案例 329
10.1 数据压缩——霍夫曼编码解码器的实现 329
10.1.1 数据压缩理论简介 329
10.1.2 Huffman树 330
10.1.3 需求分析 332
10.1.4 Huffman压缩类的接口与应用 335
10.1.5 Huffman压缩类的实现 339
10.1.6 Huffman解压缩 345
10.2.1 精确测定算法时间的困难 349
10.2 算法时间复杂度测度——算法计时器的实现 349
10.2.2 应用统计方法解决困难 350
10.2.3 完成自动分析的Timer类 353
10.2.4 应用Timer类测试STL sort算法时间性能 357
10.3 理论计算机科学家族谱的文档/视图模式——STL组件的综合应用 360
10.3.1 系统设计:“模型—视图—控制器”模式 360
10.3.2 数据关系建模与数据结构选择 362
10.3.3 从源数据文档到视图 364
10.3.4 完整的族谱视图程序以及运行示例 370
10.4 词典检索系统——数据结构选择对系统性能影响的示例 373
10.4.1 解决方案1:应用全排列的方法查找变位词 374
10.4.2 解决方案2:应用pair向量改进时间效率 377
10.4.3 解决方案3:使用映射改进空间效率 382
附录A Boost安装指南 386
附录B 随书所附光盘内容清单 391
附录C STL库容器类速查手册 392
- 《数据结构课程设计案例精编 用C/C++描述》李建学,李光元,吴春芳编著 2007
- 《数学建模案例精编》吴建国主编;汪名杰,李虎军,刘仁云副主编;王金山主审 2005
- 《数据库应用课程设计案例精编》王长松,秦琴,田瑛等编著 2009
- 《C语言课程设计案例精编》郭翠英等编著 2004
- 《数据库技术课程设计案例精编》杨昭主编;周军,郜林立,孙占林副主编 2006
- 《Visual FoxPro课程设计案例精编》张婷等编著 2004
- 《Visual FoxPro课程设计案例精编》张婷等编著 2004
- 《Java课程设计案例精编》黄晓东等编著 2007
- 《Visual FoxPro课程设计案例精编》詹斌,罗颂,余健编著 2008
- 《Access课程设计案例精编》毕超主编;何丽艳,冯雪,胡海鹰副主编 2006
- 《数据结构课程设计案例精编 用C/C++描述》李建学,李光元,吴春芳编著 2007
- 《机场工程设计优化与CAD技术》李光元,许巍,楼设荣等编著 2013
- 《21世纪交通版高等学校教材 机场工程系列教材 机场地势设计》李光元,楼设荣,许巍编著 2014
- 《排球教学训练理论与方法》唐春芳,袁文学著 2005
- 《为何不抓住飞碟》李建学,衡孝芬编著 2012
- 《教你学幽默》吴宏博,李建勇编著 2011
- 《Flash MX中文版动画实务》王绪溢,吴权威编著;李光普,樵书改编 2003
- 《皮肤病及性病学》于光元编著 1954
- 《祖国的第二大河-黄河》光元编著 1956
- 《中小学生最想知道的世界著名火山》胡元斌,李建学编著 2012
- 《THE GOVERNMENT/PRESS CONNECTION PRESS OFFICERS AND THEIR OFFICES》STEPHEN HESS 1984
- 《PRESS》POLITICS & PUBLIC OPINION IN BIHAR 1912-1947 2010
- 《Press law》Robin Callender Smith. 1978
- 《SUING THE PRESS》RODNEY A.SMOLLA 1986
- 《THE PRESS AND AMERICA》 2222
- 《FREEDOM OF THE PRESS》ERIC BARENDT 2009
- 《FREEDOM OF THE PRESS》ROB EDELMAN 2006
- 《FREEDOM OF THE PRESS》DAVID L.GEBERT 2005
- 《Racism and the press》Teun A.van Dijk 2016
- 《Im spiegel per presse 1》Albert Schmitz 1983