数据结构与算法（第2版）

内容简介

编辑推荐

本书内容包括基本数据类型、抽象数据类型、顺序表、鍊表、串、树和二叉树、图、递归与分治算法、贪心算法、分支限界和动态规划等内容；重点介绍抽象数据类型、基本数据结构、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向量的套用/23

2.3栈/26

2.3.1栈的抽象数据类型及其实现/26

2.3.2栈的套用/29

2.4递归效率分析/36

2.4.1递归方程求解/36

2.4.2生成函式求解递归方程/37

2.4.3特徵方程求解递归方程/38

2.4.4递归树方法/39

2.5伫列/40

2.5.1伫列的抽象数据类型及其实现/40

2.5.2伫列的套用——模拟银行活动/46

习题/54

第3章鍊表/56

3.1单鍊表/56

3.1.1基本概念/56

3.1.2单鍊表结点结构/57

3.1.3单鍊表结构/59

3.1.4栈的单鍊表实现/70

3.1.5伫列的单鍊表实现/71

3.1.6单鍊表的套用举例/75

3.2循环鍊表/80

3.3双鍊表/82

习题/84第4章串/87

4.1基本概念/87

4.2串的存储/88

4.3串结构和串的运算/89

4.4模式匹配/91

4.4.1朴素的模式匹配算法/91

4.4.2KMP匹配算法/92

4.4.3BM匹配算法/95

习题/98第5章排序/99

5.1基本概念/99

5.2插入排序/100

5.2.1直接插入排序/100

5.2.2折半插入排序/102

5.2.3Shell排序/104

5.3选择排序/105

5.3.1直接选择排序/105

5.3.2树形选择排序/107

5.4交换排序/108

5.4.1起泡排序/108

5.4.2快速排序/109

5.5分配排序/113

5.5.1基本思想/113

5.5.2基数排序/114

5.6归併排序/117

5.7外部排序/120

5.7.1二路合併排序/120

5.7.2多路替代选择合併排序/121

5.7.3最佳合併排序/122

习题/123第6章查找/125

6.1基本概念/125

6.2顺序查找/125

6.3折半查找/127

6.4分块查找/129

6.5散列查找/131

6.5.1概述/131

6.5.2散列函式/132

6.5.3冲突的处理/134

6.5.4散列查找的效率/137

习题/138第7章树和二叉树/140

7.1树的概念/140

7.2二叉树/141

7.2.1二叉树的概念/141

7.2.2二叉树的性质/141

7.2.3二叉树的存储方式/144

7.2.4树(树林)与二叉树的相互转换/146

7.3树(树林)、二叉树的遍历/147

7.3.1树(树林)的遍历/147

7.3.2二叉树的遍历/147

7.4抽象数据类型BinaryTree以及BinaryTree

结构/148

7.4.1抽象数据类型BinaryTree/148

7.4.2一个完整的包含构建二叉树与遍历

实现的例子/150

7.5二叉树的遍历算法/151

7.5.1非递归(使用栈)的遍历算法/151

7.5.2线索化二叉树的遍历/153

习题/157第8章树状结构的套用/159

8.1二叉排序树/159

8.1.1二叉排序树与BinarySTree结构/159

8.1.2二叉排序树的检索、插入、删除

运算/160

8.1.3等机率查找对应的最佳二叉排

序树/164

8.2平衡的二叉排序树/166

8.2.1平衡二叉排序树的定义/166

8.2.2平衡二叉排序树的插入、

删除/167

8.2.3AVL树高度/170

8.3B树、B+树/171

8.4键树和23树/175

8.4.1键树/175

8.4.223树/176

8.5Huffman最优树与树编码/178

8.5.1Huffman最优树/178

8.5.2树编码/181

8.6堆排序/183

8.7判定树/189

8.8等价类和并查集/190

8.8.1等价类/190

8.8.2并查集/190

8.9红黑树/193

习题/197第9章图/199

9.1基本概念/199

9.2图的存储表示/201

9.2.1相邻矩阵表示图/201

9.2.2图的邻接表表示/202

9.2.3邻接多重表/203

9.3基于邻接表表示的Graph结构/205

9.4图的遍历/206

9.4.1深度优先遍历/206

9.4.2广度优先遍历/208

9.5最小代价生成树/209

9.6单源最短路径问题/213

9.7每一对顶点间的最短路径问题/216

9.8有向无迴路图/218

9.8.1DAG图和AOV、AOE网/218

9.8.2AOV网的拓扑排序/220

9.8.3AOE网的关键路径/222

习题/224第10章算法设计与分析/226

10.1递归与分治/226

10.1.1递归方法设计/226

10.1.2分治法/227

10.2回溯法/229

10.3分支限界法/234

10.4贪心算法/241

