算法与数据结构（第二版）

　　本书是《计算机学科教学计划1993》的配套教材之一。它覆盖了《计算机学科教学计划1993》中开列的关于算法与数据结构主科目的所有知识单元。其主要内容有：算法与数据结构的概念、抽象数据类型（ADT）、基于序列的ADT（如表，栈，队列和串等）。反映层次关系的ADT（如树，堆和各种平衡树等）、关于集合的ADT（如字典，优先队列和共查集等）、算法设计的策略与技巧、排序与选择算法、图的算法、问题的计算复杂性、并行算法。全书强调“算法”与“数据结构”之间密不可分的联系，因而强调融数据类型与定义在数据类型上的运算于一体的抽象数据类型，为面向对象的程序设计方法打下扎实的基础。本书以知识单元为基本构件，具有可拆卸性和可重组性，内容丰富，表述详细，适合不同类型的院校按照不同的培养规格组织教学，其中基础部分可作为计算机学科各专业本科生的教材，高级专题部分可作为高年级本科生或研究生的教材。

暂缺《算法与数据结构（第二版）》作者简介

第一章　绪论                  
     　第一节　算法的复杂性                  
         一. 比较两对算法的效率                  
         二. 复杂性的计量                  
         三. 复杂性的渐近性态及其阶                  
         四. 复杂性渐近阶的重要性                  
         五. 算法复杂性渐近阶的分析                  
         六. 递归方程解的渐近阶的求法                  
 　  　第二节　算法表达中的抽象机制                  
         一. 从机器语言到高级语言的抽象                  
         二. 抽象数据类型                  
         三. 使用抽象数据类型带来的好处                  
         四. 数据结构. 数据类型和抽象数据类型                  
         习题                  
       第二章　表                  
     　第一节　ADT表                  
     　第二节　表的实现                  
         一. 表的数组实现                  
         二. 表的指针实现                  
         三. 表的游标实现                  
         四. 循环链表                  
         五. 双链表                  
     　第三节　栈                  
         一. ADT栈                  
         二. 栈的数组实现                  
         三. 栈的指针实现                  
     　第四节　队列                  
         一. ADT队列                  
         二. 用指针实现队列                  
         三. 用循环数组实现队列                  
     　第五节　映射                  
         一. ADT映射                  
         二. 用数组实现映射                  
         三. 用表实现映射                  
       习题                  
       第三章　串                  
     　第一节　ADT串                  
 　    第二节　串的实现                  
         一. 串的数组实现                  
         二. 串的指针实现                  
         三. 串的块链表示法                  
         四. 串的堆结构                  
   　  第三节　模式匹配                  
         一. 朴素的模式匹配算法                  
         二. 模式匹配的KMP算法                  
   　    习题                  
       第四章　树                  
 　    第一节　树的定义                  
  　   第二节　二叉树                  
  　   第三节　树的遍历                  
   　  第四节　ADT树                  
   　  第五节　树的实现方法                  
         一. 父亲数组表示法                  
         二. 儿子链表表示法                  
         三. 左儿子右兄弟表示法                  
   　  第六节　二叉树的实现及其应用                  
         一. 二叉树的顺序存储结构                  
         二. 二叉树的结点度表示法                  
         三. 二叉树的链式存储结构                  
         四. 果园或森林的二叉树表示                  
         五. 线索二叉树                  
         六. 二叉树的应用                  
         习题                  
       第五章　集会                  
       第一节　以集合为基础的抽象数据类型                  
         一. 集合的定义和记号                  
         二. 定义在集合上的基本运算                  
         三. 集合的简单表示法                  
       第二节　字典                  
         一 . 实现字典的简单方法                  
         二. 用散列表实现字典                  
         三. 用散列表实现映射                  
       第三节　有序字典                  
         一. 有序字典的定义                  
         二. 用数组实现有序字典                  
         三. 用二叉搜索树实现有序字典                  
       第四节　平衡树                  
         一. 红黑树                  
         二. 2－3树                  
       第五节　优先队列                  
         一. 优先队列的定义                  
         二. 优先队列的字典式实现                  
         三. 优先级树和堆                  
         四. 用数组实现堆                  
   　  第六节　并查集                  
         一. 并查集的定义及其简单实现                  
         二. 并查集的快速实现                  
         三. 并查集的构实现                  
       第七节　检索树                  
         一. 检索树与检索树结点                  
         二. 用数组表示检索树结点                  
         三. 用链接表表示检索树结点                  
         四. 检索树的效率                  
     　  习题                  
       第六章　算法设计策略与技巧                  
       第一节　递归技术与分治法                  
         一. 递归技术                  
         二. 分治法的基本思想                  
         三. 大整数的乘法                  
         四. Strassen矩阵乘法                  
         五. 最接近点对问题                  
         六. 循环赛日程表                  
   　  第二节　动态规划                  
         一. 计算矩阵连乘积                  
         二. 动态规划算法的基本要素                  
         三. 最长公共子序列                  
   　  　四. 凸多边形的最优三角剖分                  
       第三节　贪心算法                  
         一. 活动安排问题                  
         二. 贪心算法的基本要素                  
 　　  　三. 哈夫曼编码                  
         四. 贪心算法的理论基础                  
       第四节　回溯法                  
         一. 回溯法的一般描述                  
         二. n后问题                  
         三. 子集和问题                  
         四. 图的m－着色问题                  
         五. 回溯法的效率分析                  
       第五节　限界剪枝法                  
         一. 最小耗费搜索法                  
         二. 限界与剪枝                  
         三. 旅行售货员问题                  
 　      习题                  
       第七章　排序与选择                  
   　  第一节　简单排序算法                  
         一. 冒泡排序                  
         二. 插入排序                  
         三. 选择排序                  
         四. 简单排序算法的计算复杂性                  
       第二节　快速排序                  
         一. 算法的基本思想及其实现                  
         二. 快速排序的性能                  
         三. 随机快速排序算法                  
       第三节　堆排序                  
         一. 堆排序算法的基本思想及其实现                  
         二. 堆排序算法的计算复杂性                  
       第四节　线性时间排序                  
         一. 计数排序                  
         二. 桶排序                  
         三. 基数排序                  
       第五节　中位数与第k小元素                  
         一. 平均情况下的线性时间选择算法                  
         二. 最坏情况下的线性时间选择算法                  
     　　习题                  
       第八章　圈                  
       第一节　图的基本概念                  
         一. 图及其相关术语                  
         二. 抽象数据类型ADT图                  
       第二节　图的表示法                  
         一. 邻接矩阵表示法                  
         二. 邻接表表示法                  
       第三节　图的遍历                  
         一. 深度优先搜索                  
         二. 广度优先搜索                  
       第四节　图的连通性                  
         一. 深度优先生成森林                  
         二. 无圈有向图                  
         三. 有向图的强连通分支                  
         四. 无向图的割点和双连通分支                  
       第五节　最小生成树                  
         一. 最小生成树性质                  
         二. Prim算法                  
         三. Kruskal算法                  
       第六节　最短路径                  
         一. 单源最短路径                  
         二. 所有顶点对之间的最短路径                  
       第七节　图匹配                  
       　习题                  
       第九章　问题的计算复杂性                  
       第一节　计算模型                  
         一. 随机存取机RAM                  
         二. 随机存取存储程序机RASP                  
         三. RAM模型的变形与简化                  
         四. 图灵机                  
         五. 图灵机模型与RAM模型的关系                  
       第二节　问题的计算时间下界                  
         一. 问题的输入. 输出及平凡下界                  
         二. 信息论下界                  
         三. 对手论证方法                  
         四. Ben＿Or下界定理                  
         五. 问题变换与计算复杂性归约                  
       第三节　P类与NP类                  
         一. 非确定性图灵机                  
         二. P类与NP类语言                  
         三. “证书’与VP类语言                  
         四. 问题和语言                  
       第四节　NP－完全性                  
         一. 多项式时间变换与NP完全问题                  
         二. Cook定理                  
         三. 几个典型的NP-完全问题                  
       第五节  NP－完全问题的近似解法                  
         一. 近似算法的性能                  
         二. 顶点覆盖问题的近似算法                  
         三. 旅行售货员问题的近似算法                  
         四. 集合覆盖问题的近似算法                  
 　      五. 子集和问题的近似算法                  
     　  习题                  
       第十章　并行算法                  
       第一节　并行计算模型                  
         一. PRAM模型                  
         二. 同步与控制                  
         三. 并行算法的表达                  
         四. 并行算法的性能指标                  
         五. 运行时间和工作量有效性                  
       第二节　并行算法的基本设计技术                  
         一. 平衡树方法                  
         二. 指针跳越技术                  
         三. 欧拉回路技术                  
         四. 并行分治法                  
         五. 划分原理                  
         六. 流水线技术                  
         七. 接力技术                  
         八. 递归的并行随机消元法                  
         九. 确定性破对称技术                  
       第三节　EREW算法与CRCW算法的速度比较                  
         一. 并发读对提高速度的作用                  
         二. 并发写对提高速度的作用                  
         三. CRCW算法速度的上界                  
 　　    习题                  
       第十一章　高级专题                  
       第一节　算法的分摊时间分析                  
         一. 累计方法                  
         二. 记账方法                  
         三. 势能方法                  
         四. 自适应二叉搜索树                  
       第二节　可并优先队列                  
         一. 可并优先队列的定义                  
         二. 用二项堆实现可并优先队列                  
         三. 用Fibonacci堆实现可并优先队列                  
       第三节　数据结构的扩充与联合                  
         一. 动态选择树——红黑树的扩充                  
         二. 数据结构扩充的方法                  
         三. 区间树                  
         四. 数据结构的联合                  
       第四节　静态数据结构的动态化方法                  
         一. 可分解搜索问题                  
         二. 静态数据结构的半动态化                  
         三. 静态数据结构的另一种半动态化剂                  
         四. 静态数据结构的全动态变换                  
         五. 其他动态化方法                  
        习题                  
     参考文献