从算法到程序

作者: 徐子珊著

出版社: 清华大学出版社

出版时间: 2013-03

版次: 1

ISBN: 9787302304746

定价: 59.00

装帧: 平装

开本: 16开

纸张: 胶版纸

页数: 572页

字数: 867千字

正文语种: 简体中文

分类: 计算机与互联网

　　《从算法到程序》第1章讨论算法设计、分析的基本概念，第2章讨论算法设计中最常用的几个数据结构，包括链表、栈、队列、二叉搜索数、散列表等。第3章讨论了算法设计的两个基本策略：渐增策略与分支策略。这3章的内容，为读者阅读本书以后的内容奠定了基础。第4章讨论了几个代数计算的基本问题及其算法，包括矩阵运算、解线性方程组、多项式运算等。第5章讨论了几个关于计算几何的基本问题及其算法，包括线段的相交判断、平面点集的凸包计算、最邻近点对问题等。第6章讨论了关于整数运算的基本问题，包括大整数的表示与运算、最大公约数计算、模运算、素数判定及整数因数分解等。这3章内容为读者深入学习解决各种复杂问题奠定了解决数学计算问题的基础。第7~9章分别用回溯策略、动态规划策略及贪婪策略研究、解决计算机应用面临的最普遍最典型的问题组合优化问题。第10章讨论图的搜索算法及其应用。包括深度优先搜索、拓扑排序、有向图的强连通分支计算、关节点计算、广度优先搜索、网络最大流及二部图的最大匹配等问题。对所有的的经典算法及数据结构，书中给出C语言的实现函数，形成一个通用的函数库，并详尽地加以解析。伴随各种算法的设计、分析及程序实现，书中给出了丰富多彩的应用问题及其解决方案的讨论，并给出了完整的程序代码。所有程序代码都经过反复调试，第十一章介绍这些代码的使用方法。所有代码都以随书光盘的方式提供给读者方便使用。本书无论是对初学算法及程序设计入门大学生读者还是对已经在职场打拼多年的程序员并有着提高自身理论修养及技术水平愿望的读者都有着开卷有益的意义。　　徐子珊，男，副教授。数学专业出身，长期从事高校数学、算法和程序设计教学，深受学生喜爱。曾担任ACM/ICPC竞赛教练，指导过多届ITAT竞赛。2003年在复旦大学计算机科学系做国内访问学者，师从国内算法界前辈朱洪教授。2010年曾出版《算法设计、分析与实现》一书，受到读者好评。该书远销中国台湾地区，曾有多人来函索要书中相关代码。2012年出版该书修订版。
第1章计算问题
1.1计算问题及其算法
1.1.1计算问题及其描述
1.1.2算法及其描述
1.1.3伪代码的使用约定
1.1.4算法分析
1.1.5算法运行时间的渐近表示
1.2数据结构
1.2.1什么是数据结构
1.2.2数据结构对算法效率的影响
1.2.3字典与字典操作
1.3程序设计
1.3.1算法与程序
1.3.2数据类型的抽象与代码通用性
1.4数据的输入输出
1.4.1应用问题
1.4.2标准输入输出
1.4.3文件输入输出
1.5计数问题
1.5.1简单模拟
1.5.2加法原理和乘法原理
1.5.3整数序列
第2章数据结构基础
2.1线性表
2.1.1线性表的链表表示
2.1.2对链表的操作
2.1.3链表的程序实现
2.1.4链表应用
2.2栈
2.2.1栈的概念及其链表实现
2.2.2栈的程序实现
2.2.3栈的应用
2.3队列
2.3.1队列的概念及其链表实现
2.3.2队列的程序实现
2.3.3队列的应用
2.4二叉搜索树
2.4.1二叉树及其在计算机中的表示
2.4.2二叉搜索树
2.4.3二叉搜索树的查询操作
2.4.4二叉搜索树中元素的增删
2.4.5红黑树及其性质
2.4.6红黑树的操作
2.4.7红黑树的程序实现
2.4.8二叉搜索树的应用
2.5散列表
2.5.1直接寻址表与散列表
2.5.2用拉链解决冲突
2.5.3散列表的程序实现
2.5.4散列表的应用
第3章基本算法设计策略
3.1渐增型算法
3.1.1有序序列的合并问题
3.1.2序列的划分问题
3.2分治算法
3.2.1归并排序算法
3.2.2快速排序算法
3.2.3序统计与选择问题
3.3排序问题的讨论
3.3.1排序的性质
3.3.2比较型排序算法的时间复杂度
3.3.3应用
3.4堆与基于堆的优先队列
3.4.1堆的概念及其创建
3.4.2基于二叉堆的优先队列
3.4.3应用
第4章代数计算
4.1矩阵及其计算
4.1.1矩阵与向量
4.1.2矩阵的运算
4.1.3矩阵的性质
4.1.4矩阵的程序实现
4.2矩阵的LUP分解
4.2.1LUP分解法概述
4.2.2LU分解
4.2.3计算LUP分解
4.2.4程序实现
4.3解线性方程组
4.3.1前代法和回代法
4.3.2用LUP分解计算矩阵的逆
4.3.3程序实现
4.4多项式及其计算
4.4.1多项式及其表示
4.4.2多项式的运算
4.4.3FFT
4.4.4程序实现
4.5应用
4.5.1多项式的泰勒展开式
4.5.2完善序列
4.5.3函数的有理式逼近
第5章计算几何
5.1线段的性质
5.1.1叉积及其应用
5.1.2向量的极角
5.1.3程序实现
5.2判断是否存在线段相交
5.2.1算法描述与分析
5.2.2程序实现
5.3求凸壳
5.3.1Graham扫描
5.3.2程序实现
5.4求最邻近点对
5.4.1算法描述与分析
5.4.2程序实现
5.5应用
5.5.1光导管
5.5.2最小边界矩形
5.5.3德克萨斯一日游
第6章数论算法
6.1整数的表示
6.1.1整数的表示
6.1.2整数的算术运算
6.1.3程序实现
6.1.4应用
6.2初等数论的概念
6.3最大公约数
6.3.1Euclid算法
6.3.2EUCLID算法的运行时间
6.3.3Euclid算法的迭代版本
6.3.4程序实现
6.3.5应用
6.4模运算
6.4.1模加法和乘法
6.4.2解模线性方程
6.4.3元素的幂
6.4.4应用
6.5素数检测
6.5.1伪素数检测
6.5.2MillerRabin的随机素数检测
6.5.3MillerRabin素数检测的错误率
6.5.4程序实现
6.6整数分解
6.6.1Pollard的ρ探索法
6.6.2程序实现
6.6.3应用
第7章回溯策略
7.1组合问题
7.1.1组合问题的例子
7.1.2组合问题的形式化描述
7.2组合问题的回溯算法
7.2.1解空间的树状结构
7.2.2解决组合问题的回溯算法
7.2.3回溯算法的框架
7.3子集树和排列树
7.3.1子集树问题
7.3.2排列树问题
7.3.3应用
7.4用回溯算法解决组合优化问题
7.4.1组合优化问题
7.4.2用回溯策略解决组合优化问题
7.4.3应用
第8章动态规划策略
8.1组装线调度问题
8.1.1问题描述
8.1.2算法设计与分析
8.1.3应用--牛牛玩牌
8.2最长公共子序列
8.2.1问题描述
8.2.2算法设计与分析
8.2.3程序实现
8.2.4应用
8.301背包问题
8.3.1问题描述
8.3.2算法设计与分析
8.3.3程序实现
8.3.4应用
8.4带权有向图中任意两点间的最短路径
8.4.1问题描述
8.4.2算法设计与分析
8.4.3程序实现
8.4.4应用--牛牛聚会
第9章贪婪策略
9.1活动选择问题
9.1.1算法描述与分析
9.1.2程序实现
9.1.3贪婪算法与动态规划
9.1.4应用--海岸雷达
9.2Huffman编码
9.2.1算法描述与分析
9.2.2应用--R叉Huffman树
9.2.3程序实现
9.3最小生成树
9.3.1算法描述与分析
9.3.2程序实现
9.3.3应用--北方通信网
9.4单源最短路径问题
9.4.1算法描述与分析
9.4.2程序实现
9.4.3应用--西气东送
第10章图的搜索算法
10.1深度优先搜索
10.1.1算法描述与分析
10.1.2程序实现
10.1.3有向无圈图的拓扑排序
10.1.4应用--全排序
10.2有向图的强连通分支
10.2.1算法描述与分析
10.2.2程序实现
10.2.3应用--亲情号
10.3无向图的双连通分支
10.3.1算法描述与分析
10.3.2程序实现
10.3.3应用--雌雄大盗
10.4广度优先搜索
10.4.1算法描述与分析
10.4.2程序实现
10.4.3应用--攻城掠地
10.5流网络与最大流问题
10.5.1算法描述与分析
10.5.2程序实现
10.5.3应用
第11章代码实验
11.1头文件清单
11.1.1基本应用类函数
11.1.2数据结构类
11.1.3代数记算类函数
11.1.4计算几何类函数
11.1.5数论计算类函数
11.1.6回溯搜索类函数
11.1.7动态规划类函数
11.1.8贪婪策略类函数
11.1.9图的搜索类函数
11.2实验平台的搭建
11.2.1集成开发环境的安装
11.2.2实验项目的建立
11.3应用问题程序的运行实例
11.3.1加载程序文件
11.3.2调试程序
11.3.3各应用问题加载文件清单
11.4函数库的扩展
11.4.1向已有的源文件中添加新函数
11.4.2创建新的源文件
参考文献
内容简介:
　　《从算法到程序》第1章讨论算法设计、分析的基本概念，第2章讨论算法设计中最常用的几个数据结构，包括链表、栈、队列、二叉搜索数、散列表等。第3章讨论了算法设计的两个基本策略：渐增策略与分支策略。这3章的内容，为读者阅读本书以后的内容奠定了基础。第4章讨论了几个代数计算的基本问题及其算法，包括矩阵运算、解线性方程组、多项式运算等。第5章讨论了几个关于计算几何的基本问题及其算法，包括线段的相交判断、平面点集的凸包计算、最邻近点对问题等。第6章讨论了关于整数运算的基本问题，包括大整数的表示与运算、最大公约数计算、模运算、素数判定及整数因数分解等。这3章内容为读者深入学习解决各种复杂问题奠定了解决数学计算问题的基础。第7~9章分别用回溯策略、动态规划策略及贪婪策略研究、解决计算机应用面临的最普遍最典型的问题组合优化问题。第10章讨论图的搜索算法及其应用。包括深度优先搜索、拓扑排序、有向图的强连通分支计算、关节点计算、广度优先搜索、网络最大流及二部图的最大匹配等问题。对所有的的经典算法及数据结构，书中给出C语言的实现函数，形成一个通用的函数库，并详尽地加以解析。伴随各种算法的设计、分析及程序实现，书中给出了丰富多彩的应用问题及其解决方案的讨论，并给出了完整的程序代码。所有程序代码都经过反复调试，第十一章介绍这些代码的使用方法。所有代码都以随书光盘的方式提供给读者方便使用。本书无论是对初学算法及程序设计入门大学生读者还是对已经在职场打拼多年的程序员并有着提高自身理论修养及技术水平愿望的读者都有着开卷有益的意义。
作者简介:
　　徐子珊，男，副教授。数学专业出身，长期从事高校数学、算法和程序设计教学，深受学生喜爱。曾担任ACM/ICPC竞赛教练，指导过多届ITAT竞赛。2003年在复旦大学计算机科学系做国内访问学者，师从国内算法界前辈朱洪教授。2010年曾出版《算法设计、分析与实现》一书，受到读者好评。该书远销中国台湾地区，曾有多人来函索要书中相关代码。2012年出版该书修订版。
目录:
第1章计算问题
1.1计算问题及其算法
1.1.1计算问题及其描述
1.1.2算法及其描述
1.1.3伪代码的使用约定
1.1.4算法分析
1.1.5算法运行时间的渐近表示
1.2数据结构
1.2.1什么是数据结构
1.2.2数据结构对算法效率的影响
1.2.3字典与字典操作
1.3程序设计
1.3.1算法与程序
1.3.2数据类型的抽象与代码通用性
1.4数据的输入输出
1.4.1应用问题
1.4.2标准输入输出
1.4.3文件输入输出
1.5计数问题
1.5.1简单模拟
1.5.2加法原理和乘法原理
1.5.3整数序列
第2章数据结构基础
2.1线性表
2.1.1线性表的链表表示
2.1.2对链表的操作
2.1.3链表的程序实现
2.1.4链表应用
2.2栈
2.2.1栈的概念及其链表实现
2.2.2栈的程序实现
2.2.3栈的应用
2.3队列
2.3.1队列的概念及其链表实现
2.3.2队列的程序实现
2.3.3队列的应用
2.4二叉搜索树
2.4.1二叉树及其在计算机中的表示
2.4.2二叉搜索树
2.4.3二叉搜索树的查询操作
2.4.4二叉搜索树中元素的增删
2.4.5红黑树及其性质
2.4.6红黑树的操作
2.4.7红黑树的程序实现
2.4.8二叉搜索树的应用
2.5散列表
2.5.1直接寻址表与散列表
2.5.2用拉链解决冲突
2.5.3散列表的程序实现
2.5.4散列表的应用
第3章基本算法设计策略
3.1渐增型算法
3.1.1有序序列的合并问题
3.1.2序列的划分问题
3.2分治算法
3.2.1归并排序算法
3.2.2快速排序算法
3.2.3序统计与选择问题
3.3排序问题的讨论
3.3.1排序的性质
3.3.2比较型排序算法的时间复杂度
3.3.3应用
3.4堆与基于堆的优先队列
3.4.1堆的概念及其创建
3.4.2基于二叉堆的优先队列
3.4.3应用
第4章代数计算
4.1矩阵及其计算
4.1.1矩阵与向量
4.1.2矩阵的运算
4.1.3矩阵的性质
4.1.4矩阵的程序实现
4.2矩阵的LUP分解
4.2.1LUP分解法概述
4.2.2LU分解
4.2.3计算LUP分解
4.2.4程序实现
4.3解线性方程组
4.3.1前代法和回代法
4.3.2用LUP分解计算矩阵的逆
4.3.3程序实现
4.4多项式及其计算
4.4.1多项式及其表示
4.4.2多项式的运算
4.4.3FFT
4.4.4程序实现
4.5应用
4.5.1多项式的泰勒展开式
4.5.2完善序列
4.5.3函数的有理式逼近
第5章计算几何
5.1线段的性质
5.1.1叉积及其应用
5.1.2向量的极角
5.1.3程序实现
5.2判断是否存在线段相交
5.2.1算法描述与分析
5.2.2程序实现
5.3求凸壳
5.3.1Graham扫描
5.3.2程序实现
5.4求最邻近点对
5.4.1算法描述与分析
5.4.2程序实现
5.5应用
5.5.1光导管
5.5.2最小边界矩形
5.5.3德克萨斯一日游
第6章数论算法
6.1整数的表示
6.1.1整数的表示
6.1.2整数的算术运算
6.1.3程序实现
6.1.4应用
6.2初等数论的概念
6.3最大公约数
6.3.1Euclid算法
6.3.2EUCLID算法的运行时间
6.3.3Euclid算法的迭代版本
6.3.4程序实现
6.3.5应用
6.4模运算
6.4.1模加法和乘法
6.4.2解模线性方程
6.4.3元素的幂
6.4.4应用
6.5素数检测
6.5.1伪素数检测
6.5.2MillerRabin的随机素数检测
6.5.3MillerRabin素数检测的错误率
6.5.4程序实现
6.6整数分解
6.6.1Pollard的ρ探索法
6.6.2程序实现
6.6.3应用
第7章回溯策略
7.1组合问题
7.1.1组合问题的例子
7.1.2组合问题的形式化描述
7.2组合问题的回溯算法
7.2.1解空间的树状结构
7.2.2解决组合问题的回溯算法
7.2.3回溯算法的框架
7.3子集树和排列树
7.3.1子集树问题
7.3.2排列树问题
7.3.3应用
7.4用回溯算法解决组合优化问题
7.4.1组合优化问题
7.4.2用回溯策略解决组合优化问题
7.4.3应用
第8章动态规划策略
8.1组装线调度问题
8.1.1问题描述
8.1.2算法设计与分析
8.1.3应用--牛牛玩牌
8.2最长公共子序列
8.2.1问题描述
8.2.2算法设计与分析
8.2.3程序实现
8.2.4应用
8.301背包问题
8.3.1问题描述
8.3.2算法设计与分析
8.3.3程序实现
8.3.4应用
8.4带权有向图中任意两点间的最短路径
8.4.1问题描述
8.4.2算法设计与分析
8.4.3程序实现
8.4.4应用--牛牛聚会
第9章贪婪策略
9.1活动选择问题
9.1.1算法描述与分析
9.1.2程序实现
9.1.3贪婪算法与动态规划
9.1.4应用--海岸雷达
9.2Huffman编码
9.2.1算法描述与分析
9.2.2应用--R叉Huffman树
9.2.3程序实现
9.3最小生成树
9.3.1算法描述与分析
9.3.2程序实现
9.3.3应用--北方通信网
9.4单源最短路径问题
9.4.1算法描述与分析
9.4.2程序实现
9.4.3应用--西气东送
第10章图的搜索算法
10.1深度优先搜索
10.1.1算法描述与分析
10.1.2程序实现
10.1.3有向无圈图的拓扑排序
10.1.4应用--全排序
10.2有向图的强连通分支
10.2.1算法描述与分析
10.2.2程序实现
10.2.3应用--亲情号
10.3无向图的双连通分支
10.3.1算法描述与分析
10.3.2程序实现
10.3.3应用--雌雄大盗
10.4广度优先搜索
10.4.1算法描述与分析
10.4.2程序实现
10.4.3应用--攻城掠地
10.5流网络与最大流问题
10.5.1算法描述与分析
10.5.2程序实现
10.5.3应用
第11章代码实验
11.1头文件清单
11.1.1基本应用类函数
11.1.2数据结构类
11.1.3代数记算类函数
11.1.4计算几何类函数
11.1.5数论计算类函数
11.1.6回溯搜索类函数
11.1.7动态规划类函数
11.1.8贪婪策略类函数
11.1.9图的搜索类函数
11.2实验平台的搭建
11.2.1集成开发环境的安装
11.2.2实验项目的建立
11.3应用问题程序的运行实例
11.3.1加载程序文件
11.3.2调试程序
11.3.3各应用问题加载文件清单
11.4函数库的扩展
11.4.1向已有的源文件中添加新函数
11.4.2创建新的源文件
参考文献

查看详情

从算法到程序

内容简介:

作者简介:

目录: