算法之美: 隐匿在数据结构背后的原理（C++版）

✍ Scribed by 左飞

• Publisher: 电子工业出版社
• Year: 2016
• Tongue: Chinese
• Leaves: 426
• Category: Library

✦ Synopsis

《算法之美——隐匿在数据结构背后的原理（C++版）》围绕算法与数据结构这个话题，循序渐进、深入浅出地介绍了现代计算机技术中常用的40 余个经典算法，以及回溯法、分治法、贪婪法和动态规划等算法设计思想。在此过程中，《算法之美——隐匿在数据结构背后的原理（C++版）》也系统地讲解了链表（包括单向链表、单向循环链表和双向循环链表）、栈、队列（包括普通队列和优先级队列）、树（包括二叉树、哈夫曼树、堆、红黑树、AVL 树和字典树）、图、集合（包括不相交集）与字典等常用数据结构。同时，通过对22 个经典问题（包括约瑟夫环问题、汉诺塔问题、八皇后问题和骑士周游问题等）的讲解，逐步揭开隐匿在数据结构背后的算法原理，力图帮助读者夯实知识储备，激活思维技巧，并最终冲破阻碍编程能力提升的重重藩篱。

《算法之美——隐匿在数据结构背后的原理（C++版）》适合作为大专院校相关专...

《算法之美——隐匿在数据结构背后的原理（C++版）》围绕算法与数据结构这个话题，循序渐进、深入浅出地介绍了现代计算机技术中常用的40 余个经典算法，以及回溯法、分治法、贪婪法和动态规划等算法设计思想。在此过程中，《算法之美——隐匿在数据结构背后的原理（C++版）》也系统地讲解了链表（包括单向链表、单向循环链表和双向循环链表）、栈、队列（包括普通队列和优先级队列）、树（包括二叉树、哈夫曼树、堆、红黑树、AVL 树和字典树）、图、集合（包括不相交集）与字典等常用数据结构。同时，通过对22 个经典问题（包括约瑟夫环问题、汉诺塔问题、八皇后问题和骑士周游问题等）的讲解，逐步揭开隐匿在数据结构背后的算法原理，力图帮助读者夯实知识储备，激活思维技巧，并最终冲破阻碍编程能力提升的重重藩篱。

《算法之美——隐匿在数据结构背后的原理（C++版）》适合作为大专院校相关专业学生研习算法与数据结构知识的课外参考书。对有意参加信息学竞赛的读者，本书亦有很强的参考价值。此外，鉴于算法与数据结构在求职过程中常常被视为考察重点，所以就临近毕业的学生或其他欲从事IT 行业的求职者而言，阅读《算法之美——隐匿在数据结构背后的原理（C++版）》也将对面试备考大有裨益。

✦ Table of Contents

