关注微信

推荐商品

    加载中... 正在为您读取数据...
分享到:
  • 从算法到程序(附光盘1张)[平装]
  • 共3个商家     43.66元~47.20
  • 作者:徐子珊(作者)
  • 出版社:清华大学出版社;第1版(2013年3月8日)
  • 出版时间:
  • 版次 :
  • 印刷时间:
  • 包装:
  • ISBN:9787302304746

  • 商家报价
  • 简介
  • 评价
  • 加载中... 正在为您读取数据...
  • 商品描述

    编辑推荐

    《从算法到程序:从应用问题编程实践全面体验算法理论》编辑推荐:数学计算为先导,组合优化为主线。算法理论指导下的编程实践码。void型指针引领纯C通用代码,48个应用问题编程实践全面体验算法理论的力量。光盘提供完整源代码。

    作者简介

    徐子珊,男,副教授。数学专业出身,长期从事高校数学、算法和程序设计教学,深受学生喜爱。曾担任ACM/ICPC竞赛教练,指导过多届ITAT竞赛。2003年在复旦大学计算机科学系做国内访问学者,师从国内算法界前辈朱洪教授。2010年曾出版《算法设计、分析与实现》一书,受到读者好评。该书远销中国台湾地区,曾有多人来函索要书中相关代码。2012年出版该书修订版。

    目录

    第1章 计算问题 1
    1.1 计算问题及其算法 1
    1.1.1 计算问题及其描述 1
    1.1.2 算法及其描述 2
    1.1.3 伪代码的使用约定 3
    1.1.4 算法分析 4
    1.1.5 算法运行时间的渐近表示 5
    1.2 数据结构 6
    1.2.1 什么是数据结构 6
    1.2.2 数据结构对算法效率的影响 7
    1.2.3 字典与字典操作 8
    1.3 程序设计 10
    1.3.1 算法与程序 10
    1.3.2 数据类型的抽象与代码通用性 11
    1.4 数据的输入输出 13
    1.4.1 应用问题 13
    1.4.2 标准输入输出 15
    1.4.3 文件输入输出 20
    1.5 计数问题 22
    1.5.1 简单模拟 23
    1.5.2 加法原理和乘法原理 25
    1.5.3 整数序列 31

    第2章 数据结构基础 37
    2.1 线性表 38
    2.1.1 线性表的链表表示 38
    2.1.2 对链表的操作 39
    2.1.3 链表的程序实现 42
    2.1.4 链表应用 47
    2.2 栈 53
    2.2.1 栈的概念及其链表实现 53
    2.2.2 栈的程序实现 54
    2.2.3 栈的应用 56
    2.3 队列 62
    2.3.1 队列的概念及其链表实现 62
    2.3.2 队列的程序实现 63
    2.3.3 队列的应用 64
    2.4 二叉搜索树 68
    2.4.1 二叉树及其在计算机中的表示 68
    2.4.2 二叉搜索树 76
    2.4.3 二叉搜索树的查询操作 76
    2.4.4 二叉搜索树中元素的增删 78
    2.4.5 红-黑树及其性质 80
    2.4.6 红-黑树的操作 83
    2.4.7 红-黑树的程序实现 92
    2.4.8 二叉搜索树的应用 102
    2.5 散列表 102
    2.5.1 直接寻址表与散列表 102
    2.5.2 用拉链解决冲突 104
    2.5.3 散列表的程序实现 106
    2.5.4 散列表的应用 109

    第3章 基本算法设计策略 112
    3.1 渐增型算法 112
    3.1.1 有序序列的合并问题 112
    3.1.2 序列的划分问题 117
    3.2 分治算法 121
    3.2.1 归并排序算法 122
    3.2.2 快速排序算法 126
    3.2.3 序统计与选择问题 130
    3.3 排序问题的讨论 132
    3.3.1 排序的性质 132
    3.3.2 比较型排序算法的时间复杂度 133
    3.3.3 应用 136
    3.4 堆与基于堆的优先队列 141
    3.4.1 堆的概念及其创建 141
    3.4.2 基于二叉堆的优先队列 149
    3.4.3 应用 153

    第4章 代数计算 169
    4.1 矩阵及其计算 169
    4.1.1 矩阵与向量 169
    4.1.2 矩阵的运算 171
    4.1.3 矩阵的性质 173
    4.1.4 矩阵的程序实现 174
    4.2 矩阵的LUP分解 176
    4.2.1 LUP分解法概述 177
    4.2.2 LU分解 178
    4.2.3 计算LUP分解 179
    4.2.4 程序实现 182
    4.3 解线性方程组 183
    4.3.1 前代法和回代法 183
    4.3.2 用LUP分解计算矩阵的逆 185
    4.3.3 程序实现 186
    4.4 多项式及其计算 188
    4.4.1 多项式及其表示 188
    4.4.2 多项式的运算 190
    4.4.3 FFT 191
    4.4.4 程序实现 199
    4.5 应用 204
    4.5.1 多项式的泰勒展开式 204
    4.5.2 完善序列 208
    4.5.3 函数的有理式逼近 211

    第5章 计算几何 218
    5.1 线段的性质 218
    5.1.1 叉积及其应用 219
    5.1.2 向量的极角 222
    5.1.3 程序实现 223
    5.2 判断是否存在线段相交 226
    5.2.1 算法描述与分析 227
    5.2.2 程序实现 230
    5.3 求凸壳 234
    5.3.1 Graham扫描 235
    5.3.2 程序实现 239
    5.4 求最邻近点对 242
    5.4.1 算法描述与分析 242
    5.4.2 程序实现 245
    5.5 应用 248
    5.5.1 光导管 248
    5.5.2 最小边界矩形 255
    5.5.3 德克萨斯一日游 260

    第6章 数论算法 264
    6.1 整数的表示 264
    6.1.1 整数的表示 264
    6.1.2 整数的算术运算 264
    6.1.3 程序实现 269
    6.1.4 应用 275
    6.2 初等数论的概念 277
    6.3 最大公约数 283
    6.3.1 Euclid算法 284
    6.3.2 EUCLID算法的运行时间 284
    6.3.3 Euclid算法的迭代版本 286
    6.3.4 程序实现 287
    6.3.5 应用 289
    6.4 模运算 294
    6.4.1 模加法和乘法 295
    6.4.2 解模线性方程 296
    6.4.3 元素的幂 299
    6.4.4 应用 303
    6.5 素数检测 305
    6.5.1 伪素数检测 305
    6.5.2 Miller-Rabin的随机素数检测 308
    6.5.3 Miller-Rabin素数检测的错误率 310
    6.5.4 程序实现 310
    6.6 整数分解 313
    6.6.1 Pollard的ρ探索法 313
    6.6.2 程序实现 317
    6.6.3 应用 320

    第7章 回溯策略 323
    7.1 组合问题 323
    7.1.1 组合问题的例子 323
    7.1.2 组合问题的形式化描述 325
    7.2 组合问题的回溯算法 326
    7.2.1 解空间的树状结构 326
    7.2.2 解决组合问题的回溯算法 328
    7.2.3 回溯算法的框架 333
    7.3 子集树和排列树 339
    7.3.1 子集树问题 339
    7.3.2 排列树问题 343
    7.3.3 应用 349
    7.4 用回溯算法解决组合优化问题 360
    7.4.1 组合优化问题 360
    7.4.2 用回溯策略解决组合优化问题 362
    7.4.3 应用 365

    第8章 动态规划策 略37
    8.1 组装线调度问题 376
    8.1.1 问题描述 376
    8.1.2 算法设计与分析 378
    8.1.3 应用——牛牛玩牌 381
    8.2 最长公共子序列 386
    8.2.1 问题描述 386
    8.2.2 算法设计与分析 386
    8.2.3 程序实现 389
    8.2.4 应用 390
    8.3 0-1背包问题 398
    8.3.1 问题描述 398
    8.3.2 算法设计与分析 398
    8.3.3 程序实现 401
    8.3.4 应用 402
    8.4 带权有向图中任意两点间的最短路径 409
    8.4.1 问题描述 409
    8.4.2 算法设计与分析 410
    8.4.3 程序实现 413
    8.4.4 应用——牛牛聚会 415

    第9章 贪婪策略 419
    9.1 活动选择问题 419
    9.1.1 算法描述与分析 419
    9.1.2 程序实现 423
    9.1.3 贪婪算法与动态规划 424
    9.1.4 应用——海岸雷达 425
    9.2 Huffman编码 428
    9.2.1 算法描述与分析 428
    9.2.2 应用——R叉Huffman树 433
    9.2.3 程序实现 437
    9.3 最小生成树 443
    9.3.1 算法描述与分析 443
    9.3.2 程序实现 446
    9.3.3 应用——北方通信网 448
    9.4 单源最短路径问题 453
    9.4.1 算法描述与分析 453
    9.4.2 程序实现 456
    9.4.3 应用——西气东送 458

    第10章 图的搜索算法 465
    10.1 深度优先搜索 466
    10.1.1 算法描述与分析 466
    10.1.2 程序实现 469
    10.1.3 有向无圈图的拓扑排序 472
    10.1.4 应用——全排序 478
    10.2 有向图的强连通分支 482
    10.2.1 算法描述与分析 482
    10.2.2 程序实现 486
    10.2.3 应用——亲情号 489
    10.3 无向图的双连通分支 494
    10.3.1 算法描述与分析 494
    10.3.2 程序实现 497
    10.3.3 应用——雌雄大盗 498
    10.4 广度优先搜索 504
    10.4.1 算法描述与分析 504
    10.4.2 程序实现 507
    10.4.3 应用——攻城掠地 508
    10.5 流网络与最大流问题 512
    10.5.1 算法描述与分析 512
    10.5.2 程序实现 521
    10.5.3 应用 523

    第11章 代码实验 528
    11.1 头文件清单 528
    11.1.1 基本应用类函数 528
    11.1.2 数据结构类 531
    11.1.3 代数记算类函数 534
    11.1.4 计算几何类函数 536
    11.1.5 数论计算类函数 537
    11.1.6 回溯搜索类函数 539
    11.1.7 动态规划类函数 540
    11.1.8 贪婪策略类函数 540
    11.1.9 图的搜索类函数 541
    11.2 实验平台的搭建 542
    11.2.1 集成开发环境的安装 542
    11.2.2 实验项目的建立 542
    11.3 应用问题程序的运行实例 544
    11.3.1 加载程序文件 544
    11.3.2 调试程序 545
    11.3.3 各应用问题加载文件清单 546
    11.4 函数库的扩展 554
    11.4.1 向已有的源文件中添加新函数 554
    11.4.2 创建新的源文件 555

    参考文献 557

    序言

    前言
    学科的基本问题和基本方法是学科方法论的基本内容。计算机能解决的仅计算问题而已。什么是计算问题,有哪些典型的计算问题,如何描述计算问题是计算学科的基本问题之一,也是计算机应用的前提。将问题与数据加以形式化表示,并设计处解决计算问题的算法,评价算法的运行效率是计算学科的基本方法。本书的每一章节都围绕着一类或一个计算问题的形式化描述与讨论解决的算法及其分析展开。在开卷之前,先粗线条地向读者描述一下本书。
    内容的组织
    计算问题来自现实世界,现实世界五彩缤纷,计算问题林林种种。本书按典型计算问题的分类来组织各章内容。包括计数问题、代数计算问题、计算几何问题、数论问题、组合优化问题和图的搜索问题。
    计数问题是最古老的但也是人类生活须臾不能离开的计算问题,特别是在现代科技与工业领域存在大量的计数问题。用计算机快速解决计数问题是实至名归。第一章讨论解决计数问题的基础是加法原理和乘法原理的应用。
    为了让读者清醒地看到数据组织方式对算法设计方法及算法运行效率的影响,我们在第二章中浓缩了关于线性表、二叉树、散列表等最基础的几个数据结构。
    数学中的计算问题更是比比皆是。数学问题的算法,例如解线性方程组,计算多项式的变换,线段之间的位置关系等等也是很多信息处理应用问题中经常要用的基本操作。本书用第四~六三章的篇幅讨论代数、几何及数论中的典型计算问题的算法,所用的方法是第三章中介绍的渐增性策略和分治策略。
    在多个可能解中寻求最优解的组合优化问题是计算学科面对的最典型的问题,因为人类的活动几乎都涉及资源的竞争,而有资源竞争就会产生组合优化问题。本书用第七~九章三章的内容来讨论组合优化问题的解决方法。讨论是按从大到小收缩解空间的线索展开。从无约束的回溯策略开始,到加上最优子结构性质及子问题重叠性质后的动态规划策略,解空间越小,算法效率越高。笔者试图以这样的全方位地讨论组合优化问题解决方法的形式,引导读者深入理解启发式解题思想方法。
    我们在第十章讨论了一个描述应用问题的重要数学模型——图。重点讨论了图中顶点的搜索算法。利用搜索算法,讨论了诸如拓扑排序、关节点计算、网络流等几个经典的关于图的应用问题。
    算法研究历史悠久。然而今天,算法理论研究落脚点在于指导计算机程序设计实践。本书讨论的每一个经典算法,均用C语言写成了通用的功能函数,并用这些函数解决了一系列有趣的应用问题。第十一章汇总了这些函数的原型声明及数据结构的定义。
    本书写作上除了上述的内容组织形式上的特点外,还用心于以下几点。
    理论严谨,语言规范
    对每一个问题的算法,从问题的分析开始,包括思路的发展,算法的描述,正确性证明,运行时间的计算都加以详尽讨论,让读者能体验到计算学科的科学严谨性。算法设计与分析以理论繁复著称,笔者试图以朴实的文字和平和的阐述展示对问题的分析,算法步骤的思考和运行时间估算。在确保科学性、正确性的前提下尽量使用与生活语言相近的词语而避免过多生僻的专用术语,让读者在阅读中感受本书的自然亲切。
    理论与实践互动
    笔者对每一个理论算法都给出现有技术的程序实现,用以验证理论算法的正确性。虽然此前已经在理论上证明了算法的正确性,但通过实现了的程序的正确运行进一步证明理论是可行的。并且,算法的程序实现及对测试数据的调试运行能使读者深入理解算法的思想及其中细节微妙之处。对书中的每一个经典算法,均精选了1~2个应用问题,或说明如何直接掉用算法解决该问题,或说明如何运用算法设计的思想解决问题。问题均选自ACM/ICPC的赛题或中国北大的网站http://poj.org/problemlist。
    小步推进,深入浅出
    要设计一个算法来解决的计算问题往往是比较复杂的。对复杂问题的分析以及设计解决问题的算法并对其进行分析,进而实现为程序难免行文比较冗长。为减轻读者阅读疲劳,在保证内容完整性的前提下,适当地将问题分析、算法设计分析以及程序实现复杂过程按一定的内部逻辑分解成若干部分,一步一个小标题。读者可依次一步一步连续阅读,也可分多次,每次阅读一个部分。阅读时可通过小标题明确自己在整个过程中的那一部分,又不失对全局的掌控。
    图文并茂,生动形象
    算法的基础是数学。数学讲的是逻辑思维。然而,逻辑思维并不排斥形象思维。形象思维有时可为逻辑思维深入推进助力。为帮助读者快速且正确地理解抽象概念,或思想方法,或微妙的技术细节,书中在适宜的地方插入很多精心绘制的插图。通过这些插图读者可对书中相应的文字或符号表述的理论、方法或技术内容有生动、形象的认识。
    通用代码,便于引用
    本书中对所有算法的程序实现并非简单地代码堆砌。笔者对所实现的每一个C函数参数与返回值,数据与变量的设置及关键代码都进行了详尽的解析。并且将大多数算法和数据结构写成通用的代码,以光盘的形式向读者提供类似于C++的STL或Java的Collection Framework的通用库,便于读者在工作中或生活中需要时引用。
    为选用本书为算法课程教材的教师朋友,随书光盘中提供了PPT和PDF格式的课件。
    徐子珊 2012.7 记于山城重庆