算法分析与设计
2010-9
北京交通大学
石志国//刘冀伟//姚亦飞
234
算法分析与设计是一门重要课程。算法设计在各类科学计算中具有核心地位和作用，没有好的算法，计算机完成一件工作可能需要很长时间，而有好算法，完成一件工作可能仅需要几秒。同时，算法被公认为是计算科学的基石，翻开重要的学术刊物，算法都占有一席之地，没有算法，程序将不复存在。1.体系介绍算法是一门方法论方面的课程，方法论是人们认识世界、改造世界的一般方法，是人们用什么样的方式、方法来观察事物和处理问题的一般依据。在哲学上，世界观主要解决世界“是什么”的问题，方法论主要解决“怎么办”的问题。在科学计算方面，算法也是解决“怎么办”的问题。作为一门方法论的课程，主要讲解一些普适的、抽象的解决问题的方法。从认知角度来讲，对于抽象内容需要一些具体实际的例子来帮助消化吸收，否则知识将变得非常空泛。目前，算法分析与设计方面的图书从来源上可以分成两类：国内图书和国外引进。从内容上也可以分成两类：单纯讲解算法和同时讲解数据结构与算法，总体内容上几乎没有太大的区别。从算法描述上，主要以采用C／C++和Java语言描述居多，以程序实现算法框架为主，完整的算法实现的实例相对较少，这使得算法课程成为一门理论性较强的课程。编者对国内众多专业课程进行了调研，考虑到读者前期一般具有c或者C++语言基础，Java语言大多是高年级以后以选修课程的形式开设，而算法课程开设的时间一般早于Java语言，因此选择C／C++语言描述。编写算法对语言要求相对较高，涉及面的也广，因此安排一章对C++算法设计进行介绍。并在此基础上介绍了线性、非线性数据结构和排序搜索算法设计，最后详细介绍了目前算法中被称为“五虎上将”的分治法、贪心法、动态规划、回溯法和分支限界法，同时对于每一种算法都列举了几个完整的实例。
本书以程序设计作为基础、数据结构作为工具、五大核心算法作为目标，系统地介绍了算法设计中典型问题的求解过程。 全书分成程序设计基础、数据结构和五大核心算法3个部分共10章。第1部分为算法分析与程序设计基础，介绍了算法分析的时间和空间复杂度，以及C++算法相关的程序设计基础；第2部分为算法设计数据结构基础，介绍了线性和非线性数据结构基础，同时对常用的排序和搜索算法作了详细介绍；第3部分为典型算法分析与问题求解，介绍了经典算法设计中的“五虎上将”：分治法、贪心法、动态规划、回溯法和分支限界法。 本书可以作为高校及各类培训机构相关课程的教材或参考书，提供全书源代码、软件和授课幻灯片等资料，可以从图书支持网站http://www.gettop.net下载，也可以从出版社网站http://press.bjtu.edu.cn的下载栏目中下载。
第1部分 算法分析与程序设计基础 第1章 算法的基本概念 1.1 算法的基本概念 1.1.1 算法的特征 1.1.2 算法的4个标准 1.1.3 算法的描述形式 1.2 算法复杂性分析框架 1.2.1 增长次数 1.2.2 渐进符号 1.2.3 时间复杂度 1.2.4 空间复杂度 本章小结 课后习题 第2章 C++算法程序设计基础 2.1 C++语言概述 2.1.1 C++语言的优势 2.1.2 C++语言的内容 2.1.3 编程工具 2.2 C++程序结构初步 2.2.1 预处理指示符初步 2.2.2 注释 2.2.3 基本输入／输出 2.3 使用C++语言编写简单代码 2.3.1 面向过程的C语言 2.3.2 面向过程的C++语言 2.3.3 面向对象的C++语言 2.4 C++面向对象基础 2.4.1 数据成员 2.4.2 成员函数 2.4.3 类对象成员的访问 2.4.4 类的访问限制 2.4.5 动态内存分配 2.4.6 C++程序内存分配 2.5 构造函数和析构函数 2.5.1 构造函数的概念 2.5.2 析构函数的概念 2.5.3 带参数的构造函数 2.5.4 重载构造函数 2.6 类中的this指针 2.7 类中的const修饰符 2.7.1 常对象 2.7.2 常成员函数 2.7.3 常数据成员 2.8 模板的基本概念 2.8.1 使用模板的必要性 2.8.2 模板的分类 2.9 函数模板 2.9.1 函数模板的定义 2.9.2 使用函数模板 2.9.3 函数模板的重载 2.10 类模板 2.10.1 类模板的定义 2.10.2 使用类模板 2.11 继承的基本概念 2.11.1 继承的必要性 2.11.2 继承的实现方式 2.11.3 继承中的静态数据成员 2.12 基类和派生类的关系 2.12.1 基类指针 2.12.2 继承下的构造函数和析构函数 2.12.3 重写基类成员 2.12.4 调用基类成员函数 2.13 详解protected关键字 2.14 保护继承与私有继承 2.14.1 公有继承 2.14.2 私有继承 2.14.3 保护继承 本章小结 课后习题第2部分 算法设计数据结构基础 第3章 线性数据结构基础 3.1 抽象数据类型 3.2 线性表基础 3.2.1 线性表定义及特点 3.2.2 顺序表 3.2.3 链表 3.2.4 数组与链表性能比较 3.3 栈与队列基础 3.3.1 栈 3.3.2 队列 本章小结 课后习题 第4章 非线性数据结构基础 4.1 树与二叉树 4.1.1 树的基本概念 4.1.2 二叉树 4.2 树与二叉树的存储结构 4.2.1 二叉树的存储结构 4.2.2 树的存储结构 4.2.3 二叉树的遍历 4.3 图 4.3.1 图的基本概念 4.3.2 图的存储结构 本章小结 课后习题 第5章 排序与搜索算法基础 5.1 排序算法的基本概念 5.1.1 排序的分类 5.1.2 排序算法的评价标准 5.2 简单排序算法 5.2.1 插入排序 5.2.2 选择排序 5.2.3 冒泡排序 5.3 快速排序 5.4 堆排序 5.5 归并排序 5.6 希尔排序 5.7 线性表查找 5.7.1 顺序查找 5.7.2 二分查找 5.8 树与图的搜索 5.8.1 二叉排序树搜索 5.8.2 B-树 5.8.3 广度优先搜索 5.8.4 图的深度优先搜索 本章小结 课后习题第3部分 典型算法分析与问题求解 第6章 递归与分治法算法设计 6.1 递归法 6.1.1 递归算法的特性 6.1.2 递归的执行过程 6.2 递归法应用举例 6.2.1 汉诺塔问题求解 6.2.2 斐波那契数列问题求解 6.2.3 八皇后问题 6.3 分治法 6.3.1 问题提出 6.3.2 分治法概述 6.4 分治法应用举例 本章小结 课后习题 第7章 贪心算法设计 7.1 贪心法 7.1.1 问题提出 7.1.2 贪心法的基本思路 7.2 贪心法应用举例 7.2.1 背包问题 7.2.2 哈夫曼编码 7.2.3 单源最短路径 7.2.4 最小生成树 本章小结 课后习题 第8章 动态规划算法设计 8.1 动态规划法 8.1.1 动态规划法的基本概念 8.1.2 多阶段决策 8.1.3 动态规划法适用条件 8.1.4 动态规划法解决问题的步骤 8.2 动态规划法应用举例 8.2.1 多源最短路径 8.2.2 最大公共子序列问题 8.2.3 导弹拦截问题 本章小结 课后习题 第9章 回溯法算法设计 9.1 回溯法 9.1.1 回溯法的基本概念 9.1.2 回溯法的基本思想 9.1.3 回溯法求解问题的步骤 9.2 回溯法应用举例 9.2.1 小老鼠走迷宫问题 9.2.2 子集合问题 9.2.3 全排列问题 9.2.4 八皇后问题 9.2.5 0-1背包问题 本章小结 课后习题 第10章 分支限界算法设计 10.1 分支限界 10.1.1 分支限界法的基本思想 10.1.2 求解问题的适用条件和步骤 10.1.3 分支限界的优缺点 10.2 分支限界应用举例 10.2.1 0-1背包问题 10.2.2 旅行售货员问题 本章小结 课后习题附录A 部分习题参考答案参考文献
插图：1.1.1算法的特征计算机的问世是20世纪人类最伟大的发明之一，它把人类社会带进了信息技术时代，而算法是计算机科学的重要基础，就像算盘一样，人们需要为计算机编制各种各样的“口诀”即算法，才能使其工作。虽然每天都在和算法打交道，但是能严格地指出什么是算法却不是一件容易的事。著名的Webster词典在“algorithm”词条下指出：“算法即在有限步骤内解一个数学问题的过程，步骤中常常包括某一操作的重复”。更广义地说，一个算法就是解一个问题或实现某一目标的逐步过程。这个定义并未与计算机相关，事实上，我国的数学著作《九章算术》就是采用问题集的形式编的，该书共有246个问题的求解算法，远在计算机出现之前就已提出。D.E.Knuth给出了另一个说明：一个算法，就是一个有穷规则的集合，规定了一个解决某一特定类型问题的运算序列，此外还应具有如下5个重要特性。1.输入性一个算法要具有0个或多个外部量作为算法的输入，这些外部量通常体现为算法中的一组变量，有些输入量需要在算法执行过程中输入。从表面上看，有些算法好像没有输入量，实际上是输入量已被嵌入算法之中。2.输出性 一个算法必须具有一个或多个输出，以反映算法对输入数据加工后的结果，没有输出的算法是毫无意义的。
《算法分析与设计(C++描述)》：原理与技术的完美结合教学与科研的最新成果语言精练、实例丰富可操作性强，实用性突出
对于只有C语言基础的学生，该本书简要介绍了C++语言的基本特点，并用其描述算法；讲解了基本的数据结构和主流算法，也确实是一本不可多得的好书！
书很不错，很多算法都很经典，很有帮助。
下个学期读研究生，买来先预习预习
内容太浅了，不是我想要的