数据结构--C++语言描述(算法与程序设计微课版题库版高等学校计算机专业教材精选)

本书系统地介绍了各种 常用的数据结构以及查找、 排序的各种算法。全书共10 章，内容包括绪论、线性表 、栈和队列、串、数组和广 义表、树和二叉树、图、查 找、排序、实验等。每章都 配有一定数量的习题，以方 便学生巩同所学知识。 全书采用面向对象的C ++语言作为数据结构和算 法的描述语言，书中所有算 法程序都在Visual C++ 6.O 开发环境中进行了测试。 本书内容丰富，层次清 晰，结合实例，深入浅出， 可作为高等院校计算机及相 关专业数据结构课程的教材 或研究生入学考试的辅导教 材，也可作为从事软件开发 工作人员的参考用书。

主讲《数据结构》等课程；主持主研科研课题二十余项，获河北省科技进步奖三等奖一项，发明专利一项；第一作者发表科研教改论文三十多篇

第1章 绪论 1.1 数据结构的研究内容 1.2 数据结构的基本概念 1.2.1 数据、数据元素、数据项和数据对象 1.2.2 数据结构 1.3 抽象数据类型及其实现 1.3.1 数据类型 1.3.2 抽象数据类型 1.3.3 C++的类和对象 1.3.4 C++的动态存储分配 1.3.5 C++的模板 1.4 算法和算法分析 1.4.1 算法 1.4.2 算法分析 本章小结 习题 第2章 线性表 2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现 2.2.1 线性表的顺序存储结构——顺序表 2.2.2 顺序表的实现 2.3 线性表的链式表示和实现 2.3.1 线性表的链式存储结构——链表 2.3.2 单链表的定义和表示 2.3.3 单链表的实现 2.3.4 双链表 2.3.5 循环链表 2.4 顺序表和链表的比较 2.5 线性表的应用 本章小结 习题 第3章 栈和队列 3.1 栈 3.1.1 栈的定义 3.1.2 顺序栈的表示和实现 3.1.3 链栈的表示和实现 3.1.4 栈的应用 3.2 队列 3.2.1 队列的定义 3.2.2 循环队列——队列的顺序表示和实现 3.2.3 链队——队列的链式表示和实现 3.2.4 队列的应用 本章小结 习题 第4章 串 4.1 串的定义 4.2 串的存储结构 4.3 串的模式匹配 本章小结 习题 第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 广义表的存储结构 本章小结 习题 第6章 树和二叉树 6.1 树 6.1.1 树的定义 6.1.2 树的基本术语 6.1.3 树的抽象数据类型定义 6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的抽象数据类型定义 6.2.3 二叉树的性质 6.2.4 二叉树的存储结构 6.2.5 二叉链表的实现 6.3 二叉树的遍历 6.3.1 遍历的概念 6.3.2 遍历算法 6.4 线索二叉树 6.4.1 线索二叉树的概念 6.4.2 构造线索二叉树 6.4.3 线索二叉树的遍历 6.5 树和森林 6.5.1 树的存储结构 6.5.2 树和森林与二叉树的转换 6.5.3 树和森林的遍历 6.6 哈夫曼树及其应用 6.6.1 哈夫曼树的基本概念 6.6.2 哈夫曼树的构造算法 6.6.3 哈夫曼编码 本章小结 习题 第7章 图 7.1 图的基本概念 7.1.1 图的定义 7.1.2 基本术语 7.1.3 图的抽象类型定义 7.2 图的存储结构 7.2.1 邻接矩阵 7.2.2 邻接表 7.2.3 十字链表 7.2.4 邻接多重表 7.3 图的遍历 7.3.1 深度优先遍历 7.3.2 广度优先遍历 7.4 图的应用 7.4.1 最小生成树 7.4.2 最短路径 7.4.3 拓扑排序 7.4.4 关键路径 本章小结 习题 第8章 查找 8.1 查找的基本概念 8.1.1 查找的定义 8.1.2 查找算法的性能分析 8.2 基于静态表的查找 8.2.1 顺序查找 8.2.2 折半查找 8.3 二叉排序树 8.3.1 二叉排序树的概念 8.3.2 二叉排序树结点的定义 8.3.3 二叉排序树类的定义和实现 8.4 二叉平衡树 8.4.1 二叉平衡树的概念 8.4.2 二叉平衡树的平衡处理 8.4.3 二叉平衡树的插入操作 8.5 B树和B+树 8.5.1 B树 8.5.2 B+树 8.6 散列表 8.6.1 散列表的概念 8.6.2 常见的散列函数 8.6.3 处理冲突的方法 本章小结 习题 第9章 排序 9.1 排序的基本概念 9.1.1 排序的定义 9.1.2 内排序和外排序 9.1.3 排序用到的类定义 9.2 插入排序 9.2.1 直接插入排序 9.2.2 希尔排序 9.3 交换排序 9.3.1 冒泡排序 9.3.2 快速排序 9.4 选择排序 9.4.1 简单选择排序 9.4.2 堆排序 9.5 归并排序 9.6 各种内部排序算法的分析和比较 本章小结 习题 第10章 实验 实验1 一元多项式求和 实验2 求解约瑟夫问题 实验3 表达式求值 实验4 字符串的加解密 实验5 利用二叉树求解简单算术表达式 实验6 医院选址问题 附录 C++程序设计简述 A.1 C++程序的基本结构 A.2 C++的数据类型 A.3 顺序结构 A.4 选择结构 A.5 循环结构 A.6 数组 A.7 指针和引用 A.8 函数 A.9 结构体 参考文献