10.5动态规划法/242

习题/245图目录/247算法目录/252关键字索引/247参考文献/250图目录

图1.1基本的逻辑结构3

图1.2基本存储方法4

图1.3游泳池及环形过道8

图2.1向量的顺序存储19

图2.2顺序存储的栈26

图2.3中缀表达式的计值过程30

图2.4后缀表达式的计值30

图2.5中缀表达式转换成后缀表达式的过程31

图2.6汉诺塔问题的递归求解过程33

图2.7活动记录的进栈情况35

图2.8活动记录的退栈情况36

图2.9式(2.1)的递归树39

图2.10式(2.2)的递归树40

图2.11顺序存储的伫列40

图2.12伫列的操作41

图2.13循环伫列的队空和队满41

图3.1单鍊表56

图3.2从鍊表中删除一个结点56

图3.3往鍊表中插入一个结点56

图3.4附加头结点的单鍊表57

图3.5一个实际的单鍊表结构65

图3.6空的循环鍊表80

图3.7双鍊表结点82

图3.8双鍊表82

图3.9往双鍊表中插入一个结点82

图3.10从双鍊表中删除一个结点82

图3.11题3.2用图85

图4.1串的顺序存储88图4.2串的紧缩顺序存储88

图4.3串的连结存储89

图4.4第1趟比较91

图4.5第2趟比较92

图4.6朴素的模式匹配算法执行过程92

图4.7模式P=abcabcd的next数组的计算过程95

图4.8基于KMP匹配算法的模式匹配过程96

图5.1直接插入排序的过程100

图5.2折半查找过程102

图5.3Shell排序过程104

图5.4直接选择排序106

图5.5第一次树形选择排序选出最小排序码13107

图5.6第二次树形选择排序选出最小排序码14107

图5.7起泡排序过程108

图5.8第1趟快速排序的比较过程110

图5.9基数排序的分配和收集过程115

图5.10二路归併过程118

图5.11二路归併排序示意121

图5.12实现五路合併败者树122

图5.13实现五路合併一次替代选择后的败者树122

图5.14顺序合併的三路合併树122

图5.15三路最佳合併树123

图6.1折半查找过程128

图6.2分块查找过程130

图6.3用分离的同义词子表解决冲突137

图6.4用结合的同义词子表解决冲突137

图6.5几种不同的解决碰撞方法时的平均检索长度（横坐标为负载因子的

取值）138

图6.6题6.8用图139

图7.1家族树140

图7.2二叉树的五种基本形态141

图7.3表达式二叉树142

图7.4深度为3的满二叉树142

图7.5特殊的二叉树143

图7.6i与i+1在同一层的完全二叉树143

图7.7i与i+1不在同一层的完全二叉树143

图7.8完全二叉树的顺序存储144

图7.9非完全二叉树的顺序存储144

图7.10二叉树的LeftChildRightChild表示145

图7.11树(树林)与二叉树之间相互转换146

图7.12树林的例子147

图7.13图7.12对应的二叉树148

图7.14二叉树遍历实例150

图7.15对称序线索树153

图7.16在对称序线索化二叉树中插入新结点156

图7.17题7.5用图157

图7.18题7.7用图157

图7.19题7.14用图158

图7.20题7.15用图158

图8.1二叉排序树159

图8.2构造二叉排序树162

图8.3二叉排序树中删除一个结点164

图8.4删除结点11后的另一种形式164

图8.5两种不同的二叉排序树164

图8.6两棵扩充二叉树164

图8.7最佳二叉排序树的构造165

图8.8二叉树与结点的平衡因子167

图8.9平衡的二叉排序的生成过程(带★的点为插入后引起不平衡的点)168

图8.10二叉排序树的平衡旋转169

图8.11AVL二叉排序树结点的删除(结点中右边数字代表平衡因子)170

图8.12一棵7阶的B树171

图8.13B树的插入173

图8.14图8.13中删除元素80173

图8.15图8.13中删除元素4173

图8.16在图8.15中删除元素60174

图8.17在图8.16中删除元素70174

图8.18一棵3阶的B+树174

图8.19键树示例175

图8.20由图8.19压缩后的键树176

图8.21键树中插入记录176

图8.22两棵不同形式的23树177

图8.2323树的插入177

图8.24在图8.22(b)中插入8后23树的变化图178

图8.2523树的删除178

图8.26一棵扩充的二叉树178

图8.27赫夫曼最优树的构造过程179

图8.28Huffman编码树182

图8.29堆对应的完全二叉树183

图8.30堆中插入新结点183

图8.31堆中根结点的删除184

图8.32筛法建堆过程184

图8.33堆排序过程185

图8.34三个元素排序的判定树189

图8.35鉴别伪币的判定树189

图8.36用父指针表示的树状结构存储的并查集191

