算法之美(c++版).pdf

分类详细讲解数据结构及算法
目录第 1 章 从数据到算法 .................................................................. 11.1 数据与数据结构 ..................................................................................... 11.1.1 数据及其类型 ................................................................................................. 11.1.2 数据结构简介 ................................................................................................. 31.2 算法 ......................................................................................................... 51.2.1 算法的概念 ..................................................................................................... 51.2.2 算法的分析 ..................................................................................................... 81.2.3 算法的设计 ................................................................................................... 121.3 C 中的 STL ........................................................................................ 181.3.1 STL 简介 ...................................................................................................... 191.3.2 STL 构成 ...................................................................................................... 201.3.3 STL 的不同版本 ........................................................................................... 22本章参考文献 ................................................................................................ 23第 2 章 指针与数组——也谈中国古代兵制 ................................ 242.1 指针 ....................................................................................................... 242.1.1 内存与地址 ................................................................................................... 242.1.2 指针的语法 ................................................................................................... 272.1.3 使用指针变量 ............................................................................................... 292.1.4 函数与参数传递 ........................................................................................... 312.2 数组 ....................................................................................................... 362.2.1 结构型数据类型 ........................................................................................... 372.2.2 数组定义与初始化 ....................................................................................... 372.2.3 数组与指针 ................................................................................................... 412.2.4 数组的抽象数据类型 ................................................................................... 452.3 数组应用举例 ....................................................................................... 482.3.1 Z 字形编排问题 ........................................................................................... 482.3.2 大整数乘法问题 ........................................................................................... 512.3.3 九宫格问题 ................................................................................................... 522.4 动态内存管理 ....................................................................................... 532.4.1 关键词 new 和 delete .................................................................................... 532.4.2 避免内存错误 ............................................................................................... 56本章参考文献 ................................................................................................ 61第 3 章 字符串与模式匹配——梦里寻她千百度 ......................... 623.1 基本概念与定义 ................................................................................... 62 VIII │ 算法之美——隐匿在数据结构背后的原理（C 版）3.1.1 C 中的字符串 ............................................................................................ 623.1.2 字符串抽象数据类型 ................................................................................... 653.2 文本的精确匹配 ................................................................................... 663.2.1 BF 算法 ......................................................................................................... 663.2.2 MP 算法 ........................................................................................................ 673.2.3 KMP 算法 ..................................................................................................... 723.2.4 BM 算法 ....................................................................................................... 753.2.5 BMH 算法..................................................................................................... 813.3 文本的模糊匹配 ................................................................................... 833.3.1 全局编辑距离 ............................................................................................... 833.3.2 局部最佳对准 ............................................................................................... 863.3.3 N 元距离模型 ............................................................................................... 873.3.4 语音编码模型 ............................................................................................... 88本章参考文献 ................................................................................................ 89第 4 章 链表——老鹰捉小鸡 ..................................................... 914.1 链表的概念 ........................................................................................... 914.2 单向链表 ............................................................................................... 924.2.1 单向链表的结构 ........................................................................................... 924.2.2 单向链表的操作算法 ................................................................................... 944.2.3 有序链表的合并算法 ................................................................................. 1014.3 单向循环链表 ..................................................................................... 1024.3.1 单向循环链表的结构 ................................................................................. 1024.3.2 单向循环链表的实现 ................................................................................. 1034.3.3 约瑟夫环的问题 ......................................................................................... 1074.3.4 魔术师发牌问题 ......................................................................................... 1084.3.5 拉丁方阵的问题 ......................................................................................... 1094.4 双向循环链表 ..................................................................................... 1104.4.1 双向循环链表的结构 .................................................................................. 1104.4.2 双向循环链表的实现 .................................................................................. 1114.4.3 维吉尼亚加密法问题 .................................................................................. 1154.5 游标类的设计与实现 ......................................................................... 1174.5.1 游标类的结构 .............................................................................................. 1174.5.2 游标类的实现 .............................................................................................. 1184.6 STL 与链表 ......................................................................................... 1224.6.1 STL 中链表类的接口 ................................................................................. 1224.6.2 遍历 ............................................................................................................ 1244.6.3 元素的插入与删除 ..................................................................................... 125本章参考文献 .............................................................................................. 126第 5 章 先进先出与后进先出——简单而深刻 .......................... 1275.1 摞盘子的策略 ..................................................................................... 1275.1.1 栈的结构 ..................................................................................................... 1275.1.2 栈的操作及实现 ......................................................................................... 1295.1.3 括号匹配问题 ............................................................................................. 1325.1.4 停车场模拟问题 ......................................................................................... 1335.2 排队的智慧 ......................................................................................... 136 目录 │ IX5.2.1 队列的结构 ................................................................................................. 1365.2.2 队列的操作及实现 ..................................................................................... 1385.2.3 舞伴问题 ..................................................................................................... 1425.2.4 杨辉三角问题 ............................................................................................. 1435.2.5 游程编码问题 ............................................................................................. 1455.3 优先级队列——兼谈页面置换算法 .................................................. 1465.3.1 优先级队列的结构 ..................................................................................... 1465.3.2 优先级队列的实现 ..................................................................................... 1495.4 STL 中的栈与队列 ............................................................................. 1505.4.1 STL 中的 stack ........................................................................................... 1515.4.2 STL 中的 queue .......................................................................................... 1535.4.3 STL 中的 priority_queue ............................................................................ 155本章参考文献 .............................................................................................. 158第 6 章 递归——老和尚讲故事 ................................................ 1596.1 递归的概念 ......................................................................................... 1596.1.1 定义 ............................................................................................................ 1596.1.2 应用递归的原则 ......................................................................................... 1626.1.3 递归和非递归的转化 ................................................................................. 1686.2 分治法 ................................................................................................. 1706.2.1 分治法简述 ................................................................................................. 1716.2.2 汉诺塔问题 ................................................................................................. 1726.2.3 传染病问题 ................................................................................................. 1746.3 回溯法 ................................................................................................. 1766.3.1 回溯法简述 ................................................................................................. 1766.3.2 迷宫问题 ..................................................................................................... 1766.3.3 八皇后问题 ................................................................................................. 180本章参考文献 .............................................................................................. 183第 7 章 树——从红楼梦说起 ................................................... 1847.1 认识树这种结构 ................................................................................. 1847.1.1 基本定义 ..................................................................................................... 1847.1.2 一些术语 ..................................................................................................... 1867.1.3 树的抽象 ..................................................................................................... 1877.2 花开二枝分外香——二叉树及相关算法 .......................................... 1887.2.1 二叉树的定义 ............................................................................................. 1887.2.2 二叉树的性质 ............................................................................................. 1907.2.3 二叉树的实现 ............................................................................................. 1917.2.4 二叉树的遍历算法 ..................................................................................... 1967.2.5 二叉树线索化算法 ..................................................................................... 2007.3 合抱之木，生于毫末——从树到森林 .............................................. 2037.3.1 树的存储表示 ............................................................................................. 2037.3.2 树的实现 ..................................................................................................... 2067.3.3 树与森林的遍历算法 ................................................................................. 2097.3.4 森林与二叉树的转换 .................................................................................. 2117.4 哈夫曼树——最优二叉树编码算法 .................................................. 2137.4.1 哈夫曼编码 ................................................................................................. 213 X │ 算法之美——隐匿在数据结构背后的原理（C 版）7.4.2 构造哈夫曼树 ............................................................................................. 2157.4.3 哈夫曼编码的实现 ..................................................................................... 2167.5 堆 ......................................................................................................... 2207.5.1 堆的概念 ..................................................................................................... 2207.5.2 堆的建立 ..................................................................................................... 2217.5.3 堆的操作 ..................................................................................................... 2237.6 基于 STL 实现树结构 ........................................................................ 2247.6.1 STL 中的 vector .......................................................................................... 2247.6.2 STL 中的 map ............................................................................................. 228本章参考文献 .............................................................................................. 230第 8 章 图——始于哥尼斯堡的七桥问题.................................. 2318.1 图的基本概念 ..................................................................................... 2318.1.1 图的定义 ..................................................................................................... 2318.1.2 图的术语 ..................................................................................................... 2328.1.3 图的运算 ..................................................................................................... 2368.1.4 图的抽象数据类型 ..................................................................................... 2378.2 图的存储与表示 ................................................................................. 2398.2.1 图的邻接矩阵表示 ..................................................................................... 2398.2.2 图的邻接表表示 ......................................................................................... 2418.2.3 两种表示法的比较 ..................................................................................... 2438.3 图的遍历 ............................................................................................. 2448.3.1 欧拉路径与欧拉回路 ................................................................................. 2448.3.2 哈密尔顿路径与哈密尔顿回路 ................................................................. 2488.3.3 广度优先遍历算法 ..................................................................................... 2528.3.4 深度优先遍历算法 ..................................................................................... 2548.4 最短路径问题 ..................................................................................... 2588.4.1 固定起点最短路径问题 ............................................................................. 2588.4.2 非固定起点最短路径问题 ......................................................................... 2648.4.3 最短路径的动态规划解法 ......................................................................... 2668.5 最小生成树 ......................................................................................... 2738.5.1 最小生成树的定义 ..................................................................................... 2738.5.2 克鲁斯卡尔算法 ......................................................................................... 2758.5.3 普里姆算法 ................................................................................................. 279本章参考文献 .............................................................................................. 283第 9 章 树形搜索结构——做一名出色的园艺师 ....................... 2849.1 二叉搜索树 ......................................................................................... 2849.1.1 二叉搜索树的概念 ..................................................................................... 2849.1.2 二叉搜索树的操作 ..................................................................................... 2859.1.3 二叉搜索树的实现 ..................................................................................... 2889.1.4 二叉搜索树的分析 ..................................................................................... 2919.2 自平衡的二叉搜索树——AVL 树 ..................................................... 2949.2.1 AVL 树的概念 ............................................................................................ 2949.2.2 AVL 树的旋转 ............................................................................................ 2959.2.3 AVL 树的实现 ............................................................................................ 2999.3 树中亦有“红与黑” ......................................................................... 303 目录 │ XI9.3.1 红黑树的概念 ............................................................................................. 3039.3.2 红黑树的操作 ............................................................................................. 3069.3.3 红黑树的实现 ............................................................................................. 3149.4 基于 Trie 树的单词检索 ..................................................................... 3149.4.1 Trie 树的概念 ............................................................................................. 3159.4.2 Trie 树的表示 ............................................................................................. 3169.4.3 Trie 树的实现 ............................................................................................. 317本章参考文献 .............................................................................................. 320第 10 章 集合与字典——再言搜索之话题 ............................... 32110.1 集合论基础 ....................................................................................... 32110.1.1 集合的概念 ............................................................................................... 32110.1.2 集合的运算 ............................................................................................... 32310.2 集合的实现 ....................................................................................... 32510.2.1 位向量集合 ............................................................................................... 32510.2.2 单链表集合 ............................................................................................... 33010.3 字典 ................................................................................................... 33710.3.1 字典的概念 ............................................................................................... 33810.3.2 搜索运算 ................................................................................................... 34210.4 散列 ................................................................................................... 34610.4.1 散列的概念 ............................................................................................... 34710.4.2 散列函数 ................................................................................................... 34810.4.3 字符串散列 ............................................................................................... 35110.4.4 处理散列冲突 ........................................................................................... 35310.5 拼写检查问题 ................................................................................... 35810.6 不相交集 ........................................................................................... 36310.6.1 不相交集的概念 ....................................................................................... 36310.6.2 不相交集的实现 ....................................................................................... 36610.6.3 犯罪团伙的问题 ....................................................................................... 36910.6.4 路径压缩的实现 ....................................................................................... 37010.7 STL 中的 set ...................................................................................... 371本章参考文献 .............................................................................................. 374第 11 章 排序——有序让世界更美好 ....................................... 37511.1 排序问题概述 ................................................................................... 37511.1.1 基本概念和定义 ....................................................................................... 37511.1.2 排序算法的分类 ....................................................................................... 37611.1.3 排序算法的分析 ....................................................................................... 37711.2 插入排序 ........................................................................................... 37811.2.1 直接插入排序 ........................................................................................... 37811.2.2 二分插入排序 ........................................................................................... 38011.2.3 希尔排序 ................................................................................................... 38211.3 选择排序 ........................................................................................... 38411.3.1 直接选择排序 ........................................................................................... 38411.3.2 堆排序 ....................................................................................................... 38611.4 交换排序 ........................................................................................... 390 XII │ 算法之美——隐匿在数据结构背后的原理（C 版）11.4.1 冒泡排序 ................................................................................................... 39011.4.2 鸡尾酒排序 ............................................................................................... 39211.4.3 快速排序 ................................................................................................... 39511.5 归并排序 ........................................................................................... 39911.6 计数排序 ........................................................................................... 403本章参考文献 .............................................................................................. 407附录 经典求职面试题目 .......................................................... 408