C++数据结构原理与经典问题求解

出版者:电子工业出版社

作者:左飞

页数:531

出版时间:2008-10

价格:55.00元

装帧:平装

isbn号码:9787121073212

具体描述

《C++数据结构原理与经典问题求解》是一部关于计算机科学与工程领域基础性核心课程——数据结构与算法的专著。全书以典型数据结构、程序设计方法及问题求解方法为研究对象，用C++面向对象程序设计语言作为描述语言，时刻突出对经典问题求解这一要旨，并将丰富的C++语言程序设计实践融入其中。全书采用“数据结构原理描述→面向对象实现→解决经典问题→STL介绍”的基本架构，既强调理论的完整性，又突出实例引导的驱动性，用经典问题和大量背景描述提高读者的阅读兴趣，从而使原本枯燥的理论变得妙趣横生。基于上述框架，《C++数据结构原理与经典问题求解》简要回顾了基本C++程序设计方法后，又全面系统地介绍了链表、队列、栈、树、图等基本数据结构。此外，《C++数据结构原理与经典问题求解》还提供了近百个算法、数十个经典问题和十余个综合问题的完整实现代码近万余行。

目录信息

第1章 绪论 1
1.1 数据与数据结构 2
1.1.1 数据及其类型 2
1.1.2 数据结构简介 4
1.2 算法 6
1.2.1 算法的概念 6
1.2.2 算法的分析 8
1.2.3 算法的设计 12
1.3 C++语言简介 18
1.3.1 C++的产生与发展 18
1.3.2 C++与面向对象思想 20
1.3.3 C++中的类和对象 23
1.4 本章小结 28
第2章 C++编程基础 29
2.1 开始C++编程 30
2.1.1 输入输出 30
2.1.2 预处理 38
2.1.3 名字空间 44
2.2 深入的类编程 50
2.2.1 访问控制 50
2.2.2 初始化与清除 53
2.2.3 动态创建对象 57
2.2.4 友元函数 60
2.2.5 拷贝构造函数 61
2.3 丰富的C++特性 65
2.3.1 常量 65
2.3.2 函数重载 68
2.3.3 运算符重载 71
2.3.4 异常处理 77
2.4 代码重用机制 79
2.4.1 继承 80
2.4.2 多态 87
2.4.3 模板 90
2.5 标准模板库 93
2.5.1 STL简介 94
2.5.2 STL构成 95
2.5.3 STL的不同版本 97
2.6 本章小结 98
第3章 指针、数组与字符串 99
3.1 指针 100
3.1.1 指针的概念 100
3.1.2 指针的语法 102
3.1.3 函数与参数传递 103
3.2 数组 108
3.2.1 数组定义与初始化 109
3.2.2 数组与指针 113
3.2.3 数组的抽象数据类型 116
3.2.4 大整数乘法问题 120
3.2.5 荷兰国旗问题 121
3.3 字符串 124
3.3.1 C++中的字符串 124
3.3.2 字符串抽象数据类型 126
3.3.3 字符串的匹配算法 128
3.3.4 字符串指数问题 141
3.4 动态内存管理 142
3.4.1 关键词new和delete 143
3.4.2 避免内存错误 146
3.5 本章小结 152
第4章 链表 153
4.1 单向链表 154
4.1.1 单向链表的结构 154
4.1.2 单向链表类的实现 155
4.1.3 有序链表的合并 162
4.1.4 多项式加法问题 163
4.2 单向循环链表 164
4.2.1 单向循环链表的结构 164
4.2.2 单向循环链表类的实现 166
4.2.3 约瑟夫问题 169
4.2.4 魔术师发牌问题 170
4.2.5 拉丁方阵问题 172
4.3 双向循环链表 173
4.3.1 双向循环链表的结构 173
4.3.2 双向循环链表类的实现 174
4.3.3 Vigenere加密问题 182
4.3.4 选美比赛问题 184
4.4 游标类的设计与实现 186
4.4.1 游标类的结构 186
4.4.2 游标类的实现 187
4.5 STL与链表 191
4.5.1 STL中链表类的接口 191
4.5.2 遍历 194
4.5.3 元素的插入与删除 196
4.6 本章小结 196
第5章 栈与队列 197
5.1 栈 198
5.1.1 栈的结构 198
5.1.2 栈的实现 199
5.1.3 括号匹配问题 203
5.1.4 停车场模拟问题 204
5.2 队列 208
5.2.1 队列的结构 208
5.2.2 队列的实现 210
5.2.3 舞伴问题 214
5.2.4 杨辉三角形问题 215
5.2.5 游程编码问题 216
5.3 优先级队列 218
5.3.1 优先级队列的结构 218
5.3.2 优先级队列的实现 220
5.4 STL中的栈与队列 222
5.4.1 STL中的stack 222
5.4.2 STL中的queue 224
5.4.3 STL中的priority_queue 226
5.5 本章小结 229
第6章 递归 231
6.1 递归的概念 232
6.1.1 递归的定义 232
6.1.2 应用递归的原则 235
6.1.3 递归和非递归的转化 240
6.2 分治法 243
6.2.1 分治法简述 243
6.2.2 汉诺塔问题 244
6.2.3 传染病问题 246
6.3 回溯法 250
6.3.1 回溯法简述 251
6.3.2 迷宫问题 251
6.3.3 八皇后问题 255
6.3.4 骑士周游问题 258
6.4 本章小结 265
第7章 树 267
7.1 树的概念 268
7.1.1 树的定义 268
7.1.2 树的术语 271
7.1.3 树的抽象数据类型 272
7.2 二叉树 273
7.2.1 二叉树的定义 273
7.2.2 二叉树的性质 275
7.2.3 二叉树的实现 276
7.2.4 二叉树的遍历 285
7.2.5 二叉树的线索化 289
7.3 树与森林 291
7.3.1 树的存储表示 291
7.3.2 树的实现 294
7.3.3 树与森林的遍历 298
7.3.4 森林与二叉树的转换 300
7.4 霍夫曼树 304
7.4.1 霍夫曼树的概念 304
7.4.2 霍夫曼树的构造方法 305
7.4.3 霍夫曼编码及其实现 307
7.5 堆 313
7.5.1 堆的概念 314
7.5.2 堆的建立 314
7.5.3 堆的操作 316
7.6 基于STL实现树结构 317
7.6.1 STL中的vector 317
7.6.2 STL中的map 321
7.7 医院建模问题 323
7.8 本章小结 328
第8章 图 329
8.1 图的基本概念 330
8.1.1 图的定义 330
8.1.2 图的术语 331
8.1.3 图的运算 334
8.1.4 图的抽象数据类型 336
8.2 图的存储与表示 337
8.2.1 图的邻接矩阵表示 337
8.2.2 图的邻接表表示 339
8.2.3 两种表示法的比较 342
8.3 图的遍历 342
8.3.1 欧拉路径与欧拉回路 343
8.3.2 哈密尔顿路径与哈密尔顿回路 345
8.3.3 广度优先遍历 346
8.3.4 深度优先遍历 349
8.4 最短路径问题 353
8.4.1 固定起点最短路问题 353
8.4.2 非固定起点最短路问题 355
8.4.3 最短路径的动态规划解法 358
8.4.4 旅游交通路线问题 364
8.5 最小生成树 372
8.5.1 最小生成树的定义 372
8.5.2 克鲁斯卡尔算法 373
8.5.3 普里姆算法 375
8.6 经典问题举例 379
8.6.1 文字游戏问题 380
8.6.2 道路修建问题 382
8.6.3 回家路线问题 385
8.6.4 水塘计算问题 387
8.6.5 棍子还原问题 389
8.7 本章小结 392
第9章 树形搜索结构 393
9.1 二叉搜索树 394
9.1.1 二叉搜索树的概念 394
9.1.2 二叉搜索树的操作 395
9.1.3 二叉搜索树的实现 397
9.1.4 二叉搜索树的分析 400
9.2 AVL树 403
9.2.1 AVL树的概念 404
9.2.2 AVL树的旋转 405
9.2.3 AVL树的实现 410
9.3 红黑树 418
9.3.1 红黑树的概念 418
9.3.2 红黑树的操作 421
9.3.3 红黑树的实现 428
9.4 Trie树 433
9.4.1 Trie树的概念 433
9.4.2 Trie树的表示 434
9.4.3 Trie树的实现 435
9.5 本章小结 439
第10章 集合与字典 441
10.1 集合论基础 442
10.1.1 集合的概念 442
10.1.2 集合的运算 444
10.2 集合的实现 445
10.2.1 位向量集合 445
10.2.2 链表集合 451
10.3 字典 460
10.3.1 字典的概念 461
10.3.2 搜索运算 463
10.4 散列 467
10.4.1 散列的概念 467
10.4.2 散列函数 469
10.4.3 处理散列冲突 471
10.4.4 散列的应用 475
10.5 经典问题举例 476
10.5.1 拼写检查问题 476
10.5.2 无线网络问题 485
10.5.3 第K个数问题 488
10.6 STL中的set 490
10.7 本章小结 493
第11章 排序 495
11.1 排序问题概述 496
11.1.1 基本概念和定义 496
11.1.2 排序算法的分类 497
11.1.3 排序算法分析与选择 497
11.2 插入排序 498
11.2.1 直接插入排序 498
11.2.2 二分法插入排序 501
11.2.3 希尔排序 503
11.3 选择排序 506
11.3.1 直接选择排序 506
11.3.2 堆排序 508
11.4 交换排序 512
11.4.1 冒泡法排序 512
11.4.2 Shaker排序 514
11.4.3 快速排序 517
11.5 归并排序 522
11.6 计数排序 526
11.7 本章小结 531
参考文献 532
· · · · · · (收起)

