第1章 绪论 1
1.1数据结构的重要性 1
1.2面向对象程序设计 2
1.2.1面向对象方法 2
1.2.2 C＋＋的特征及基本概念 3
1.3基本术语 4
1.4抽象数据类型 6
1.5数据结构的概念 8
1.6数据的逻辑结构 10
1.7数据的存储结构 11
1.8数据的运算 13
1.9数据的逻辑结构、存储结构及数据的运算的关系 14
1.10算法的描述和分析 14
1.10.1算法描述 14
1.10.2算法分析 15
小结 17
习题一 17
第2章 算法基础 19
2.1算法的相关概念 19
2.1.1算法的概念 19
2.1.2算法与程序 19
2.1.3数据结构与算法 20
2.2算法分析的相关概念 20
2.2.1算法分析的概念 21
2.2.2算法的时间复杂度 22
2.2.3算法的空间复杂度 25
2.3算法分析举例 26
2.3.1多项式问题 26
2.3.2静态搜索问题 27
2.4检验一个算法分析 30
小结 31
习题二 31
第3章 面向对象程序设计与C＋＋ 35
3.1面向对象程序设计的概念 35
3.2面向对象的程序设计与C＋＋ 35
3.3变量、常量与数据类型 36
3.3.1变量 36
3.3.2常量 36
3.3.3数据类型 37
3.4控制语句 41
3.4.1表达式语句和空语句 41
3.4.2块语句 41
3.4.3选择语句 42
3.4.4循环语句 42
3.4.5转移语句 42
3.5函数 43
3.5.1函数定义 43
3.5.2函数声明 43
3.5.3函数调用 44
3.5.4参数传递 44
3.5.5函数重载 46
3.5.6构造函数和析构函数 47
3.5.7友元函数 48
3.6继承与派生 48
3.7多态性、虚函数和纯虚函数 49
3.8模板 51
3.8.1模板的概念 51
3.8.2函数模板与模板函数 52
3.8.3类模板与模板类 54
3.9输入与输出 55
小结 56
习题三 56
第4章 线性表 57
4.1线性表及其抽象数据类型说明 57
4.1.1线性表及其逻辑结构 57
4.1.2线性表的抽象数据类型描述 61
4.2线性表的顺序存储 62
4.2.1顺序存储 62
4.2.2顺序表（LinearList）类的定义 63
4.2.3顺序表（LinearList）类的实现 64
4.3线性表的链式存储 67
4.3.1线性链表的存储结构 67
4.3.2线性链表（Chain）类的定义 69
4.3.3线性链表（Chain）类的实现 70
4.3.4循环链表 74
4.3.5循环链表CircularList类的实现 75
4.3.6双向链表 76
4.3.7可利用空间表 78
4.3.8表遍历器 79
4.4线性表的顺序存储和链式存储的比较 81
4.5链式存储结构的应用 82
4.5.1约瑟夫问题 82
4.5.2一元多项式求和 83
小结 87
习题四 87
第5章 栈和队列 91
5.1栈 91
5.1.1栈的定义 91
5.1.2栈的顺序存储结构 94
5.1.3栈的链式存储结构 97
5.1.4顺序栈和链式栈的比较 99
5.2栈的应用 100
5.2.1迷宫问题 100
5.2.2表达式求值 103
5.2.3汉诺塔问题 106
5.2.4数制转换 108
5.2.5行编辑 108
5.3队列 110
5.3.1队列的定义 110
5.3.2队列的顺序存储 112
5.3.3队列的链式存储 120
5.3.4顺序队列与链式队列的比较 123
5.3.5优先队列 124
5.4队列的应用 124
5.4.1解决设备速度不匹配问题 124
5.4.2舞伴问题 125
5.4.3火车车厢重排 126
小结 128
习题五 129
第6章 串 133
6.1 C＋＋语言的字符和字符串 133
6.2串的基本概念 134
6.3串的存储结构 135
6.3.1串的顺序存储结构 136
6.3.2串的链式存储结构 137
6.3.3串的索引存储结构 138
6.4串的操作 139
6.4.1常用的C＋＋字符串函数 139
6.4.2串的抽象数据类型的描述 141
6.4.3串的类定义 142
6.4.4部分成员函数的实现 143
6.5串的基本运算与实现 146
6.5.1串插入 146
6.5.2串删除 147
6.6模式匹配 149
6.6.1模式匹配的BF算法 149
6.6.2模式匹配的KMP算法 151
6.7串在文本编辑中的应用 155
小结 156
习题六 156
第7章 数组和广义表 159
7.1 C＋＋中数组的定义及抽象数据类型表示 159
7.1.1 C＋＋中数组的定义 159
7.1.2数组的抽象数据类型表示 160
7.2数组的顺序存储结构 161
7.3矩阵的压缩存储 162
7.3.1特殊矩阵的压缩存储 163
7.3.2稀疏矩阵的压缩存储 166
7.4广义表的概念 173
7.5广义表的存储结构表示 174
7.6广义表的运算 176
小结 183
习题七 183
第8章 树 187
8.1树 187
8.1.1树的定义 187
8.1.2树的表示形式 188
8.1.3树的常用术语 189
8.1.4树的基本操作 189
8.1.5一个树的接口 190
8.1.6树的基本算法 191
8.2二叉树 193
8.2.1二叉树的定义 193
8.2.2二叉树的性质 194
8.2.3二叉树的接口 197
8.2.4二叉树的存储结构 197
8.2.5二叉树的遍历 204
8.2.6二叉树遍历的应用 207
8.3线索二叉树 208
8.3.1线索二叉树的类定义 208
8.3.2中序线索二叉树 212
8.4树、森林和二叉树的关系 215
8.4.1树的存储结构 215
8.4.2森林与二叉树的转换 218
8.4.3树和森林的遍历 220
8.5哈夫曼树及其应用 222
8.5.1哈夫曼树的定义 222
8.5.2哈夫曼树的构造 223
8.5.3哈夫曼树在编码问题中的应用 226
小结 227
习题八 228
第9章 图 231
9.1图的基本概念 231
9.1.1图的定义及基本概念 231
9.1.2图的抽象数据类型 234
9.2图的存储结构 236
9.2.1邻接矩阵表示法 236
9.2.2邻接表 242
9.2.3十字链表 249
9.2.4邻接多重表 250
9.3图的遍历 252
9.3.1深度优先搜索 252
9.3.2广度优先搜索 254
9.3.3欧拉回路 255
9.4图的连通性 257
9.4.1连通分量 257
9.4.2重连通分量 259
9.5生成树 259
9.5.1普里姆（Prim）算法 261
9.5.2克鲁斯卡尔（Kruskal）算法 264
9.6最短路径 266
9.6.1单源最短路径 266
9.6.2求每一对顶点之间的最短路径 269
9.7拓扑排序 270
9.8关键路径 274
小结 280
习题九 280
第10章 查找 285
10.1基本概念 285
10.2线性表的查找 286
10.2.1顺序查找 286
10.2.2折半查找 288
10.2.3索引查找 290
10.2.4分块查找 294
10.3树表查找 296
10.3.1二叉查找树 296
10.3.2平衡二叉树 303
10.3.3 B—树 307
10.4哈希表的查找 309
10.4.1哈希表 309
10.4.2构造哈希表的基本方法 311
10.4.3解决冲突的方法 313
10.4.4哈希表的查找方法 315
10.5各种查找方法的比较 316
小结 317
习题十 318
第11章 排序 321
11.1基本概念 321
11.2内部排序 324
11.2.1插入排序 324
11.2.2交换排序 329
11.2.3选择排序 333
11.2.4归并排序 341
11.2.5基数排序 345
11.3内部排序方法比较 349
11.4外部排序简介 350
小结 351
习题十一 351
第12章 递归 355
12.1递归的定义 355
12.2常见递归问题 356
12.2.1汉诺塔问题 356
12.2.2八皇后问题 358
12.2.3表达式树 360
12.3递归的实现 362
12.4消除递归 365
12.4.1尾递归和单向递归的消除 365
12.4.2用栈模拟系统运行时的栈 367
12.5递归的评估 370
小结 371
习题十二 371
第13章 文件 375
13.1外存储器的介绍 375
13.2磁盘 376
13.3有关文件的概念 377
13.3.1文件及其类别 378
13.3.2文件的操作 379
13.4文件的组织 380
13.4.1顺序文件 381
13.4.2索引文件 382
13.4.3散列文件 388
13.4.4多关键字文件 389
13.5外部排序 391
13.5.1外部排序的简单方法 392
13.5.2两路归并 392
13.5.3多路归并 395
13.6文件的索引结构 396
13.6.1索引向量 396
13.6.2树形索引结构 397
小结 397
习题十三 397
参考文献 399