《数据结构与C++语言描述：应用标准模板库（STL）》- 第2版
作者: William Ford, William Topp
译者: 陈君
出版社: 清华大学出版社（Pearson Education授权）
原版: Data Structures with C++ Using STL, Second Edition (2002)
页数: 889页（扫描版PDF）
文件大小: 21.25 MB
核心概述
本书是经典的CS数据结构教材，以C++面向对象视角讲解数据结构，强调**容器（Container）与迭代器（Iterator）**的统一抽象。全书围绕”容器API → ADT抽象 → 具体实现”的三层结构展开，适合已掌握C++基础语法（类、模板、继承）的读者。
内容结构
第一部分：基础容器（第1-10章）
| 章节 | 主题 | 关键概念 |
|---|---|---|
| 第1章 | 数据结构入门 | 数据结构的抽象形式、作为类的ADT、应用程序编程接口(API) |
| 第2章 | 对象设计技术 | 需求分析、对象复合、封装 |
| 第3章 | 算法概述 | 选择排序、简单查找算法、复杂度分析、常见数量级 |
| 第4章 | miniVector | 向量容器、动态内存管理、析构函数、赋值运算符 |
| 第5章 | 指针与动态内存 | 指针基础、数组与指针、动态数组 |
| 第6章 | 表容器和迭代器 | 链表实现、迭代器模式、词频统计 |
| 第7章 | 栈 | Stack ADT、miniStack实现、STL stack、后缀表达式计算 |
| 第8章 | 队列和优先级队列 | Queue ADT、有界队列、优先级队列排序 |
| 第9章 | 双向链表 | linkedQueue实现、双向链表操作 |
| 第10章 | 关联容器 | miniMap实现、二叉搜索树、红黑树(STL map) |
第二部分：高级容器（第11-16章）
| 章节 | 主题 | 关键概念 |
|---|---|---|
| 第11章 | 集合与映射 | Set ADT、映射实现 |
| 第12章 | 平衡树 | AVL树、伸展树 |
| 第13章 | 堆 | Heap ADT、堆排序、优先队列实现 |
| 第14章 | 哈希表 | Hash Table实现、冲突解决策略 |
| 第15章 | 图的基础 | 图表示、遍历算法 |
| 第16章 | 图的高级算法 | 最小生成树、最短路径、拓扑排序 |
补充内容
- 递归: 贯穿全书，第3章和第7章有专门讲解
- 模板语法: 第2章介绍，用于实现泛型容器
- 项目设计: 每章末尾有编程练习和项目设计题
- 源代码: 作者网站 http://www.uop.edu/fordtopp 可获取完整代码
核心方法论
1. 三层抽象模型
API层（行为描述） → ADT层（抽象数据类型） → 实现层（具体代码）
- API: 描述容器的公共操作（insert、remove、find等）
- ADT: 用伪代码或数学形式定义容器语义
- 实现: 用C++类模板实现，包含完整的构造函数、析构函数、拷贝控制
2. miniContainer 与 STL Container 对照
书中为每种数据结构提供：
miniXxx类：教学用简化实现，帮助理解底层机制STL Xxx类：工业级标准实现，作为进阶选学内容
3. 统一容器观
以容器为核心概念，将数组、向量、表、栈、队列、树、图统一视为”存储大型数据集合的结构”，强调不同容器在不同访问模式下的效率差异。
重要技术要点
向量容器（Vector）
- 动态数组实现，支持随机访问
- 需处理深拷贝、容量扩容、内存泄漏防护
- STL
std::vector是其标准化版本
链表（List）
- 单向链表 vs 双向链表
- 迭代器模式实现：
begin()/end() - 节点插入/删除的时间复杂度O(1) vs 顺序查找O(n)
栈与队列
- 栈：后进先出（LIFO），应用于表达式计算、函数调用
- 队列：先进先出（FIFO），应用于任务调度
- 优先级队列：堆实现，O(log n) 插入/删除
树结构
- 二叉搜索树（BST）：O(log n) 查找，最坏O(n)
- 平衡树（AVL/伸展树）：保证O(log n)操作
- 红黑树：STL
map/set的实现基础
哈希表
- 开放寻址 vs 链地址法
- 负载因子与再哈希策略
- STL
unordered_map/unordered_set是标准实现
图
- 邻接矩阵 vs 邻接表
- DFS/BFS 遍历
- 拓扑排序（AOV网）
- 最小生成树（Prim/Kruskal）
- 最短路径（Dijkstra）
与相关知识的关联
- 《C++ Primer》- 第五版-Stanley-Lippman：C++语法基础
- 《Effective C++》- 第三版-55个改善程序与设计的具体做法-Scott-Meyers：C++最佳实践
- 《C++ Concurrency in Action》-第二版-Anthony-Williams：并发编程
- 《现代C++设计》-泛型编程与设计模式应用-Andrei-Alexandrescu：泛型编程进阶
适用场景
- 计算机专业数据结构课程核心教材
- 已掌握C++基础的开发者进阶数据结构
- 面试准备（LeetCode中等难度题目涉及的大部分结构）
- STL容器底层原理理解
处理信息
- 云盘路径:
/田浩然上传的资料/电子书/C_C++/美河提供数据结构C.语言描述.应用标准摸板库STL第2版.pdf - PDF类型: scanned（扫描版）
- 处理日期: 2026-09-04
- 提取方式: tesseract OCR预览前10页 + 目录结构分析
- 状态: done_toc_only（扫描版全文OCR耗时过长，仅提取目录和前言内容）