用户评价

这本书的排版和逻辑组织达到了专业水准，阅读起来有一种“顺畅的挑战感”。它没有那种为了凑字数而堆砌的冗余叙述，每一个章节、每一个示例代码块似乎都有其存在的明确目的。我尤其欣赏作者在介绍递归与迭代转换时所采取的策略，他不仅仅是展示了两种实现方式，而是通过追踪函数调用栈和状态变量的演变，清晰地揭示了编译器内部是如何处理递归的，以及在什么情况下，迭代实现会更具优势（比如避免栈溢出）。当我尝试用书中的思想去重构我项目中的一个性能瓶颈——一个复杂的权限校验系统时，我发现可以通过将树形结构转化为合适的栈操作序列，极大地简化了代码逻辑并提升了响应速度。这本书的“问题求解”部分，与其说是提供解决方案，不如说是提供了一种系统性的问题分解和建模思维，这对于提升编程的“高级感”至关重要。

坦率地说，初翻此书时我有些被它的深度震慑住了。它显然不是为初学者准备的“入门读物”，更像是一本资深开发者用于查漏补缺、夯实基础的案头书。我注意到作者在讲解链表和数组的区别时，并没有停留在简单的内存连续性上，而是深入探讨了现代CPU缓存行填充（Cache Line Padding）对不同结构遍历性能的实际影响，这在工程实践中往往是性能差异的决定性因素。这种将计算机体系结构知识嵌入到数据结构教学中的做法，极大地提升了本书的价值。此外，书中对“经典问题求解”部分的选材非常老道，聚焦于那些经受住时间考验的、具有普遍意义的难题，比如最大流/最小割的Ford-Fulkerson方法，作者用清晰的步骤图解说明了残余网络的概念，使得这个复杂的流网络问题变得可视化和可操作。这本书要求读者具备扎实的C++语法基础和一定的离散数学背景，否则阅读起来会比较吃力，但对于愿意投入的读者，它提供的是一种超越代码实现的深刻理解。

