数据结构与算法：C++语言描述

　　《数据结构与算法：C++语言描述》根据作者多年在南京邮电学院讲授“数据结构”和“算法设计与分析”课程的教学经验，在编写用Pascal、C和C++语言描述的几本数据结构教材基础上，参考近几年国内外多种优秀教材编写而成。《数据结构与算法：C++语言描述》涵盖了“数据结构与算法”的核心知识单元，使用C++语言描述。书中不仅系统介绍了各种传统的数据结构和搜索、排序算法，还引入了比较高级的数据结构，如伸展树和跳表。《数据结构与算法：C++语言描述》讨论算法分析和算法设计策略，讨论搜索和排序算法的时间下界，还介绍了随机算法以及NP难度和NP完全问题。全书条理清晰，内容翔实。书中算法都有完整的C++程序，程序结构清晰，构思精巧，既是读者学习数据结构与算法的很好示例，也是很好的C++程序设计示例。《数据结构与算法：C++语言描述》深入浅出，配有大量的实例和图示，并有丰富的习题，适于自学。《数据结构与算法：C++语言描述》是一本数据结构与算法知识合二为一的教材，且易于取舍和重组，因此可作为高等院校计算机专业或其他相关专业的“数据结构”或“数据结构与算法”课程的教材，也可供学习该领域知识的人员参考。

暂缺《数据结构与算法：C++语言描述》作者简介

