《数据结构 算法与应用 C++语言描述》课后习题答案

《数据结构、算法与应用：C++语言描述》在简要回顾了基本的C++ 程序设计概念的基础上，全面系统地介绍了队列、堆栈、树、图等基本数据结构，以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法，为数据结构与算法的继续学习和研究奠定了一个坚实的基础。更为可贵的是，《数据结构、算法与应用：C++语言描述》不仅仅介绍了理论知识，还提供了50多个应用实例及600多道练习题。

目录

• 译者序
• 前言
• 第一部分 预备知识
• 第1章 C++程序设计 1
• 1.1 引言 1
• 1.2 函数与参数 2
• 1.2.1 传值参数 2
• 1.2.2 模板函数 3
• 1.2.3 引用参数 3
• 1.2.4 常量引用参数 4
• 1.2.5 返回值 4
• 1.2.6 递归函数 5
• 1.3 动态存储分配 9
• 1.3.1 操作符new 9
• 1.3.2 一维数组 9
• 1.3.3 异常处理 10
• 1.3.4 操作符delete 10
• 1.3.5 二维数组 10
• 1.4 类 13
• 1.4.1 类Currency 13
• 1.4.2 使用不同的描述方法 18
• 1.4.3 操作符重载 20
• 1.4.4 引发异常 22
• 1.4.5 友元和保护类成员 23
• 1.4.6 增加#ifndef, #define和#endif语句 24
• 1.5 测试与调试 24
• 1.5.1 什么是测试 24
• 1.5.2 设计测试数据 26
• 1.5.3 调试 28
• 1.6 参考及推荐读物 29
• 第2章 程序性能 30
• 2.1 引言 30
• 2.2 空间复杂性 31
• 2.2.1 空间复杂性的组成 31
• 2.2.2 举例 35
• 2.3 时间复杂性 37
• 2.3.1 时间复杂性的组成 37
• 2.3.2 操作计数 37
• 2.3.3 执行步数 44
• 2.4 渐进符号（O、 健?、 o） 55
• 2.4.1 大写O符号 56
• 2.4.2 椒?58
• 2.4.3 符号 59
• 2.4.4 小写o符号 60
• 2.4.5 特性 60
• 2.4.6 复杂性分析举例 61
• 2.5 实际复杂性 66
• 2.6 性能测量 68
• 2.6.1 选择实例的大小 69
• 2.6.2 设计测试数据 69
• 2.6.3 进行实验 69
• 2.7 参考及推荐读物 74
• 第二部分 数据结构
• 第3章 数据描述 75
• 3.1 引言 75
• 3.2 线性表 76
• 3.3 公式化描述 77
• 3.3.1 基本概念 77
• 3.3.2 异常类NoMem 79
• 3.3.3 操作 79
• 3.3.4 评价 83
• 3.4 链表描述 86
• 3.4.1 类ChainNode 和Chain 86
• 3.4.2 操作 88
• 3.4.3 扩充类Chain 91
• 3.4.4 链表遍历器类 92
• 3.4.5 循环链表 93
• 3.4.6 与公式化描述方法的比较 94
• 3.4.7 双向链表 95
• 3.4.8 小结 96
• 3.5 间接寻址 99
• 3.5.1 基本概念 99
• 3.5.2 操作 100
• 3.6 模拟指针 102
• 3.6.1 SimSpace的操作 103
• 3.6.2 采用模拟指针的链表 106
• 3.7 描述方法的比较 110
• 3.8 应用 111
• 3.8.1 箱子排序 111
• 3.8.2 基数排序 116
• 3.8.3 等价类 117
• 3.8.4 凸包 122
• 3.9 参考及推荐读物 127
• 第4章 数组和矩阵 128
• 4.1 数组 128
• 4.1.1 抽象数据类型 128
• 4.1.2 C++数组 129
• 4.1.3 行主映射和列主映射 129
• 4.1.4 类Array1D 131
• 4.1.5 类Array2D 133
• 4.2 矩阵 137
• 4.2.1 定义和操作 137
• 4.2.2 类Matrix 138
• 4.3 特殊矩阵 141
• 4.3.1 定义和应用 141
• 4.3.2 对角矩阵 143
• 4.3.3 三对角矩阵 144
• 4.3.4 三角矩阵 145
• 4.3.5 对称矩阵 146
• 4.4 稀疏矩阵 149
• 4.4.1 基本概念 149
• 4.4.2 数组描述 149
• 4.4.3 链表描述 154
• 第5章 堆栈 161
• 5.1 抽象数据类型 161
• 5.2 派生类和继承 162
• 5.3 公式化描述 163
• 5.3.1 Stack的效率 164
• 5.3.2 自定义Stack 164
• 5.4 链表描述 166
• 5.5 应用 169
• 5.5.1 括号匹配 169
• 5.5.2 汉诺塔 170
• 5.5.3 火车车厢重排 172
• 5.5.4 开关盒布线 176
• 5.5.5 离线等价类问题 178
• 5.5.6 迷宫老鼠 180
• 5.6 参考及推荐读物 188
• 第6章 队列 189
• 6.1 抽象数据类型 189
• 6.2 公式化描述 190
• 6.3 链表描述 194
• 6.4 应用 197
• 6.4.1 火车车厢重排 197
• 6.4.2 电路布线 201
• 6.4.3 识别图元 204
• 6.4.4 工厂仿真 206
• 6.5 参考及推荐读物 217
• 第7章 跳表和散列 218
• 7.1 字典 218
• 7.2 线性表描述 219
• 7.3 跳表描述 222
• 7.3.1 理想情况 222
• 7.3.2 插入和删除 223
• 7.3.3 级的分配 224
• 7.3.4 类SkipNode 224
• 7.3.5 类SkipList 225
• 7.3.6 复杂性 229
• 7.4 散列表描述 229
• 7.4.1 理想散列 229
• 7.4.2 线性开型寻址散列 230
• 7.4.3 链表散列 234
• 7.5 应用——文本压缩 238
• 7.5.1 LZW压缩 239
• 7.5.2 LZW压缩的实现 239
• 7.5.3 LZW解压缩 243
• 7.5.4 LZW解压缩的实现 243
• 7.6 参考及推荐读物 247
• 第8章 二叉树和其他树 248
• 8.1 树 248
• 8.2 二叉树 251
• 8.3 二叉树的特性 252
• 8.4 二叉树描述 253
• 8.4.1 公式化描述 253
• 8.4.2 链表描述 254
• 8.5 二叉树常用操作 256
• 8.6 二叉树遍历 256
• 8.7 抽象数据类型BinaryTree 259
• 8.8 类BinaryTree 260
• 8.9 抽象数据类型及类的扩充 263
• 8.9.1 输出 263
• 8.9.2 删除 264
• 8.9.3 计算高度 264
• 8.9.4 统计节点数 265
• 8.10 应用 265
• 8.10.1 设置信号放大器 265
• 8.10.2 在线等价类 268
• 8.11 参考及推荐读物 275
• 第9章 优先队列 276
• 9.1 引言 276
• 9.2 线性表 277
• 9.3 堆 278
• 9.3.1 定义 278
• 9.3.2 最大堆的插入 279
• 9.3.3 最大堆的删除 279
• 9.3.4 最大堆的初始化 280
• 9.3.5 类MaxHeap 281
• 9.4 左高树 285
• 9.4.1 高度与宽度优先的最大及最小左高树 285
• 9.4.2 最大HBLT的插入 287
• 9.4.3 最大HBLT的删除 287
• 9.4.4 合并两棵最大HBLT 287
• 9.4.5 初始化最大HBLT 289
• 9.4.6 类MaxHBLT 289
• 9.5 应用 293
• 9.5.1 堆排序 293
• 9.5.2 机器调度 294
• 9.5.3 霍夫曼编码 297
• 9.6 参考及推荐读物 302
• 第10章 竞赛树 303
• 10.1 引言 303
• 10.2 抽象数据类型WinnerTree 306
• 10.3 类WinnerTree 307
• 10.3.1 定义 307
• 10.3.2 类定义 307
• 10.3.3 构造函数、析构函数及Winner函数 308
• 10.3.4 初始化赢者树 308
• 10.3.5 重新组织比赛 310
• 10.4 输者树 311
• 10.5 应用 312
• 10.5.1 用最先匹配法求解箱子装载问题 312
• 10.5.2 用相邻匹配法求解箱子装载问题 316
• 第11章 搜索树 319
• 11.1 二叉搜索树 320
• 11.1.1 基本概念 320
• 11.1.2 抽象数据类型BSTree和IndexedBSTree 321
• 11.1.3 类BSTree 322
• 11.1.4 搜索 322
• 11.1.5 插入 323
• 11.1.6 删除 324
• 11.1.7 类DBSTree 326
• 11.1.8 二叉搜索树的高度 327
• 11.2 AVL树 328
• 11.2.1 基本概念 328
• 11.2.2 AVL树的高度 328
• 11.2.3 AVL树的描述 329
• 11.2.4 AVL搜索树的搜索 329
• 11.2.5 AVL搜索树的插入 329
• 11.2.6 AVL搜索树的删除 332
• 11.3 红－黑树 334
• 11.3.1 基本概念 334
• 11.3.2 红－黑树的描述 336
• 11.3.3 红－黑树的搜索 336
• 11.3.4 红－黑树的插入 336
• 11.3.5 红－黑树的删除 339
• 11.3.6 实现细节的考虑及复杂性分析 343
• 11.4 B－树 344
• 11.4.1 索引顺序访问方法 344
• 11.4.2 m 叉搜索树 345
• 11.4.3 m 序B－树 346
• 11.4.4 B－树的高度 347
• 11.4.5 B－树的搜索 348
• 11.4.6 B－树的插入 348
• 11.4.7 B－树的删除 350
• 11.4.8 节点结构 353
• 11.5 应用 354
• 11.5.1 直方图 354
• 11.5.2 用最优匹配法求解箱子装载问题 357
• 11.5.3 交叉分布 359
• 11.6 参考及推荐读物 363
• 第12章 图 365
• 12.1 基本概念 365
• 12.2 应用 366
• 12.3 特性 368
• 12.4 抽象数据类型Graph和Digraph 370
• 12.5 无向图和有向图的描述 371
• 12.5.1 邻接矩阵 371
• 12.5.2 邻接压缩表 373
• 12.5.3 邻接链表 374
• 12.6 网络描述 375
• 12.7 类定义 376
• 12.7.1 不同的类 376
• 12.7.2 邻接矩阵类 377
• 12.7.3 扩充Chain类 380
• 12.7.4 类LinkedBase 381
• 12.7.5 链接类 382
• 12.8 图的遍历 386
• 12.8.1 基本概念 386
• 12.8.2 邻接矩阵的遍历函数 387
• 12.8.3 邻接链表的遍历函数 388
• 12.9 语言特性 389
• 12.9.1 虚函数和多态性 389
• 12.9.2 纯虚函数和抽象类 391
• 12.9.3 虚基类 391
• 12.9.4 抽象类和抽象数据类型 393
• 12.10 图的搜索算法 394
• 12.10.1 宽度优先搜索 394
• 12.10.2 类Network 395
• 12.10.3 BFS的实现 395
• 12.10.4 BFS的复杂性分析 396
• 12.10.5 深度优先搜索 397
• 12.11 应用 399
• 12.11.1 寻找路径 399
• 12.11.2 连通图及其构件 400
• 12.11.3 生成树 402
• 第三部分 算法设计方法
• 第13章 贪婪算法 405
• 13.1 最优化问题 405
• 13.2 算法思想 406
• 13.3 应用 409
• 13.3.1 货箱装船 409
• 13.3.2 0/1背包问题 410
• 13.3.3 拓扑排序 412
• 13.3.4 二分覆盖 415
• 13.3.5 单源最短路径 421
• 13.3.6 最小耗费生成树 424
• 13.4 参考及推荐读物 433
• 第14章 分而治之算法 434
• 14.1 算法思想 434
• 14.2 应用 440
• 14.2.1 残缺棋盘 440
• 14.2.2 归并排序 443
• 14.2.3 快速排序 447
• 14.2.4 选择 452
• 14.2.5 距离最近的点对 454
• 14.3 解递归方程 462
• 14.4 复杂性的下限 463
• 14.4.1 最小最大问题的下限 464
• 14.4.2 排序算法的下限 465
• 第15章 动态规划 467
• 15.1 算法思想 467
• 15.2 应用 469
• 15.2.1 0/1背包问题 469
• 15.2.2 图像压缩 471
• 15.2.3 矩阵乘法链 476
• 15.2.4 最短路径 480
• 15.2.5 网络的无交叉子集 483
• 15.2.6 元件折叠 486
• 15.3 参考及推荐读物 491
• 第16章 回溯 492
• 16.1 算法思想 492
• 16.2 应用 496
• 16.2.1 货箱装船 496
• 16.2.2 0/1背包问题 503
• 16.2.3 最大完备子图 506
• 16.2.4 旅行商问题 508
• 16.2.5 电路板排列 510
• 第17章 分枝定界 516
• 17.1 算法思想 516
• 17.2 应用 519
• 17.2.1 货箱装船 519
• 17.2.2 0/1背包问题 526
• 17.2.3 最大完备子图 528
• 17.2.4 旅行商问题 529
• 17.2.5 电路板排列 532