我之前对数据结构的学习停留在“能用”的层面，仅限于会调用库函数实现功能，但对于为什么是这个复杂度、为什么某个结构比另一个更优，总是心里没底。这本厚厚的《C++数据结构原理与经典问题求解》彻底改变了我的认知。它的叙述风格非常严谨，带着一种工程师特有的务实感，不玩虚的，上来就是数学证明和代码层面的具象化。最让我惊喜的是它对图论部分的处理，不同于其他教材将DFS/BFS作为独立的章节，这本书将它们融入到拓扑排序、最小生成树等具体应用场景中，使得算法不再是孤立的知识点，而是解决特定工程问题的工具箱。尤其是在处理动态规划的章节，作者展示了如何通过状态转移方程的设计，巧妙地将看似无关的子问题串联起来，这在优化我正在进行的一个资源分配模型时，提供了全新的思路。说实话，这本书的阅读体验是“慢热”的，需要投入大量时间去啃硬骨头，但一旦那些晦涩的推导逻辑在你脑中被打通，那种豁然开朗的感觉，是其他轻松读物无法比拟的。

这本《C++数据结构原理与经典问题求解》简直是为我这种想深入理解底层机制的程序员量身定做的。我过去用其他语言实现数据结构时，总觉得是在“搭积木”，这次终于有机会用C++的视角，去探究那些抽象概念背后的内存布局和性能权衡。书里对STL源码层面的剖析简直是教科书级别的，它不像有些书籍只是罗列算法流程，而是深入到了C++模板元编程和面向对象设计如何优雅地支撑起复杂数据结构实现。我特别欣赏作者在讲解平衡二叉树（比如AVL或红黑树）时，那种不厌其烦地展示旋转操作如何保证对数时间复杂度的细致推导，完全杜绝了死记硬背的可能性。读完后，我在处理一个需要高效查找和插入的场景时，不再是盲目调用 `std::map`，而是能基于对底层B树或红黑树结构的理解，更好地预估资源消耗和选择最合适的容器。它提供的那些经典问题求解案例，比如最短路径算法的优化路径选择，也远超出了基础排序和搜索的范畴，更像是实战中会遇到的瓶颈点。这本书真正做到了将“原理”与“求解”无缝衔接，不再是两个孤立的部分。

我对这本书的结构安排非常满意，它遵循了一种“由浅入深，应用驱动”的教学路径。起始于基础的线性结构，稳步过渡到复杂的非线性结构，并在每一个关键节点都穿插了如何利用这些结构解决实际计算难题的案例。例如，在讨论堆（Heap）结构时，作者立刻将其应用于优先队列的实现，并接着阐述了基于堆的Top K元素查找的效率优势，这种紧密的关联性确保了知识点不会成为孤立的理论。更难得的是，书中对C++模板的运用恰到好处，许多泛型算法的实现体现了C++特有的灵活性和表达力，读者可以清晰地看到，如何编写出既高效又可复用的数据结构代码。这本书给我的感觉是，它不是在教你“如何写出能跑的C++代码”，而是在教你“如何写出高性能、易维护的C++数据结构代码”。它更像是一本技艺精湛的工匠手册，而非入门级的编程指南。

问题导引，实例详尽，可操作性强。

不错的书 作者花了很大的功夫 不过 与国外书还是有差距的~！

问题导引，实例详尽，可操作性强。

这书上的C++部分挺好的，有很多小的细节，用的例子也挺好的。后面部分内容还没看，没法评论

这书上的C++部分挺好的，有很多小的细节，用的例子也挺好的。后面部分内容还没看，没法评论