从算法到程序 作者:徐子珊 编著出版时间:2013年版内容简介 《从算法到程序》第1章讨论算法设计、分析的基本概念,第2章讨论算法设计中最常用的几个数据结构,包括链表、栈、队列、二叉搜索数、散列表等。第3章讨论了算法设计的两个基本策略:渐增策略与分支策略。这3章的内容,为读者阅读本书以后的内容奠定了基础。第4章讨论了几个代数计算的基本问题及其算法,包括矩阵运算、解线性方程组、多项式运算等。第5章讨论了几个关于计算几何的基本问题及其算法,包括线段的相交判断、平面点集的凸包计算、最邻近点对问题等。第6章讨论了关于整数运算的基本问题,包括大整数的表示与运算、最大公约数计算、模运算、素数判定及整数因数分解等。这3章内容为读者深入学习解决各种复杂问题奠定了解决数学计算问题的基础。第7~9章分别用回溯策略、动态规划策略及贪婪策略研究、解决计算机应用面临的最普遍最典型的问题组合优化问题。第10章讨论图的搜索算法及其应用。包括深度优先搜索、拓扑排序、有向图的强连通分支计算、关节点计算、广度优先搜索、网络最大流及二部图的最大匹配等问题。对所有的的经典算法及数据结构,书中给出C语言的实现函数,形成一个通用的函数库,并详尽地加以解析。伴随各种算法的设计、分析及程序实现,书中给出了丰富多彩的应用问题及其解决方案的讨论,并给出了完整的程序代码。所有程序代码都经过反复调试,第十一章介绍这些代码的使用方法。所有代码都以随书光盘的方式提供给读者方便使用。本书无论是对初学算法及程序设计入门大学生读者还是对已经在职场打拼多年的程序员并有着提高自身理论修养及技术水平愿望的读者都有着开卷有益的意义。目录第1章计算问题11.1计算问题及其算法11.1.1计算问题及其描述11.1.2算法及其描述21.1.3伪代码的使用约定31.1.4算法分析41.1.5算法运行时间的渐近表示51.2数据结构61.2.1什么是数据结构61.2.2数据结构对算法效率的影响71.2.3字典与字典操作81.3程序设计101.3.1算法与程序101.3.2数据类型的抽象与代码通用性111.4数据的输入输出131.4.1应用问题131.4.2标准输入输出151.4.3文件输入输出201.5计数问题221.5.1简单模拟231.5.2加法原理和乘法原理251.5.3整数序列31第2章数据结构基础372.1线性表382.1.1线性表的链表表示382.1.2对链表的操作392.1.3链表的程序实现422.1.4链表应用472.2栈532.2.1栈的概念及其链表实现532.2.2栈的程序实现542.2.3栈的应用562.3队列622.3.1队列的概念及其链表实现622.3.2队列的程序实现632.3.3队列的应用642.4二叉搜索树682.4.1二叉树及其在计算机中的表示682.4.2二叉搜索树762.4.3二叉搜索树的查询操作762.4.4二叉搜索树中元素的增删782.4.5红?黑树及其性质802.4.6红?黑树的操作832.4.7红?黑树的程序实现922.4.8二叉搜索树的应用1022.5散列表1022.5.1直接寻址表与散列表1022.5.2用拉链解决冲突1042.5.3散列表的程序实现1062.5.4散列表的应用109第3章基本算法设计策略1123.1渐增型算法1123.1.1有序序列的合并问题112 3.1.2序列的划分问题117 3.2分治算法1213.2.1归并排序算法1223.2.2快速排序算法1263.2.3序统计与选择问题1303.3排序问题的讨论1323.3.1排序的性质1323.3.2比较型排序算法的时间复杂度1333.3.3应用1363.4堆与基于堆的优先队列1413.4.1堆的概念及其创建1413.4.2基于二叉堆的优先队列1493.4.3应用153第4章代数计算1694.1矩阵及其计算1694.1.1矩阵与向量1694.1.2矩阵的运算1714.1.3矩阵的性质1734.1.4矩阵的程序实现1744.2矩阵的LUP分解1764.2.1LUP分解法概述1774.2.2LU分解1784.2.3计算LUP分解1794.2.4程序实现1824.3解线性方程组1834.3.1前代法和回代法1834.3.2用LUP分解计算矩阵的逆1854.3.3程序实现1864.4多项式及其计算1884.4.1多项式及其表示1884.4.2多项式的运算1904.4.3FFT1914.4.4程序实现1994.5应用2044.5.1多项式的泰勒展开式2044.5.2完善序列2084.5.3函数的有理式逼近211第5章计算几何2185.1线段的性质2185.1.1叉积及其应用2195.1.2向量的极角2225.1.3程序实现2235.2判断是否存在线段相交2265.2.1算法描述与分析2275.2.2程序实现2305.3求凸壳2345.3.1Graham扫描2355.3.2程序实现2395.4求最邻近点对2425.4.1算法描述与分析2425.4.2程序实现2455.5应用2485.5.1光导管2485.5.2最小边界矩形2555.5.3德克萨斯一日游260第6章数论算法2646.1整数的表示2646.1.1整数的表示2646.1.2整数的算术运算2646.1.3程序实现2696.1.4应用2756.2初等数论的概念2776.3最大公约数2836.3.1Euclid算法2846.3.2EUCLID算法的运行时间2846.3.3Euclid算法的迭代版本2866.3.4程序实现2876.3.5应用2896.4模运算2946.4.1模加法和乘法2956.4.2解模线性方程2966.4.3元素的幂2996.4.4应用3036.5素数检测3056.5.1伪素数检测3056.5.2Miller?Rabin的随机素数检测3086.5.3Miller?Rabin素数检测的错误率3106.5.4程序实现3106.6整数分解3136.6.1Pollard的ρ探索法3136.6.2程序实现3176.6.3应用320第7章回溯策略3237.1组合问题3237.1.1组合问题的例子3237.1.2组合问题的形式化描述3257.2组合问题的回溯算法3267.2.1解空间的树状结构3267.2.2解决组合问题的回溯算法3287.2.3回溯算法的框架3337.3子集树和排列树3397.3.1子集树问题3397.3.2排列树问题3437.3.3应用3497.4用回溯算法解决组合优化问题3607.4.1组合优化问题3607.4.2用回溯策略解决组合优化问题3627.4.3应用365第8章动态规划策略378.1组装线调度问题3768.1.1问题描述3768.1.2算法设计与分析3788.1.3应用——牛牛玩牌3818.2最长公共子序列3868.2.1问题描述3868.2.2算法设计与分析3868.2.3程序实现3898.2.4应用3908.30?1背包问题3988.3.1问题描述3988.3.2算法设计与分析3988.3.3程序实现4018.3.4应用4028.4带权有向图中任意两点间的最短路径4098.4.1问题描述4098.4.2算法设计与分析4108.4.3程序实现4138.4.4应用——牛牛聚会415第9章贪婪策略4199.1活动选择问题4199.1.1算法描述与分析4199.1.2程序实现4239.1.3贪婪算法与动态规划4249.1.4应用——海岸雷达4259.2Huffman编码4289.2.1算法描述与分析4289.2.2应用——R叉Huffman树4339.2.3程序实现4379.3最小生成树4439.3.1算法描述与分析4439.3.2程序实现4469.3.3应用——北方通信网4489.4单源最短路径问题4539.4.1算法描述与分析4539.4.2程序实现4569.4.3应用——西气东送458第10章图的搜索算法46510.1深度优先搜索46610.1.1算法描述与分析46610.1.2程序实现46910.1.3有向无圈图的拓扑排序47210.1.4应用——全排序47810.2有向图的强连通分支48210.2.1算法描述与分析48210.2.2程序实现48610.2.3应用——亲情号48910.3无向图的双连通分支49410.3.1算法描述与分析49410.3.2程序实现49710.3.3应用——雌雄大盗49810.4广度优先搜索50410.4.1算法描述与分析50410.4.2程序实现50710.4.3应用——攻城掠地50810.5流网络与最大流问题51210.5.1算法描述与分析51210.5.2程序实现52110.5.3应用523第11章代码实验52811.1头文件清单52811.1.1基本应用类函数52811.1.2数据结构类53111.1.3代数记算类函数53411.1.4计算几何类函数53611.1.5数论计算类函数53711.1.6回溯搜索类函数53911.1.7动态规划类函数54011.1.8贪婪策略类函数54011.1.9图的搜索类函数54111.2实验平台的搭建54211.2.1集成开发环境的安装54211.2.2实验项目的建立54211.3应用问题程序的运行实例54411.3.1加载程序文件54411.3.2调试程序54511.3.3各应用问题加载文件清单54611.4函数库的扩展55411.4.1向已有的源文件中添加新函数55411.4.2创建新的源文件555参考文献557 上一篇: 新编中文Windows 2000学习捷径 张军安 主编 2002年版 下一篇: 信息与计算科学丛书 广义逆的符号模式 [卜长江,魏益民 著] 2014年版