第1章 绪论 1
1.1什么是数据结构 1
1.2基本术语 4
1.3算法和算法分析 6
1.3.1算法 7
1.3.2算法设计的要求 7
1.3.3算法效率的度量 7
小结 9
习题 9
第2章 线性表 11
2.1线性表的定义和基本操作 11
2.1.1线性表的定义 11
2.1.2线性表的抽象数据类型 12
2.2线性表的顺序存储结构 12
2.2.1顺序表的结构 13
2.2.2顺序表基本操作的实现 14
2.2.3顺序表的一个简单应用 19
2.3线性表的链式存储结构 22
2.3.1线性链表 23
2.3.2线性链表的一个应用实例 29
2.3.3循环链表和双向链表 34
2.3.4循环链表的一个应用实例 37
小结 40
习题 41
第3章 栈和队列 45
3.1栈 45
3.1.1栈的定义 45
3.1.2栈的抽象数据类型 45
3.1.3栈的表示和实现 46
3.2栈的应用举例 51
3.2.1数制转换 51
3.2.2括号匹配检测 53
3.2.3表达式求值 54
3.2.4迷宫求解 60
3.3栈与递归 66
3.3.1函数的嵌套调用 66
3.3.2递归调用 66
3.4队列 71
3.4.1队列的定义 71
3.4.2队列的抽象数据类型 71
3.4.3链队列——队列的链式表示和实现 72
3.4.4循环队列——队列的顺序表示和实现 75
3.4.5一个队列的应用实例 78
小结 83
习题 83
第4章 串及模式匹配 86
4.1串类型的定义 86
4.2串的存储结构及其运算 87
4.2.1串的定长顺序存储 87
4.2.2堆的分配存储结构 89
4.2.3串的块链存储结构 91
4.3串的模式匹配 91
4.3.1简单的模式匹配算法 92
4.3.2改进后的模式匹配算法 94
4.4串操作应用举例 100
小结 107
习题 107
第5章 数组和广义表 108
5.1数组的定义和运算 108
5.2数组的顺序存储结构 109
5.3矩阵的压缩存储 110
5.3.1特殊矩阵 110
5.3.2稀疏矩阵 114
5.4广义表 118
5.4.1广义表的定义 118
5.4.2广义表的运算 119
5.5广义表的存储结构 119
小结 121
习题 121
第6章 树与二叉树 122
6.1树的基本概念 122
6.2二叉树 124
6.2.1二叉树的定义 124
6.2.2二叉树的性质 125
6.2.3二叉树的存储结构 126
6.3遍历二叉树和线索二叉树 129
6.3.1二叉树的遍历方法与算法实现 129
6.3.2二叉树的非递归算法实现 131
6.3.3由遍历序列恢复二叉树 135
6.3.4线索二叉树 137
6.4树和森林 138
6.4.1树的存储表示 138
6.4.2森林与二叉树的转换 140
6.4.3树和森林的遍历 142
6.5哈夫曼树及其应用 144
6.5.1最优二叉树 144
6.5.2哈夫曼编码 146
6.6回溯法与树的遍历 149
小结 150
习题 150
第7章图 152
7.1图的基本概念 152
7.2图的存储结构及基本操作 155
7.2.1邻接矩阵 155
7.2.2邻接表 158
7.2.3有向图的十字链表 162
7.2.4邻接多重表 166
7.3图的遍历 167
7.3.1深度优先搜索（Depth_First Search） 168
7.3.2广度优先搜索（Breadth_ First Search） 170
7.4图的连通性问题 174
7.4.1无向图的连通性 174
7.4.2有向图的连通性 174
7.4.3生成树和生成森林 175
7.5有向无环图及其应用 185
7.5.1拓扑排序 186
7.5.2关键路径 192
7.6最短路径 195
7.6.1从一个源点到其余各顶点的最短路径 195
7.6.2每一对顶点间的最短路径 197
小结 199
习题 199
第8章 查找 200
8.1基本概念 200
8.2静态查找表 201
8.2.1顺序查找 201
8.2.2有序表的查找 203
8.2.3索引顺序表的查找 207
8.3动态查找表 210
8.3.1二叉排序树 210
8.3.2平衡二叉树 221
8.3.3 B-树和B+树 230
8.4哈希表 236
8.4.1哈希表和哈希查找 237
8.4.2常用的哈希函数 238
8.4.3处理冲突的方法 241
8.4.4哈希表的查找及其分析 244
小结 245
习题 245
第9章 内部排序 247
9.1排序的基本概念 247
9.2插入排序 248
9.2.1直接插入排序 248
9.2.2希尔排序 251
9.3交换排序 253
9.3.1冒泡排序 253
9.3.2快速排序 255
9.4选择排序 259
9.4.1简单选择排序 259
9.4.2堆排序 261
9.5归并排序 265
9.6基数排序 267
9.6.1多关键字排序的算法思想 267
9.6.2链式基数排序 268
9.7各种内部排序算法的比较 270
9.7.1选择排序算法的依据 270
9.7.2选择排序算法的结论 270
小结 271
习题 271