内 容 简 介
前言
目录
45 个算法
22 个经典问题
第1章
从数据到算法
1.1 数据与数据结构
1.1.1 数据及其类型
1.1.2 数据结构简介
1.2 算法
1.2.1 算法的概念
1.2.2 算法的分析
1．算法的空间复杂度
2．算法的时间复杂度
1.2.3 算法的设计
1．贪婪算法
2．分治法
3．动态规划
4．回溯法
5．概率算法
1.3 C++中的STL
1.3.1 STL简介
1.3.2 STL构成
1．容器
2．算法
3．迭代器
1.3.3 STL的不同版本
1．HP STL
2．Plauger STL
3．Rouge Wave STL
4．STLport
5．SGI STL
本章参考文献
第2章
指针与数组——也谈中国古代兵制
2.1 指针
2.1.1 内存与地址
2.1.2 指针的语法
2.1.3 使用指针变量
2.1.4 函数与参数传递
2.2 数组
2.2.1 结构型数据类型
2.2.2 数组定义与初始化
2.2.3 数组与指针
2.2.4 数组的抽象数据类型
2.3 数组应用举例
2.3.1 Z字形编排问题
2.3.2 大整数乘法问题
2.3.3 九宫格问题
2.4 动态内存管理
2.4.1 关键词new和delete
2.4.2 避免内存错误
1．内存泄漏
2．重复释放
3．坏指针问题
4．超量写内存
本章参考文献
第3章
字符串与模式匹配——梦里寻她千百度
3.1 基本概念与定义
3.1.1 C++中的字符串
3.1.2 字符串抽象数据类型
3.2 文本的精确匹配
3.2.1 BF算法
3.2.2 MP算法
3.2.3 KMP算法
3.2.4 BM算法
3.2.5 BMH算法
3.3 文本的模糊匹配
3.3.1 全局编辑距离
3.3.2 局部最佳对准
3.3.3 N元距离模型
3.3.4 语音编码模型
本章参考文献
第4章
链表——老鹰捉小鸡
4.1 链表的概念
4.2 单向链表
4.2.1 单向链表的结构
4.2.2 单向链表的操作算法
1．节点类与链表类
2．插入操作的实现
3．删除操作的实现
4．其他操作的实现
4.2.3 有序链表的合并算法
4.3 单向循环链表
4.3.1 单向循环链表的结构
4.3.2 单向循环链表的实现
4.3.3 约瑟夫环的问题
4.3.4 魔术师发牌问题
4.3.5 拉丁方阵的问题
4.4 双向循环链表
4.4.1 双向循环链表的结构
4.4.2 双向循环链表的实现
4.4.3 维吉尼亚加密法问题
4.5 游标类的设计与实现
4.5.1 游标类的结构
4.5.2 游标类的实现
4.6 STL与链表
4.6.1 STL中链表类的接口
4.6.2 遍历
4.6.3 元素的插入与删除
本章参考文献
第5章
先进先出与后进先出——简单而深刻
5.1 摞盘子的策略
5.1.1 栈的结构
5.1.2 栈的操作及实现
5.1.3 括号匹配问题
5.1.4 停车场模拟问题
5.2 排队的智慧
5.2.1 队列的结构
5.2.2 队列的操作及实现
5.2.3 舞伴问题
5.2.4 杨辉三角问题
5.2.5 游程编码问题
5.3 优先级队列——兼谈页面置换算法
5.3.1 优先级队列的结构
5.3.2 优先级队列的实现
5.4 STL中的栈与队列
5.4.1 STL中的stack
5.4.2 STL中的queue
5.4.3 STL中的priority_queue
本章参考文献
第6章
递归——老和尚讲故事
6.1 递归的概念
6.1.1 定义
6.1.2 应用递归的原则
6.1.3 递归和非递归的转化
6.2 分治法
6.2.1 分治法简述
6.2.2 汉诺塔问题
6.2.3 传染病问题
6.3 回溯法
6.3.1 回溯法简述
6.3.2 迷宫问题
6.3.3 八皇后问题
本章参考文献
第7章
树——从红楼梦说起
7.1 认识树这种结构
7.1.1 基本定义
7.1.2 一些术语
7.1.3 树的抽象
7.2 花开二枝分外香——二叉树及相关算法
7.2.1 二叉树的定义
7.2.2 二叉树的性质
7.2.3 二叉树的实现
7.2.4 二叉树的遍历算法
1．前序遍历
2．中序遍历
3．后序遍历
7.2.5 二叉树线索化算法
7.3 合抱之木，生于毫末——从树到森林
7.3.1 树的存储表示
1．双亲节点数组表示法
2．孩子节点多重链表表示法
3．孩子节点链表表示法
4．左子女—右兄弟表示法
7.3.2 树的实现
7.3.3 树与森林的遍历算法
1．深度优先遍历
2．广度优先遍历
7.3.4 森林与二叉树的转换
1．树转换为二叉树
2．森林转化为二叉树
3．二叉树转换为树和森林
7.4 哈夫曼树——最优二叉树编码算法
7.4.1 哈夫曼编码
7.4.2 构造哈夫曼树
7.4.3 哈夫曼编码的实现
7.5 堆
7.5.1 堆的概念
7.5.2 堆的建立
7.5.3 堆的操作
7.6 基于STL实现树结构
7.6.1 STL中的vector
7.6.2 STL中的map
本章参考文献
第8章
图——始于哥尼斯堡的七桥问题
8.1 图的基本概念
8.1.1 图的定义
8.1.2 图的术语
8.1.3 图的运算
8.1.4 图的抽象数据类型
8.2 图的存储与表示
8.2.1 图的邻接矩阵表示
8.2.2 图的邻接表表示
8.2.3 两种表示法的比较
8.3 图的遍历
8.3.1 欧拉路径与欧拉回路
8.3.2 哈密尔顿路径与哈密尔顿回路
8.3.3 广度优先遍历算法
8.3.4 深度优先遍历算法
8.4 最短路径问题
8.4.1 固定起点最短路径问题
8.4.2 非固定起点最短路径问题
8.4.3 最短路径的动态规划解法
8.5 最小生成树
8.5.1 最小生成树的定义
8.5.2 克鲁斯卡尔算法
8.5.3 普里姆算法
本章参考文献
第9章
树形搜索结构——做一名出色的园艺师
9.1 二叉搜索树
9.1.1 二叉搜索树的概念
9.1.2 二叉搜索树的操作
9.1.3 二叉搜索树的实现
9.1.4 二叉搜索树的分析
9.2 自平衡的二叉搜索树——AVL树
9.2.1 AVL树的概念
9.2.2 AVL树的旋转
1．单旋
2．双旋
9.2.3 AVL树的实现
9.3 树中亦有“红与黑”
9.3.1 红黑树的概念
9.3.2 红黑树的操作
1．旋转
2．插入
3．删除
9.3.3 红黑树的实现
9.4 基于Trie树的单词检索
9.4.1 Trie树的概念
9.4.2 Trie树的表示
9.4.3 Trie树的实现
本章参考文献
第10章
集合与字典——再言搜索之话题
10.1 集合论基础
10.1.1 集合的概念
10.1.2 集合的运算
10.2 集合的实现
10.2.1 位向量集合
10.2.2 单链表集合
10.3 字典
10.3.1 字典的概念
10.3.2 搜索运算
1．顺序搜索
2．折半搜索
10.4 散列
10.4.1 散列的概念
10.4.2 散列函数
1．直接定址法
2．除留余数法
3．平方取中法
4．乘余取整法
5．折叠法
10.4.3 字符串散列
1．BKDR散列
2．RS散列
3．FNV散列
10.4.4 处理散列冲突
1．线性探查法
2．二次探查法
3．双重散列法
10.5 拼写检查问题
10.6 不相交集
10.6.1 不相交集的概念
10.6.2 不相交集的实现
10.6.3 犯罪团伙的问题
10.6.4 路径压缩的实现
10.7 STL中的set
本章参考文献
第11章
排序——有序让世界更美好
11.1 排序问题概述
11.1.1 基本概念和定义
1．数据表
2．关键码
3．排序的数学定义
11.1.2 排序算法的分类
1．稳定排序和非稳定排序
2．内排序与外排序
11.1.3 排序算法的分析
11.2 插入排序
11.2.1 直接插入排序
11.2.2 二分插入排序
11.2.3 希尔排序
11.3 选择排序
11.3.1 直接选择排序
11.3.2 堆排序
11.4 交换排序
11.4.1 冒泡排序
11.4.2 鸡尾酒排序
11.4.3 快速排序
11.5 归并排序
11.6 计数排序
本章参考文献
附录
经典求职面试题目