第1章 数据结构概论 1
1.1问题的提出 2
1.2基本概念与术语 3
1.3数据结构的概念 5
1.4数据的逻辑结构、存储结构及运算 7
1.4.1数据的逻辑结构 7
1.4.2数据的存储结构 8
1.4.3数据的运算 9
1.4.4逻辑结构、存储结构及运算的关系 10
1.5算法与算法特性 10
1.5.1算法及其特性 10
1.5.2算法的描述方法 11
1.5.3算法与程序及数据结构 11
1.6算法性能分析及算法度量 12
1.6.1算法性能分析 12
1.6.2算法度量 12
小结 15
习题 15
拓展实验：电话号码的查询 16
第2章 线性表 17
2.1线性表的定义与运算 18
2.1.1线性表的定义 18
2.1.2线性表的抽象数据类型 18
2.2线性表的顺序存储 19
2.2.1顺序存储 19
2.2.2顺序表的运算 21
2.3线性表的链式存储 24
2.3.1线性链表及运算 24
2.3.2静态链表及运算 31
2.3.3循环链表及运算 32
2.3.4双向链表及运算 34
2.4线性表的应用 36
2.4.1约瑟夫问题 37
2.4.2一元多项式求和问题 38
2.4.3集合应用问题 41
小结 43
习题 43
拓展实验：线性表的合并 44
第3章 栈与队列 46
3.1栈 47
3.1.1栈的定义 47
3.1.2栈的顺序存储结构 48
3.1.3栈的链式存储结构 50
3.2栈的应用 52
3.2.1子程序的调用和返回问题 52
3.2.2数制转换问题 52
3.3队列 53
3.3.1队列的定义 53
3.3.2队列的顺序存储结构 54
3.3.3队列的链式存储结构 60
3.4队列的应用 64
3.4.1设备速度不匹配问题 64
3.4.2舞伴问题 65
小结 66
习题 66
拓展实验：算术表达式求值 67
第4章串 68
4.1串的基本概念 69
4.2串的存储结构 70
4.2.1串的静态存储结构 70
4.2.2串的动态存储结构 71
4.3串的基本运算 73
4.3.1串的抽象数据类型定义 73
4.3.2串的基本运算实现 74
4.4模式匹配 78
4.4.1 BF算法 78
4.4.2 KMP算法 80
4.5串的应用 84
小结 85
习题 85
拓展实验：设计简单的文本编辑器 86
第5章 数组 87
5.1数组及其基本操作 87
5.1.1数组的概念 88
5.1.2抽象数据类型数组的定义 89
5.2数组的存储结构 90
5.3数组在矩阵运算中的应用 93
5.3.1特殊矩阵的压缩存储 93
5.3.2稀疏矩阵的压缩存储 94
小结 102
习题 102
拓展实验：一元多项式的值计算 103
第6章树 104
6.1树的概念 105
6.1.1树的定义 105
6.1.2树的表示方法 106
6.1.3树的基本术语 106
6.1.4树的ADT定义 107
6.2二叉树 107
6.2.1二叉树的定义及基本结构 108
6.2.2二叉树的存储结构 109
6.2.3二叉树的遍历 112
6.3线索二叉树 115
6.3.1二叉树的线索化 115
6.3.2利用线索遍历 116
6.4树、森林、二叉树之间的关系 120
6.4.1树的存储结构 121
6.4.2森林与二叉树的转换 124
6.4.3树和森林的遍历 127
6.5哈夫曼算法及其应用 128
6.5.1哈夫曼树的定义 128
6.5.2哈夫曼二叉树的构造 129
6.5.3哈夫曼树在编码问题中的应用 131
小结 135
习题 135
拓展实验：创建二叉树 138
第7章图 139
7.1图的概念与ADT定义 140
7.1.1图的概念 140
7.1.2图的抽象数据类型定义 144
7.2图的存储结构 144
7.2.1邻接矩阵 145
7.2.2邻接表 147
7.2.3十字链表 150
7.2.4邻接多重表 152
7.3图的遍历 153
7.3.1深度优先搜索 153
7.3.2广度优先搜索 155
7.4图的应用 157
7.4.1生成树 157
7.4.2最短路径 162
7.4.3拓扑排序 166
7.4.4关键路径 170
小结 176
习题 176
拓展实验：图的深度优先搜索 179
第8章 查找 180
8.1查找的基本概念 181
8.2静态查找问题 182
8.2.1顺序查找 182
8.2.2二分查找 182
8.3线性表的查找方法 184
8.3.1线性查找 184
8.3.2折半查找 185
8.3.3分块查找 188
8.4树表的查找方法 190
8.4.1二叉查找树 190
8.4.2平衡二叉树 196
8.4.3 B-树 202
8.5哈希表的查找方法 203
8.5.1哈希表 203
8.5.2构造哈希表的基本方法 205
8.5.3解决冲突的方法 206
8.5.4哈希表的查找方法 209
8.6各种查找方法的比较 210
小结 210
习题 210
拓展实验：折半查找 212
第9章 排序 213
9.1排序的基本概念 214
9.2内部排序 216
9.2.1插入排序 216
9.2.2冒泡排序 220
9.2.3快速排序 221
9.2.4选择排序 223
9.2.5归并排序 229
9.2.6基数排序 231
9.3内部排序方法比较 234
9.4内部排序方法的选择 235
9.5外部排序简介 236
小结 236
习题 236
拓展实验：希尔排序 238
第10章 递归 239
10.1递归的定义与类型 240
10.1.1递归的定义 240
10.1.2递归的类型 240
10.2递归应用举例 240
10.2.1汉诺塔问题 240
10.2.2八皇后问题 243
10.3递归的实现 244
10.4递归到非递归的转换过程 247
10.5递归的时间和空间复杂度 250
小结 251
习题 251
拓展实验：汉诺塔问题研究 252
第11章 文件 253
11.1外存储器简介 254
11.2有关文件的概念 255
11.2.1文件及其类别 255
11.2.2文件的操作 256
11.3文件的组织 258
11.3.1顺序文件 258
11.3.2索引文件 259
11.3.3散列文件 264
11.3.4多关键字文件 265
小结 267
习题 267
拓展实验：索引文件 268
参考文献 269