数据结构实用教程

第1章 绪论

1.1 数据与数据类型

1.1.1 数据

1.1.2 数据的计算机表示与数据类型

1.1.3 抽象数据类型

1.2 数据结构

1.3 算法与算法分析

1.3.1 算法

1.3.2 算法的性能分析与度量

1.3.3 算法的时间复杂度

1.3.4 算法的空间复杂度

习题1

第2章 线性表

2.1 线性表的类型定义及结构特征

2.2 线性表类型的实现——顺序映像

2.3 线性表类型的实现——链式存储映像

2.3.1 单链表

2.3.2 其他形式的链表

2.4 线性表的应用

2.4.1 两个有序表的合并

2.4.2 集合运算

2.4.3 一元多项式的表示和相加

习题2

第3章 其他线性结构

3.1 栈

3.1.1 栈的定义和基本操作

3.1.2 栈的存储结构及操作实现

3.1.3 栈的应用举例

3.2 队列

3.2.1 队列的定义和基本操作

3.2.2 队列的存储结构及操作实现

3.2.3 队列应用举例

3.3串

3.3.1 串的基本概念和基本操作

3.3.2 串的存储结构

3.4 数组

3.4.1 数组的定义和基本操作

3.4.2 数组的存储表示

3.4.3 特殊矩阵的压缩存储

3.4.4 稀疏矩阵的压缩存储

3.5 广义表

3.5.1 广义表的基本概念和基本操作

3.5.2 广义表的存储结构

习题3

第4章 树型结构

4.1 树、森林的定义及基本术语

4.2 二叉树

4.2.1 二叉树的结构定义

4.2.2 几种特殊形态的二叉树

4.2.3 二叉树的性质

4.2.4 二叉树的存储结构

4.2.5 二叉链表类的定义

4.2.6 二叉树的递归遍历

4.2.7 几个二叉树基本操作的例子

4.2.8 二叉树的非递归遍历

4.2.9 其他部分成员函数的实现

4.2.10 主函数（演示二叉链表类部分基本操作的执行结果）

4.2.11 线索二叉树

4.3 树与森林的再讨论

4.3.1 树的存储结构

4.3.2 树和森林的遍历

4.4 树型结构的应用

4.4.1 算术表达式求值

4.4.2 树与等价问题

4.4.3 赫夫曼树及赫夫曼编码

习题4

第5章 图

5.1 图的定义和术语

5.2 图的存储结构

5.2.1 邻接矩阵表示法

5.2.2 邻接表表示法

5.2.3 十字链表表示法

5.2.4 邻接多重表表示法

5.3 图的基本操作

5.3.1 类的定义与实现

5.3.2 图的遍历

5.3.3 图的连通性

5.4 最小生成树

5.4.1 Prim算法

5.4.2 Kruskal算法

5.5 拓扑排序和关键路径

5.5.1 有向无环图

5.5.2 拓扑排序

5.5.3 关键路径

5.6 最短路径

5.6.1 单源最短路径

5.6.2 每对顶点间的最短路径

习题

第6章 查找

6.1 查找表的定义

6.2 静态查找表

6.2.1 顺序查找

6.2.2 折半查找

6.2.3 分块查找

6.3 动态查找表

6.3.1 二叉排序树

6.3.2 平衡二叉排序树

6.3.3 B?树和B+树

6.4 哈希查找

6.4.1 哈希表的定义

6.4.2 哈希函数的构造方法

6.4.3 处理冲突的办法

6.4.4 哈希表的查找及分析

6.4.5 哈希表的构建与查找算法

习题6

第7章 排序

7.1 插入类排序

7.1.1 直接插入排序

7.1.2 折半插入排序

7.1.3 2-路插入排序

7.1.4 希尔排序

7.2 分划类排序

7.2.1 冒泡排序

7.2.2 快速排序

7.3 选择类排序

7.3.1 简单选择排序

7.3.2 树形选择排序

7.3.3 堆排序

7.4 归并类排序

7.5 基数排序

7.5.1 多关键字的排序

7.5.2 基数排序

7.6 内部排序的比较

7.7 外部排序

7.7.1 外部存储设备

7.7.2 外部排序的方法

7.7.3 败者树

习题

附录A

参考文献

《高等学校工程创新型“十二五”规划计算机教材》为国家级优秀教学团队教学成果。《数据结构实用教程（C++版）》根据教育部高等学校计算机科学与技术教学指导委员会制定的《高等学校计算机科学与技术专业发展战略研究报告暨专业规范》编写，首先介绍了数据结构的核心基础知识——数据、数据类型、数据结构等基本概念和算法、算法的性能度量等知识，然后集中讨论了四种基本的数据结构——集合、线性表、树和图，同时介绍了栈、队列、串、数组以及广义表等数据结构，最后介绍了排序和查找的几种基础算法及实现（用C++语言）。本书强调数据结构的工程应用，以模板的形式给出各种不同数据对象应用数据结构的多个实例，从而实现数据结构与工程应用的有机结合。本书可以作为高等院校计算机及相关专业学生的教材，也可供培训机构及自学者参考。