数据结构与算法(第3版)

本书由国防科技大学熊岳山教授编写，

“数据结构与算法”是计算机科学与技术、软件工程等相关专业的重要基础课，是这些专业的核心课程之一，是一门集技术性、理论性和实践性于一体的课程。本书内容包括基本数据类型、抽象数据类型、线性表、链表、串、树和二叉树、图、递归与分治算法、贪心算法、分支限界法和动态规划法等内容；并重点介绍抽象数据类型、基本数据结构、C语言数据结构描述、数据结构的应用、算法设计与分析以及算法性能评价等内容，目的是让读者理解数据抽象与编程实现的关系，提高用计算机解决实际问题的能力。
本书结构合理，内容丰富，算法描述清晰，用C语言编写的算法代码都已调试通过，便于自学，可作为高等院校计算机科学与技术专业、军事院校的基础合训专业和其他相关专业的教材和参考书，也可供从事计算机软件开发的科技工作者参考。

第1章数据结构概述1
1.1基本概念1
1.1.1数据、数据元素、数据对象1
1.1.2数据结构2
1.2数据结构的分类3
1.3数据类型5
1.3.1基本类型和组合类型5
1.3.2抽象数据类型5
1.4算法和算法分析8
1.4.1算法概念8
1.4.2算法分析9
习题11
第2章向量、栈和队列13
2.1线性表13
2.1.1线性表的抽象数据类型13
2.1.2线性表的结构表示15
2.2向量18
2.2.1向量的抽象数据类型18
2.2.2向量的插入和删除20
2.2.3向量的应用22
2.3栈25
2.3.1栈的抽象数据类型及其实现25
2.3.2栈的应用27
2.4递归效率分析34
2.4.1递归方程求解34
2.4.2生成函数求解递归方程35
2.4.3特征方程求解递归方程36
2.4.4递归树方法37
2.5队列38
2.5.1队列的抽象数据类型及其实现39
2.5.2队列的应用——模拟银行活动44
习题51
第3章链表53
3.1单链表53
3.1.1基本概念53
3.1.2单链表结点结构54
3.1.3单链表结构56
3.1.4栈的单链表实现65
3.1.5队列的单链表实现66
3.1.6单链表的应用举例70
3.2循环链表74
3.3双链表76
习题78
第4章串81
4.1基本概念81
4.2串的存储82
4.3串结构和串的运算83
4.4模式匹配85
4.4.1朴素的模式匹配算法85
4.4.2KMP匹配算法86
4.4.3BM匹配算法89
习题91
第5章排序93
5.1基本概念93
5.2插入排序94
5.2.1直接插入排序94
5.2.2折半插入排序95
5.2.3Shell排序97
5.3选择排序99
5.3.1直接选择排序99
5.3.2树形选择排序100
5.4交换排序101
5.4.1起泡排序101
5.4.2快速排序103
5.5分配排序106
5.5.1基本思想106
5.5.2基数排序107
5.6归并排序110
5.7外部排序113
5.7.1二路合并排序113
5.7.2多路替代选择合并排序114
5.7.3很好合并排序114
习题116
第6章查找117
6.1基本概念117
6.2顺序查找117
6.3折半查找119
6.4分块查找121
6.5散列查找123
6.5.1概述123
6.5.2散列函数124
6.5.3冲突的处理126
6.5.4散列查找的效率129
习题130
第7章树和二叉树132
7.1树的概念132
7.2二叉树133
7.2.1二叉树的概念133
7.2.2二叉树的性质133
7.2.3二叉树的存储方式136
7.2.4树(树林)与二叉树的相互转换138
7.3树(树林)、二叉树的遍历139
7.3.1树(树林)的遍历139
7.3.2二叉树的遍历139
7.4抽象数据类型BinaryTree以及BinaryTree结构140
7.4.1抽象数据类型BinaryTree140
7.4.2一个完整的包含构建二叉树与遍历实现的例子142
7.5二叉树的遍历算法143
7.5.1非递归(使用栈)的遍历算法143
7.5.2线索化二叉树的遍历145
习题148
第8章树结构的应用150
8.1二叉排序树150
8.1.1二叉排序树与BinarySTree结构150
8.1.2二叉排序树的检索、插入、删除运算151
8.1.3等概率查找对应的很好二叉排序树154
8.2平衡的二叉排序树157
8.2.1平衡二叉排序树的定义157
8.2.2平衡二叉排序树的插入、删除157
8.2.3AVL树高度161
8.3B树、B+树161
8.4键树和23树165
8.4.1键树165
8.4.223树167
8.5Huffman很优树与树编码168
8.5.1Huffman很优树168
8.5.2树编码171
8.6堆排序173
8.7判定树178
8.8等价类和并查集179
8.8.1等价类179
8.8.2并查集180
8.9红黑树182
8.10跳表186
8.10.1跳表时间复杂度分析187
8.10.2跳表的空间复杂度分析187
8.10.3高效的动态插入和删除188
8.10.4小结189
习题189
第9章图191
9.1基本概念191
9.2图的存储表示193
9.2.1相邻矩阵表示图193
9.2.2图的邻接表表示194
9.2.3邻接多重表195
9.3基于邻接表表示的Graph结构197
9.4图的遍历197
9.4.1深度优先遍历198
9.4.2广度优先遍历200
9.5最小代价生成树201
9.6单源最短路径问题205
9.7每一对顶点间的最短路径问题208
9.8有向无回路图209
9.8.1DAG图和AOV、AOE网209
9.8.2AOV网的拓扑排序211
9.8.3AOE网的关键路径213
习题215
第10章算法设计与分析217
10.1递归与分治217
10.1.1递归方法设计217
10.1.2分治法218
10.2回溯法220
10.3分支限界法225
10.4贪心算法231
10.5动态规划法232
10.6数据结构中的Catalan数235
10.6.1问题描述235
10.6.2问题解析235
10.6.3递归方程求解236
习题237
关键词索引239
参考文献242