《数据结构及应用算法教程（修订版）》是2014年清华大学出版社出版的图书。
本书从数据类型的角度，分别讨论了四大类型的数据结构的逻辑特性、存储表示及其应用。此外，还专辟一章，以若干实例阐述以抽象数据类型为中心的程序设计方法。书中每一章后都配有适量的习题，以供读者复习提高之用。第1～9章还专门设有“解题指导与示例”一节内容，不仅给出答案，对大部分题目提供了详尽的解答注释；其中的一些算法题还给出了多种解法。书中主要算法和最后一章的实例中的全部程序代码均收录在与本书配套的光盘之中。
本书内容丰富，概念阐述细致清楚，可作为高等院校计算机类专业和信息类相关专业“数据结构”或“软件基础”课程的本科教材。另外，对于准备参加计算机类研究生专业课统考的考生，本书也可作为应试的解题指导。
目录
- 第1章绪论1
- 1.1数据结构讨论的范畴1
- 1.2与数据结构相关的概念2
- 1.2.1基本概念和术语3
- 1.2.2数据结构(datastructures)4
- 1.2.3数据类型和抽象数据类型5
- 1.3算法及其描述和分析6
- 1.3.1算法6
- 1.3.2算法的描述6
- 1.3.3算法效率的衡量方法和准则9
- 1.3.4算法的存储空间需求10
- 解题指导与示例11
- 习题16
- 第2章线性表18
- 2.1线性表的类型定义18
- 2.1.1线性表的定义18
- 2.1.2线性表的基本操作19
- 2.2线性表的顺序表示和实现22
- 2.2.1顺序表--线性表的顺序存储表示22
- 2.2.2顺序表中基本操作的实现23
- 2.2.3顺序表其他算法举例28
- 2.3线性表的链式表示和实现31
- 2.3.1单链表和指针31
- 2.3.2单链表的基本操作32
- 2.3.3单链表的其他操作举例36
- 2.3.4循环链表39
- 2.3.5双向链表40
- 2.4有序表42
- 2.5顺序表和链表的综合比较47
- 解题指导与示例47
- 习题57
- 第3章排序60
- 3.1排序的基本概念60
- 3.2简单排序方法63
- 3.2.1插入排序63
- 3.2.2起泡排序65
- 3.3先进排序方法67
- 3.3.1快速排序67
- 3.3.2归并排序69
- 3.3.3堆排序71
- 3.4基数排序72
- 3.5各种排序方法的综合比较76
- 解题指导与示例78
- 习题84
- 第4章栈和队列86
- 4.1栈86
- 4.1.1栈的结构特点和操作86
- 4.1.2栈的表示和操作的实现87
- 4.2栈的应用举例90
- 4.3队列98
- 4.3.1队列的结构特点和操作98
- 4.3.2队列的表示和操作的实现100
- 4.4队列应用举例104
- 解题指导与示例109
- 习题113
- 第5章串和数组115
- 5.1串的定义和操作115
- 5.2串的表示和实现118
- 5.2.1定长顺序存储表示118
- 5.2.2堆分配存储表示119
- 5.2.3块链存储表示120
- 5.3正文模式匹配121
- 5.4正文编辑--串操作应用举例123
- 5.5数组124
- 5.5.1数组的定义和操作124
- 5.5.2数组的顺序表示和实现125
- 5.5.3数组的应用127
- 5.6矩阵的压缩存储130
- 5.6.1特殊形状矩阵的存储表示130
- 5.6.2随机稀疏矩阵的存储压缩131 [2]
- 解题指导与示例137
- 习题142
- 第6章二叉树和树144
- 6.1二叉树144
- 6.1.1二叉树的定义和基本术语144
- 6.1.2二叉树的几个基本性质147
- 6.1.3二叉树的存储结构148
- 6.2二叉树遍历150
- 6.2.1问题的提出150
- 6.2.2遍历算法描述152
- 6.2.3二叉树遍历应用举例153
- 6.2.4线索二叉树157
- 6.3树和森林159
- 6.3.1树和森林的定义159
- 6.3.2树和森林的存储结构161
- 6.3.3树和森林的遍历164
- 6.4树的应用168
- 6.4.1堆排序的实现168
- 6.4.2二叉排序树171
- 6.4.3赫夫曼树及其应用173
- 解题指导与示例179
- 习题198
- 第7章图和广义表201
- 7.1图的定义和术语201
- 7.2图的存储结构204
- 7.2.1图的数组（邻接矩阵）存储表示204
- 7.2.2图的邻接表存储表示205
- 7.3图的遍历207
- 7.3.1深度优先搜索遍历图208
- 7.3.2广度优先搜索遍历图210
- 7.4连通网的最小生成树215
- 7.5单源最短路径217
- 7.6拓扑排序221
- 7.7关键路径223
- 7.8广义表225
- 7.8.1广义表的定义225
- 7.8.2广义表的存储结构226
- 7.8.3广义表的遍历227
- 解题指导与示例228
- 习题246
- 第8章查找表248
- 8.1静态查找表249
- 8.1.1顺序查找250
- 8.1.2折半查找251
- 8.1.3分块查找254
- 8.2动态查找表255
- 8.2.1二叉查找树256
- 8.2.2键树260
- 8.3哈希表及其查找265
- 8.3.1什么是哈希表265
- 8.3.2构造哈希函数的几种方法267
- 8.3.3处理冲突的方法和建表示例268
- 8.3.4哈希表的查找及其性能分析269
- 8.3.5哈希表的应用举例272
- 解题指导与示例274
- 习题285
- 第9章文件287
- 9.1基本概念287
- 9.1.1外存储器简介287
- 9.1.2有关文件的基本概念288
- 9.2顺序文件289
- 9.2.1存储在顺序存储器上的文件289
- 9.2.2存储在直接存储器上的文件291
- 9.3索引文件291
- 9.3.1B树291
- 9.3.2B+树和索引顺序文件293
- 9.4哈希文件295
- 9.4.1文件组织方式295
- 9.4.2文件的操作296
- 9.5多关键码文件296
- 9.5.1倒排文件297
- 9.5.2索引链接文件297
- 解题指导与示例299
- 习题300
- 第10章数据结构程序设计示例301
- 10.1抽象数据类型301
- 10.2从问题到程序的求解过程304
- 10.2.1建立数据结构模型设计抽象数据类型305
- 10.2.2算法设计306
- 10.2.3实现抽象数据类型307
- 10.2.4编制程序代码并进行静态测试和动态调试308
- 10.3程序的规范说明309
- 10.4应用示例分析311
- 10.4.1含并、交和差运算的集合类型312
- 10.4.2最佳任务分配方案求解322
- 10.4.3排队问题的系统仿真330
- 10.4.4十进制四则运算计算器339
- 10.4.5自行车零部件库的库存模型345
- 10.4.6教务课程计划的辅助制定353
- 10.4.7一个小型全文检索模型360
- 10.4.8汽车牌照的快速查找369
- 实习题377
- 实习一链表的维护与文件形式的保存378
- 实习二用回溯法求解“稳定婚配”问题378
- 实习三以队列实现的仿真技术预测理发馆的经营状况379
- 实习四利用树形结构的搜索算法模拟因特网域名的查询380
- 实习五管道铺设施工的最佳方案选择381
- 实习六使用哈希表技术判别两个源程序的相似性381
- 附录算法一览表384
- 参考文献391
