算法分析与设计

第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++语言概述

第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 部分习题参考答案参考文献

本书以程序设计作为基础、数据结构作为工具、五大核心算法作为目标，系统地介绍了算法设计中典型问题的求解过程。 全书分成程序设计基础、数据结构和五大核心算法3个部分共10章。第1部分为算法分析与程序设计基础，介绍了算法分析的时间和空间复杂度，以及C++算法相关的程序设计基础；第2部分为算法设计数据结构基础，介绍了线性和非线性数据结构基础，同时对常用的排序和搜索算法作了详细介绍；第3部分为典型算法分析与问题求解，介绍了经典算法设计中的“五虎上将”：分治法、贪心法、动态规划、回溯法和分支限界法。 本书可以作为高校及各类培训机构相关课程的教材或参考书，提供全书源代码、软件和授课幻灯片等资料，可以从图书支持网站http://www.gettop.net下载，也可以从出版社网站http://press.bjtu.edu.cn的下载栏目中下载。

作为一本基础性的图书，全书以简短的章节解决典型的算法问题，涵盖了绝大多数算法设计中的常用技术，回避了一些生涩而且不常使用的算法。在表达每一种算法时，先对问题进行分析，给出解题的一般流程，然后提供了相应解决实际问题的完整程序，并用图来直观表示其结果。同时也注重对算法的复杂性分析。 全书从程序设计基础、数据结构基础和五大算法三个方面分为三个部分共10章，每章都附有大量的习题，有利于读者对书中内容的理解和应用。