第1章 绪论 1
1.1数据结构讨论的范畴 2
1.2数据结构的基本概念 2
1.2.1基本术语 2
1.2.2数据结构 4
1.2.3数据类型和抽象数据类型 6
1.3算法及其描述和分析 9
1.3.1算法的特性及其设计原则 9
1.3.2算法的描述 10
1.3.3算法分析 11
思考题与习题 15
第2章 线性表 17
2.1线性表的定义和基本运算 18
2.2线性表的顺序存储结构 20
2.2.1顺序存储结构 20
2.2.2顺序表的基本操作及其时间效率分析 22
2.3线性表的链式存储结构 24
2.3.1单链表及其基本操作 24
2.3.2特殊链表 32
2.4线性表的应用示例——多项式的代数运算 36
思考题与习题 38
第3章 栈和队列 41
3.1栈 42
3.1.1栈的定义及其运算 42
3.1.2顺序栈 43
3.1.3多栈共享邻接空间 46
3.1.4链栈 47
3.1.5栈的应用举例 49
3.2队列（queue） 58
3.2.1队列的定义及其运算 59
3.2.2队列的顺序存储结构 60
3.2.3队列的链式存储结构 62
3.2.4循环队列 64
3.2.5队列的应用举例 66
思考题与习题 70
第4章 字符串 73
4.1串的概念 74
4.1.1串的定义 74
4.1.2主串和子串 75
4.2串的存储结构 76
4.2.1串的静态存储结构 76
4.2.2串的动态存储结构 77
4.3求子串运算 78
4.4串的模式匹配 80
4.4.1串的模式匹配的简单算法 80
4.4.2模式匹配的改进算法—KMP算法 82
思考题与习题 85
第5章 数组与特殊矩阵 87
5.1数组的概念 88
5.2静态数组与动态数组 90
5.3特殊矩阵及其压缩存储 93
5.3.1特殊矩阵 93
5.3.2特殊矩阵的压缩存储 94
5.4稀疏矩阵 97
5.4.1三元组顺序表 98
5.4.2行逻辑链接的顺序表 100
5.4.3十字链表 101
思考题与习题 102
第6章树 105
6.1基本概念 106
6.1.1树的定义和有关术语 106
6.1.2二叉树 108
6.2二叉树的存储 110
6.2.1顺序存储结构 110
6.2.2链式存储结构 112
6.3二叉树的抽象数据类型 112
6.4二叉树的遍历 115
6.4.1二叉树的遍历方法 115
6.4.2二叉树的遍历算法 118
6.4.3树、森林和二叉树的转换 122
6.5二叉树的构造 124
6.5.1用中序序列和先序序列构造二叉树 124
6.5.2用扩充先序序列构造二叉树 126
6.6线索二叉树 127
6.6.1线索二叉树的定义及结构 127
6.6.2线索二叉树的操作 128
6.7树的存储结构 131
6.8树和森林的遍历 135
6.8.1树的遍历 135
6.8.2森林的遍历 135
6.9哈夫曼树 136
6.9.1哈夫曼树算法 136
6.9.2哈夫曼树在编码问题中的应用 139
思考题与习题 143
第7章 图 147
7.1基本概念 148
7.1.1图的定义 148
7.1.2有关术语 148
7.2图的存储方法 151
7.2.1邻接矩阵及其顺序存储 151
7.2.2邻接表 154
7.2.3十字链表 157
7.2.4邻接多重表 160
7.3图的遍历 162
7.3.1深度优先搜索 162
7.3.2广度优先搜索 167
7.4最小生成树 169
7.4.1最小生成树的基本概念 169
7.4.2构造最小生成树的普里姆（Prim）方法 169
7.4.3构造最小生成树的克鲁斯卡尔（Kruskal）算法 173
7.5最短路径 176
7.5.1单源点最短路径 176
7.5.2每一对顶点之间的最短路径 179
7.6有向无环图及其应用 181
7.6.1 AOV网与拓扑排序 181
7.6.2 AOE网与关键路径 191
思考题与习题 198
第8章 查找 203
8.1基本概念与术语 204
8.2线性表的查找 205
8.2.1顺序查找 205
8.2.2顺序表的折半查找 206
8.2.3分块查找 209
8.3查找树 210
8.3.1二叉查找树 210
8.3.2平衡二叉树（AVL树） 218
8.3.3 B-树和B＋树 226
8.4哈希表查找（杂凑法） 234
8.4.1哈希表与哈希方法 234
8.4.2哈希函数的构造方法 235
8.4.3处理冲突方法 237
8.4.4哈希表中查找和插入算法的实现 241
8.4.5哈希表的查找算法分析 242
思考题与习题 243
第9章 排序 247
9.1基本概念 248
9.2插入排序 248
9.2.1直接插入排序 248
9.2.2二分法插入排序 250
9.2.3表插入排序 251
9.2.4希尔排序（Shell′s Sort） 253
9.3交换排序 254
9.3.1冒泡排序（Bubble Sort） 254
9.3.2快速排序 256
9.4选择排序 258
9.4.1简单选择排序 258
9.4.2树形选择排序 259
9.4.3堆排序（Heap Sort） 260
9.5二路归并排序 264
9.6基数排序 264
9.6.1多关键字排序 265
9.6.2链式基数排序 265
思考题与习题 268
参考文献 270