本书是普通高等教育“十一五”国家级规划教材，也是北京市精品课程主讲教材。本书按照IEEE/ACM CC2005和教育部教指委关于“计算机科学与技术专业规范”（ CCC2005）的要求编写，力求使学生较全面地理解数据结构的概念、掌握各种数据结构与算法的实现方式，同时比较不同数据结构和算法的特点，重点强调实践教学和学生动手能力的培养。
本书的内容涉及基本数据结构、排序、索引、检索、高级数据结构等内容，借助抽象数据类型，从逻辑结构的角度系统地介绍线性表、字符串、二叉树、树和图等各种基本数据结构；从算法的角度系统地介绍各类排序、检索和索引算法；从应用的角度介绍一些更复杂的数据结构与算法分析技术。本书采用能够更自然体现抽象数据类型概念的C++语言作为算法描述语言，注意对每一种数据结构的不同存储方法及相关算法进行比较分析。很多算法使用了参数化的模板，从而提高了算法中数据类型的通用性，支持高效的代码重用。
目录
- 第1章 概论
- 1.1 问题求解
- 1.1.1 问题描述：股市的传言
- 1.1.2 问题分析和抽象
- 1.1.3 数据结构和算法设计
- 1.2 数据结构
- 1.2.1 数据的逻辑结构
- 1.2.2 数据的存储结构
- 1.2.3 抽象数据类型
- 1.3 算法
- 1.3.1 算法的概念
- 1.3.2 算法设计
- 1.4 算法分析
- 1.4.1 渐进分析方法
- 1.4.2 最佳、最差和平均情况
- 1.4.3 时间和空间的折衷
- 1.4.4 求解问题时数据结构的选择和评价
- 本章小结
- 习题
- 上机题
- 第2章 线性表
- 2.1 线性表的概念
- 2.1.1 线性表的抽象数据类型
- 2.1.2 线性表的存储结构
- 2.1.3 线性表运算分类
- 2.2 顺序表
- 2.2.1 顺序表的类定义
- 2.2.2 顺序表的运算实现
- 2.3 链表
- 2.3.1 单链表
- 2.3.2 双链表
- 2.3.3 循环链表
- 2.4 线性表实现方法的比较
- 本章小结
- 习题
- 上机题
- 第3章 栈与队列
- 3.1 栈
- 3.1.1 栈的抽象数据类型
- 3.1.2 顺序栈
- 3.1.3 链式栈
- 3.1.4 表达式求值
- 3.1.5 栈与递归
- 3.2 队列
- 3.2.1 队列的抽象数据类型
- 3.2.2 顺序队列
- 3.2.3 链式队列
- 3.3 栈与队列的深入讨论
- 3.3.1 顺序栈与链式栈的比较
- 3.3.2 顺序队列与链式队列的比较
- 3.3.3 限制存取点的表
- 本章小结
- 习题
- 上机题
- 第4章 字符串
- 4.1 字符串的基本概念
- 4.1.1 字符编码
- 4.1.2 字符的编码顺序
- 4.1.3 字符串抽象数据类型
- 4.2 字符串的存储结构和实现
- 4.2.1 字符串的顺序存储
- 4.2.2 字符串类class String的存储结构
- 4.2.3 字符串运算的实现
- 4.3 字符串的模式匹配
- 4.3.1 朴素的模式匹配算法
- 4.3.2 字符串的特征向量
- 4.3.3 KMP模式匹配算法
- 本章小结
- 习题
- 上机题
- 第5章 二叉树
- 5.1 二叉树的概念
- 5.1.1 二叉树的定义和基本术语
- 5.1.2 满二叉树、完全二叉树、扩充二叉树
- 5.1.3 二叉树的主要性质
- 5.2 二叉树的周游
- 5.2.1 二叉树的抽象数据类型
- 5.2.2 深度优先周游二叉树
- 5.2.3 广度优先周游二叉树
- 5.3 二叉树的存储结构
- 5.3.1 二叉树的链式存储结构
- 5.3.2 完全二叉树的顺序存储结构
- 5.4 二叉搜索树
- 5.5 堆与优先队列
- 5.5.1 堆的定义及其实现
- 5.5.2 优先队列
- 5.6 Huffman树及其应用
- 5.6.1 Huffman树
- 5.6.2 Huffman编码
- 本章小结
- 习题
- 上机题
- 第6章 树
- 6.1 树的定义和基本术语
- 6.1.1 树和森林
- 6.1.2 森林与二叉树的等价转换
- 6.1.3 树的抽象数据类型
- 6.1.4 树的周游
- 6.2 树的链式存储结构
- 6.2.1 “子结点表”表示方法
- 6.2.2 静态“左子/右兄”表示法
- 6.2.3 动态表示法
- 6.2.4 动态“左子/右兄”二叉链表表示法
- 6.2.5 父指针表示法和在并查集中的应用
- 6.3 树的顺序存储结构
- 6.3.1 带右链的先根次序表示
- 6.3.2 带双标记的先根次序表示
- 6.3.3 带度数的后根次序表示
- 6.3.4 带双标记的层次次序表示
- 6.4 K叉树
- 本章小结
- 习题
- 上机题
- 第7章 图
- 7.1 图的定义和基本术语
- 7.2 图的抽象数据类型
- 7.3 图的存储结构
- 7.3.1 相邻矩阵
- 7.3.2 邻接表
- 7.3.3 十字链表
- 7.4 图的周游
- 7.4.1 深度优先周游
- 7.4.2 广度优先周游
- 7.4.3 拓扑排序
- 7.5 最短路径
- 7.5.1 单源最短路径
- 7.5.2 每对顶点之间的最短路径
- 7.6 最小生成树
- 7.6.1 Prim算法
- 7.6.2 Kruskal算法
- 本章小结
- 习题
- 上机题
- 第8章 内排序
- 8.1 排序问题的基本概念
- 8.2 插入排序
- 8.2.1 直接插入排序
- 8.2.2 Shell排序
- 8.3 选择排序
- 8.3.1 直接选择排序
- 8.3.2 堆排序
- 8.4 交换排序
- 8.4.1 冒泡排序
- 8.4.2 快速排序
- 8.5 归并排序
- 8.6 分配排序和索引排序
- 8.6.1 桶式排序
- 8.6.2 基数排序
- 8.6.3 索引排序
- 8.7 排序算法的时间代价
- 8.7.1 简单排序算法的时间代价
- 8.7.2 排序算法的理论和实验时间
- 8.7.3 排序问题的下限
- 本章小结
- 习题
- 上机题
- 第9章 文件管理和外排序
- 9.1 主存储器和外存储器
- 9.2 文件的组织和管理
- 9.2.1 文件组织
- 9.2.2 C++的流文件
- 9.3 外排序
- 9.3.1 置换选择排序
- 9.3.2 二路外排序
- 9.3.3 多路归并——选择树
- 本章小结
- 习题
- 上机题
- 第10章 检索
- 10.1 基于线性表的检索
- 10.1.1 顺序检索
- 10.1.2 二分检索
- 10.1.3 分块检索
- 10.2 集合的检索
- 10.2.1 集合的数学特性
- 10.2.2 计算机中的集合
- 10.3 散列方法
- 10.3.1 散列函数
- 10.3.2 开散列方法（拉链法）
- 10.3.3 闭散列方法（开地址法）
- 10.3.4 闭散列表的算法
- 10.3.5 散列方法的效率分析
- 10.3.6 散列方法的应用
- 本章小结
- 习题
- 上机题
- 第11章 索引技术
- 11.1 线性索引
- 11.2 静态索引——多分树
- 11.3 倒排索引
- 11.3.1 基于属性的倒排
- 11.3.2 对正文文件的倒排
- 11.4 动态索引
- 11.4.1 B树
- 11.4.2 B+树
- 11.4.3 B树的性能分析
- 11.4.4 动态索引和静态索引性能的比较
- 11.5 位索引技术
- 11.5.1 位图索引
- 11.5.2 签名文件
- 11.6 红黑树
- 11.6.1 红黑树的定义
- 11.6.2 红黑树的相关性质
- 11.6.3 插入结点算法
- 11.6.4 删除结点算法
- 本章小结
- 习题
- 上机题
- 第12章 高级数据结构
- 12.1 多维数组
- 12.1.1 多维数组的存储
- 12.1.2 特殊矩阵
- 12.1.3 稀疏矩阵
- 12.2 广义表和存储管理
- 12.2.1 广义表的定义和存储结构
- 12.2.2 可利用空间表
- 12.2.3 存储的动态分配和回收
- 12.2.4 失败处理策略和无用单元回收
- 12.3 Trie结构和Patricia树
- 12.4 改进的二叉搜索树
- 12.4.1 最佳二叉搜索树
- 12.4.2 平衡的二叉搜索树
- 12.4.3 伸展树
- 本章小结
- 习题
- 上机题
- 参考文献
