本书是数据结构案例教程，以软件重用为指导思想，以STL库中实现的数据结构（容器)为参照，重构了数据结构的视角和知识体系，并突出实战性和应用性。全书共分三部分：第一部分是理论基础，介绍数据结构和算法的基础知识，C++语言的关键特征以及支撑STL设计的核心理念和机制；第二部分是基础数据结构，涵盖了基础的数据结构，并包含丰富的例子；第三部分是综合应用，包括4个大的案例，是对前面章节所讲的基础数据结构的综合应用。本书附带的光盘中包含经过主流C++编译器编译通过的所有程序的源代码及编译后生成的可执行程序和第三方软件。本书将C++泛型编程知识与数据结构知识紧密地结合在了一起，是国内比较罕见的、有技术深度的、符合现代发展方向的优秀教材／教辅读物。本书适合于在校信息科学与技术类学生作为课程设计指导用书，亦可随数据结构课程同步学习，也非常适合于工作中的程序员以更加实践化的角度温习和应用数据结构。

本书具体内容安排如下：第一部分是理论基础，包括绪论和第1、2、3、4章，介绍数据结构和算法的基础知识，C++语言的关键特征以及支撑STL设计的核心理念和机制。第二部分是基础数据结构，从第5章到第9章，涵盖了基础的数据结构，并包含丰富的例子。第三部分（即第10章）是综合应用，包括4个大的案例，是对前面章节所讲的基础数据结构的综合应用。

第一部分 理论基础

绪言——致成长中的程序员们

一、为什么要使用C++?

二、为什么要使用STL?

三、编程的一些规范

四、应当使用什么开发环境?

第1章 数据结构导论

1.1数据结构与算法

1.1.1数据结构

1.1.2算法

1.2数据结构的抽象形式——抽象

数据类型

1.2.1抽象数据类型

1.2.2应用程序编程接口(API)

1.2.3维护程序和文档

1.3C++类和抽象数据类型

l.3.1C++类

113.2继承性

1.3.3多态性

1.3.4泛型设计和模板

1.4运算与算法

1.4.1运算

1.4.2算法

1.5算法分析

1.5.1时空性能

1.5.2时问复杂度分析

1.5.3空间复杂度分析

1.5.4算法分析与代码优化调整

第2章 C++语言概述

2.1C++语言的演化和

标准化历程

2.2C++支持的程序设计风格

2.2.1基于过程的程序设计

2.2.2基于对象的程序设计

2.2.3面向对象的程序设计

2.2.4泛型程序设计

2.3模块化程序设计

2.3.1函数

2.3.2类和封装机制

2.4类的构造、析构和赋值

2.4.1构造函数和析构函数

2.4.2类的赋值

2.5类层次结构——继承和多态

2.5.1访问控制：public、private

和protected继承

2.5.2虚函数与多态

2.6异常处理

2.6.1异常处理的应用情况

2.6.2异常处理基础知识

2.6.3其他错误处理技术

2.7推荐的编程习惯和风格

第3章 C++模板编程入门

3.1类模板

3.1.1如何定义类模板

3.1.2如何实现类模板的

成员函数

3.1.3如何使用类模板

3.2函数模板

3.2.1如何定义函数模板

3.2.2如何使用函数模板

3.3模板实例化

3.4模板的特化

3.4.1类模板的特化

3.4.2函数模板的特化

3.5模板参数

3.6静态成员和变量

3.7模板和friend

3.8函数对象(仿函数)

3.8.1如何定义函数对象

3.8.2函数对象的使用

3.8.3模板函数对象

3.8.4标准库中的函数对象

第4章 泛型设计、STL库

与数据结构

4.1标准C++与STL

4.1.1模板——现代C++风格

的基础

4.1.2STL的发展历程

4.1.3STL与C++标准程序库

4.1.4STL的实现版本

4.1.5准标准程序库：Boost库

4.1.6泛型算法与STL的

应用展示

4.2泛型程序设计与多态

4.2.1面向对象程序设计中

的多态

4.2.2泛型程序设计中的多态

4.2.3GP与OOP的对比

4.3泛型程序设计与STL.

4.3.1STL库的设计：容器、

算法与迭代器

4.3.2Accumulate函数示例

4.4概念与模型

4.4.1必要条件集合

4.4.2示例：迭代器

4.5关联类型与特性类

4.5.1函数模板中需要的

关联类型

4.5.2类中的typedef嵌套

4.5.3特性类的定义

4.5.4部分特化

4.5.5标签分派

4.6STL中的核心concept：

迭代器剖析

4.6.1迭代器概述

4.6.2迭代器与索引的比较

4.6.3STL的迭代器分类

4.6.4STL中迭代器种类

的选择

4.7STL的其他组件

4.7.1STL的数据结构：容器

4.7.2STL算法

4.7.3函数对象

4.7.4适配器

4.7.5分配器

第二部分 基础数据结构

第5章 线性表

5.1线性表概述

5.1.1线性表基础知识

5.1.2线性表类ADT

5.2顺序存储结构——顺序表

5.2.1顺序表的定义及特点

5.2.2顺序表的遍历与查找

5.2.3顺序表的其他操作

5.2.4顺序表类ADT

以及类定义

5.3链式存储结构——链表

5.3.1单链表

