新编数据结构与算法考研指导

第1章 递归1

1.1 数据结构的递归本质分析1

1.2 数据结构定义2

1.3 递归算法模型设计4

1.3.1 递归算法一般形式4

1.3.2 前序递归5

1.3.3 中序递归25

1.3.4 后序递归28

小结31

习题一31

第2章 递归转非递归33

2.1 栈的定义33

2.2 递归转非递归的一般原则34

2.3 前序递归转非递归34

2.3.1 一条递归语句34

2.3.2 两条递归语句37

2.3.3 多条递归语句的一般形式47

2.4 中序递归转非递归52

2.5 后序递归转非递归55

2.5.1 一条递归语句55

2.5.2 多条递归语句的后序递归55

2.5.3 递推公式60

小结63

习题二64

第3章 回溯法65

3.1 回溯法的基本概念65

3.2 回溯法模型设计66

3.2.1 回溯法的一般形式66

3.2.2 回溯法的分类67

3.3 回溯法与递归差异分析77

3.3.1 回溯法与递归的区别77

3.3.2 实例分析77

小结80

习题三80

第4章 技巧型算法82

4.1 线性表的应用82

4.1.1 线性表的基本操作82

4.1.2 基本操作扩展82

4.1.3 线性表应用102

4.2 栈、队列的应用105

4.2.1 栈的基本操作105

4.2.2 栈的应用举例107

4.2.3 队列的基本操作111

4.2.4 队列的应用举例118

4.3 数组结构的应用123

4.4 串的应用130

4.5 树和图的应用133

4.6 排序算法的应用136

4.6.1 插入排序136

4.6.2 选择排序139

4.6.3 交换排序143

4.6.4 其他排序问题149

4.7 数学方法152

习题四156

第5章 特殊问题的算法159

附录A 数据结构基础知识部分考研分析162

参考文献167

本书不是数据结构算法的简单赘述，而是以算法的功能为基础，对算法进行纵向分类，挖掘算法之间内在的联系，构建数据结构算法的统一体系，使考研同学顺利掌握算法设计要领。书中将数据结构知识分解为4类问题：递归、递归转非递归、回溯、技巧型算法，以及其他小概率特殊问题的算法。本书突破以往的同类教程以线性表、栈和队列、串、数组和广义表、树、图、查找、排序给出各章的算法描述的讲述方式，避免了由于算法较多、难度较大，学生学习起来多会感觉烦琐、凌乱而迷茫。本书采用实例教学法，在讲清基本知识点的基础上，尽量使用实例加以说明，因此书中包含了大量实用例子，绝大部分例子都给出了详细的分析过程及程序代码，代码短小精悍，容易理解。 因此学习本书将使读者对“数据结构”课程的理解产生质的飞跃。

《新编数据结构算法考研指导》：高等学校计算机专业教材精选·算法与程序设计