《我的第一本算法书(图灵图书) (Chinese Edition)》
作者:石田保辉,宮崎修一
序章 算法的基本知识
108
选 择 排 序第 1 章 数据结构
210
N o . 1 1 什 么 是 数 据 结 构 决 定 了 数 据 的 顺 序 和 位 置 关 系396
栈 这 种 最 后 添 加 的 数 据 最 先 被 取 出 , 即 “ 后 进 先 出 ” 的 结 构 , 我 们 称 为 L a s t I n F i r s t O u t , 简 称 L I F O 。397
与 链 表 和 数 组 一 样 , 栈 的 数 据 也 是 线 性 排 列407
队 列 中 的 数 据 也 呈 线 性 排 列419
队 列 这 种 最 先 进 去 的 数 据 最 先 被 取 来 , 即 “ 先 进 先 出 ” 的 结 构 , 我 们 称 为 F i r s t I n F i r s t O u t , 简 称 F I F O 。427
哈 希 表430
哈 希 表 存 储 的 是 由 键 ( k e y ) 和 值 ( v a l u e ) 组 成 的 数 据465
存 储 位 置 重 复 了 的 情 况 便 叫 作 “ 冲 突 ”489
在 哈 希 表 中 , 我 们 可 以 利 用 哈 希 函 数 快 速 访 问 到 数 组 中 的 目 标 数 据 。 如 果 发 生 哈 希 冲 突 , 就 使 用 链 表 进 行 存 储 。 这 样 一 来 , 不 管 数 据 量 为 多 少 , 我 们 都 能 够 灵 活 应 对494
存 储 数 据 的 过 程 中 , 如 果 发 生 冲 突 , 可 以 利 用 链 表 在 已 有 数 据 的 后 面 插 入 新 数 据 来 解 决 冲 突 。 这 种 方 法 被 称 为 “ 链 地 址 法 ”501
因 为 哈 希 表 在 数 据 存 储 上 的 灵 活 性 和 数 据 查 询 上 的 高 效 性 , 编 程 语 言 的 关 联 数 组 等 也 常 常 会 使 用 它502
堆 是 一 种 图 的 树 形 结 构 , 被 用 于 实 现 “ 优 先 队 列 ”503
优 先 队 列 是 一 种 数 据 结 构 , 可 以 自 由 添 加 数 据 , 但 取 出 数 据 时 要 从 最 小 值 开 始 按 顺 序 取 出 。510
堆 中 存 储 数 据 时 必 须 遵 守 这 样 一 条 规 则 : 子 结 点 必 定 大 于 父 结 点 。539
堆 中 最 顶 端 的 数 据 始 终 最 小 , 所 以 无 论 数 据 量 有 多 少 , 取 出 最 小 值 的 时 间 复 杂 度 都 为 。541
所 以 取 出 数 据 需 要 的 运 行 时 间 和 树 的 高 度 成 正 比 。 假 设 数 据 量 为 , 根 据 堆 的 形 状 特 点 可 知 树 的 高 度 为 , 那 么 重 构 树 的 时 间 复 杂 度 便 为 。548
狄 克 斯 特 拉 算 法 , 每 一 步 都 需 要 从 候 补 顶 点 中 选 择 距 离 起 点 最 近 的 那 个 顶 点 。 此 时 , 在 顶 点 的 选 择 上 就 可 以 用 到 堆 。550
二 叉 查 找 树 ( 又 叫 作 二 叉 搜 索 树 或 二 叉 排 序 树 ) 是 一 种 数 据 结 构 , 采 用 了 图 的 树 形 结 构 ( 关 于 树 形 结 构 的 详 细 说 明 请 参 考 4 2 节 ) 。 数 据 存 储 于 二 叉 查 找 树 的 各 个 结 点 中557
二 叉 查 找 树 有 两 个 性 质 。 第 一 个 是 每 个 结 点 的 值 均 大 于 其 左 子 树 上 任 意 一 个 结 点 的 值561
第 二 个 是 每 个 结 点 的 值 均 小 于 其 右 子 树 上 任 意 一 个 结 点 的 值
第 2 章 排序692
冒 泡 排 序722
选 择 排 序744
插 入 排 序 是 一 种 从 序 列 左 端 开 始 依 次 对 数 据 进 行 排 序 的 算777
堆 排 序 的 特 点 是 利 用 了 数 据 结 构 中 的 堆809
归 并 排 序 算 法 会 把 序 列 分 成 长 度 相 同 的 两 个 子 序 列 , 当 无 法 继 续 往 下 分 时 ( 也 就 是 每 个 子 序 列 中 只 有 一 个 数 据 时 ) , 就 对 子 序 列 进 行 归 并 。 归 并 指 的 是 把 两 个 排 好 序 的 子 序 列 合 并 成 一 个 有 序 序 列845
快 速 排 序 算 法 首 先 会 在 序 列 中 随 机 选 择 一 个 基 准 值 ( p i v o t ) , 然 后 将 除 了 基 准 值 以 外 的 数 分 为 “ 比 基 准 值 小 的 数 ” 和 “ 比 基 准 值 大 的 数 ” 这 两 个 类 别 , 再 将 其 排 列 成 以 下 形 式885
快 速 排 序 是 一 种 “ 分 治 法 ”
第 3 章 数组的查找904
线 性 查 找 是 一 种 在 数 组 中 查 找 数 据 的 算 法919
二 分 查 找 也 是 一 种 在 数 组 中 查 找 数 据 的 算 法
###第 4 章 图的搜索1027
深 度 优 先 搜 索1060
贝 尔 曼 福 特 ( B e l l m a n F o r d ) 算 法 是 一 种 在 图 中 求 解 最 短 路 径 问 题 的 算 法1117
, 狄 克 斯 特 拉 ( D i j k s t r a ) 算 法 也 是 求 解 最 短 路 径 问 题 的 算 法 , 使 用 它 可 以 求 得 从 起 点 到 终 点 的 路 径 中 权 重 总 和 最 小 的 那 条 路 径 路 径1182
A * ( A S t a r ) 算 法 也 是 一 种 在 图 中 求 解 最 短 路 径 问 题 的 算 法 , 由 狄 克 斯 特 拉 算 法 发 展 而 来
第 5 章 安全算法1288
哈 希 函 数第 7 章 其他算法
1775
欧 几 里 得 算 法 ( 又 称 辗 转 相 除 法 ) 用 于 计 算 两 个 数 的 最 大 公 约 数 , 被 称 为 世 界 上 最 古 老 的 算 法1822
费 马 测 试 被 称 为 概 率 性 素 性 测 试 , 它 判 断 的 是 “ 某 个 数 是 素 数 的 概 率 大 不 大 ” 。1833
“ 费 马 小 定 理 ”1843
的 “ 米 勒 拉 宾 ( M i l l e r R a b i n ) 素 性 测 试 ” 。 用 这 个 方 法 重 复 进 行 测 试 后 , 当 数 不 是 素 数 的 概 率 小 于 时 , 就 可 以 大 致 判 断 该 数 为 素 数 。1851
“ 卡 迈 克 尔 数 ” ( C a r m i c h a e l n u m b e r s ) , 也 叫 “ 绝 对 伪 素 数 ”1856
“ A K S 算 法1858
网 页 排 名 ( P a g e R a n k , 也 叫 作 佩 奇 排 名 ) 是 一 种 在 搜 索 网 页 时 对 搜 索 结 果 进 行 排 序 的 算 法 。1880
随 机 游 走 模 型 ” ( r a n d o m w a l k m o d e l )1927
汉诺塔
总结
本书结合大量的图解详细的解析了各种算法的渐进演变。
适合人群:了解算法但不了解算法里常用的名词
复习指数:#