算法与数据结构

第1章 绪论

1.1 利用计算机解决问题的几个步骤

1.2 基本概念和术语

1.3 算法及其复杂度分析

1.4 算法的描述语言

第2章 算法分析技术

2.1 无穷大的阶

2.2 若干序列和函数的渐进性质

2.2.1 调和级数

2.2.2 Fibonacci序列

2.2.3 log2函数

2.2.4 基本定理

2.2.5 Catalan数

2.2.6 一个特别序列

2.3 算法的时间复杂度

2.4 算法的空间复杂度

2.5 冒泡排序算法复杂度分析

2.6 分摊复杂度分析

2.6.1 累计法

2.6.2 势函数法

2.6.3 捐款记账法

习题

第3章 线性表

3.1 顺序线性表：向量

3.1.1 Vector类模板的成员变量

3.1.2 向量的迭代子

3.1.3 获取向量的成员

3.1.4 向量元素的删除

3.1.5 向量的存储管理

3.1.6 添加函数

3.1.7 完整的Vector类

3.2 单链表

3.2.1 单链表迭代子类

3.2.2 添加和删除操作

3.3 其他形式的单链表

3.4 双链表

3.5 静态链表

3.6 动态内存管理

3.7 矩阵

3.8 对称矩阵

3.9 稀疏矩阵

习题

第4章 栈与队列

4.1 栈的定义与实现

4.2 栈与函数调用

4.2.1 函数调用框架

4.2.2 汉诺塔问题

4.2.3 间接递归调用

4.3 广义栈

4.4 回溯法

4.4.1 八皇后问题

4.4.2 八皇后问题回溯法的改进

4.5 队列

4.5.1 用链表实现队列

4.5.2 用循环数组实现队列

4.6 双端队列

4.7 基数排序

习题

第5章 字符串与模式匹配算法

5.1 字符集与字符

5.2 字符串

5.3 简单模式匹配算法

5.4 KMP算法

5.4.1 KMP算法的改进

5.4.2 KMP类

5.5 有限状态自动机模式匹配算法

5.5.1 有限状态自动机

5.5.2 模式匹配有限状态自动机

5.6 Boyer-Moore模式匹配算法

5.7 BM-KMP模式匹配算法

习题

第6章 树与二叉树

6.1 树与森林

6.2 二叉树

6.3 二又树的二叉链表表示

……

第7章 选择

第8章 查找

第9章 排序

第10章 图

第11章 STL简介

第12章 C++语言概要

第13章 伪随机数产生与高精度计时器

参考文献

索引

《算法与数据结构（C++版）》是普通高等教育“十一五”国家级规划教材，系统介绍各种数据结构、常用算法及算法分析技术。数据结构的内容包括线性结构、树形结构、哈希结构、索引结构；算法方面的内容包括选择算法、查找算法、排序算法。《算法与数据结构（C++版）》还较为详细地分析了各种算法的时间复杂度和空间复杂度，介绍了分摊复杂度分析技术。作为各种数据结构和算法的应用，《算法与数据结构（C++版）》给出了图的标准界面及其实现。利用这个标准界面，实现了图论中的一些经典算法。
《算法与数据结构（C++版）》以算法为主线组织内容，仿照C++标准模板库的界面给出了许多算法和数据结构的实现。《算法与数据结构（C++版）》可作为高校计算机相关专业“数据结构”课程的教材，也可作为计算机工作者的参考书。