第1章 绪论 1
1.1什么是数据结构 2
1.2基本概念 5
1.2.1数据的逻辑结构 6
1.2.2数据的存储结构 7
1.2.3数据的运算 8
1.3数据类型和抽象数据类型 9
1.4算法和算法分析 11
1.4.1算法的描述 11
1.4.2算法设计的要求 12
1.4.3算法分析 12
本章总结 15
习题1 15
第2章 线性表 19
2.1线性表的类型定义 20
2.1.1线性表的定义 20
2.1.2线性表的抽象数据类型 20
2.2线性表的顺序存储 23
2.2.1顺序表 23
2.2.2基本操作的实现 25
2.3线性表的链式存储 31
2.3.1线性链表 31
2.3.2单链表基本操作的实现 34
2.3.3静态链表 39
2.3.4循环链表 39
2.3.5双向链表 40
2.4线性表的应用 44
本章总结 50
习题2 50
第3章 栈与队列 54
3.1栈 55
3.1.1栈的基本概念 55
3.1.2栈的抽象数据类型 57
3.1.3栈的存储实现和运算实现 58
3.2栈的应用举例 64
3.3栈与递归的实现 71
3.3.1递归的概念 71
3.3.2递归过程和运行时栈 76
3.3.3递归算法的效率分析 78
3.3.4设计举例 79
3.4队列 83
3.4.1队列的定义及基本运算 83
3.4.2队列的存储实现及运算实现 84
3.4.3队列的应用 91
3.4.4优先级队列 93
本章总结 93
习题3 94
第4章串 96
4.1串的逻辑结构 97
4.1.1串的基本概念 97
4.1.2串的抽象数据类型 97
4.1.3串的比较 99
4.1.4常用的C+++串函数 100
4.2串的存储结构 102
4.2.1顺序存储结构 102
4.2.2链式存储结构 104
4.3串的模式匹配 106
4.3.1简单串模式匹配算法 107
4.3.2无回溯的模式匹配算法 109
4.4串的应用——文本编辑 110
本章总结 111
习题4 112
第5章 多维数组与广义表 114
5.1数组 115
5.1.1数组的基本概念 115
5.1.2数组的抽象数据类型 116
5.1.3数组的顺序存储结构和寻址公式 117
5.2矩阵的压缩存储 120
5.2.1特殊矩阵 121
5.2.2稀疏矩阵 125
5.3十字链表 136
5.3.1十字链表存储结构 136
5.3.2十字链表的实现 137
5.4广义表 143
5.4.1广义表的基本概念 143
5.4.2广义表的存储结构 146
本章总结 151
习题5 151
第6章 树与二叉树 154
6.1树 155
6.1.1树的基本概念 155
6.1.2树的抽象数据类型 156
6.2树的存储结构与遍历 158
6.2.1树的存储结构 158
6.2.2树和森林的遍历 163
6.3二叉树 164
6.3.1二叉树的基本概念 164
6.3.2二叉树的性质 167
6.4二叉树的存储结构 169
6.4.1顺序存储结构 169
6.4.2链式存储结构 170
6.5二叉树的实现 172
6.5.1二叉树的类定义 172
6.5.2基本操作的实现 174
6.6二叉树的遍历 179
6.6.1遍历二叉树的定义 179
6.6.2遍历二叉树的递归算法 180
6.6.3遍历二叉树的非递归算法 182
6.7二叉树的线索化 186
6.7.1线索二叉树的定义 186
6.7.2线索二叉树的类定义 187
6.7.3基本操作的实现 189
6.8树和森林与二叉树的转换 192
6.8.1树与二叉树的转换 192
6.8.2森林与二叉树的转换 194
6.9哈夫曼树及其应用 197
6.9.1哈夫曼树 197
6.9.2哈夫曼编码 199
本章总结 205
习题6 206
第7章图 209
7.1图的基本概念与操作 210
7.1.1图的基本概念 210
7.1.2图的抽象数据类型 213
7.2图的存储结构 215
7.2.1邻接矩阵法 215
7.2.2邻接表 218
7.2.3十字链表（有向图） 220
7.2.4邻接多重表（无向图） 222
7.3图的遍历 224
7.3.1概述 224
7.3.2深度优先搜索 225
7.3.3广度优先搜索 227
7.3.4图的（强）连通分量 228
7.4最小生成树 229
7.4.1 Prim算法 230
7.4.2 Kruskal算法 232
7.5有向无环图及其应用 234
7.5.1拓扑排序与AOV网 234
7.5.2关键路径与AOE网 237
7.6最短路径 242
7.6.1单源点到其余各顶点的最短路径 243
7.6.2所有顶点对之间的最短路径 246
本章总结 249
习题7 249
第8章 查找表 252
8.1基本概念 253
8.2静态查找表 254
8.2.1顺序表上的查找 256
8.2.2有序表上的二分查找 259
8.2.3索引顺序表上的查找 262
8.3动态查找表 264
8.3.1二叉排序树 264
8.3.2平衡二叉树 273
8.3.3 B树 276
8.3.4 B+树 281
8.4哈希表 284
8.4.1哈希表的基本概念 284
8.4.2哈希函数构造方法 286
8.4.3哈希冲突解决方法 290
8.4.4哈希表类设计 292
本章总结 297
习题8 297
第9章 排序 300
9.1基本概念 301
9.2插入排序 303
9.2.1直接插入排序 304
9.2.2希尔排序 307
9.3交换排序 309
9.3.1冒泡排序 309
9.3.2快速排序 311
9.4选择排序 314
9.4.1直接选择排序 315
9.4.2堆排序 317
9.5归并排序 322
9.6基数排序 324
9.7各种内部排序算法的比较 328
9.8外部排序简介 329
本章总结 331
习题9 331
第10章 文件 334
10.1基本概念 335
10.1.1文件及其类别 335
10.1.2文件的逻辑结构和物理结构 336
10.1.3外存储器简介 338
10.2顺序文件 338
10.3索引文件 340
10.4索引顺序文件 343
10.4.1 ISAM文件 343
10.4.2 VSAM文件 346
10.5散列文件 348
10.6多关键字文件 350
10.6.1多重表文件 350
10.6.2倒排文件 351
本章总结 352
习题10 353
参考文献 354