当前位置:主页 > 计算机电子书 > C++ > 算法下载
算法之美:隐匿在数据结构背后的原理(C++版)

算法之美:隐匿在数据结构背后的原理(C++版) PDF 高质量版

  • 更新:2021-07-02
  • 大小:175.56MB
  • 类别:算法
  • 作者:左飞
  • 出版:电子工业出版社
  • 格式:PDF

  • 资源介绍
  • 相关推荐

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

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

目录

  • 第1 章 从数据到算法 .................................................................. 1
  • 1.1 数据与数据结构 ..................................................................................... 1
  • 1.1.1 数据及其类型 ................................................................................................. 1
  • 1.1.2 数据结构简介 ................................................................................................. 3
  • 1.2 算法 ......................................................................................................... 5
  • 1.2.1 算法的概念 ..................................................................................................... 5
  • 1.2.2 算法的分析 ..................................................................................................... 8
  • 1.2.3 算法的设计 ................................................................................................... 12
  • 1.3 C++中的STL ........................................................................................ 18
  • 1.3.1 STL 简介 ...................................................................................................... 19
  • 1.3.2 STL 构成 ...................................................................................................... 20
  • 1.3.3 STL 的不同版本 ........................................................................................... 22
  • 本章参考文献 ................................................................................................ 23
  • 第2 章 指针与数组——也谈中国古代兵制 ................................ 24
  • 2.1 指针 ....................................................................................................... 24
  • 2.1.1 内存与地址 ................................................................................................... 24
  • 2.1.2 指针的语法 ................................................................................................... 27
  • 2.1.3 使用指针变量 ............................................................................................... 29
  • 2.1.4 函数与参数传递 ........................................................................................... 31
  • 2.2 数组 ....................................................................................................... 36
  • 2.2.1 结构型数据类型 ........................................................................................... 37
  • 2.2.2 数组定义与初始化 ....................................................................................... 37
  • 2.2.3 数组与指针 ................................................................................................... 41
  • 2.2.4 数组的抽象数据类型 ................................................................................... 45
  • 2.3 数组应用举例 ....................................................................................... 48
  • 2.3.1 Z 字形编排问题 ........................................................................................... 48
  • 2.3.2 大整数乘法问题 ........................................................................................... 51
  • 2.3.3 九宫格问题 ................................................................................................... 52
  • 2.4 动态内存管理 ....................................................................................... 53
  • 2.4.1 关键词new 和delete .................................................................................... 53
  • 2.4.2 避免内存错误 ............................................................................................... 56
  • 本章参考文献 ................................................................................................ 61
  • 第3 章 字符串与模式匹配——梦里寻她千百度 ......................... 62
  • 3.1 基本概念与定义 ................................................................................... 62
  • 3.1.1 C++中的字符串 ............................................................................................ 62
  • 3.1.2 字符串抽象数据类型 ................................................................................... 65
  • 3.2 文本的精确匹配 ................................................................................... 66
  • 3.2.1 BF 算法 ......................................................................................................... 66
  • 3.2.2 MP 算法 ........................................................................................................ 67
  • 3.2.3 KMP 算法 ..................................................................................................... 72
  • 3.2.4 BM 算法 ....................................................................................................... 75
  • 3.2.5 BMH 算法 ..................................................................................................... 81
  • 3.3 文本的模糊匹配 ................................................................................... 83
  • 3.3.1 全局编辑距离 ............................................................................................... 83
  • 3.3.2 局部最佳对准 ............................................................................................... 86
  • 3.3.3 N 元距离模型 ............................................................................................... 87
  • 3.3.4 语音编码模型 ............................................................................................... 88
  • 本章参考文献 ................................................................................................ 89
  • 第4 章 链表——老鹰捉小鸡 ..................................................... 91
  • 4.1 链表的概念 ........................................................................................... 91
  • 4.2 单向链表 ............................................................................................... 92
  • 4.2.1 单向链表的结构 ........................................................................................... 92
  • 4.2.2 单向链表的操作算法 ................................................................................... 94
  • 4.2.3 有序链表的合并算法 ................................................................................. 101
  • 4.3 单向循环链表 ..................................................................................... 102
  • 4.3.1 单向循环链表的结构 ................................................................................. 102
  • 4.3.2 单向循环链表的实现 ................................................................................. 103
  • 4.3.3 约瑟夫环的问题 ......................................................................................... 107
  • 4.3.4 魔术师发牌问题 ......................................................................................... 108
  • 4.3.5 拉丁方阵的问题 ......................................................................................... 109
  • 4.4 双向循环链表 ...................................................................................... 110
  • 4.4.1 双向循环链表的结构 ................................................................................. 110
  • 4.4.2 双向循环链表的实现 .................................................................................. 111
  • 4.4.3 维吉尼亚加密法问题 ................................................................................. 115
  • 4.5 游标类的设计与实现 .......................................................................... 117
  • 4.5.1 游标类的结构 ............................................................................................. 117
  • 4.5.2 游标类的实现 ............................................................................................. 118
  • 4.6 STL 与链表 ......................................................................................... 122
  • 4.6.1 STL 中链表类的接口 ................................................................................. 122
  • 4.6.2 遍历 ............................................................................................................. 124
  • 4.6.3 元素的插入与删除 ..................................................................................... 125
  • 本章参考文献 .............................................................................................. 126
  • 第5 章 先进先出与后进先出——简单而深刻 .......................... 127
  • 5.1 摞盘子的策略 ..................................................................................... 127
  • 5.1.1 栈的结构 ..................................................................................................... 127
  • 5.1.2 栈的操作及实现 ......................................................................................... 129
  • 5.1.3 括号匹配问题 ............................................................................................. 132
  • 5.1.4 停车场模拟问题 ......................................................................................... 133
  • 5.2 排队的智慧 ......................................................................................... 136
  • 5.2.1 队列的结构 ................................................................................................. 136
  • 5.2.2 队列的操作及实现 ..................................................................................... 138
  • 5.2.3 舞伴问题 ..................................................................................................... 142
  • 5.2.4 杨辉三角问题 ............................................................................................. 143
  • 5.2.5 游程编码问题 ............................................................................................. 145
  • 5.3 优先级队列——兼谈页面置换算法 .................................................. 146
  • 5.3.1 优先级队列的结构 ..................................................................................... 146
  • 5.3.2 优先级队列的实现 ..................................................................................... 149
  • 5.4 STL 中的栈与队列 ............................................................................. 150
  • 5.4.1 STL 中的stack ........................................................................................... 151
  • 5.4.2 STL 中的queue .......................................................................................... 153
  • 5.4.3 STL 中的priority_queue ............................................................................ 155
  • 本章参考文献 .............................................................................................. 158
  • 第6 章 递归——老和尚讲故事 ................................................ 159
  • 6.1 递归的概念 ......................................................................................... 159
  • 6.1.1 定义 ............................................................................................................ 159
  • 6.1.2 应用递归的原则 ......................................................................................... 162
  • 6.1.3 递归和非递归的转化 ................................................................................. 168
  • 6.2 分治法 ................................................................................................. 170
  • 6.2.1 分治法简述 ................................................................................................. 171
  • 6.2.2 汉诺塔问题 ................................................................................................. 172
  • 6.2.3 传染病问题 ................................................................................................. 174
  • 6.3 回溯法 ................................................................................................. 176
  • 6.3.1 回溯法简述 ................................................................................................. 176
  • 6.3.2 迷宫问题 ..................................................................................................... 176
  • 6.3.3 八皇后问题 ................................................................................................. 180
  • 本章参考文献 .............................................................................................. 183
  • 第7 章 树——从红楼梦说起 ................................................... 184
  • 7.1 认识树这种结构 ................................................................................. 184
  • 7.1.1 基本定义 ..................................................................................................... 184
  • 7.1.2 一些术语 ..................................................................................................... 186
  • 7.1.3 树的抽象 ..................................................................................................... 187
  • 7.2 花开二枝分外香——二叉树及相关算法 .......................................... 188
  • 7.2.1 二叉树的定义 ............................................................................................. 188
  • 7.2.2 二叉树的性质 ............................................................................................. 190
  • 7.2.3 二叉树的实现 ............................................................................................. 191
  • 7.2.4 二叉树的遍历算法 ..................................................................................... 196
  • 7.2.5 二叉树线索化算法 ..................................................................................... 200
  • 7.3 合抱之木,生于毫末——从树到森林 .............................................. 203
  • 7.3.1 树的存储表示 ............................................................................................. 203
  • 7.3.2 树的实现 ..................................................................................................... 206
  • 7.3.3 树与森林的遍历算法 ................................................................................. 209
  • 7.3.4 森林与二叉树的转换 .................................................................................. 211
  • 7.4 哈夫曼树——最优二叉树编码算法 .................................................. 213
  • 7.4.1 哈夫曼编码 ................................................................................................. 213
  • 7.4.2 构造哈夫曼树 ............................................................................................. 215
  • 7.4.3 哈夫曼编码的实现 ..................................................................................... 216
  • 7.5 堆 ......................................................................................................... 220
  • 7.5.1 堆的概念 ..................................................................................................... 220
  • 7.5.2 堆的建立 ..................................................................................................... 221
  • 7.5.3 堆的操作 ..................................................................................................... 223
  • 7.6 基于STL 实现树结构 ........................................................................ 224
  • 7.6.1 STL 中的vector .......................................................................................... 224
  • 7.6.2 STL 中的map ............................................................................................. 228
  • 本章参考文献 .............................................................................................. 230
  • 第8 章 图——始于哥尼斯堡的七桥问题 .................................. 231
  • 8.1 图的基本概念 ..................................................................................... 231
  • 8.1.1 图的定义 ..................................................................................................... 231
  • 8.1.2 图的术语 ..................................................................................................... 232
  • 8.1.3 图的运算 ..................................................................................................... 236
  • 8.1.4 图的抽象数据类型 ..................................................................................... 237
  • 8.2 图的存储与表示 ................................................................................. 239
  • 8.2.1 图的邻接矩阵表示 ..................................................................................... 239
  • 8.2.2 图的邻接表表示 ......................................................................................... 241
  • 8.2.3 两种表示法的比较 ..................................................................................... 243
  • 8.3 图的遍历 ............................................................................................. 244
  • 8.3.1 欧拉路径与欧拉回路 ................................................................................. 244
  • 8.3.2 哈密尔顿路径与哈密尔顿回路 ................................................................. 248
  • 8.3.3 广度优先遍历算法 ..................................................................................... 252
  • 8.3.4 深度优先遍历算法 ..................................................................................... 254
  • 8.4 最短路径问题 ..................................................................................... 258
  • 8.4.1 固定起点最短路径问题 ............................................................................. 258
  • 8.4.2 非固定起点最短路径问题 ......................................................................... 264
  • 8.4.3 最短路径的动态规划解法 ......................................................................... 266
  • 8.5 最小生成树 ......................................................................................... 273
  • 8.5.1 最小生成树的定义 ..................................................................................... 273
  • 8.5.2 克鲁斯卡尔算法 ......................................................................................... 275
  • 8.5.3 普里姆算法 ................................................................................................. 279
  • 本章参考文献 .............................................................................................. 283
  • 第9 章 树形搜索结构——做一名出色的园艺师 ....................... 284
  • 9.1 二叉搜索树 ......................................................................................... 284
  • 9.1.1 二叉搜索树的概念 ..................................................................................... 284
  • 9.1.2 二叉搜索树的操作 ..................................................................................... 285
  • 9.1.3 二叉搜索树的实现 ..................................................................................... 288
  • 9.1.4 二叉搜索树的分析 ..................................................................................... 291
  • 9.2 自平衡的二叉搜索树——AVL 树 .................................................... 294
  • 9.2.1 AVL 树的概念 ............................................................................................ 294
  • 9.2.2 AVL 树的旋转 ............................................................................................ 295
  • 9.2.3 AVL 树的实现 ............................................................................................ 299
  • 9.3 树中亦有“红与黑” ......................................................................... 303
  • 9.3.1 红黑树的概念 ............................................................................................. 303
  • 9.3.2 红黑树的操作 ............................................................................................. 306
  • 9.3.3 红黑树的实现 ............................................................................................. 314
  • 9.4 基于Trie 树的单词检索 ..................................................................... 314
  • 9.4.1 Trie 树的概念 ............................................................................................. 315
  • 9.4.2 Trie 树的表示 ............................................................................................. 316
  • 9.4.3 Trie 树的实现 ............................................................................................. 317
  • 本章参考文献 .............................................................................................. 320
  • 第10 章 集合与字典——再言搜索之话题 ............................... 321
  • 10.1 集合论基础 ....................................................................................... 321
  • 10.1.1 集合的概念 ............................................................................................... 321
  • 10.1.2 集合的运算 ............................................................................................... 323
  • 10.2 集合的实现 ....................................................................................... 325
  • 10.2.1 位向量集合 ............................................................................................... 325
  • 10.2.2 单链表集合 ............................................................................................... 330
  • 10.3 字典 ................................................................................................... 337
  • 10.3.1 字典的概念 ............................................................................................... 338
  • 10.3.2 搜索运算 ................................................................................................... 342
  • 10.4 散列 ................................................................................................... 346
  • 10.4.1 散列的概念 ............................................................................................... 347
  • 10.4.2 散列函数 ................................................................................................... 348
  • 10.4.3 字符串散列 ............................................................................................... 351
  • 10.4.4 处理散列冲突 ........................................................................................... 353
  • 10.5 拼写检查问题 ................................................................................... 358
  • 10.6 不相交集 ........................................................................................... 363
  • 10.6.1 不相交集的概念 ....................................................................................... 363
  • 10.6.2 不相交集的实现 ....................................................................................... 366
  • 10.6.3 犯罪团伙的问题 ....................................................................................... 369
  • 10.6.4 路径压缩的实现 ....................................................................................... 370
  • 10.7 STL 中的set ...................................................................................... 371
  • 本章参考文献 .............................................................................................. 374
  • 第11 章 排序——有序让世界更美好 ....................................... 375
  • 11.1 排序问题概述 ................................................................................... 375
  • 11.1.1 基本概念和定义 ....................................................................................... 375
  • 11.1.2 排序算法的分类 ....................................................................................... 376
  • 11.1.3 排序算法的分析 ....................................................................................... 377
  • 11.2 插入排序 ........................................................................................... 378
  • 11.2.1 直接插入排序 ........................................................................................... 378
  • 11.2.2 二分插入排序 ........................................................................................... 380
  • 11.2.3 希尔排序 ................................................................................................... 382
  • 11.3 选择排序 ........................................................................................... 384
  • 11.3.1 直接选择排序 ........................................................................................... 384
  • 11.3.2 堆排序 ....................................................................................................... 386
  • 11.4 交换排序 ........................................................................................... 390
  • 11.4.1 冒泡排序 ................................................................................................... 390
  • 11.4.2 鸡尾酒排序 ............................................................................................... 392
  • 11.4.3 快速排序 ................................................................................................... 395
  • 11.5 归并排序 ........................................................................................... 399
  • 11.6 计数排序 ........................................................................................... 403
  • 本章参考文献 .............................................................................................. 407
  • 附录 经典求职面试题目 .......................................................... 408
     

资源下载

资源下载地址1:https://pan.baidu.com/s/1ZoRrrKm5B2nW3C5HXsPhsuw

相关资源

网友留言