《高等学校适用教材 数据结构》

第一章 绪论1

1.1 算法和数据结构1

1.2 算法描述语言5

1.3 用程序求解问题9

1.4 算法的运行时间分析14

1.5 算法的运行时间计算18

习题21

第二章 基本抽象数据类型——线性表23

2.1 线性表23

2.2 线性表的顺序实现25

2.3 线性表的非顺序实现——单链表30

2.4 可用空间表和单链表的基本操作35

2.5 多项式加法和循环单链表41

2.6 双链表48

2.7 动态存贮管理51

习题60

第三章 栈、队列和广义表62

3.1 栈62

3.2 队列69

3.3 表达式求值75

3.4 等价关系81

3.5 广义表85

3.6 递归算法和递归调用的处理88

3.7 无用单元的收集与集中92

习题99

第四章 串和集合101

4.1 串101

4.2 集合和集合基本表示方法109

4.3 字典115

4.4 哈希表117

4.5 关于哈希方法的讨论126

习题129

第五章 树131

5.1 树的基本概念和术语131

5.2 树的实现和遍历133

5.3 关于树实现方法的讨论137

5.4 二叉树142

5.5 二叉树实现方法和遍历145

习题150

第六章 集合的树形结构表示方法151

6.1 偏序树151

6.2 二叉检索树154

6.3 二叉检索树的检索时间分析和平衡树158

6.4 B树165

习题170

第七章 图171

7.1 图的基本概念及术语171

7.2 图的实现和抽象数据类型173

7.3 图的遍历和连通分量179

7.4 生成树182

7.5 有向网络的最短路径问题187

7.6 有向无回路图及其应用193

习题203

第八章 内部排序206

8.1 插入排序206

8.2 希尔排序210

8.3 选择排序214

8.4 堆阵排序217

8.5 快速排序221

8.6 合并排序228

8.7 基数排序231

习题237

第九章 外部排序239

9.1 外存设备简介239

9.2 多路合并排序243

9.3 多步合并排序249

9.4 初始有序段256

习题265

第十章 算法设计技术266

10.1 分治法设计技术266

10.2 动态设计法设计技术271

10.3 贪心法设计技术277

10.4 回溯法设计技术281

10.5 局部搜索法设计技术284

习题288