第一部分基础知识
第1章概论
1.1算法与数据结构
1.1.1算法
1.1.2数据结构
1.1.3数据的逻辑结构
1.1.4数据的存储表示
1.1.5数据结构的运算
1.2数据抽象和抽象数据类型
1.2.1抽象、数据抽象和过程抽象
1.2.2封装与信息隐蔽
1.2.3数据类型和抽象数据类型
1.2.4数据结构与抽象数据类型
1.3面向对象方法
1.3.1面向对象方法的由来
1.3.2面向对象方法的基本思想
1.3.3面向对象方法的要素
1.3.4面向对象方法和抽象数据
类型
1.4描述数据结构和算法
1.4.1数据结构的规范
1.4.2实现数据结构
本章小结
习题
第2章算法基础
2.1算法复杂度
2.1.1什么是好的算法
2.1.2影响程序运行时间的因素
2.1.3算法的时间复杂度
2.1.4使用程序步分析算法
2.1.5算法的空间复杂度
2.2渐近表示法
2.2.1大O记号
2.2.2Ω记号
2.2.3Θ记号
2.2.4小o记号
2.2.5算法按时间复杂度分类
2.3递归、归纳和递推
2.3.1递归
2.3.2递归算法示例
2.3.3证明方法
2.3.4递推关系
本章小结
习题
第二部分数据结构
第3章数组和链表
3.1结构和类
3.1.1结构
3.1.2结构表示元素
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单循环链表
3.3.5双向链表
3.4采用模拟指针的链表
3.4.1结点结构
3.4.2可用空间表
3.5异常处理
本章小结
习题
第4章堆栈和队列
4.1堆栈
4.1.1堆栈ADT
4.1.2堆栈的顺序表示
4.1.3堆栈的链接表示
4.2队列
4.2.1队列ADT
4.2.2队列的顺序表示
4.2.3队列的链接表示
4.3表达式计算
4.3.1表达式
4.3.2中缀表达式转换为后缀表
达式
4.3.3计算后缀表达式的值
4.4实现递归
4.4.1子程序调用和系统栈
4.4.2递归函数的性能
4.4.3尾递归
4.5演示与测试
本章小结
习题
第5章线性表和数组ADT
5.1线性表
5.1.1线性表ADT
5.1.2线性表的顺序表示
5.1.3线性表的链接表示
5.1.4两种存储表示的比较
5.2多项式的算术运算
5.2.1多项式ADT
5.2.2多项式的链接表示
5.2.3项结点类
5.2.4多项式类
5.2.5多项式的输入和输出
5.2.6多项式相加
5.2.7重载运算符函数
5.3数组作为抽象数据类型
5.3.1数组ADT
5.3.2一维数组的C++类
5.4特殊矩阵
5.4.1对称矩阵
5.4.2带状矩阵
5.5稀疏矩阵
5.5.1稀疏矩阵ADT
5.5.2稀疏矩阵的顺序表示
5.5.3稀疏矩阵转置
5.5.4稀疏矩阵的正交链表表示
5.5.5建立正交链表
5.5.6打印正交链表
本章小结
习题
第6章字符串和广义表
6.1字符串
6.1.1字符串ADT
6.1.2字符串的存储表示
6.1.3串运算的实现
6.1.4简单模式匹配算法
6.1.5模式匹配的KMP算法
6.2广义表
6.2.1广义表的概念
6.2.2广义表ADT
6.2.3广义表的存储表示
6.2.4广义表算法
本章小结
习题
第7章树
7.1树的基本概念
7.1.1树的定义
7.1.2基本术语
7.2二叉树
7.2.1二叉树的定义
7.2.2二叉树的性质
7.2.3二叉树ADT
7.2.4二叉树的存储表示
7.2.5二叉树类
7.2.6二叉树基本运算
7.3二叉树的遍历
7.3.1二叉树遍历算法
7.3.2二叉树遍历的递归算法
7.3.3二叉树遍历的应用实例
7.4二叉树遍历的非递归算法
7.4.1遍历器类
7.4.2中序遍历器类
7.5二叉线索树
7.5.1二叉线索树的定义
7.5.2构造中序线索树
7.5.3遍历二叉线索树
7.6树和森林
7.6.1森林与二叉树的转换
7.6.2树和森林的存储表示
7.6.3树和森林的遍历
7.7堆和优先权队列
7.7.1堆
7.7.2优先权队列ADT
7.7.3优先权队列类
7.7.4实现优先权队列
7.8哈夫曼树和哈夫曼编码
7.8.1树的路径长度
7.8.2哈夫曼树和哈夫曼算法
7.8.3哈夫曼树类
7.8.4构造哈夫曼树
7.8.5哈夫曼编码
7.9并查集和等价关系
7.9.1并查集ADT
7.9.2并查集的存储表示
7.9.3并查集类
7.9.4函数Union和Find
7.9.5改进的函数Union和Find
7.9.6按等价关系分组
本章小结
习题
第8章集合和搜索
8.1集合和搜索
8.1.1集合和搜索的概念
8.1.2动态集ADT
8.1.3集合的表示
8.2顺序搜索
8.2.1无序表的顺序搜索
8.2.2有序表的顺序搜索
8.2.3平均搜索长度
8.2.4自组织表
8.3二分搜索
8.3.1分治法和二分搜索
8.3.2对半搜索
8.3.3二叉判定树
8.3.4斐波那契搜索
8.4搜索算法的时间下界
本章小结
习题
第9章动态集和搜索树
9.1二叉搜索树
9.1.1二叉搜索树的定义
9.1.2二叉搜索树的搜索
9.1.3二叉搜索树的插入
9.1.4二叉搜索树的删除
9.1.5平均情况时间分析
9.2二叉平衡树
9.2.1二叉平衡树的定义
9.2.2二叉平衡树类
9.2.3二叉平衡树的平衡旋转
9.2.4二叉平衡树的插入
9.2.5二叉平衡树的删除
9.2.6二叉平衡树的高度
9.3B-树
9.3.1m叉搜索树
9.3.2B-树的定义
9.3.3B-树的高度
9.3.4B-树的搜索
9.3.5B-树的插入
9.3.6B-树的删除
9.4键树
9.4.1键树的定义
9.4.2双链树
9.4.3Trie树
9.5伸展树
9.5.1伸展树的伸展操作
9.5.2性能分析
本章小结
习题
第10章跳表和散列表
10.1字典
10.2跳表
10.2.1什么是跳表
10.2.2跳表类
10.2.3跳表的搜索
10.2.4跳表的插入
10.2.5跳表的删除
10.3散列表
10.3.1散列技术
10.3.2散列函数
10.3.3拉链法
10.3.4开地址法
10.3.5线性探查法
10.3.6其他开地址法
10.3.7性能分析
本章小结
习题
第11章图
11.1图的基本概念
11.1.1图的定义与术语
11.1.2图ADT
11.2图的存储结构
11.2.1图的矩阵表示法
11.2.2图的邻接矩阵实现
11.2.3图的邻接表表示法
11.2.4图的邻接表实现
11.3图的遍历
11.3.1扩充的图类
11.3.2深度优先遍历
11.3.3宽度优先遍历
11.3.4基本遍历方法
11.4拓扑排序
11.4.1用顶点代表活动的AOV网
11.4.2拓扑排序算法
11.4.3拓扑排序C++程序
11.5关键路径
11.5.1用边代表活动的AOE网
11.5.2关键路径算法
11.5.3关键路径C++程序
11.6最小代价生成树
11.6.1基本概念
11.6.2普里姆算法
11.6.3克鲁斯卡尔算法
11.6.4最优化问题和贪心法
11.6.5贪心法求解最小代价
生成树
11.7最短路径
11.7.1贪心法和单源最短路径
11.7.2迪杰斯特拉算法
11.7.3所有顶点之间的最短路径
本章小结
习题
第12章内排序
12.1基本概念
12.2简单排序算法
12.2.1直接插入排序
12.2.2简单选择排序
12.2.3冒泡排序
12.3快速排序
12.3.1分治法与快速排序
12.3.2快速排序算法
12.3.3性能分析
12.4两路合并排序
12.4.1合并两个有序序列
12.4.2分治法和两路合并排序
12.4.3合并排序算法
12.4.4性能分析
12.5堆排序
12.5.1堆排序算法
12.5.2实现堆排序
12.5.3性能分析
12.6排序算法的时间下界
12.7基数排序
12.7.1分配排序
12.7.2基数排序算法
12.7.3实现基数排序
本章小结
习题
第13章文件和外排序
13.1辅助存储器简介
13.1.1主存储器和辅助存储器
13.1.2磁盘存储器
13.2文件
13.2.1文件的基本概念
13.2.2文件的组织方式
13.3文件的索引结构
13.3.1静态索引结构
13.3.2动态索引结构
13.4外排序
13.4.1外排序的基本过程
13.4.2初始游程的生成
13.4.3多路合并
13.4.4最佳合并树
本章小结
习题
第三部分算法设计与分析
第14章问题求解和算法设计
14.1问题求解方法
14.1.1问题和问题求解
14.1.2问题求解过程
14.1.3系统生命周期
14.1.4问题求解策略
14.2分治法
14.2.1一般方法
14.2.2递推关系
14.2.3求最大、最小元
14.2.4选择问题
14.2.5斯特拉森矩阵相乘
14.3贪心法
14.3.1一般方法
14.3.2最佳合并模式
14.3.3背包问题
14.3.4贪心法的基本要素
14.4动态规划法
14.4.1动态规划法的基本要素
14.4.2最优二叉搜索树
14.5回溯法
14.5.1一般方法
14.5.2n-皇后问题
14.5.3子集和数问题
14.6分支限界法
14.6.1一般方法
14.6.2基于上下界的分支限界法
14.6.30/1背包问题
14.6.4旅行商问题
14.7随机算法
14.7.1基本概念
14.7.2拉斯维加斯算法
14.7.3蒙特卡罗算法
14.7.4舍伍德算法
本章小结
习题
第15章NP难度和NP完全问题
15.1基本概念
15.1.1不确定算法和可满足性
问题
15.1.2P类和NP类问题
15.1.3NP难度和NP完全问题
15.1.4Cook定理
15.2一些典型的NP完全问题
15.2.1最大集团判定问题
15.2.2顶点覆盖判定问题
15.2.33元CNF-可满足性
15.2.4图着色数判定问题
本章小结
习题
附录
附录A实习要求和实习题
A.1面向对象方法概述
A.2实习目的
A.3实习要求
A.4实习步骤
A.5实习报告
A.6实习题
附录BC++程序设计概要
B.1函数与参数传递
B.2动态存储分配
B.3类与对象
B.4函数和操作符重载
B.5继承性和派生类
B.6多态性、虚函数和动态联编
B.7纯虚函数和抽象类
B.8模板函数和模板类
B.9友元函数和友元类
附录C专有名词中英文对照表
参考文献