第1章 数据结构绪论 1
1.1开场白 2
1.2你数据结构怎么学的？ 3
1.3数据结构起源 4
1.4基本概念和术语 5
1.4.1数据 5
1.4.2数据元素 5
1.4.3数据项 6
1.4.4数据对象 6
1.4.5数据结构 6
1.5逻辑结构与物理结构 7
1.5.1逻辑结构 7
1.5.2物理结构 9
1.6抽象数据类型 11
1.6.1数据类型 11
1.6.2抽象数据类型 12
1.7总结回顾 14
1.8结尾语 15
第2章 算法 17
2.1开场白 18
2.2数据结构与算法关系 18
2.3两种算法的比较 19
2.4算法定义 20
2.5算法的特性 21
2.5.1输入输出 21
2.5.2有穷性 21
2.5.3确定性 21
2.5.4可行性 21
2.6算件设计的要求 22
2.6.1正确性 22
2.6.2可读性 23
2.6.3健壮性 23
2.6.4时间效率高和存储量低 23
2.7算法效率的度量方法 24
2.7.1事后统计方法 24
2.7.2事前分析估算方法 25
2.8函数的渐近增长 27
2.9算法时间复杂度 29
2.9.1算法时间复杂度定义 29
2.9.2推导大O阶方法 30
2.9.3常数阶 30
2.9.4线性阶 31
2.9.5对数阶 32
2.9.6平方阶 32
2.10常见的时间复杂度 35
2.11最坏情况与平均情况 35
2.12算法空间复杂度 36
2.13总结回顾 37
2. 14结尾语 38
第3章 线性表 41
3.1开场白 42
3.2线性表的定义 42
3.3线性表的抽象数据类型 45
3.4线性表的顺序存储结构 47
3.4.1顺序存储定义 47
3.4.2顺序存储方式 47
3.4.3数据长度与线性表长度区别 48
3.4.4地址计算方法 49
3.5顺序存储结构的插入与删除 50
3.5.1获得元素操作 50
3.5.2插入操作 51
3.5.3删除操作 52
3.5.4线性表顺序存储结构的优缺点 54
3.6线性表的链式存储结构 55
3.6.1顺序存储结构不足的解决办法 55
3.6.2线性表链式存储结构定义 56
3.6.3头指针与头结点的异同 58
3.6.4线性表链式存储结构代码描述 58
3.7单链表的读取 60
3.8单链表的插入与删除 61
3.8.1单链表的插入 6
3.8.2单链表的删除 64
3.9单链表的整表创建 66
3.10单链表的整表删除 69
3.11单链表结构与顺序存储结构优缺点 70
3.12静态链表 71
3.12.1静态链表的插入操作 73
3.12.2静杰链表的删除操作 75
3.12.3静态链表优缺点 77
3.13循环链表 78
3.14双向链表 81
3.15 总结回顾 84
3.16结尾语 85
第4章 栈与队列 87
4.1开场白 88
4.2栈的定义 89
4.2.1栈的定义 89
4.2.2进栈出栈变化形式 90
4.3栈的抽象数据类型 91
4.4栈的顺序存储结构及实现 92
4.4.1栈的顺序存储结构 92
4.4.2栈的顺序存储结构——进栈操作 93
4.4.3栈的顺序存储结构——出栈操作 94
4.5两栈共享空间 94
4.6栈的链式存储结构及实现 97
4.6.1栈的链式存储结构 97
4.6.2栈的链式存储结构——进栈操作 98
4.6.3栈的链式存储结构——出栈操作 99
4.7栈的作用 100
4.8栈的应用——递归 100
4.8.1斐波那契数列实现 101
4.8.2递归定义 103
4.9栈的应用——四则运算表达式求值 104
4.9.1后缀（逆波兰）表示法定义 104
4.9.2后缀表达式计算结果 106
4.9.3中缀表达式转后缀表达式 108
4.10队列的定义 111
4.11队列的抽象数据类型 112
4. 12循环队列 112
4.12.1队列顺序存储的不足 112
4.12.2循环队列定义 114
4.13队列的链式存储结构及实现 117
4.13.1队列的链式存储结构——入队操作 118
4.13.2队列的链式存储结构——出队操作 119
4.14总结回顾 120
4.15结尾语 121
第5章串 123
5.1开场白 124
5.2串的定义 124
5.3串的比较 126
5.4串的抽象数据类型 127
5.5串的存储结构 129
5.5.1串的顺序存储结构 129
5.5.2串的链式存储结构 131
5.6朴素的模式匹配算法 131
5.7 KMP模式匹配算法 135
5.7.1 KMP模式匹配算法原理 135
5.7.2 next数组值推导 139
5.7.3 KMP模式匹配算法实现 141
5.7.4 KMP模式匹配算法改进 142
5.7.5 nextval数组值推导 144
5.8总结回顾 146
5.9结尾语 146
第6章树 149
6.1开场白 150
6.2树的定义 150
6.2.1结点分类 152
6.2.2结点间关系 152
6.2.3树的其他相关概念 153
6.3树的抽象数据类型 154
6.4树的存储结构 155
6.4.1双亲表示法 155
6.4.2孩子表示法 158
6.4.3孩子兄弟表示法 162
6.5二叉树的定义 163
6.5.1二叉树特点 165
6.5.2特殊二叉树 166
6.6二叉树的性质 169
6.6.1二叉树性质1 169
6.6.2二叉树性质2 169
6.6.3一叉树性质3 169
6.6.4二叉树性质4 170
6.6.5二叉树性质5 171
6.7二叉树的存储结构 172
6.7.1二叉树顺序存储结构 172
6.7.2二叉链表 173
6.8遍历二叉树 174
6.8.1二叉树遍历原理 174
6.8.2二叉树遍历方法 175
6.8.3前序遍历算法 178
6.8.4中序遍历算法 181
6.8.5后序遍历算法 184
6.8.6推导遍历结果 184
6.9二叉树的建立 187
6.10线索二叉树 188
6.10.1线索二叉树原理 188
6.10.2线索二叉树结构实现 191
6.11树、森林与二叉树的转换 195
6.11.1树转换为二叉树 196
6.11.2森林转换为二叉树 197
6.11.3二叉树转换为树 197
6.11.4二叉树转换为森林 198
6.11.5树与森林的遍历 199
6.12赫夫曼树及其应用 200
6.12.1赫夫曼树 200
6.12.2赫夫曼树定义与原理 203
6.12.3赫夫曼编码 205
6.13总结回顾 208
6.14结尾语 209
第7章图 211
7.1开场白 212
7.2图的定义 213
7.2.1各种图定义 214
7.2.2图的顶点与边间关系 217
7.2.3连通图相关术语 219
7.2.4图的定义与术语总结 222
7.3图的抽象数据类型 222
7.4图的存储结构 223
7.4.1邻接矩阵 224
7.4.2邻接表 228
7.4.3十字链表 232
7.4.4邻接多重表 234
7.4.5边集数组 236
7.5图的遍历 237
7.5.1深度优先遍历 238
7.5.2广度优先遍历 242
7.6最小生成树 245
7.6.1普里姆（Pm）算法 247
7.6.2克鲁斯卡尔（Kskal ）算法 251
7.7最短路径 257
7.7.1迪杰斯特拉（Dijkstra）算法 259
7.7.2弗洛伊德（Floyd ）算法 265
7.8拓扑排序 270
7.8.1拓扑排序介绍 271
7.8.2拓扑排序算法 272
7.9关键路径 277
7.9.1关键路径算法原理 279
7.9.2关键路径算法 280
7.10总结回顾 287
7.11结尾语 289
第8章 查找 291
8.1开场白 292
8.2查找概论 293
8.3顺序表查找 295
8.3.1顺序表查找算法 296
8.3.2顺序表查找优化 297
8.4有序表查找 298
8.4.1折半查找 298
8.4.2插值查找 301
8.4.3斐波那契查找 302
8.5线性索引查找 306
8.5.1稠密索引 307
8.5.2分块索引 308
8.5.3倒排索引 311
8.6二叉排序树 313
8.6.1二叉排序树查找操作 316
8.6.2二叉排序树插入操作 318
8.6.3二叉排序树删除操作 320
8.6.4二叉排序树总结 327
8.7平衡二叉树（AVL树） 328
8.7.1平衡二叉树实现原理 330
8.7.2平衡二叉树实现算法 334
8.8多路查找树（B树） 341
8.8.1 2-3树 343
8.8.2 2-3-4树 348
8.8.3 B树 349
8.8.4 B+树 351
8.9散列表查找（哈希表）概述 353
8.9.1散列表查找定义 354
8.9.2散列表查找步骤 355
8.10散列函数的构造方法 356
8.10.1直接定址法 357
8.10.2数字分析法 358
8.10.3平方取中法 358
8.10.4折叠法 359
8.10.5除留余数法 359
8.10.6随机数法 360
8.11处理散列冲突的方法 360
8.11.1开放定址法 361
8.11.2再散列函数法 363
8.11.3链地址法 363
8.11.4公共溢出区法 364
8.12散列表查找实现 365
8.12.1散列表查找算法实现 365
8.12.2散列表查找性能分析 367
8. 13总结回顾 368
8.14结尾语 369
第9章 排序 373
9.1开场白 374
9.2排序的基本概念与分类 375
9.2.1排序的稳定性 376
9.2.2内排序与外排序 377
9.2.3排序用到的结构与函数 378
9.3冒泡排序 378
9.3.1最简单排序实现 379
9.3.2冒泡排序算法 380
9.3.3冒泡排序优化&3 82
9.3.4冒泡排序复杂度分析 383
9.4简单选择排序 384
9.4.1简单选择排序算法 384
9.4.2简单选择排序复杂度分析&3 85
9.5直接插入排序 386
9.5.1直接插入排序算法 386
9.5.2直接插入排序复杂度分析 388
9.6希尔排序 389
9.6.1希尔排序原理 391
9.6.2希尔排序算法 391
9.6.3希尔排序复杂度分析 395
9.7堆排序 396
9.7.1堆排序算法 398
9.7.2堆排序复杂度分析 405
9.8归并排序 406
9.8.1归并排序算法 407
9.8.2归并排序复杂度分析 413
9.8.3非递归实现归并排序 413
9.9快速排序 417
9.9.1快速排序算法 417
9.9.2快速排序复杂度分析 421
9.9.3快速排序优化 422
9.10总结回顾 428
9.11结尾语 430
关键词索引 435
参考文献 439