图8.37并查集的查找、合併过程191

图8.38Union加权规则示意图192

图8.39路径压缩的例子193

图8.40一棵阶为2的红黑树194

图8.41红黑树的生长过程194

图8.42一棵2阶红黑树195

图8.43红黑树中删除元素88195

图8.44图8.43调整后的红黑树196

图8.45图8.44中删除元素71196

图8.46图8.45调整后的红黑树196

图8.47图8.46中删除元素63196

图8.48调整图8.47后的红黑树197

图8.49题8.15用图198

图9.1无向图和有向图199

图9.2图G4=(V,E)200

图9.3图G3的强连通分量201

图9.4G1的生成树201

图9.5G3的生成树林201

图9.6图G5(网路)201

图9.7图的邻接表表示203

图9.8G5的邻接表表示204

图9.9图9.7(a)的邻接多重表表示204

图9.10图9.7(c)的多重鍊表表示205

图9.11有向图深度优先搜寻过程206

图9.12无向图深度方向优先遍历207

图9.13广度优先生成树(树林)209

图9.14T的变化图210

图9.15Prim算法构造最小生成树的过程211

图9.16Kruskal构造最小生成树的过程213

图9.17有向图G213

图9.18含三个顶点的有向网路217

图9.19表达式树218

图9.20共享结点后的表达式树219

图9.21表示各课程优先关係的AOV网219

图9.22一个AOV网的例子220

图9.23图9.22的关键路径为(a1,a4,a8,a11)或(a1,a4,a7,a10)222

图9.24题9.1用图224

图9.25题9.2用图224

图9.26题9.3用图224

图9.27题9.5用图224

图9.28题9.6用图225

图9.29题9.7用图225

图9.30题9.10用图225

图9.31题9.12用图225

图10.1用01矩阵表示的迷宫230

图10.201背包问题的解空间树235

图10.3树T241

图10.4树T0241

图10.5树T1242

图10.6内部结点构造图242

图10.7题10.5用图245

算法目录

算法1.1计算修建游泳池工程造价8

算法1.2计算两个n×n矩阵的乘积10

算法2.1线性表运算15

算法2.2向量运算19

算法2.3向量的插入21

算法2.4向量的删除22

算法2.5集合併运算23

算法2.6集合交运算24

算法2.7约瑟夫问题25

算法2.8堆叠运算27

算法2.9后缀表达式计值31

算法2.10求和与阶乘的递归算法33

算法2.11汉诺塔问题的递归求解实现34

算法2.12阶乘的递归调用35

算法2.13伫列的运算42

算法2.14优先权伫列45

算法2.15事件驱动模拟49

算法3.1单鍊表结点及操作58

算法3.2单鍊表中的运算60

算法3.3用Nodelib中的函式实现单鍊表的建立和查找68

算法3.4基于单鍊表结构的操作方法实现单鍊表的建立和查找69

算法3.5链栈运算70

算法3.6链伫列运算72

算法3.7列印缓冲池76

算法3.8模拟列印缓冲池的实现主函式78

算法3.9循环鍊表运算81

算法3.10双鍊表中的运算83算法4.1串运算90

算法4.2KMP匹配算法93

算法4.3计算next数组94

算法5.1直接插入排序101

算法5.2折半插入排序102

算法5.3Shell排序105

算法5.4直接选择排序106

算法5.5起泡排序108

算法5.6快速排序111

算法5.7基数排序115

算法5.8归併排序118

算法5.9一趟两组归併119

算法5.10两组归併119

算法6.1顺序查找126

算法6.2折半查找128

算法6.3线性探测法解决冲突135

算法6.4用双散列函式解决冲突136

算法7.1二叉树构建与遍历150

算法7.2使用栈的二叉树前序遍历151

算法7.3使用栈的二叉树对称序遍历152

算法7.4使用栈的二叉树后序遍历152

算法7.5对称序线索化二叉树154

算法7.6在对称序线索树中找指定结点的对称序后继155

算法7.7对称序遍历对称序线索化二叉树155

算法7.8在对称序线索化二叉树中插入一新结点156

算法8.1将p所指结点插入以q为根结点指针的二叉排序树中160

算法8.2构造二叉排序树161

算法8.3二叉排序树中结点的删除162

算法8.4构造Huffman树180

算法8.5大根堆185

算法9.1基于邻接表表示图的深度优先遍历算法207

算法9.2Prim算法211

算法9.3Dijkstra算法215

算法9.4Floyd算法求网路中任意两顶点间的最短路径217

算法9.5拓扑排序221

算法10.1整数划分227

算法10.2迷宫问题230

算法10.3n皇后问题233

算法10.4背包问题的分支限界法算法236

算法10.5求两字元串的最长公共子序列243