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

第一章 引论 1

第一节 抽象数据类型、算法和C 1

一、抽象数据类型 1

二、ADT的描述 2

三、算法 4

四、算法的描述 5

第二节 数据的逻辑结构和存储结构 9

一、逻辑结构 9

二、存储结构 11

第三节 软件工程简介 13

一、分析阶段 14

二、设计阶段 16

三、实现阶段 25

四、维护阶段 26

第四节 算法的复杂性 26

一、算法的度量 26

二、算法的时间复杂性 28

第五节 递归算法设计与分析 31

一、递归算法设计 31

二、递归算法分析 34

小结 37

习题 37

第一节 一般的表 41

一、表的定义 41

第二章 线性数据结构 41

二、表的抽象运算 42

第二节 表的存储设计 44

一、表的链式存储 44

二、表的连续设计 46

第三节 表的实现 48

一、链接表的动态实现 48

二、链接表的静态实现 49

三、表的连续实现 50

四、其他形式的链表 55

第四节 表的应用 58

一、特长整数相加 58

二、多项式运算 60

第五节 栈 62

一、ADT栈 63

二、栈的设计与实现 64

三、栈的应用 70

第六节 队列 80

一、队列的设计 80

二、队列的存储设计 80

第七节 串 88

一、串的概念 88

二、串的设计 90

三、模式匹配 90

三、广义表的递归算法 98

二、存储设计 98

第八节 广义表 98

一、广义表的概念 98

小结 99

习题 100

上机题 101

第三章 树 102

第一节 树的概念 102

一、树的定义 102

二、树的实现 104

第二节 二叉树 106

一、二叉树的定义 106

二、二叉树的性质 108

三、二叉树的表示 109

第三节 二叉树的遍历 112

一、遍历算法 112

二、遍历算法的应用 114

第四节 线索二叉树 116

一、二叉树的线索化 117

二、线索二叉树的维护 119

三、一种新的二叉树存储表示 121

第五节 树、森林与二叉树 122

一、树、森林到二叉树的转换 122

二、树和森林的遍历 123

一、通讯编码问题 125

第六节 哈夫曼树及其应用 125

二、哈夫曼算法 126

三、编码和译码 128

小结 128

习题 129

上机题 130

第四章 集合 131

第一节 集合概述 131

一、用位向量实现集合 133

二、用链接表实现集合 133

三、数组表示 134

二、优先队列的实现 136

第二节 优先队列 136

一、优先队列概述 136

第三节 具有操作Merge和Find的集合 139

一、并查集合 140

二、等价问题 140

第四节 二叉查找树 144

一、二叉查找树概述 144

二、平衡的二叉查找树 148

三、B-树 154

第五节 字典与散列表 159

一、开散列 161

二、闭散列 163

三、散列函数效率的估计 165

小结 167

习题 167

上机题 168

第五章 图 169

第一节 图的概念 169

一、基本概念 169

二、图的抽象数据类型 171

第二节 图的表示 172

一、邻接矩阵 172

二、邻接表 172

第三节 图的遍历 173

一、深度优先遍历法 174

二、广度优先遍历法 175

第四节 最小代价生成树 176

一、生成树 176

二、最小代价生成树 177

第五节 最短路径 180

一、从某个顶点到其余各顶点的最短路径 180

二、求每一对顶点之间的最短路径 183

第六节 拓扑排序 184

一、拓扑排序概述 185

一、关键路径概述 187

第七节 关键路径 187

二、拓扑算法 187

二、求关键路径 188

第八节 网络流的算法 191

一、网络与流 192

二、可行流与最大流 193

三、可改进路P 193

四、寻找最大流的标号法 195

小结 197

习题 198

上机题 199

第一节 选择排序 200

第六章 排序技术 200

第二节 堆排序 204

第三节 冒泡排序 209

第四节 插入排序 210

第五节 快速排序 211

第六节 归并排序 215

第七节 基数排序 218

小结 221

习题 222

上机题 222

第七章 外排序和文件的组织 223

第一节 磁盘排序的方法 223

二、缓冲区的并行处理 224

一、多路平衡归并的实现 224

三、生成初始归并段 228

第二节 磁带归并 231

一、磁带归并段的分布 231

二、归并段的非均匀分布 232

第三节 文件的组织 234

一、文件的概念 234

二、文件的组织 235

小结 240

习题 240

一、直接具有递归特性 241

二、分析建立递归模型 241

第一节 递归技术 241

第八章 算法设计方法 241

第二节 分治算法 243

一、分治算法的基本思想 243

二、算法举例 243

第三节 动态规划法 247

一、动态规划法思想 247

二、算法举例 247

第四节 贪心法 252

一、贪心算法实例 252

二、贪心法的基本内容 254

一、回溯法的设计思路 255

第五节 回溯法 255

二、回溯法的解 256

小结 259

习题 259

第九章 并行算法设计与分析 260

第一节 并行模型 260

一、并行计算模型 260

二、并行算法的描述和性能分析 263

第二节 并行算法设计 264

一、广播与求前缀和 264

二、并行选择算法 265

—、图灵机 268

第一节 图灵机和非确定图灵机 268

第十章 NP-完全性 268

二、随机存取计算机 271

三、非确定图灵机 272

第二节 语言、P和NP、多项式转换和NP-完全问题类 274

一、语言、P和NP问题 274

二、多项式转换 274

三、可满足性问题是NP-完全的 276

第三节 NP完全问题的求解 279

一、确定NP-完全问题 279

二、穷举法 279

三、求次优解 282

参考文献 286