●章数据结构绪论1
1.1开场白2
1.2你数据结构怎么学的3
1.3数据结构起源4
1.4基本概念和术语5
1.4.1数据5
1.4.2数据元素6
1.4.3数据项7
1.4.4数据对象7
1.4.5数据结构7
1.5逻辑结构与物理结构8
1.5.1逻辑结构8
1.5.2物理结构9
1.6数据类型11
1.6.1数据类型定义11
1.6.2抽象数据类型12
1.7总结回顾13
1.8结尾语14
第2章算法15
2.1开场白16
2.2数据结构与算法的关系16
2.3两种算法的比较17
2.4算法定义18
2.5算法的特性19
2.5.1输入输出19
2.5.2有穷性19
2.5.3确定性20
2.5.4可行性20
2.6算法设计的要求20
2.6.1正确性21
2.6.2可读性21
2.6.3健壮性21
2.时间效率高和存储量低22
2.7算法效率的度量方法22
2.7.1事后统计方法22
2.7.2事前分析估算方法23
2.8函数的渐近增长25
2.9算法时间复杂度27
2.9.1算法时间复杂度定义27
2.9.2推导大O阶方法28
2.9.3常数阶28
2.9.4线性阶29
2.9.5对数阶29
2.9.6平方阶29
2.10常见的时间复杂度31
2.11坏情况与平均情况32
2.12算法空间复杂度33
2.13总结回顾34
2.14结尾语35
第3章线性表37
3.1开场白38
3.2线性表的定义39
3.3线性表的抽象数据类型41
3.4线性表的顺序存储结构43
3.4.1顺序存储定义43
3.4.2顺序存储方式43
3.4.3数据长度与线性表长度的区别44
3.4.4地址计算方法45
3.5顺序存储结构的插入与删除46
3.5.1获得元素操作46
3.5.2插入操作46
3.5.3删除操作47
3.5.4线性表顺序存储结构的优缺点49
3.6线性表的链式存储结构49
3.6.1顺序存储结构不足的解决办法49
3.6.2线性表链式存储结构定义50
3.6.3头指针与头结点的异同52
3.线性表链式存储结构代码描述52
3.7单链表的读取53
3.8单链表的插入与删除54
3.8.1单链表的插入54
3.8.2单链表的删除56
3.9单链表的整表创建58
3.10单链表的整表删除60
3.11单链表结构与顺序存储结构的优缺点61
3.12静态链表62
3.12.1静态链表的插入操作
3.12.2静态链表的删除操作65
3.12.3静态链表的优缺点67
3.13循环链表67
3.14双向链表70
3.15总结回顾72
3.16结尾语73
第4章栈与队列75
4.1开场白76
4.2栈的定义76
4.2.1栈的定义76
4.2.2进栈出栈变化形式78
4.3栈的抽象数据类型78
4.4栈的顺序存储结构及实现79
4.4.1栈的顺序存储结构79
4.4.2栈的顺序存储结构——进栈操作80
4.4.3栈的顺序存储结构——出栈操作81
4.5两栈共享空间81
4.6栈的链式存储结构及实现83
4.6.1栈的链式存储结构83
4.6.2栈的链式存储结构——进栈操作84
4.6.3栈的链式存储结构——出栈操作85
4.7栈的作用85
4.8栈的应用——递归86
4.8.1斐波那契数列的实现86
4.8.2递归的定义88
4.9栈的应用——四则运算表达式求值89
4.9.1后缀（逆波兰）表示法的定义89
4.9.2后缀表达式的计算结果90
4.9.3中缀表达式转后缀表达式92
4.10队列的定义93
4.11队列的抽象数据类型94
4.12循环队列95
4.12.1队列顺序存储的不足95
4.12.2循环队列的定义96
4.13队列的链式存储结构及实现99
4.13.1队列的链式存储结构——入队操作100
4.13.2队列的链式存储结构——出队操作100
4.14总结回顾101
4.15结尾语102
第5章串103
5.1开场白104
5.2串的定义104
5.3串的比较105
5.4串的抽象数据类型107
5.5串的存储结构108
5.5.1串的顺序存储结构108
5.5.2串的链式存储结构109
5.6朴素的模式匹配算法110
5.7KMP模式匹配算法113
5.7.1KMP模式匹配算法的原理113
5.7.2next数组值的推导116
5.7.3KMP模式匹配算法的实现117
5.7.4KMP模式匹配算法的改进119
5.7.5nextval数组值的推导120
5.8总结回顾122
5.9结尾语122
第6章树125
6.1开场白126
6.2树的定义126
6.2.1结点的分类127
6.2.2结点间的关系128
6.2.3树的其他相关概念129
6.3树的抽象数据类型129
树的存储结构130
.1双亲表示法130
.2孩子表示法133
.3孩子兄弟表示法136
6.5二树的定义137
6.5.1二树的特点139
6.5.2特殊二树140
6.6二树的性质142
6.6.1二树的性质1142
6.6.2二树的性质2143
6.6.3二树的性质3143
6.二树的性质4144
6.6.5二树的性质5144
6.7二树的存储结构145
6.7.1二树的顺序存储结构145
6.7.2二链表146
6.8遍历二树147
6.8.1二树的遍历原理147
6.8.2二树的遍历方法148
6.8.3前序遍历算法150
6.8.4中序遍历算法153
6.8.5后序遍历算法156
6.8.6推导遍历结果156
6.9二树的建立158
6.10线索二树159
6.10.1线索二树的原理159
6.10.2线索二树结构的实现162
6.11树、森林与二树的转换165
6.11.1树转换为二树166
6.11.2森林转换为二树167
6.11.3二树转换为树168
6.11.4二树转换为森林169
6.11.5树与森林的遍历170
6.12哈夫曼树及其应用171
6.12.1哈夫曼树171
6.12.2哈夫曼树的定义与原理173
6.12.3哈夫曼编码176
6.13总结回顾177
6.14结尾语178
第7章图181
7.1开场白182
7.2图的定义182
7.2.1各种图的定义183
7.2.2图的顶点与边间的关系185
7.2.3连通图的相关术语187
7.2.4图的定义与术语总结189
7.3图的抽象数据类型190
7.4图的存储结构191
7.4.1邻接矩阵192
7.4.2邻接表195
7.4.3十字链表198
7.4.4邻接多重表199
7.4.5边集数组201
7.5图的遍历202
7.5.1深度优先遍历203
7.5.2广度优先遍历205
7.6小生成树208
7.6.1普里姆（Prim）算法209
7.6.2克鲁斯卡尔（Kruskal）算法213
7.7短路径218
7.7.1迪杰斯特拉（Dijkstra）算法220
7.7.2弗洛伊德（Floyd）算法225
7.8拓扑排序229
7.8.1拓扑排序介绍229
7.8.2拓扑排序算法230
7.9关键路径234
7.9.1关键路径算法的原理236
7.9.2关键路径算法237
7.10总结回顾242
7.11结尾语243
第8章查找245
8.1开场白246
8.2查找概论247
8.3顺序表查找249
8.3.1顺序表查找算法249
8.3.2顺序表查找优化250
8.4有序表查找251
8.4.1折半查找251
8.4.2插值查找253
8.4.3斐波那契查找255
8.5线性索引查找257
8.5.1稠密索引258
8.5.2分块索引258
8.5.3倒排索引260
8.6二排序树262
8.6.1二排序树的查找操作2
8.6.2二排序树的插入操作266
8.6.3二排序树的删除操作267
8.二排序树总结272
8.7平衡二树（AVL树）273
8.7.1平衡二树的实现原理275
8.7.2平衡二树的实现算法278
8.8多路查找树（B树）284
8.8.12-3树285
8.8.22-3-4树289
8.8.3B树290
8.8.4B树292
8.9散列表查找（哈希表）概述294
8.9.1散列表查找定义294
8.9.2散列表查找步骤295
8.10散列函数的构造方法296
8.10.1直接定址法297
8.10.2数字分析法297
8.10.3平方取中法298
8.10.4折叠法298
8.10.5除留余数法298
8.10.6随机数法299
8.11处理散列冲突的方法300
8.11.1开放定址法300
8.11.2再散列函数法302
8.11.3链地址法302
8.11.4公共溢出区法302
8.12散列表查找的实现303
8.12.1散列表查找的算法实现303
8.12.2散列表查找的性能分析305
8.13总结回顾305
8.14结尾语306
第9章排序309
9.1开场白310
9.2排序的基本概念与分类310
9.2.1排序的稳定性311
9.2.2内排序与外排序312
9.2.3排序用到的结构与函数313
9.3冒泡排序314
9.3.1简单排序的实现314
9.3.2冒泡排序算法315
9.3.3冒泡排序优化316
9.3.4冒泡排序复杂度分析317
9.4简单选择排序318
9.4.1简单选择排序算法318
9.4.2简单选择排序复杂度分析319
9.5直接插入排序320
9.5.1直接插入排序算法320
9.5.2直接插入排序复杂度分析322
9.6希尔排序323
9.6.1希尔排序原理324
9.6.2希尔排序算法325
9.6.3希尔排序复杂度分析328
9.7堆排序329
9.7.1堆排序算法331
9.7.2堆排序复杂度分析337
9.8归并排序337
9.8.1归并排序算法338
9.8.2归并排序复杂度分析343
9.8.3非递归实现归并排序343
9.9快速排序346
9.9.1快速排序算法346
9.9.2快速排序复杂度分析349
9.9.3快速排序优化350
9.10总结回顾354
9.11结尾语357