目录

第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

第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抽象数据类型BinaryTree148

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树177

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

8.10跳表197

8.10.1跳表时间复杂度分析198

8.10.2跳表的空间复杂度分析198

8.10.3高效的动态插入和删除199

8.10.4小结200

习题201第9章图203

9.1基本概念203

9.2图的存储表示205

9.2.1相邻矩阵表示图205

9.2.2图的邻接表表示206

9.2.3邻接多重表207

9.3基于邻接表表示的Graph结构209

9.4图的遍历210

9.4.1深度优先遍历210

9.4.2广度优先遍历212

9.5最小代价生成树213

9.6单源最短路径问题217

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

9.8有向无回路图222

9.8.1DAG图和AOV、AOE网222

9.8.2AOV网的拓扑排序224

9.8.3AOE网的关键路径226

习题228第10章算法设计与分析230

10.1递归与分治230

10.1.1递归方法设计230

10.1.2分治法231

10.2回溯法233

10.3分支限界法238

10.4贪心算法245

10.5动态规划法246

10.6数据结构中的Catalan数249

10.6.1问题描述249

10.6.2问题解析249

10.6.3递归方程求解251

习题252关键词索引254

参考文献257

第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