第1章 绪论 1
1.1数据结构 1
1.1.1基本概念 1
1.1.2数据的逻辑结构 2
1.1.3数据的存储结构 3
1.1.4数据结构的操作 3
1.1.5数据结构研究的内容及作用 5
1.2算法 6
1.2.1什么是算法 6
1.2.2算法的描述 7
1.2.3算法设计的目标 7
1.2.4算法效率分析 8
1.2.5算法存储空间分析 10
1.3数据结构、算法和程序的关系 10
1.3.1数据结构与算法 10
1.3.2数据结构与程序 11
1.4算法效率的典型例题 12
1.5本章小结 15
1.6习题 15
第2章 线性表 18
2.1线性表的逻辑结构 18
2.1.1线性表的定义 18
2.1.2线性表的基本操作 19
2.2线性表的顺序存储结构 20
2.2.1顺序表 20
2.2.2顺序表的基本运算 23
2.3顺序表的查找 25
2.3.1按位置查找元素 25
2.3.2按内容查找元素 25
2.3.3顺序表的查找操作的效率分析 27
2.4顺序表的插入与删除 27
2.4.1在顺序表的第i个位置插入一个元素 27
2.4.2删除顺序表的第i个位置元素 28
2.4.3顺序表的插入与删除操作的效率分析 29
2.5顺序表的典型例题 30
2.6线性表的链式存储结构 32
2.6.1单链表 32
2.6.2循环链表 34
2.6.3双向链表 35
2.6.4静态链表 36
2.7单链表的建立及其实现 37
2.7.1创建带头结点的空单链表的算法实现 37
2.7.2用头插法单链表的插入算法实现 37
2.7.3用尾插法单链表的插入算法实现 38
2.7.4在第i个位置插入结点的单链表插入算法实现 39
2.8单链表基本运算的实现 41
2.8.1单链表辅助运算的实现 41
2.8.2单链表求表长的实现 42
2.8.3单链表查找操作的实现 42
2.8.4单链表删除操作的实现 43
2.9双向链表基本运算的实现 44
2.9.1双向链表插入操作的实现 45
2.9.2双向链表删除操作的实现 46
2.10链表的典型例题 47
2.11本章小结 50
2.12习题 50
第3章栈 53
3.1栈的逻辑结构 53
3.1.1栈的定义 53
3.1.2栈的基本运算 53
3.2栈的顺序存储与操作实现 54
3.2.1栈的顺序存储 54
3.2.2顺序栈的操作实现 55
3.3栈的链式存储与操作实现 57
3.3.1栈的链式存储 57
3.3.2链栈的操作实现 58
3.4栈的典型举例 60
3.5本章小结 65
3.6习题 65
第4章 队列 67
4.1队列的逻辑结构 67
4.1.1队列的定义 67
4.1.2队列的基本操作 68
4.2队列的顺序存储与操作实现 68
4.2.1队列的顺序存储表示 68
4.2.2队列的基本运算 69
4.3循环队列的存储与操作实现 71
4.3.1循环队列的顺序存储 71
4.3.2循环队列的操作实现 72
4.4队列的链式存储与操作实现 74
4.4.1队列的链式存储 74
4.4.2链队列的操作实现 75
4.5队列的典型举例 77
4.6本章小结 84
4.7习题 85
第5章 串 86
5.1串的定义、表示和实现 86
5.1.1串的基本概念 86
5.1.2串的基本操作 87
5.2串的存储结构 89
5.2.1串的顺序存储结构 89
5.2.2串的堆存储结构 91
5.2.3串的链式存储结构 92
5.3串的模式匹配 93
5.3.1简单模式匹配算法 93
5.3.2改进的模式匹配算法 94
5.4串的典型例题 98
5.5算法设计举例 102
5.6本章小结 108
5.7习题 108
第6章 数组和广义表 110
6.1数组 110
6.1.1数组的定义 110
6.1.2数组的顺序存储结构 110
6.2特殊矩阵的压缩存储 112
6.2.1对称矩阵 112
6.2.2三角矩阵 113
6.2.3对角矩阵 114
6.3稀疏矩阵的压缩存储 115
6.3.1稀疏矩阵的定义 115
6.3.2三元组表的存储方法 116
6.3.3十字链表的存储方法 120
6.4广义表 121
6.4.1广义表的概念和基本操作 122
6.4.2广义表的存储结构 123
6.4.3广义表基本操作的实现 125
6.5本章小结 128
6.6习题 129
第7章 二叉树 132
7.1二叉树的定义、性质和基本操作 132
7.1.1二叉树的定义 132
7.1.2二叉树的基本性质 134
7.1.3二叉树的基本操作 135
7.2二叉树的存储 135
7.2.1顺序存储结构 135
7.2.2链式存储结构 136
7.3二叉树的遍历 139
7.3.1二叉树遍历的方法和结构 139
7.3.2二叉链表存储结构下二叉树遍历算法的实现 140
7.3.3非递归的二叉树遍历算法 143
7.3.4二叉树遍历的应用 145
7.4线索二叉树 149
7.4.1二叉树的线索链表 149
7.4.2以中序线索链表为存储结构的中序遍历 151
7.4.3线索链表的生成 151
7.5哈夫曼树及其应用 152
7.5.1哈夫曼树的定义 152
7.5.2哈夫曼树的构造方法 153
7.5.3最优前缀编码 154
7.5.4哈夫曼编码算法的实现 156
7.6本章小结 157
7.7习题 158
第8章 树 161
8.1树的定义与术语 161
8.2树的存储结构 162
8.2.1双亲表示法 162
8.2.2孩子表示法 163
8.2.3孩子兄弟表示法 164
8.3树、森林与二叉树的相互转换 166
8.3.1树与二叉树的相互转换 166
8.3.2森林与二叉树的相互转换 166
8.3.3树和森林的遍历 168
8.4树的典型例题 169
8.5算法设计举例 172
8.5.1设计哈夫曼编码 172
8.5.2前缀算术表达式转换 174
8.6本章小结 176
8.7习题 176
第9章 图 178
9.1图的定义 178
9.2图的基本术语 180
9.3图的基本操作 182
9.4图的存储结构 183
9.4.1邻接矩阵 183
9.4.2邻接表 186
9.5图的遍历 188
9.5.1深度优先遍历 188
9.5.2广度优先遍历 189
9.6最小生成树 191
9.6.1最小生成树的基本概念 191
9.6.2普里姆算法 192
9.6.3克鲁斯卡尔算法 194
9.7最短路径 195
9.7.1求某一个顶点到其余各顶点的最短路径 195
9.7.2求任意一对顶点之间的最短路径 198
9.8关键路径 201
9.8.1 AOV网与拓扑排序 201
9.8.2 AOE网与关键路径 204
9.9图的典型例题 210
9.10本章小结 218
9.11习题 219
第10章 查找 222
10.1查找表 222
10.2静态查找表 222
10.2.1顺序查找 223
10.2.2有序表的折半查找 224
10.2.3分块查找 227
10.3动态查找表——二叉排序树 227
10.3.1二叉排序树的查找过程 228
10.3.2二叉排序树的插入操作 229
10.3.3二叉排序树的删除操作 230
10.3.4二叉排序树的查找分析 232
10.4动态查找表——平衡二叉树 233
10.4.1左单旋转（LL型） 233
10.4.2右单旋转（RR型） 234
10.4.3先左后右双向旋转（LR型） 234
10.4.4先右后左双向旋转（RL型） 235
10.4.5二叉平衡树平衡化算法 235
10.5动态查找表——B-树和B+树 239
10.5.1 B-树的定义 239
10.5.2 B-树的查找 240
10.5.3在B-树上插入结点 242
10.5.4在B-树上删除结点 244
10.5.5 B+树 245
10.6哈希表 245
10.6.1哈希表与哈希方法 246
10.6.2常用的哈希函数 246
10.6.3处理冲突的方法 248
10.6.4哈希表的查找分析 250
10.7查找的典型例题 251
10.8算法设计举例 253
10.9本章小结 261
10.10习题 261
第11章 排序 264
11.1基本概念 264
11.2插入排序 265
11.2.1直接插入排序 265
11.2.2折半插入排序 267
11.2.3表插入排序 268
11.2.4希尔排序 271
11.3交换排序 272
11.3.1冒泡排序 272
11.3.2快速排序 274
11.4选择排序 277
11.4.1直接选择排序 277
11.4.2树形选择排序 278
11.4.3堆排序 280
11.5二路归并排序 282
11.6基数排序 284
11.6.1多关键码排序 285
11.6.2链式基数排序 286
11.7排序的典型例题 289
11.8算法设计举例 290
11.9本章小结 292
11.10习题 293
参考文献 296