数据结构与算法PDF|Epub|txt|kindle电子书版本网盘下载

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第一章 引论1

第一节 抽象数据类型1

一、程序设计的一个基本原则是抽象1

二、抽象数据类型1

第二节 数据结构2

一、基本术语3

二、数据的逻辑结构3

三、数据的存储结构4

第三节 算法的概念4

第四节 算法设计基本技术6

一、分治法6

二、贪心法7

三、动态规划法8

四、基本检索与遍历技术8

五、回溯法9

第五节 算法分析9

一、算法复杂度9

二、时间复杂度9

三、空间复杂度17

四、分析算法的意义17

习题18

第二章 线性表22

第一节 线性表22

一、线性表的逻辑结构22

二、线性表抽象数据类型23

第二节 线性表的顺序存储结构23

一、顺序表24

二、顺序表类的实现25

三、顺序存储结构的特点29

第三节 线性表的链式存储结构30

一、单链表30

二、单链表类的实现32

三、循环链表39

四、双向链表40

五、链式存储结构的特点43

第四节 线性表的应用44

一、一元多项式相加44

二、约瑟夫问题49

习题51

第三章 栈和队列54

第一节 栈54

一、栈的基本概念54

二、栈的顺序存储结构55

三、栈的链式存储结构57

四、顺序栈和链栈的比较59

五、栈的应用59

第二节 递归和递归消除67

第三节 队列71

一、队列的基本概念71

二、队列的顺序存储72

三、队列的链式存储76

习题82

第四章 串84

第一节 基本概念84

第二节 字符串的存储结构85

一、顺序存储85

二、链式存储86

第三节 串类的实现88

一、顺序串类的实现88

二、链串类的实现99

习题101

第五章 数组和广义表103

第一节 数组的逻辑结构定义103

第二节 数组的顺序存储104

第三节 矩阵的存储106

一、特殊矩阵106

二、稀疏矩阵108

第四节 广义表的定义111

第五节 广义表的存储112

第六节 广义表的递归算法113

一、广义表的深度114

二、复制广义表115

习题115

第六章 树118

第一节 树的基本概念118

一、树的定义118

二、树的逻辑表示方法119

三、树的基本术语120

四、树的性质122

第二节 树的存储结构122

—、双亲表示法122

二、孩子表示法123

三、孩子兄弟表示法124

第三节 二叉树125

一、二叉树的定义125

二、二叉树的抽象数据类型125

三、二叉树的性质126

四、二叉树的存储结构128

第四节 树、森林与二叉树的转换131

第五节 树的遍历134

一、二叉树的遍历135

二、二叉树遍历的应用142

三、树和森林的遍历143

第六节 线索二叉树145

一、中序线索树的建立147

二、在中序线索树中查找某结点的直接前趋148

三、在中序线索树中查找某结点的直接后继148

四、中序线索树的遍历149

五、在中序线索树中插入结点149

第七节 树的应用151

习题158

第七章 图161

第一节 图的定义和有关术语161

第二节 图的存储结构165

一、邻接矩阵165

二、邻接表167

第三节 图的遍历170

一、深度优先遍历171

二、广度优先遍历172

第四节 生成树和最小生成树173

一、无向连通图的生成树173

二、带权无向连通图的最小生成树174

第五节 最短路径178

一、单源最短路径178

二、每对顶点之间的最短路径181

第六节 拓扑排序183

一、拓扑排序183

二、拓扑排序算法184

第七节 关键路径185

习题187

第八章 集合与查找190

第一节 集合及其运算190

第二节 线性表及其查找192

一、顺序查找192

二、二分查找192

三、其他线性表的查找193

第三节 树结构的查找194

一、二叉检索树194

二、平衡二叉检索树199

第四节 散列存储与散列查找202

一、散列存储202

二、散列函数203

三、解决冲突205

四、散列查找的效率210

第五节 索引存储211

习题213

第九章 内部排序214

第一节 基本概念214

第二节 插入排序215

一、直接插入排序215

二、折半插入排序217

三、希尔排序218

第三节 选择排序220

一、直接选择排序220

二、堆排序222

第四节 交换排序229

一、冒泡排序229

二、快速排序231

第五节 归并排序235

第六节 分配排序238

一、桶排序238

二、基数排序240

第七节 内部排序方法的比较与选择243

习题244

第十章 文件与外排序247

第一节 磁盘与文件管理247

一、磁盘247

二、文件的操作系统视图248

三、文件249

第二节 文件的组织技术250

—、输入顺序文件250

二、散列文件250

三、线性结构索引文件251

四、树结构索引文件255

第三节 外排序258

一、外排序过程概述258

二、多路归并259

三、置换-选择排序和最优归并261

习题264

第十一章 算法分析技术266

第一节 对数与级数求和266

一、对数266

二、级数求和266

第二节 递归过程与递归方程268

一 、递归过程的分析268

二、一类递归方程的解268

第三节 算法复杂性分析示例271

一、二分查找的时间复杂度271

二、以比较为基础的检索的时间下界272

三、快速排序的分析272

四、排序算法的时间下界274

五、二叉树遍历的复杂度275

习题275

第十二章 多项式时间可计算性277

第一节 易解的问题和难解的问题277

第二节 P与NP问题类277

一、不确定性算法277

二、P与NP问题类280

第三节 NP完全性和COOK定理280

一、多项式归约280

二、NP困难和NP完全问题280

三、S．A．COOK定理281

第四节 若干NP完全问题281

一、命题逻辑的可满足性问题和重言式问题281

二、无向图的完全图(团集)问题、离集问题和顶点覆盖问题282

三、有向图的回路的边集、顶集问题282

四、H回路问题和旅行销售员问题283

五、O-1整数规划问题283

六、集合族的粘连问题、隔衬问题、集合覆盖问题283

七、着色问题和离集、团集覆盖问题284

八、集合的恰当覆盖及由它推出的一些NP完全性问题284

九、装包问题、排序问题、等分问题及最大分割问题285

习题286

参考文献287