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

本书缘起
一家世界**的IT公司给其面试者出了如下两道测试题。
1.一辆有7节车厢的列车在星期五下午18点17分离开车站,并以50 km/h的速度行驶。现在是**,请问你要去哪里?
2.股票A目前的报价是100元。3个月后,这个价钱可能涨到120元,也可能跌到90元。如果现在给你一次机会允许你用110元钱在接下来的3个月内买这个股票,你将如何使用这110元钱。请将你的决策过程告诉我们。
无独有偶,许多世界**的软件公司都喜欢在面试时问一些考查应试者思维能力的问题,为什么呢?道理很简单,单纯掌握一门编程语言并不足以编写出好的程序。重要的是,掌握思考问题的方法和解决问题的策略。
古语云:“授人以鱼,不如授人以渔。”如果说吃鱼是目的,那么钓鱼就是手段。尽管一条鱼能解一时之饥,但却不能解长久之饥;如果想永远有鱼吃,那就要学会钓鱼的方法。这就是作者写作本书的目的和动机。
本书不仅是一本向程序员传授专业技术的书,更是一本教导人们如何思考问题的书。
本书对象
数据结构和算法是计算机程序设计领域的重要理论和技术基础,是计算机学科的核心课程,也是计算机科学研究的基础方向。数据结构不但为数据存储和问题解决提供逻辑结构基础,还可以提供一种抽象现实世界的思维方式,即使非计算机专业的人员学习和了解它也有助于发散思维,激发创意。而算法设计则在提供实际问题解决方案的同时,帮助训练人脑对问题的抽象能力和逻辑思维能力,因此学习这方面的知识也大有裨益。

第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
参考文献 533
……

内外兼修:精湛高超的C++编程技巧与级富魅力的算法合计艺术相得益彰
神形并重:生动的经典问题求解与丰富的数据结构原理娓娓道来
润物无声:编程技能的培养与抽象思维的训练浑然一体
由浅入深,通俗易懂,注重趣味性,避免枯燥说教
内容生动,结构合理,强调实践性,编程实例丰富
理念先进,方法为要,突出多角度,倡导正确思想