第1章 绪论 1
1.1数据结构的研究与发展 1
1.1.1国外的研究与发展 1
1.1.2国内的研究与发展 1
1.1.3数据结构在计算机专业中的地位 2
1.2什么是数据结构 3
1.3数据结构的基础知识 7
1.4数据类型与抽象数据类型 11
1.5算法和算法的量度 14
1.5.1算法简述 14
1.5.2算法的特征 14
1.5.3算法对应的程序设计模式 15
1.5.4时间复杂度 21
1.5.5空间复杂度 24
1.6数据结构的选择与评价 25
第2章 线性表 27
2.1线性表的基本概念 27
2.1.1线性表的定义 27
2.1.2线性表的抽象数据类型定义 27
2.1.3线性表的存储结构 29
2.1.4线性表的抽象数据类型定义的应用 30
2.2线性表的顺序存储结构 33
2.2.1线性表的顺序存储结构定义 33
2.2.2线性表的顺序存储结构的基本操作 33
2.3线性表的链式存储结构 39
2.3.1线性表的链式存储结构定义 39
2.3.2线性表的链式存储结构的基本操作 40
2.3.3循环链表与双向链式存储结构及操作 48
2.4顺序表与链表的比较 52
2.5线性表的应用例子 54
2.5.1一元多项式的线性表的顺序存储结构及运算 54
2.5.2一元多项式的线性表的链式存储结构 54
第3章 栈和队列 61
3.1栈的基本概念 61
3.1.1栈的定义 61
3.1.2栈的抽象数据类型定义 62
3.1.3栈的表示和实现 62
3.2栈的应用 68
3.2.1数制转换 68
3.2.2括号匹配 70
3.2.3运用栈实现行编辑程序 72
3.2.4迷宫求解 74
3.2.5表达式求值 81
3.3栈与递归 88
3.3.1递归的概念 88
3.3.2递归过程的内部实现 90
3.3.3递归消除 91
3.3.4阅读一个递归程序 95
3.4队列的基本概念 106
3.4.1队列的定义 106
3.4.2队列的抽象数据类型定义 107
3.4.3队列的表示和实现 108
3.5队列的应用——离散事件模拟的例子 115
第4章 串 123
4.1串的基本概念 123
4.1.1串的定义 123
4.1.2串的抽象数据类型定义 124
4.1.3C语言函数库中的串处理函数 127
4.2串的存储结构及算法 128
4.2.1串的静态存储结构及算法 128
4.2.2串的动态存储结构及算法 132
4.3串的模式匹配算法 137
4.3.1模式匹配的朴素算法 137
4.3.2模式匹配的首尾匹配算法 139
4.3.3KMP算法 141
4.4文本编辑的应用 147
4.4.1文本编辑举例 147
4.4.2高级语言程序设计的编译方法 148
第5章 数组和广义表 152
5.1数组的基本概念 152
5.1.1数组的定义 152
5.1.2数组的抽象数据类型定义 153
5.1.3数组的表示和实现 153
5.2数组的应用——矩阵的压缩存储 158
5.2.1特殊矩阵 158
5.2.2稀疏矩阵 160
5.3广义表的基本概念 177
5.3.1广义表的定义 177
5.3.2广义表的抽象数据类型定义 179
5.3.3广义表的表示和实现 180
第6章 树和二叉树 185
6.1树的基本概念 185
6.1.1树的定义 185
6.1.2树的抽象数据类型定义 187
6.2二叉树的基本概念 188
6.2.1二叉树的定义 188
6.2.2二叉树的抽象数据类型定义 189
6.2.3二叉树的性质 191
6.2.4二叉树的存储结构 193
6.3遍历二叉树 196
6.3.1问题的提出 196
6.3.2二叉树遍历算法 197
6.3.3二叉树遍历递归算法的应用 202
6.4线索二叉树 205
6.4.1问题的提出 205
6.4.2线索二叉树的存储结构 205
6.4.3二叉树的中序线索化 207
6.5树和森林 224
6.5.1树、森林与二叉树的相互转换 224
6.5.2树与森林的存储 226
6.5.3树和森林的遍历 229
6.6哈夫曼树及其应用 230
6.6.1最优二叉树（哈夫曼树） 230
6.6.2哈夫曼编码 233
6.6.3哈夫曼树与判定树 240
第7章 图 242
7.1图的基本概念 242
7.1.1图的定义 242
7.1.2图的抽象数据类型定义 247
7.1.3图的存储结构 248
7.2图的遍历 253
7.2.1深度优先搜索 254
7.2.2广度优先搜索 266
7.3生成树与最小生成树 271
7.3.1Prim算法 273
7.3.2Kruskal算法 276
7.3.3生成树与图的遍历 278
7.4两点之间的最短路径 279
7.4.1从某个源点到其余各顶点的最短路径 280
7.4.2每一对顶点之间的最短路径 285
7.5拓扑排序 287
7.5.1拓扑排序的定义 287
7.5.2关键路径 295
第8章 查找 306
8.1查找的基本概念 306
8.2静态查找表 307
8.2.1无序顺序表查找——顺序查找 307
8.2.2有序顺序表的查找——折半查找 310
8.2.3索引顺序表查找——分块查找 313
8.3动态查找表 315
8.3.1二叉排序树 315
8.3.2平衡二叉树 321
8.4哈希表 329
8.4.1什么是哈希表 329
8.4.2哈希函数的构造方法 330
8.4.3处理冲突的方法 332
8.4.4哈希表的查找 337
8.4.5哈希表实现的比较 338
第9章 内部排序 340
9.1排序的基本概念 340
9.2插入排序 341
9.2.1直接插入排序 341
9.2.2折半插入排序 344
9.2.3表插入排序 345
9.2.4希尔排序 347
9.3交换排序 350
9.3.1起泡排序 350
9.3.2快速排序 351
9.4选择排序 354
9.4.1简单选择排序 354
9.4.2堆排序 356
9.5归并排序 360
9.6分配排序 363
9.6.1多关键字排序 363
9.6.2基数排序 364
9.7各种内部排序方法的比较 368
参考文献 370