数据结构教程

第1章 基础

1.1 什么是数据结构

1.2 程序性能分析

1.2.1 程序性能的衡量标准

1.2.2 程序的事后测试

1.2.3 时间复杂性的计算方法

1.2.4 空间复杂性的计算方法

1.2.5 计算复杂性的表示方法

1.2.6 两种代价计算方法的比较

1.3 从抽象数据类型到C＋＋语言描述

1.4 C＋＋基础知识

1.4.1 C＋＋中的类和对象

1.4.2 C＋＋的输入和输出

1.4.3 C＋＋中的变量和常量

1.4.4 C＋＋中的函数

1.4.5 C＋＋中的动态存储分配

1.4.6 C＋＋中的继承

1.4.7 C＋＋中的多态性

1.4.8 其他

1.5 进阶导读

习题

第2章 线性表

2.1 线性表及其基本运算

2.1.1 线性表的定义与特点

2.1.2 线性表的基本运算

2.2 数组

2.2.1 数组的定义和特点

2.2.2 数组的类定义

2.2.3 数组的顺序存储方式

2.2.4 稀疏矩阵

2.3 线性表的顺序表示——顺序表

2.3.1 顺序表的定义和特点

2.3.2 顺序表类定义

2.3.3 顺序表的插入

2.3.4 顺序表的删除

2.3.5 顺序表的应用实例——用顺序存储的线性表表示多项式

2.4 线性表的链式表示——链表

2.4.1 线性链表的逻辑结构与建立

2.4.2 线性链表的类定义

2.4.3 线性链表的插入与删除

2.4.4 线性链表的应用实例——用线性链表表示多项式

2.4.5 几种变形的线性链表

2.4.6 双向链表

2.5 进阶导读

习题

第3章 串

3.1 串的定义

3.2 串的逻辑结构和基本操作

3.3 串的存储结构

3.3.1 串的数组存储表示

3.3.2 串的块链存储表示

3.4 串的实现

3.4.1 串的自定义类

3.4.2 串的实现

3.5 串的模式匹配算法

3.5.1 BF算法

3.5.2 KR算法

3.5.3 KMP算法

3.5.4 BM算法

3.6 进阶导读

习题

第4章 栈和队列

4.1 栈

4.1.1 栈的基本操作

4.1.2 用数组实现栈

4.1.3 用链表实现栈

4.1.4 栈的应用实例

4.2 队列

4.2.1 用数组实现队列

4.2.2 循环队列

4.2.3 双向队列

4.2.4 用链表实现队列

4.2.5 队列的应用举例

4.3 进阶导读

习题

第5章 递归和广义表

5.1 递归的概念

5.2 递归转化为非递归

5.3 广义表

5.3.1 广义表的概念与存储结构

5.3.2 广义表递归算法的实现

5.4 进阶导读

习题

第6章 树、二叉树和森林

6.1 基本概念

6.2 树的存储结构

6.3 树的线性表示

6.4 树的遍历

6.5 二叉树

6.6 二叉树的存储表示

6.7 二叉树的各种遍历

6.8 线索化二叉树

6.9 堆

6.10 计算二叉树的数目

6.11 二叉树的应用：霍夫曼树和霍夫曼编码

6.12 进阶导读

习题

第7章 查找与索引

7.1 查找与索引的概念

7.2 基于顺序表的查找

7.2.1 顺序表

7.2.2 顺序查找

7.2.3 有序顺序表上的查找操作

7.3 二叉查找树

7.3.1 二叉查找树的结构

7.3.2 二叉查找树上的查找

7.3.3 基于二叉查找树的遍历

7.3.4 最优二叉查找树

7.3.5 动态二叉查找树

7.4 B－树和B＋树

7.4.1 B－树的结构

7.4.2 B－树的查询

7.4.3 B－树的插入

7.4.4 B－树的删除

7.4.5 B＋树

7.5 Trie树

7.5.1 Trie树的定义

7.5.2 Trie树的查找

7.5.3 Trie树的插入和删除

7.6 Hash查找

7.6.1 Hash函数

7.6.2 解决冲突的方法

7.6.3 Hash查找的讨论

7.7 进阶导读

习题

第8章 图

8.1 图的基本概念

8.2 图的存储结构

8.2.1 邻接矩阵

8.2.2 邻接表

8.3 图的遍历与求图的连通分量

8.3.1 深度优先查找法

8.3.2 广度优先查找法

8.3.3 求图的连通分量

8.4 生成树与最小（代价）生成树

8.4.1 普里姆（Prim）算法

8.4.2 克鲁斯卡尔（Kruskal）算法

8.5 最短路径

8.5.1 求某个顶点到其他顶点的最短路径

8.5.2 求一对顶点之间的最短路径

8.5.3 传递闭包

8.6 拓扑排序

8.7 关键路径

8.8 进阶导读

习题

第9章 排序

9.1 问题定义

9.2 基本排序方法

9.2.1 插入排序

9.2.2 冒泡排序

9.2.3 选择排序

9.3 归并排序

9.4 快速排序

9.4.1 基本算法

9.4.2 性能

9.4.3 快速排序的一些改进策略

9.4.4 重复值

9.5 堆排序

9.5.1 堆及其基本操作

9.5.2 堆排序

9.6 希尔排序

9.7 基数排序

9.8 内部排序方法的比较

9.9 进阶导读——中的sort（）函数

习题

第10章 外部排序

10.1 外部存储设备

10.1.1 磁带存储设备

10.1.2 磁盘存储设备

10.2 外排序的基本过程

10.3 磁盘文件的外排序方法

10.4 磁带文件的外排序方法

10.4.1 平衡合并排序

10.4.2 多阶段合并排序

10.5 进阶导读

习题

《数据结构教程》是为全国高等院校计算机及相关专业开设数据结构课程而精心组织和编著的一本实用教材，内容覆盖了教育部计算机科学与技术专业硕士研究生入学统一考试的大纲要求。《数据结构教程》采用C＋＋描述，强调原理阐述与应用结合，避免大段冗长代码，并在每章最后增加进阶和最新研究成果的介绍，引导学有余力的学生进一步自学与本章内容相关的数据结构知识。