第1章 绪论 1
1.1什么是数据结构 1
1.1.1数据结构的定义 1
1.1.2数据的逻辑结构 2
1.1.3数据的存储结构 5
1.1.4数据的运算 8
1.1.5数据结构和数据类型 9
1.2算法及其描述 11
1.2.1什么是算法 11
1.2.2算法描述 12
1.3算法分析 31
1.3.1算法设计的目标 31
1.3.2算法的时间效率分析 31
1.3.3算法的存储空间分析 34
1.4数据结构的目标 35
本章小结 39
练习题1 39
第2章 线性表 42
2.1线性表的定义 42
2.1.1什么是线性表 42
2.1.2线性表的抽象数据类型描述 43
2.2线性表的顺序存储结构 43
2.2.1线性表的顺序存储结构——顺序表 43
2.2.2顺序表基本运算的实现 44
2.3线性表的链式存储结构 50
2.3.1线性表的链式存储结构——链表 50
2.3.2单链表 51
2.3.3双链表 62
2.3.4循环链表 69
2.4线性表的应用 75
2.4.1求解两个多项式相加问题 75
2.4.2采用顺序存储结构求解 76
2.4.3采用链式存储结构求解 79
本章小结 83
练习题2 83
第3章 栈和队列 88
3.1栈 88
3.1.1栈的定义 88
3.1.2栈的顺序存储结构及其基本运算的实现 90
3.1.3栈的链式存储结构及其基本运算的实现 95
3.1.4栈的应用示例 98
3.2队列 109
3.2.1队列的定义 109
3.2.2队列的顺序存储结构及其基本运算的实现 110
3.2.3队列的链式存储结构及其基本运算的实现 117
3.2.4队列的应用示例 122
本章小结 126
练习题3 126
第4章 串 129
4.1串的基本概念 129
4.1.1什么是串 129
4.1.2串的抽象数据类型 130
4.2串的存储结构 131
4.2.1串的顺序存储结构——顺序串 131
4.2.2串的链式存储结构——链串 136
4.3串的模式匹配 144
4.3.1 Brute-Force算法 145
4.3.2 KMP算法 147
本章小结 153
练习题4 153
第5章 数组和广义表 155
5.1数组 155
5.1.1数组的基本概念 155
5.1.2数组的存储结构 156
5.1.3特殊矩阵的压缩存储 158
5.2稀疏矩阵 160
5.2.1稀疏矩阵的三元组表示 160
5.2.2稀疏矩阵的十字链表表示 164
5.3递归 166
5.3.1递归的定义 166
5.3.2何时使用递归 167
5.3.3递归模型 168
5.3.4递归算法的设计步骤 169
5.3.5递归算法转换为非递归算法 172
5.4广义表 173
5.4.1广义表的定义 173
5.4.2广义表的存储结构 175
5.4.3广义表的运算 178
本章小结 183
练习题5 184
第6章 树和二叉树 186
6.1树 186
6.1.1树的定义 186
6.1.2树的逻辑结构表示方法 187
6.1.3树的基本术语 188
6.1.4树的性质 189
6.1.5树的基本运算 190
6.1.6树的存储结构 191
6.2二叉树 193
6.2.1二叉树的概念 193
6.2.2二叉树的性质 194
6.2.3二叉树的存储结构 196
6.2.4二叉树的递归算法设计 198
6.2.5二叉树的基本运算及实现 199
6.2.6二叉树的遍历 203
6.2.7二叉树的构造 221
6.3线索二叉树 226
6.3.1线索二叉树的定义 226
6.3.2线索化二叉树 228
6.3.3遍历线索化二叉树 230
6.4哈夫曼树 231
6.4.1哈夫曼树的定义 231
6.4.2哈夫曼树的构造算法 232
6.4.3哈夫曼编码 234
6.5二叉树与树、森林之间的转换 236
6.5.1树和二叉树的转换 236
6.5.2森林和二叉树的转换 237
本章小结 238
练习题6 239
第7章 图 242
7.1图的基本概念 242
7.1.1图的定义 242
7.1.2图的基本术语 243
7.2图的存储结构和基本运算的实现 246
7.2.1邻接矩阵存储方法 246
7.2.2邻接表存储方法 247
7.3图的遍历 254
7.3.1什么是图的遍历 254
7.3.2深度优先遍历 254
7.3.3广度优先遍历 256
7.3.4非连通图的遍历 257
7.3.5图遍历算法的应用 259
7.4生成树和最小生成树 267
7.4.1生成树和最小生成树的概念 267
7.4.2普里姆算法 271
7.4.3克鲁斯卡尔算法 273
7.5最短路径 275
7.5.1路径的概念 275
7.5.2求一个顶点到其余各顶点的最短路径 276
7.5.3求每对顶点之间的最短路径 278
7.6拓扑排序 282
7.7 AOE网与关键路径 284
本章小结 289
练习题7 289
第8章 查找 294
8.1查找的基本概念 294
8.2线性表的查找 295
8.2.1顺序查找 295
8.2.2折半查找 297
8.2.3索引存储结构和分块查找 301
8.3树表的查找 304
8.3.1二叉排序树 304
8.3.2平衡二叉树 312
8.3.3 B-树 317
8.3.4B+树 321
8.3.5 2-3-4树 324
8.3.6红黑树 326
8.4哈希表的查找 329
8.4.1哈希表的基本概念 329
8.4.2哈希函数的构造方法 330
8.4.3哈希冲突的解决方法 331
8.4.4哈希表的查找及性能分析 334
本章小结 336
练习题8 336
第9章 内排序 339
9.1排序的基本概念 339
9.2插入排序 341
9.2.1直接插入排序 341
9.2.2折半插入排序 344
9.2.3希尔排序 345
9.3交换排序 348
9.3.1冒泡排序 348
9.3.2快速排序 349
9.4选择排序 353
9.4.1简单选择排序 353
9.4.2堆排序 355
9.5归并排序 359
9.6基数排序 362
9.7各种内排序方法的比较和选择 366
本章小结 367
练习题9 367
第10章 外排序 370
10.1外排序概述 370
10.2磁盘排序 371
10.2.1磁盘排序过程 371
10.2.2生成初始归并段 373
10.2.3多路平衡归并 375
10.2.4最佳归并树 378
本章小结 381
练习题10 381
第11章 数据结构和STL 383
11.1STL概述 383
11.1.1STL的发展和特点 383
11.1.2 C+++标准库和STL 383
11.1.3什么是算法 384
11.1.4什么是容器 385
11.1.5什么是迭代器 386
11.1.6 STL和数据结构的关系 386
11.2使用ST L 387
11.2.1使用STL的名字空间 387
11.2.2使用STL的示例 387
11.3迭代器 389
11.3.1自己设计迭代器 389
11.3.2 STL的迭代器及其使用 391
11.4容器 392
11.4.1顺序容器 392
11.4.2关联容器 397
11.4.3适配器容器 400
11.5算法 404
11.5.1非可变序列算法 404
11.5.2可变序列算法 404
11.5.3排序算法 405
11.5.4通用数值算法 405
本章小结 407
练习题11 407
附录A 书中部分算法清单 410
附录B 部分练习题参考答案 414
参考文献 416