第1章 绪论 1
1.1数据结构的概念 1
1.1.1引言 1
1.1.2数据结构的发展及其在计算机科学中所处的地位 2
1.1.3什么是数据结构 3
1.1.4有关概念和术语 3
1.2数据类型和抽象数据类型 6
1.2.1数据类型 6
1.2.2抽象数据类型 6
1.3算法和算法分析 6
1.3.1算法特性 7
1.3.2算法描述 7
1.3.3算法性能分析与度量 8
第2章 线性表 11
2.1线性表的类型定义 11
2.2线性表的顺序存储结构及实现 13
2.2.1线性表的顺序存储 13
2.2.2顺序表的实现 14
2.3线性表的链式存储结构及实现 18
2.3.1线性表的链式存储 18
2.3.2单链表的实现 18
2.3.3其他形式的链表 25
2.4线性表的其他存储方法 27
2.4.1顺序存储与链式存储的比较 27
2.4.2静态链表 28
2.4.3间接寻址 29
2.5线性表应用举例 29
第3章 特殊线性表 35
3.1栈 35
3.1.1栈的逻辑结构 35
3.1.2栈的顺序存储结构及实现 37
3.1.3栈的链式存储及实现 40
3.1.4顺序栈和链栈的比较 42
3.1.5栈的应用举例 42
3.2队列 48
3.2.1队列的逻辑结构 49
3.2.2队列的顺序存储结构及实现 50
3.2.3队列的链式存储及实现 54
3.2.4队列的应用 57
第4章 串及其模式匹配 59
4.1串的定义 59
4.1.1串的相关概念 59
4.1.2串的抽象数据类型定义 60
4.2串的存储结构 61
4.2.1串的顺序存储结构 62
4.2.2串的链式存储结构 62
4.2.3串的索引存储结构 63
4.2.4串的堆存储 64
4.3顺序串的实现 64
4.3.1常用C+＋字符串函数 64
4.3.2串类 65
4.4串操作举例 71
4.5模式匹配 72
第5章 广义线性表 79
5.1数组 79
5.1.1数组的定义 79
5.1.2数组的顺序存储 81
5.2矩阵的压缩存储 83
5.2.1特殊矩阵的压缩存储 83
5.2.2稀疏矩阵的压缩存储 85
5.2.3稀疏矩阵的运算 87
5.3广义表 97
5.3.1广义表的逻辑结构 97
5.3.2广义表的存储 100
5.3.3广义表的实现 102
第6章 树和二叉树 107
6.1树的定义和基本术语 107
6.2二叉树 109
6.2.1二叉树的基本概念 109
6.2.2二叉树的主要性质 114
6.3二叉树的存储结构与实现 116
6.3.1二叉树的存储 116
6.3.2二叉树的基本操作及实现 118
6.4二叉树的遍历 126
6.4.1二叉树的遍历方法及递归实现 126
6.4.2二叉树遍历的非递归实现 131
6.4.3由遍历序列恢复二叉树 134
6.4.4不用栈的二叉树遍历的非递归方法 136
6.5线索二叉树 137
6.5.1线索二叉树及其结构 137
6.5.2线索二叉树的基本操作实现 138
6.6二叉树的应用 143
6.6.1二叉树遍历的应用 143
6.6.2最优二叉树——哈夫曼树 145
6.7树 151
6.7.1树的基本操作 151
6.7.2树的存储结构 153
6.8树、森林与二叉树的转换 157
6.8.1树转换为二叉树 157
6.8.2森林转换为二叉树 158
6.8.3二叉树转换为树和森林 159
6.9树和森林的遍历 159
6.9.1树的遍历 159
6.9.2森林的遍历 160
6.10树的应用 160
6.10.1判定树 161
6.10.2集合的表示 162
6.10.3求关系等价类问题 164
第7章 图 167
7.1图的基本概念 167
7.2图的存储结构及实现 172
7.2.1邻接矩阵 172
7.2.2邻接表 174
7.2.3十字链表 178
7.2.4邻接多重表 181
7.3图的遍历 182
7.3.1深度优先搜索 183
7.3.2广度优先搜索 185
7.4图的连通性 186
7.4.1无向图的连通性 186
7.4.2有向图的连通性 187
7.4.3生成树和生成森林 187
7.4.4关节点和重连通分量 190
7.5最小生成树 193
7.5.1最小生成树的基本概念 193
7.5.2构造最小生成树的Prim算法 194
7.5.3构造最小生成树的Kruskal算法 196
7.6最短路径 199
7.6.1从一个源点到其他各点的最短路径 199
7.6.2每一对顶点之间的最短路径 202
7.7有向无环图及其应用 204
7.7.1有向无环图的概念 204
7.7.2 AOV网与拓扑排序 205
7.7.3 AOE图与关键路径 210
第8章 查找 217
8.1基本概念与术语 217
8.2静态查找表 219
8.2.1静态查找表结构 219
8.2.2顺序查找 220
8.2.3有序表的折半查找 222
8.2.4有序表的其他查找方法 225
8.2.5分块查找 226
8.3动态查找表 227
8.3.1二叉排序树 227
8.3.2平衡二叉树（AVL树） 234
8.3.3 B-树和B+树 240
8.4哈希表查找（杂凑法、散列法） 245
8.4.1哈希表与哈希方法 245
8.4.2常用的哈希函数 246
8.4.3处理冲突的方法 248
8.4.4哈希表的查找分析 250
第9章 排序 257
9.1基本概念 257
9.2插入排序 258
9.2.1直接插入排序 258
9.2.2折半插入排序 260
9.2.3表插入排序 261
9.2.4希尔排序 264
9.3交换排序 266
9.3.1冒泡排序 267
9.3.2快速排序 268
9.4选择排序 271
9.4.1简单选择排序 272
9.4.2树形选择排序 273
9.4.3堆排序 276
9.5归并排序 279
9.6基数排序 281
9.6.1多关键字排序 281
9.6.2链式基数排序 282
9.7各种内部排序方法的比较 286
参考文献 288