第1章 引言 1
1.1数据结构 1
数据结构的概念 1
数据结构的分类 3
1.2抽象数据类型 4
1.3结构化程序设计 8
逐步求精 9
分而治之 11
1.4算法及其描述 12
算法 12
算法的C语言描述 12
1.5算法的时间复杂度和空间复杂度 14
本章小结 16
习题1 17
第2章 线性表 18
2.1线性表的定义 18
2.2线性表的顺序存储结构 19
顺序表 20
顺序表的应用举例 22
2.3线性表的链式存储结构 24
单链表 24
循环链表 29
双向链表 29
链表的应用举例 31
2.4线性表的顺序和链式存储结构的比较 33
2.5线性表的应用 34
本章小结 36
习题2 36
第3章 栈和队列 38
3.1栈 38
3.2栈的实现与应用 39
栈的顺序存储结构 39
栈的链式存储结构 43
迷宫问题 45
3.3栈与递归 48
3.4队列 54
3.5队列的实现与应用 55
队列的顺序存储结构 55
循环队列的顺序存储结构 57
队列的链式存储结构 59
超市结账队列 61
本章小结 65
习题3 66
第4章 串、数组和广义表 68
4.1串 68
串的基本概念 68
串的运算 69
串的顺序存储结构 69
串的链式存储结构 72
串的匹配算法 7
4.2数组 79
数组的基本概念 80
一维数组的存储结构 81
二维数组的存储结构 81
稀疏矩阵的压缩存储 82
4.3广义表 94
广义表的逻辑结构 94
广义表的物理结构 95
广义表的递归算法 97
本章小结 100
习题4 101
第5章 树 102
5.1树 102
树的定义 102
树的相关术语和表达形式 103
树的存储结构 105
5.2二叉树 109
二叉树的定义和相关术语 109
二叉树的主要性质 110
二叉树的存储结构 111
二叉树的基本操作及实现 113
5.3遍历二叉树 114
遍历二叉树的递归算法 114
二叉树遍历的非递归算法 116
遍历二叉树算法的应用 119
由遍历序列构造二叉树 121
5.4线索二叉树 122
线索二叉树的基本概念 122
线索二叉树的有关算法 124
5.5树、森林与二叉树的转换 126
树转换为二叉树 126
森林转换为二叉树 127
二叉树转换为树和森林 128
树和森林的遍历 129
5.6哈夫曼树 130
哈夫曼树的基本概念 130
哈夫曼树的应用 133
本章小结 135
习题5 136
第6章 图 138
6.1基本术语 138
图 138
子图和完全图 139
回路和连通图 140
树和网络 142
6.2图的存储 143
邻接矩阵 143
邻接表 144
6.3图的遍历和连通分量 146
深度优先搜索 147
宽度优先搜索 148
图的连通分量 150
图的割顶和块 151
6.4最小生成树 153
什么是最小生成树 153
无向图的最小生成树 154
有向图的最小树形图 157
6.5最短路径 161
单源最短路径问题 162
顶点间的最短路径问题 164
服务点设置问题——求图的中心 166
6.6拓扑排序和最长路径 168
拓扑排序 168
关键路径 171
本章小结 176
习题6 176
第7章 查找 179
7.1查找方法概述 179
7.2无序表的顺序查找 181
7.3有序表的查找 183
折半查找 183
分块索引查找 186
7.4二叉搜索树 189
7.5平衡二叉树 194
7.6 B-树和B+树 201
B-树 201
B+树 209
7.7哈希查找技术 210
哈希函数的构造方法 211
哈希表的冲突处理方法 215
哈希表的实现 218
本章小结 223
习题7 224
第8章 内部排序 226
8.1概述 226
8.2插入排序 227
直接插入排序 227
折半插入排序 229
表插入排序 230
希尔排序 232
8.3交换排序 233
冒泡排序 233
快速排序 235
8.4选择排序 237
简单选择排序(Simple Selection Sort) 237
树形选择排序 238
堆排序 239
8.5归并排序 242
8.6基数排序法 244
多关键字排序 244
链式基数排序 245
8.7各种内部排序法的比较 248
8.8排序操作应用举例 249
本章小结 251
习题8 252
第9章 文件及外部排序 254
9.1文件的基本概念 254
顺序文件 255
索引文件 257
ISAM文件及VSAM文件 259
9.2外部排序算法 262
多路平衡归并算法 263
初始归并段的产生算法 266
并行操作的缓冲区处理 268
最佳归并树 269
本章小结 270
习题9 271