数据结构——C语言描述(第3版)

本书在前两版的基础上修订而成。本书主要包括数据结构的基本概念、基本数据结构(线性表、栈、队列、串、数组、广义表、树、图）和基本技术（查找、排序）三个部分，涉及经典的数据组织方式和处理算法，内容丰富，概念清晰。本书用C语言作为算法描述语言，采用面向对象的方法讲述数据结构中的技术，在内容上提供了更加丰富的资源，加入了便于自主学习的新形态教学资源以及作者多年对重要知识点和学习难点的理解与总结，提供了数据结构试题选编样卷及参考答案，便于读者学习，便于教师在翻转课堂上使用。本书既可作为大专院校计算机等专业“数据结构”课程的教材，也可供计算机开发和应用人员学习和参考。

第1章绪论1
1.1什么是数据结构（定义）1
1.2数据结构的内容9
1.3算法11
1.4算法描述的工具12
1.5对算法作性能评价16
1.6关于数据结构的学习21
习题22
实习题23
第2章线性表24
2.1线性表的概念及运算24
2.1.1线性表的逻辑结构24
2.1.2线性表的抽象数据类型定义25
2.2线性表的顺序存储26
2.2.1线性表的顺序存储结构26
2.2.2线性表顺序存储结构上的基本运算27
2.3线性表的链式存储32
2.3.1单链表32
2.3.2单链表上的基本运算33
2.3.3循环链表41
2.3.4双向链表43
2.3.5静态链表45
2.3.6顺序表和链表的比较48
2.4一元多项式的表示及相加49
习题53
实习题55
第3章限定性线性表——栈和队列56
3.1栈56
3.1.1栈的定义56
3.1.2栈的表示和实现57
3.1.3栈的应用举例62
3.1.4栈与递归的实现68
3.2队列74
3.2.1队列的定义74
3.2.2队列的表示和实现75
3.2.3队列的应用举例79
习题82
实习题83
第4章串85
4.1串的定义85
4.2抽象数据类型串的实现87
4.2.1定长顺序串87
4.2.2堆串91
4.2.3块链串96
4.3串的应用举例：文本编辑96
习题97
实习题98
第5章数组和广义表100
5.1数组的定义和运算100
5.2数组的顺序存储和实现101
5.3特殊矩阵的压缩存储104
5.3.1三角矩阵104
5.3.2带状矩阵105
5.3.3稀疏矩阵106
5.4广义表116
5.4.1广义表的概念116
5.4.2广义表的存储结构117
5.4.3广义表的操作实现118
习题120
实习题120
第6章树和二叉树122
6.1树的概念与定义122
6.2二叉树124
6.2.1二叉树的定义与基本操作124
6.2.2二叉树的性质125
6.2.3二叉树的存储结构127
6.3二叉树的遍历与线索化129
6.3.1二叉树的遍历129
6.3.2基于栈的递归消除132
6.3.3遍历算法应用135
6.3.4线索二叉树140
6.4树、森林和二叉树的关系144
6.4.1树的存储结构144
6.4.2树、森林与二叉树的相互转换146
6.4.3树与森林的遍历149
6.5哈夫曼树及其应用150
6.5.1哈夫曼树150
6.5.2哈夫曼编码152
6.5.3哈夫曼编码算法的实现154
习题156
实习题157
第7章图159
7.1图的定义与基本术语159
7.1.1图的定义159
7.1.2基本术语161
7.2图的存储结构163
7.2.1邻接矩阵表示法163
7.2.2邻接表表示法166
7.2.3十字链表168
7.2.4邻接多重表170
7.3图的遍历171
7.3.1深度优先搜索172
7.3.2广度优先搜索175
7.4图的连通性问题177
7.4.1无向图的连通分量177
7.4.2最小生成树178
7.5有向无环图的应用182
7.5.1拓扑排序182
7.5.2关键路径185
7.6最短路径190
7.6.1求某一顶点到其他各顶点的最短路径191
7.6.2求任意一对顶点间的最短路径193
习题195
实习题197
第8章查找199
8.1查找的基本概念199
8.2基于线性表的查找法200
8.2.1顺序查找法200
8.2.2折半查找法201
8.2.3分块查找法203
8.3基于树的查找法204
8.3.1二叉排序树204
8.3.2平衡二叉排序树210
8.3.3B-树218
8.4计算式查找法——哈希法227
8.4.1哈希函数的构造方法227
8.4.2处理冲突的方法229
8.4.3哈希表的查找过程231
8.4.4哈希法性能分析232
习题235
实习题236
第9章内部排序237
9.1排序的基本概念237
9.2插入类排序238
9.2.1直接插入排序238
9.2.2折半插入排序240
9.2.3表插入排序241
9.2.4希尔排序241
9.3交换类排序法244
9.3.1冒泡排序（相邻比序法）244
9.3.2快速排序246
9.4选择类排序法248
9.4.1简单选择排序249
9.4.2树形选择排序250
9.4.3堆排序250
9.5归并排序255
9.6分配类排序257
9.6.1多关键字排序258
9.6.2链式基数排序258
9.6.3基数排序的顺序表结构262
9.7各种排序方法的综合比较262
习题263
实习题265
第10章外部排序266
10.1外存信息的特性266
10.1.1磁带存储器266
10.1.2磁盘存储器267
10.2外排序的基本方法269
10.2.1磁盘排序269
10.2.2磁带排序274
习题277
附录数据结构试题选编278
附录A样卷一：期末考试试题278
附录B样卷二：期末考试试题281
附录C样卷三：硕士研究生入学考试试题284
附录D样卷四：硕士研究生入学考试试题286
参考文献288