数据结构与算法基础PDF电子书下载

第一章 绪论 1

1.1数据结构的研究对象 1

1.2数据结构发展概况 3

1.3抽象数据型 3

1.3.1 抽象数据型的定义 3

1.3.2 数据型、数据结构和抽象数据型 6

1.3.3抽象数据型的规格描述 7

1.3.4 抽象数据型的实现 9

1.3.5 多层次抽象技术 13

1.3.6抽象数据型的优点 13

1.4逐步求精的程序设计方法 14

1.4.1如何求解一个问题 14

1.4.2算法的逐步求精 15

1.4.3 小结 19

1.5关于本书采用的描述语言 19

1.5.1 结构类型说明 19

1.5.2输入输出 19

1.5.3 用new和delete的动态存储分配 20

1.5.4 引入引用类型 20

1.5.5 其他 22

习题 22

第二章 算法设计与分析的基本方法及技巧 23

2.1程序的运行时间 24

2.2一类递归方程的求解 29

2.2.1 与递归方程解有关的两个问题 29

2.2.2 猜解法 31

2.2.3 一类递归方程的展开式与通解 32

2.3分治 35

2.3.1 一般方法 35

2.3.2 整数乘法 36

2.3.3 求两个矩阵的乘积 37

2.4平衡 39

2.5贪心法 40

2.5.1 一般方法 40

2.5.2 背包问题 40

2.6动态规则 43

2.6.1 一般方法 43

2.6.2求n个矩阵的乘积 45

2.6.3联赛胜负概率问题 47

2.6.4评注 48

2.7回溯 49

2.7.1 一般方法 49

2.7.2单词匹配问题 50

2.7.3 回溯算法与解空间的组织 52

2.7.4 8皇后问题 53

习题 55

第三章 线性表 59

3.1抽象数据型线性表 59

3.2线性表的实现 60

3.2.1指针和游标 61

3.2.2 线性表的数组实现 62

3.2.3 线性表的指针实现 64

3.2.4 线性表的游标实现 68

3.2.5双向链接表 69

3.2.6环形链表 70

3.3栈 71

3.3.1栈的数组实现 72

3.3.2栈和递归过程 74

3.4排队 74

3.4.1排队的指针实现 75

3.4.2排队的循环数组实现 77

3.5多项式的代数运算 79

3.6串 82

3.6.1抽象数据型串 82

3.6.2 串的表示 84

3.7数组 87

3.7.1 抽象数据型数组 87

3.7.2数组的表示 88

3.8广义表 90

习题 93

第四章 树 96

4.1基本术语 96

4.2二元树 97

4.2.1 二元树的定义及遍历 97

4.2.2二元树的性质 99

4.2.3抽象数据型二元树 100

4.2.4二元树的表示 101

4.2.5 二元树的复制 107

4.3树 109

4.3.1抽象数据型树 109

4.3.2树的表示 111

4.4森林和二元树间的转换 116

4.5树的应用 119

4.5.1 用树结构表示集合 119

4.5.2判定树 122

4.5.3哈夫曼（Huffman）树 124

4.5.4表达式求值 133

4.6 23树 135

4.6.1 2-3树的插入操作 137

4.6.2 2-3树的删除操作 139

4.6.3 2-3树的连接操作 140

4.6.4 2-3树的拆分操作 141

4.6.5 2-3树的UNION和MIN操作 142

习题 142

第五章 图以及与图有关的算法 147

5.1基本定义 147

5.2图的表示 149

5.2.1 邻接矩阵（adjacency matrix） 149

5.2.2邻接表（adjacency list） 149

5.3图的搜索算法 150

5.3.1 先深搜索与先深编号 151

5.3.2先广搜索与先广编号 152

5.4图与树的联系 153

5.4.1 先深生成森林和先广生成森林 153

5.4.2无向图与开放树的联系 154

5.4.3最小生成树 155

5.5无向图的双连通性（Biconnectivity） 158

5.5.1 无向图的双连通分量 158

5.5.2求关节点 159

5.6有向图的搜索 163

5.7强连通性 164

5.8拓扑分类 165

5.8.1 无环路有向图 166

5.8.2拓扑分类算法 166

5.9关键路径 168

5.10单源最短路径 173

5.11每一对结点之间的最短路径 175

5.11.1 Floyd算法 175

5.11.2Warshall算法 178

5.11.3 求有向图的中心点 178

5.12求有向图的基本环路 179

习题 182

第六章 查找 187

6.1线性查找 187

6.2折半查找 189

6.3分块查找 190

6.4二元查找树 192

6.5最优二元查找树 196

6.6散列法 199

6.6.1 内散列表 199

6.6.2散列函数 202

6.6.3 冲突的处理 204

6.6.4 外散列表 206

习题 208

第七章 分类 211

7.1简单的分类算法 212

7.1.1气泡分类 212

7.1.2插入分类 213

7.1.3选择分类 213

7.2快速分类 215

7.3归并分类 218

7.3.1 合并两个分类序列 218

7.3.2归并分类 219

7.4堆分类 221

7.5基数分类 224

7.6词典分类 229

7.7顺序统计 233

7.7.1 顺序统计的算法 233

7.7.2 顺序统计的期望时间 234

习题 236

第八章 外部分类 240

8.1磁盘文件的归并分类 240

8.1.1 K路归并 241

8.1.2 并行操作的缓冲区处理 243

8.1.3初始归并段的生成 244

8.2磁带文件的归并分类 245

8.2.1 平衡归并分类 245

8.2.2 多阶段归并分类 246

习题 248

第九章 文件 249

9.1文件及文件操作 249

9.1.1 文件的有关概念 249

9.1.2文件操作 249

9.2文件组织 250

9.2.1 顺序式文件 251

9.2.2索引文件 252

9.2.3散列文件 254

9.2.4链接式文件和多重链表文件 255

9.2.5倒排文件 256

习题 257

参考文献 258