《数据结构(C++语言描述)》的目的是要为师生提供一本涉及该课程教学主要内容的合适教材。本书各章的介绍中，既包含了数据结构的基本概念，也介绍了算法的设计与实现。实际上，数据结构与算法设计是程序设计的核心，二者是密不可分的。掌握了初步的程序设计方法之后，面对实际的应用问题，最重要的就是学习如何选择和设计有效的数据结构和算法，解决问题才是编写程序的目的。本书采用准C++语言作为全书的基本描述语言，书中对各段程序代码都尽可能地给出了说明，相信即使没有学习过C++的读者，也能很快理解书中的内容。本书由辛运帏、陈有祺编写。

《数据结构(C++语言描述)》将数据结构与算法设计有机地结合起来，向读者系统地介绍数据结构的基本概念及主要的算法设计方法。

全书共分七章：第1章介绍了数据结构的基本概念及主要的数学方法；第2～5章分别介绍了线性表，栈、队列和数组，树，图等重要的数据结构及基本操作的实现过程；第6～7章介绍了查找和排序等数据结构的相关知识。本书在内容讲授过程中辅以大量的实例，旨在帮助读者更好地理解概念，并使用这些概念去解决实际问题。书中主要算法都用C++语言写出，并给出了必要的注释。

《数据结构(C++语言描述)》概念清楚，选材精练，叙述深入浅出，并借助例子和图表来说明基本概念和方法，直观易懂，同时涵盖了研究生入学考试大纲“数据结构”课程的知识点。每章后面都附有习题，读者可以通过练习来检验所学知识。本书可以作为高等院校计算机专业学生的教材，也可以作为广大工程技术人员的参考书。本书由辛运帏、陈有祺编写。

前言

教学建议

第1章 绪论

1.1 数据结构的基本概念和术语

1.2 抽象数据类型及面向对象的概念

1.2.1 抽象数据类型

1.2.2 面向对象的概念

1.3 有关的预备知识

1.3.1 集合

1.3.2 递归

1.4 算法和算法分析

1.4.1 算法的基本概念

1.4.2 算法的评估和复杂度度量

1.4.3 算法设计的一个实例

本章小结

习题

第2章 线性表

2.1 线性表的定义和基本运算

2.1.1 线性表的定义

2.1.2 线性表的操作

2.2 线性表的实现

2.2.1 顺序存储结构

2.2.2 链式存储结构

2.2.3 两种基本存储实现方式的比较

2.2.4 循环链表

2.2.5 双向链表

2.3 线性表的应用

本章小结

习题

第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.3.3 特殊数组

3.3.4 数组的应用

本章小结

习题

第4章 树与二叉树

4.1 树

4.1.1 树的基本概念

4.1.2 树的抽象数据类型

4.2 二叉树

4.2.1 二叉树的定义及其主要特性

4.2.2 二叉树的实现

4.2.3 二叉树的遍历

4.3 树与森林

4.3.1 树的存储结构

4.3.2 森林与二叉树的转换

4.3.3 树和森林的遍历

4.4 哈夫曼树和哈夫曼编码

本章小结

习题

第5章 图结构

5.1 图

5.1.1 图的基本概念

5.1.2 图的抽象数据类型

5.2 图的存储结构

5.2.1 邻接矩阵

5.2.2 邻接表

5.2.3 图的实现

5.3 图的遍历及求图的连通分量

5.3.1 深度优先搜索

5.3.2 广度优先搜索

5.3.3 无向图的连通分量

5.4 有向无环图及拓扑排序

5.4.1 有向无环图

5.4.2 拓扑排序

5.5 生成树和最小代价生成树

5.5.1 生成树

5.5.2 最小代价生成树

5.6 单源最短路径

5.6.1 问题的提出

5.6.2 单源最短路径的算法

本章小结

习题

第6章 查找

6.1 查找的基本概念

6.2 顺序表的查找

6.2.1 顺序查找方法

6.2.2 折半查找方法

6.3 树形结构的查找

6.3.1 二叉排序树

6.3.2 平衡二叉树

6.3.3 B树

6.4 哈希表及其查找

6.4.1 哈希的概念

6.4.2 哈希函数的构造方法

6.4.3 处理冲突的几种方法

6.4.4 哈希表的查找及其效率分析

本章小结

习题

第7章 内部排序

7.1 排序的基本概念

7.2 插入排序

7.2.1 直接插入排序

7.2.2 折半插入排序

7.2.3 希尔排序

7.3 交换排序

7.4 基于分治法的排序

7.4.1 归并排序

7.4.2 快速排序

7.5 选择排序

7.5.1 简单选择排序

7.5.2 堆排序

7.6 分配排序和桶式排序

7.7 有关内部排序算法的比较

本章小结

习题

附录

数据结构综合测试题

数据结构期末模拟考试试卷一

数据结构期末模拟考试试卷二

数据结构期末模拟考试试卷三

参考文献