《数据结构实用教程（C++版）》课后习题答案

《数据结构实用教程（C++版）》是 2011年电子工业出版社出版的图书，作者是万健。本书可以作为高等院校计算机及相关专业学生的教材，也可供培训机构及自学者参考。

本书为国家级优秀教学团队教学成果。根据教育部高等学校计算机科学与技术教学指导委员会制定的《高等学校计算机科学与技术专业发展战略研究报告暨专业规范》编写，首先介绍了数据结构的核心基础知识——数据、数据类型、数据结构等基本概念和算法、算法的性能度量等知识，然后集中讨论了四种基本的数据结构——集合、线性表、树和图，同时介绍了栈、队列、串、数组以及广义表等数据结构，最后介绍了排序和查找的几种基础算法及实现（用C 语言）。强调数据结构的工程应用，以模板的形式给出各种不同数据对象应用数据结构的多个实例，从而实现数据结构与工程应用的有机结合。

目录

• 第1章
• 绪 论
• 1.1 数据与数据类型 1
• 1.1.1 数据 1
• 1.1.2 数据的计算机表示与数据类型 2
• 1.1.3 抽象数据类型 5
• 1.2 数据结构 7
• 1.3 算法与算法分析 10
• 1.3.1 算法 10
• 1.3.2 算法的性能分析与度量 11
• 1.3.3 算法的时间复杂度 11
• 1.3.4 算法的空间复杂度 14
• 习题1 14
• 第2章
• 线性表
• 2.1 线性表的类型定义及结构特征 15
• 2.2 线性表类型的实现——顺序映像 17
• 2.3 线性表类型的实现——链式存储映像 26
• 2.3.1 单链表26
• 2.3.2 其他形式的链表 35
• 2.4 线性表的应用 37
• 2.4.1 两个有序表的合并 38
• 2.4.2 集合运算 40
• 2.4.3 一元多项式的表示和相加 42
• 习题2 47
• 第3章
• 其他线性结构
• 3.1 栈 48
• 3.1.1 栈的定义和基本操作 48
• 3.1.2 栈的存储结构及操作实现 49
• 3.1.3 栈的应用举例 55
• 3.2 队列 68
• 3.2.1 队列的定义和基本操作 68
• 3.2.2 队列的存储结构及操作实现 70
• 3.2.3 队列应用举例 77
• 3.3 串 83
• 3.3.1 串的基本概念和基本操作 83
• 3.3.2 串的存储结构 85
• 3.4 数组 87
• 3.4.1 数组的定义和基本操作 87
• 3.4.2 数组的存储表示 89
• 3.4.3 特殊矩阵的压缩存储 90
• 3.4.4 稀疏矩阵的压缩存储 92
• 3.5 广义表 96
• 3.5.1 广义表的基本概念和基本操作 97
• 3.5.2 广义表的存储结构 99
• 习题3 101
• 第4章
• 树型结构
• 4.1 树、森林的定义及基本术语 104
• 4.2 二叉树 105
• 4.2.1 二叉树的结构定义 105
• 4.2.2 几种特殊形态的二叉树 106
• 4.2.3 二叉树的性质 107
• 4.2.4 二叉树的存储结构 108
• 4.2.5 二叉链表类的定义 110
• 4.2.6 二叉树的递归遍历 114
• 4.2.7 几个二叉树基本操作的例子 116
• 4.2.8 二叉树的非递归遍历 118
• 4.2.9 其他部分成员函数的实现 121
• 4.2.10 主函数（演示二叉链表类部分基本操作的执行结果） 123
• 4.2.11 线索二叉树 126
• 4.3 树与森林的再讨论 129
• 4.3.1 树的存储结构 129
• 4.3.2 树和森林的遍历 132
• 4.4 树型结构的应用 134
• 4.4.1 算术表达式求值 134
• 4.4.2 树与等价问题 139
• 4.4.3 赫夫曼树及赫夫曼编码 145
• 习题4 154
• 第5章
• 图
• 5.1 图的定义和术语 156
• 5.2 图的存储结构 160
• 5.2.1 邻接矩阵表示法 160
• 5.2.2 邻接表表示法 162
• 5.2.3 十字链表表示法 164
• 5.2.4 邻接多重表表示法 165
• 5.3 图的基本操作 167
• 5.3.1 类的定义与实现 167
• 5.3.2 图的遍历 175
• 5.3.3 图的连通性 181
• 5.4 最小生成树 182
• 5.4.1 Prim算法 183
• 5.4.2 Kruskal算法 186
• 5.5 拓扑排序和关键路径 187
• 5.5.1 有向无环图 187
• 5.5.2 拓扑排序 188
• 5.5.3 关键路径 190
• 5.6 最短路径 194
• 5.6.1 单源最短路径 194
• 5.6.2 每对顶点间的最短路径 197
• 习题5 199
• 第6章
• 查 找
• 6.1 查找表的定义 201
• 6.2 静态查找表 202
• 6.2.1 顺序查找 202
• 6.2.2 折半查找 203
• 6.2.3 分块查找 206
• 6.3 动态查找表 207
• 6.3.1 二叉排序树 207
• 6.3.2 平衡二叉排序树 213
• 6.3.3 B?树和B+树 221
• 6.4 哈希查找 226
• 6.4.1 哈希表的定义 226
• 6.4.2 哈希函数的构造方法 227
• 6.4.3 处理冲突的办法 229
• 6.4.4 哈希表的查找及分析 231
• 6.4.5 哈希表的构建与查找算法 233
• 习题6 236
• 第7章
• 排 序
• 7.1 插入类排序 237
• 7.1.1 直接插入排序 238
• 7.1.2 折半插入排序 239
• 7.1.3 2-路插入排序 240
• 7.1.4 希尔排序 241
• 7.2 分划类排序 242
• 7.2.1 冒泡排序 242
• 7.2.2 快速排序 243
• 7.3 选择类排序 247
• 7.3.1 简单选择排序 247
• 7.3.2 树形选择排序 248
• 7.3.3 堆排序 249
• 7.4 归并类排序 252
• 7.5 基数排序 254
• 7.5.1 多关键字的排序 254
• 7.5.2 基数排序 254
• 7.6 内部排序的比较 259
• 7.7 外部排序 262
• 7.7.1 外部存储设备 262
• 7.7.2 外部排序的方法 262
• 7.7.3 败者树 263
• 习题7 264
• 参考文献 269