第1章 绪论 1
1…1数据结构的产生和发展 1
1…2什么是数据结构 2
1…3基本术语 3
1…4算法和算法的分析 5
算法 5
算法的描述 5
算法分析 6
本章小结 10
习题一 10
第2章 线性表 12
2…1线性表及其基本运算操作 12
2…2线性表的顺序存储结构——顺序表 13
顺序表 13
顺序表的存储定义和基本运算 14
2…3线性表的链式存储结构——单链表 21
单链表 21
静态单链表 26
单向循环链表 31
2…4线性表的链式存储结构——双向链表 34
双向链表 34
双向链表的基本运算及其实现 35
2…5单链表的应用实例 38
多项式相加 38
集合的运算 42
本章小结 44
习题二 44
第3章 栈和队列 49
3…1栈及其运算 49
3…2栈的顺序存储结构 51
顺序栈及其运算 51
两个栈共享存储空间 54
3…3栈的链式存储结构 56
3…4栈的应用举例 57
算术表达式求值 57
数制的转换问题 59
括号匹配的检测 60
栈与递归 61
3…5队列 65
队列及其运算 65
队列的链式存储结构及其运算 66
队列的顺序存储结构及其运算 69
其他队列 73
3…6队列的应用 74
本章小结 78
习题三 78
第4章 数组及其应用 82
4…1数组及其顺序存储结构 82
数组 82
数组的顺序存储结构 83
4…2矩阵的压缩存储 85
特殊矩阵的压缩存储 85
稀疏矩阵的压缩存储 87
本章小结 93
习题四 93
第5章 字符串 95
5…1串和串的主要运算 95
串的基本概念 95
串的主要运算及其函数 96
5…2串的存储结构及其基本运算的实现 98
串的定长顺序存储表示 98
串的堆分配存储表示 100
串的块链存储表示 103
5…3串的模式匹配及其算法 105
5…4串的应用实例——文本编辑 109
本章小结 110
习题五 111
第6章 树与二叉树 114
6…1树 114
树的基本概念 114
树的存储表示 116
6…2二叉树 119
二叉树的定义及运算 119
二叉树的性质 120
二叉树的存储表示 123
6…3二叉树的遍历 126
二叉树的先（根）序遍历 127
二叉树的中（根）序遍历 129
二叉树的后（根）序遍历 130
层次序遍历 132
二叉树遍历算法的应用 133
6…4线索二叉树 136
线索化二叉树 137
线索二叉树的遍历 141
6…5树、森林与二叉树的转换及遍历 143
树与二叉树的转换 144
森林与二叉树的转换 145
树、森林的遍历 147
6…6哈夫曼树及其应用 147
哈夫曼树 148
哈夫曼算法 148
哈夫曼编码 151
本章小结 156
习题六 157
第7章 图 159
7…1图的基本概念 159
图的定义及运算 159
图的基本术语 160
7…2图的存储表示 162
邻接矩阵表示法 162
邻接表表示法 164
图的其他存储表示法 166
图的存储结构的建立 168
7…3图的遍历 171
深度优先遍历 172
广度优先遍历 175
求图的连通分量 177
7…4图的生成树和最小生成树 177
无向连通图的生成树 177
网络的最小生成树 178
7…5有向无环图及其应用 183
AOV网及其拓扑排序 183
AOE网及其关键路径 187
7…6最短路径问题 192
单源最短路径问题 192
每对顶点间的最短路径问题 195
本章小结 198
习题七 199
第8章 查找 201
8…1查找的基本概念 201
8…2线性顺序表的静态查找 202
顺序查找 202
线性顺序表的二分查找 203
分块查找 206
8…3二叉排序树的动态查找 207
二叉排序树 208
平衡二叉树 213
8…4B-树和B±树 219
B-树及其查找 219
B-树的插入和删除 220
B±树 222
8…5哈希表及其查找 223
概述 223
哈希函数的构造方法 224
处理冲突的方法 226
哈希表的查找 227
本章小结 229
习题八 230
第9章 排序 232
9…1排序的基本概念 232
9…2简单排序 233
直接插入排序 233
冒泡排序 234
9…3堆排序 235
9…4归并排序 240
9…5基数排序 242
9…6快速排序 244
9…7各种内部排序的比较 246
9…8外部排序 247
2-路归并 247
多路替代选择归并排序 249
最佳归并排序 250
本章小结 251
习题九 251
第10章 文件 253
10…1文件的概念 253
10…2顺序文件 255
10…3索引文件 258
10…4ISAM文件 260
10…5VSAM文件 262
10…6直接存取文件 264
10…7多关键字文件 265
多重表文件 265
倒排文件 266
本章小结 267
习题十 267
第11章 实验 271
实验一线性表和数组的应用 271
实验二链表的应用与操作 271
实验三数组和栈的应用 272
实验四字符串的存储和运算 273
实验五二叉排序树的建立与遍历 274
实验六哈夫曼编／译码器的设计 274
实验七图的存储操作与应用 275
实验八构造Hash表 276
实验九排序的应用 277
实验十多关键字排序的应用 277
附件 实验报告书写规范 278
附录 习题参考答案 280
参考文献 331