数据结构随着程序设计的发展而发展，面向对象技术是目前最流行的程序设计技术。为了适应形势的需要，有必要开设结合面向对象技术的数据结构课程。本书采用面向对象的观点讨论数据结构技术，并以C++语言作为算法描述工具。

马石安等编著的《数据结构与应用教程(C++版）》包括10章和一个附录：第0章介绍C++程序设计语言预备知识，让不熟悉C++的读者迅速掌握C++的基本要点，为后续章节打下基础；第1章为绪论，介绍数据结构的发展、研究的内容、基本概念和术语及算法的定义和分析；第2～7章讲解线性表、栈和队列、串、数组和广义表、树和二叉树及图等数据结构的逻辑结构、存储结构和相关算法，并对每种算法进行了c++语言实现和评价，最后通过实例来了解它们的基本应用；第8章和第9章介绍在计算机中非常广泛的两种运算：排序和查找，结合图解和实例描述常用的排序和查找算法，并给出了C++语言实现，还着重在时间上作出了定量或定性的分析比较。附录部分是实验内容，供上机选用。

马石安等编著的《数据结构与应用教程(C++版）》采用面向对象的观点讨论数据结构技术，并以c++类模板作为算法描述工具。

《数据结构与应用教程(C++版）》在简要回顾C++程序设计概念的基础上，全面系统地介绍了线性表、栈和队列、串、数组和广义表、树和二叉树及图等数据结构，讨论了常用的查找和排序技术。对每一种数据结构，除了详细阐述其逻辑结构、存储结构和相关算法外，并对所有算法进行了c++语言实现和评价，最后通过实例来了解它的基本应用。对查找和排序算法，还着重在时间上作出了定量或定性的分析比较。本书最后还精心设计了8个上机实验。

《数据结构与应用教程(C++版）》条理清晰，语言通俗，图文并茂，可操作性强，列举实例丰富、典型。每章后面提供的练习题和附录部分的实验内容与教学要求一致，并提供全方位的教学资源。

《数据结构与应用教程(C++版）》可作为高等院校计算机及相关专业的教材或参考书，也可供自学者使用。

第0章 C++程序设计语言预备知识

 O.1 一个简单C++语言程序

0.1.1 C++程序基本结构

0.1.2 C++程序基本组成

0.1.3 简单的输入／输出

 0.2 指针与引用

O.2.1 指针

O.2.2 引用

 O.3 动态存储分配

 O.4 函数

0.4.1 函数的定义与调用

0.4.2 函数的参数传递

0.4.3 函数原型与带默认参数的函数

0.4.4 重载函数

 0.5 类与对象

O.5.1 类

0.5.2 对象

O.5.3 构造函数与析构函数

O.5.4 友元函数

 O.6 运算符重载

O.6.1 用成员函数重载运算符

O.6.2 用友元函数重载运算符

 O.7 模板

0.7.1 模板的概念

0.7.2 函数模板

0.7.3 类模板

第1章 绪论

 1.1 数据结构的产生和发展

 1.2 数据结构研究的内容

 1.3 基本概念和术语

1.3.1 数据和数据元素

1.3.2 数据结构

 1.4 算法

1.4.1 算法的定义及特性

1.4.2 算法的描述

1.4.3 算法设计的目标

1.4.4 算法的分析

 1.5 习题

第2章 线性表

 2.1 线性表的逻辑结构

2.1.1 线性表的定义

2.1.2 线性表的操作

 2.2 线性表的顺序存储结构

2.2.1 顺序表

2.2.2 顺序表基本运算的实现

2.2.3 小结

 2.3 线性表的链式存储结构

2.3.1 单链表

2.3.2 单循环链表

2.3.3 双链表

 2.4 顺序表和链表的比较

 2.5 线性表的应用

2.5.1 一元多项式的表示

2.5.2 一元多项式的存储结构

2.5.3 一元多项式加法的算法分析与实现

 2.6 习题

第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 习题

第4章 串

 4.1 串的逻辑结构

4.1.1 串的基本概念

4.1.2 串的基本操作

4.1.3 常用的C++字符串函数

 4.2 串的顺序存储结构

4.2.1 顺序串

4.2.2 顺序串基本操作的实现

4.2.3 模式匹配

 4.3 串的链式存储结构

 4.4 串的应用

4.4.1 问题描述

4.4.2 算法的设计与实现

 4.5 习题

第5章 数组和广义表

 5.1 数组

5.1.1 数组的逻辑结构

5.1.2 数组的顺序存储结构

 5.2 矩阵的压缩存储

5.2.1 特殊矩阵

5.2.2 稀疏矩阵

 5.3 广义表

5.3.1 广义表的逻辑结构

5.3.2 广义表的存储结构

5.3.3 广义表基本操作的实现

 5.4 多维数组的应用

5.4.1 问题描述

5.4.2 设计要求

5.4.3 算法的分析与实现

 5.5 习题

第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.3 二叉树的逻辑结构

6.3.1 二又树的概念

6.3.2 二叉树的基本性质

6.3.3 二叉树的遍历操作

6.3.4 由遍历序列恢复二叉树

 6.4 二叉树的存储结构

6.4.1 二叉树的顺序存储结构

6.4.2 二叉链表

6.4.3 三叉链表

 6.5 线索二叉树

6.5.1 线索二叉树的定义及结构

6.5.2 线索二叉树基本操作的实现

 6.6 树、森林与二叉树的转换

 6.7 树的应用

6.7.1 哈夫曼树的基本概念

6.7.2 哈夫曼算法

6.7.3 哈夫曼编码

 6.8 习题

第7章 图

 7.1 图的逻辑结构

7.1.1 图的定义

7.1.2 图的基本术语

7.1.3 图的基本操作

 7.2 图的存储结构

7.2.1 邻接矩阵

7.2.2 邻接表

7.2.3 邻接矩阵和邻接表的比较

 7.3 图的遍历

7.3.1 深度优先搜索遍历

7.3.2 广度优先搜索遍历

 7.4 生成树和最小生成树

7.4.1 生成树与生成森林

7.4.2 最小生成树

 7.5 最短路径

7.5.1 单源最短路径

7.5.2 所有顶点对之间的最短路径

 7.6 DAG图及其应用

7.6.1 DAG的概念

7.6.2 AOV网与拓扑排序

7.6.3 AOE网与关键路径

 7.7 习题

第8章 排序

 8.1 概述

8.1.1 排序的基本术语

8.1.2 排序方法的分类

8.1.3 排序算法的基本操作和存储方式

8.1.4 排序算法性能评价

 8.2 插入排序

8.2.1 直接插入排序

8.2.2 折半插入排序

8.2.3 希尔排序

 8.3 交换排序

8.3.1 冒泡排序

8.3.2 快速排序

 8.4 选择排序

8.4.1 直接选择排序

8.4.2 堆排序

 8.5 归并排序

 8.6 基数排序

 8.7 各种内排序方法的比较和选择

 8.8 习题

第9章 查找

 9.1 概述

9.1.1 基本概念

9.1.2 查找算法的性能

 9.2 线性表的查找

9.2.1 顺序查找

9.2.2 二分查找

9.2.3 分块查找

 9.3 树表的查找

9.3.1 二叉排序树

9.3.2 平衡二又树

 9.4 散列表的查找

9.4.1 散列表的概念

9.4.2 常用的散列函数

9.4.3 处理冲突的方法

9.4.4 散列表上的运算

9.4.5 查找性能的分析

 9.5 习题

附录 实验内容

 实验1 线性表

 实验2 栈和队列

 实验3 串

 实验4 数组和广义表

 实验5 树和二叉表

 实验6 图

 实验7 排行

 实验8 查找

参考文献