数据结构与算法经典问题解析（原书第2版）

本书以简明易懂的方式介绍了数据结构与算法的基本知识，内容全面、系统。描述方式基于C/C++语言，对数据结构中容易混淆的问题进行了透彻的阐述，对每一个问题均给出了不同的解决方案。涵盖入职面试中常见的数据结构与算法方面的问题，既可以作为数据结构课程的教材，也可以作为研究生考试的参考以及程序员的参考手册。

译者序 前言 第1章 绪论 1 1.1 变量 1 1.2 数据类型 1 1.3 数据结构 2 1.4 抽象数据类型 2 1.5 什么是算法 3 1.6 为什么需要算法分析 3 1.7 算法分析的目的 3 1.8 什么是运行时间分析 4 1.9 如何比较算法 4 1.10 什么是增长率 4 1.11 常用的增长率 4 1.12 分析的类型 5 1.13 渐近表示 6 1.14 大O表示法 6 1.15 Ω表示法 7 1.16 Θ表示法 8 1.17 重要说明 9 1.18 为什么称为渐近分析 9 1.19 渐近分析指南 9 1.20 渐近表示法的性质 11 1.21 常用的对数和累加公式 11 1.22 分治法主定理 12 1.23 分治法主定理的相关问题 12 1.24 问题规模减小和递归求解主定理 13 1.25 问题规模减小和递归求解主定理的变型 13 1.26 猜测和确认的方法 14 1.27 平摊分析 15 1.28 算法分析的相关问题 15 第2章 递归和回溯 28 2.1 引言 28 2.2 什么是递归 28 2.3 为什么要用递归 28 2.4 递归函数的格式 28 2.5 递归和内存（可视化） 29 2.6 递归与迭代 30 2.7 递归说明 30 2.8 递归算法的经典用例 30 2.9 递归的相关问题 31 2.10 什么是回溯 32 2.11 回溯算法的经典用例 32 2.12 回溯的相关问题 32 第3章 链表 34 3.1 什么是链表 34 3.2 链表抽象数据类型 34 3.3 为什么要用链表 35 3.4 数组概述 35 3.5 链表、数组和动态数组的比较 36 3.6 单向链表 36 3.7 双向链表 41 3.8 循环链表 46 3.9 一种存储高效的双向链表 51 3.10 松散链表 52 3.11 链表的相关问题 55 第4章 栈 72 4.1 什么是栈 72 4.2 如何使用栈 72 4.3 栈抽象数据类型 73 4.4 异常 73 4.5 应用 73 4.6 实现 73 4.7 栈的各种实现方法比较 77 4.8 栈的相关问题 78 第5章 队列 98 5.1 什么是队列 98 5.2 如何使用队列 98 5.3 队列抽象数据类型 99 5.4 异常 99 5.5 应用 99 5.6 实现 99 5.7 队列的相关问题 104 第6章 树 110 6.1 什么是树 110 6.2 术语 110 6.3 二叉树 111 6.4 二叉树的遍历 114 6.5 通用树（N叉树） 135 6.6 线索（无栈或无队列结构）二叉树遍历 141 6.7 表达式树 147 6.8 异或树 149 6.9 二叉搜索树 150 6.10 平衡二叉搜索树 164 6.11 AVL树 165 6.12 树的其他形式 178 6.1 2.1红黑树 178 6.1 2.2伸展树 179 6.1 2.3增强树 179 6.1 2.4替罪羊树 179 6.1 2.5区间树 180 第7章 优先队列和堆 181 7.1 什么是优先队列 181 7.2 优先队列ADT 181 7.3 优先队列的应用 182 7.4 优先队列的实现 182 7.5 堆和二叉堆 183 7.6 二叉堆 184 7.7 优先队列（堆）的相关问题 190 第8章 并查集ADT 201 8.1 引言 201 8.2 等价关系和等价类 201 8.3 并查集ADT 202 8.4 应用 202 8.5 并查集ADT实现中的权衡 202 8.6 快速UNION实现（慢FIND） 203 8.7 快速UNION实现（快速FIND） 206 8.8 路径压缩 208 8.9 小结 209 8.10 并查集的相关问题 209 第9章 图算法 211 9.1 引言 211 9.2 术语 211 9.3 图的应用 214 9.4 图的表示 214 9.5 图的遍历 217 9.6 拓扑排序 225 9.7 最短路径算法 226 9.8 最小生成树 231 9.9 图算法的相关问题 235 第10章 排序 256 10.1 什么是排序 256 10.2 为什么需要排序 256 10.3 排序的分类 256 10.4 其他分类方法 257 10.5 冒泡排序 257 10.6 选择排序 258 10.7 插入排序 259 10.8 希尔排序 261 10.9 归并排序 262 10.10 堆排序 264 10.11 快速排序 264 10.12 树排序 266 10.13 排序算法比较 267 10.14 线性排序算法 267 10.15 计数排序 267 10.16 桶排序 268 10.17 基数排序 268 10.18 拓扑排序 269 10.19 外部排序 269 10.20 排序的相关问题 270 第11章 查找 279 11.1 什么是查找 279 11.2 为什么需要查找 279 11.3 查找的类型 279 11.4 符号表和散列 281 11.5 字符串查找算法 281 11.6 查找的相关问题 281 第12章 选择算法 (中位数) 304 12.1 什么是选择算法 304 12.2 基于排序的选择算法 304 12.3 基于划分的选择算法 304 12.4 线性选择算法——中位数的中位数算法 305 12.5 按照排序顺序查找K个最小元素 305 12.6 选择算法的相关问题 305 第13章 符号表 314 13.1 引言 314 13.2 什么是符号表 314 13.3 符号表的实现 315 13.4 符号表实现方法的比较 315 第14章 散列 317 14.1 什么是散列 317 14.2 为什么用散列 317 14.3 散列表ADT 317 14.4 散列的例子 317 14.5 散列的组成部分 319 14.6 散列表 319 14.7 散列函数 319 14.8 负载因子 320 14.9 冲突 320 14.10 冲突解决技术 320 14.11 分离链接法 320 14.12 开放定址法 321 14.13 冲突解决技术的比较 322 14.14 散列如何达到O(1)的时间复杂度 322 14.15 散列技术 323 14.16 不适用散列表的问题 323 14.17 布鲁姆过滤器 323 14.18 散列的相关问题 325 第15章 字符串算法 335 15.1 引言 335 15.2 字符串匹配算法 335 15.3 蛮力法 336 15.4 Robin-Karp字符串匹配算法 336 15.5 基于有限自动机的字符串匹配算法 337 15.6 KMP算法 338 15.7 Boyce-Moore算法 342 15.8 存储字符串的数据结构 342 15.9 字符串的散列表实现 342 15.10 字符串的二叉搜索树实现 343 15.11 键树 343 15.12 三叉搜索树 345 15.13 二叉搜索树、键树和三叉搜索树的比较 349 15.14 后缀树 349 15.15 字符串的相关问题 353 第16章 算法设计技术 361 16.1 引言 361 16.2 分类 361 16.3 按实现方法分类 361 16.4 按设计方法分类 362 16.5 其他分类法 363 第17章 贪婪算法 364 17.1 引言 364 17.2 贪婪策略的定义 364 17.3 贪婪算法的要素 364 17.4 贪婪算法的适用范围 365 17.5 贪婪算法的优缺点 365 17.6 贪婪算法的应用 365 17.7 贪婪思想 365 17.8 贪婪算法的相关问题 368 第18章 分治算法 375 18.1 引言 375 18.2 分治策略的定义 375 18.3 分治法的适用范围 375 18.4 分治法的图形化描述 375 18.5 分治思想 376 18.6 主定理 377 18.7 分治法的应用 377 18.8 分治法的相关问题 378 第19章 动态规划算法 390 19.1 引言 390 19.2 动态规划策略的定义 390 19.3 动态规划策略的性质 390 19.4 动态规划的适用范围 390 19.5 动态规划的实现方法 391 19.6 动态规划算法的例子 391 19.7 动态规划思想 391 19.8 动态规划的相关问题 396 第20章 复杂度类型 425 20.1 引言 425 20.2 多项式/指数时间 425 20.3 决策问题的定义 426 20.4 决策过程 426 20.5 复杂度类型的定义 426 20.6 复杂度类型 426 20.7 归约 428 20.8 复杂度类型的相关问题 430 第21章 杂谈 433 21.1 引言 433 21.2 位运算的使用 433 21.2.1 按位与操作 433 21.2.2 按位或操作 434 21.2.3 按位异或操作 434 21.2.4 按位左移操作 434 21.2.5 按位右移操作 434 21.2.6 按位补操作 434 21.2.7 检测第K位是否置位 434 21.2.8 第K位置位 435 21.2.9 第K位清零 435 21.2.10 切换第K位 435 21.2.11 切换值为1的最右位 435 21.2.12 隔离值为1的最右位 435 21.2.13 隔离值为0的最右位 435 21.2.14 检查某个数是否是2的幂 436 21.2.15 将某个数乘以2的幂 436 21.2.16 将某个数除以2的幂 436 21.2.17 找到给定操作数的模 436 21.2.18 反转二进制数 436 21.2.19 位值1的计数 436 21.2.20 创建末尾位为0的掩码 437 21.2.21 交换奇偶位 438 21.2.22 不使用除法来计算平均数 438 21.3 其他编程问题 438 参考文献 442

纳拉辛哈•卡鲁曼希（Narasimha Karumanchi）在尼赫鲁科技大学获得计算机科学科技学士学位，在印度理工学院孟买分校获得计算机科学科技硕士学位。他是亚马逊印度公司的软件开发工程师，之前曾就职于IBM和微软公司。他善于用轻松、浅显的方式编写技术书籍，出版了多部著作，其作品在亚马逊上深受好评，目前已被翻译为中文、韩文和日文等。他在各种培训中心和大学教授过数据结构和算法。

暂无其它内容！

暂时还没有人为这本书评论！