5.3.2双向链表

5.3.3循环链表

5.3.4链表类ADT以及类定义

5.4vector的基本操作及应用

5.4.1vector迭代器

5.4.2vector的基本操作

5.5list的基本操作及应用

5.5.1list迭代器

5.5.2list的基本操作

5.6slist的基本操作及应用

5.6.1slist的迭代器

5.6.2slist的基本操作

5.7线性表的应用案例

5.7.1稀疏多项式的加法

和乘法

5.7.2大整数加法

第6章 栈与队列

6.1双端队列

6.1.1deque概况

6.1.2操作与应用

6.2堆栈基础

6.2.1堆栈的定义

6.2.2堆栈ADT

6.3栈的使用

6.3.1进制转换

6.3.2列车调度

6.4表达式计算

6.4.1中缀表达式转换为

后缀表达式

6.4.2后缀表达式的计算

6.4.3测试

6.5队列和优先队列

6.5.1队列的定义

6.5.2队列ADT

6.5.3队列的实现

6.5.4优先队列

6.6使用队列

6.6.1时间驱动的模拟

6.6.2基数排序法

6.7栈与队列的综合实例

6.7.1农夫过河问题

6.7.2深度优先搜索算法

6.7.3广度优先搜索算法

第7章 递归

7.1递归基础

7.1.1递归的概念

7.1.2使用递归的情况

7.2汉诺塔问题

7.2.1问题的提出

7.2.2问题的递归求解

7.2.3Hanoi类

7.3迷宫问题

7.3.1问题的提出

7.3.2迷宫的回溯分析

7.3.3Maze类

7.4八皇后问题

7.4.1问题的描述

7.4.2八皇后问题的回溯分析

7.4.3QueenChess类的设计

7.5递归算法的评价

7.5.1递归工作栈

7.5.2递归算法的复杂度

7.5.3递归与迭代的比较

第8章 树和二叉树

8.1树和二叉树基础知识

8.1.1序列容器与有序关联容器

8.1.2广义树结构

8.1.3二叉树的定义与性质

8.1.4二叉树遍历算法

8.1.5二叉树遍历算法的应用

8.2二叉搜索树基础知识

8.2.1二叉搜索树的定义

8.2.2二叉搜索树的操作

8.2.3二叉搜索树类ADT’

8.2.4二叉搜索树的结构

8.2.5二叉搜索树的实现要点

8.2.6二叉搜索树的迭代器

8.3二叉树类算法的实现代码分析

8.3.1二叉树类的声明与接口

8.3.2二叉树的遍历操作实现

8.3.3树遍历算法的应用

8.3.4二叉树相关算法的

测试程序

8.4二叉搜索树类的实现代码分析

8.4.1二叉搜索树节点和

树类的声明

8.4.2构造函数、析构函数

和赋值运算符

8.4.3二叉搜索树的查找与

更新操作

8.4.4二叉搜索树的测试程序

8.5二叉搜索树应用案例

8.5.1消除重复项

8.5.2音像商店事务管理系统

第9章 图

9.1图的抽象

9.1.1图的描述

9.1.2图的数据结构

9.2图的算法

9.2.1图搜索算法

9.2.2拓扑排序

9.2.3连通分量算法

9.2.4最短路径问题

9.2.5最小生成树问题

9.3Boost图库介绍

9.3.1STL中的泛型

9.3.2BGL中的泛型

9.3.3BGL中的图算法

9.3.4BGL实现的数据结构

9.3.5BGL的历史

9.4图类的实现与应用

9.4.1图的概念(Concepts)

9.4.2图类的实现

9.4.3图类应用示例

9.5图算法的实现和应用

9.5.1访问器

9.5.2图遍历算法的应用

9.5.3拓扑排序的应用

9.5.4最短路径算法的应用

9.5.5最小生成树算法的应用

9.6图的建模与可视化——Graphviz

软件与DOT语言

9.6.1核心绘图引擎

9.6.2图文件描述

语言——DOT语言

9.6.3Graphviz应用示例

第三部分 综合应用

第10章 综合应用案例

10.1数据压缩——霍夫曼编码

解码器的实现

10.1.1数据压缩理论简介

10.1.2Huffman树

10.1.3需求分析

10.1.4Huffman压缩类的接口

与应用

10.1.5Huffman压缩类的

实现

10.1.6Ituffman解压缩

10.2算法时间复杂度测度——算法

计时器的实现

10.2.1精确测定算法时间

的困难

10.2.2应用统计方法解决

困难

10.2.3完成自动分析的

Timer类

10.2.4应用Timer类测试

STLsort算法时间性能

10.3理论计算机科学家族谱的文档

／视图模式——STL组件的

综合应用

10.3.1系统设计：“模型

一视图一控制器”

模式

10.3.2数据关系建模与

数据结构选择

10.3.3从源数据文档到视图

1O.3.4完整的族谱视图程序

以及运行示例

10.4词典检索系统——数据结构

选择对系统性能影响的示例

10.4.1解决方案1：应用全排列

的方法查找变位词

10.4.2解决方案2：应用pair

向量改进时间效率

10.4.3解决方案3：使用映射

改进空间效率

附录A B00st安装指南

附录B 随书所附光盘内容清单

附录C STL库容器类速查手册