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

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

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

第1章 数据结构和算法1

1.1 数据和数据类型1

1.1.1 数据和数据元素1

1.1.2 数据类型2

1.1.3 抽象数据类型4

1.1.4 抽象数据类型程序应用实例5

1.1.5 数据对象6

1.2 数据结构6

1.2.1 数据的逻辑结构6

1.2.2 数据元素的存储结构8

1.2.3 常用的数据运算10

1.3 算法描述工具——C语言12

1.3.1 指针类型与指针变量13

1.3.2 结构类型与结构变量15

1.3.3 函数与参数17

1.3.4 递归定义和递归函数18

1.3.5 动态存储分配19

1.3.6 文件操作21

1.3.7 程序测试与测试集23

1.3.8 测试数据的设计23

1.3.9 程序调试问题25

1.4 算法和算法评价25

1.4.1 算法的概念25

1.4.2 算法的性质27

1.4.3 算法的评价标准28

1.5 算法性能分析29

1.5.1 算法的时间性能分析29

1.5.2 算法的空间性能分析33

小结33

习题34

第2章 顺序表及其应用38

2.1 顺序表的基本概念38

2.1.1 顺序表的定义38

2.1.2 顺序表的数据结构分析38

2.1.3 顺序表的数据类型描述39

2.2 顺序表基本算法40

2.3 顺序表基本算法性能分析43

2.3.1 时间性能分析43

2.3.2 空间性能分析44

2.4 顺序表的应用1——查找问题44

2.4.1 查找的概念44

2.4.2 简单顺序查找算法45

2.4.3 有序表的二分查找算法47

2.4.4 分块查找算法51

2.4.5 3种查找算法的性能比较52

2.5 顺序表的应用2——排序问题53

2.5.1 排序的概念53

2.5.2 顺序表的数据类型54

2.5.3 插入排序——直接插入排序算法54

2.5.4 插入排序——希尔排序算法57

2.5.5 交换排序——冒泡排序算法59

2.5.6 交换排序——快速排序算法61

2.5.7 选择排序——直接选择排序算法65

2.5.8 归并排序算法67

2.5.9 排序算法的性能分析与比较71

2.6 顺序表的应用3——字符处理问题71

2.6.1 串和顺序串的定义及相关概念71

2.6.2 顺序串的数据结构分析72

2.6.3 顺序串的基本运算72

2.6.4 顺序串的数据类型定义74

2.6.5 顺序串的基本运算算法74

2.6.6 串的模式匹配算法77

小结78

习题78

第3章 链表及其应用83

3.1 链表的基本概念83

3.1.1 链表的定义83

3.1.2 链表的逻辑结构83

3.1.3 链表的存储结构84

3.1.4 静态链表和动态链表85

3.1.5 链表基本运算86

3.2 单链表的数据结构86

3.2.1 单链表的逻辑结构86

3.2.2 单链表的存储结构86

3.3 单链表基本算法88

3.3.1 单链表的基本算法88

3.3.2 单链表基本算法性能分析93

3.4 循环链表94

3.4.1 单循环链表94

3.4.2 双向循环链表95

3.4.3 双向循环链表的结点插入算法96

3.4.4 双向循环链表的结点删除算法97

3.5 链表的应用98

3.5.1 多项式相加问题98

3.5.2 两个链表的归并问题101

3.5.3 箱子排序问题103

3.5.4 链表在字符处理方面的应用——链串105

小结107

习题107

第4章 堆栈及其应用112

4.1 堆栈的基本概念112

4.1.1 堆栈的定义112

4.1.2 堆栈的逻辑结构112

4.1.3 堆栈的基本算法113

4.2 顺序栈及其基本算法113

4.2.1 顺序栈的概念及数据类型113

4.2.2 顺序栈的基本算法114

4.2.3 顺序栈基本算法性能分析115

4.3 链栈及其基本算法116

4.3.1 链栈的概念及数据类型116

4.3.2 链栈的基本算法117

4.3.3 链栈基本算法性能分析118

4.4 堆栈的应用118

4.4.1 数制转换问题118

4.4.2 简单的文字编辑器问题119

4.4.3 表达式计算问题120

4.4.4 括号匹配问题126

4.4.5 汉诺塔问题128

4.4.6 火车车厢重排问题132

4.4.7 开关盒布线问题136

4.4.8 离线等价类问题139

4.4.9 迷宫老鼠问题142

小结145

习题146

第5章 队列及其应用149

5.1 队列的基本概念149

5.1.1 队列的定义149

5.1.2 队列的逻辑结构150

5.1.3 队列的基本算法150

5.2 顺序队列及其基本算法150

5.2.1 顺序队列的概念及数据类型150

5.2.2 顺序循环队列151

5.2.3 循环队列基本算法153

5.2.4 循环队列基本算法性能分析154

5.3 链队列及其基本算法155

5.3.1 链队列的概念及数据类型155

5.3.2 链队列基本算法156

5.3.3 链队列基本算法性能分析157

5.4 基数排序问题157

5.4.1 多关键字排序问题158

5.4.2 链式基数排序算法思想158

5.4.3 链式基数排序算法实现的技术要点160

5.4.4 链表基数排序算法及其性能分析160

5.5 火车车厢重排问题162

5.5.1 问题分析及算法思想162

5.5.2 火车车厢重排算法设计162

5.5.3 火车车厢重排算法及其性能分析163

5.6 电路布线问题165

5.6.1 电路布线问题分析165

5.6.2 电路布线问题算法思想165

5.6.3 电路布线问题算法设计166

5.6.4 电路布线问题算法及其性能分析166

5.7 识别图元问题168

5.7.1 识别图元问题分析168

5.7.2 识别图元算法设计168

5.7.3 识别图元算法及其分析169

5.8 工厂仿真问题170

5.8.1 工厂仿真问题分析170

5.8.2 工厂仿真问题算法设计171

5.8.3 工厂仿真问题算法及其性能分析173

小结174

习题174

第6章 特殊矩阵、广义表及其应用178

6.1 数组与矩阵178

6.1.1 数组与矩阵的概念及其相互关系178

6.1.2 数组的存储结构179

6.2 特殊矩阵的压缩存储180

6.2.1 对称矩阵及其存储结构181

6.2.2 三角矩阵及其存储结构181

6.2.3 对角矩阵及其存储结构182

6.2.4 稀疏矩阵及其存储结构和建表算法183

6.3 矩阵的应用实例187

6.3.1 稀疏矩阵的转置问题187

6.3.2 稀疏矩阵的加法运算问题189

6.4 广义表193

6.4.1 广义表的概念193

6.4.2 广义表的存储结构194

6.4.3 广义表的应用——m元多项式的表示196

小结198

习题198

第7章 二叉树及其应用201

7.1 二叉树的基本概念201

7.1.1 二叉树的定义201

7.1.2 二叉树的基本术语202

7.1.3 两种特殊的二叉树202

7.1.4 二叉树的性质203

7.2 二叉树的存储结构205

7.2.1 二叉树的顺序存储结构205

7.2.2 二叉树的链接存储结构205

7.2.3 建立二叉树的算法206

7.3 二叉树的遍历算法208

7.3.1 二叉树遍历的概念208

7.3.2 二叉树遍历递归算法209

7.3.3 二叉树先序遍历非递归算法211

7.3.4 二叉树中序遍历非递归算法212

7.3.5 二叉树后序遍历非递归算法213

7.4 线索二叉树214

7.4.1 线索二叉树的概念214

7.4.2 二叉树的线索化215

7.4.3 线索二叉树的查找算法216

7.5 二叉树的应用1——基本算法217

7.6 二叉树的应用2——哈夫曼树220

7.6.1 基本概念220

7.6.2 哈夫曼树221

7.6.3 哈夫曼树的构造过程221

7.6.4 哈夫曼树的存储结构及哈夫曼算法222

7.6.5 哈夫曼算法223

7.6.6 哈夫曼树的应用——哈夫曼编码223

7.7 二叉树的应用3——二叉排序树225

7.7.1 二叉排序树及其性质225

7.7.2 二叉排序树的存储结构226

7.7.3 二叉排序树的结点查找算法226

7.7.4 二叉排序树的结点插入算法227

7.7.5 二叉排序树的生成算法228

7.7.6 二叉排序树的结点删除算法229

7.7.7 二叉排序树结点查找算法性能分析231

7.7.8 平衡二叉排序树232

7.8 二叉树的应用4——堆和堆排序239

7.8.1 堆和堆排序的概念239

7.8.2 堆的调整算法240

7.8.3 建堆242

7.8.4 堆排序算法及性能分析243

小结244

习题244

第8章 树和森林及其应用253

8.1 树和森林的基本概念253

8.1.1 树和森林的定义253

8.1.2 树的性质254

8.1.3 树和森林的遍历255

8.1.4 树、森林与二叉树的关系256

8.2 树的存储结构258

8.2.1 树的顺序存储结构258

8.2.2 树的链接存储结构259

8.3 树的基本算法及性能分析261

8.3.1 树转换为二叉树算法及性能分析261

8.3.2 森林转换为二叉树算法及性能分析262

8.3.3 二叉树转换为树算法及性能分析263

8.3.4 二叉树转换为森林算法及性能分析265

8.3.5 树的遍历算法265

8.3.6 森林的遍历算法266

8.4 树的应用——B树267

8.4.1 B树的概念267

8.4.2 B树的数据存储类型267

8.4.3 B树的查找算法268

8.4.4 B树的插入算法270

8.4.5 B树的删除算法及实例275

小结278

习题278

第9章 散列结构及其应用282

9.1 散列结构的基本概念282

9.1.1 散列结构的概念282

9.1.2 散列存储结构——散列表283

9.1.3 散列函数284

9.1.4 冲突处理方法——开放定址法287

9.1.5 冲突处理方法——链地址法289

9.2 线性探测散列算法290

9.2.1 线性探测散列算法的数据类型290

9.2.2 线性探测散列基本算法290

9.3 链地址法散列算法293

9.3.1 链地址散列算法的数据类型293

9.3.2 链地址散列基本算法294

9.4 散列结构的查找性能分析295

9.5 散列结构应用1——LZW压缩问题296

9.5.1 LZW压缩问题296

9.5.2 LZW压缩算法及其算法性能分析297

9.5.3 LZW解压缩问题298

9.5.4 LZW解压缩算法及其算法性能分析299

9.6 散列结构应用2——直接存取文件300

9.6.1 基本概念300

9.6.2 直接存取文件的存储结构及类型301

9.6.3 文件操作1——查找结点算法301

9.6.4 文件操作2——增加结点算法302

9.6.5 文件操作3——删除结点算法303

小结304

习题304

第10章 图及其应用307

10.1 图的概念307

10.1.1 图的定义307

10.1.2 图的基础知识308

10.1.3 图的基本运算311

10.2 图的存储结构及其基本算法312

10.2.1 邻接矩阵及其数据类型312

10.2.2 邻接矩阵的基本算法314

10.2.3 邻接表及其数据类型315

10.2.4 邻接表的基本算法317

10.2.5 逆邻接表318

10.2.6 十字链表及其数据类型319

10.2.7 十字链表的基本算法320

10.2.8 邻接多重表及其数据类型321

10.2.9 邻接多重表的基本算法322

10.3 图的遍历及算法323

10.3.1 深度优先搜索遍历324

10.3.2 深度优先搜索遍历算法324

10.3.3 广度优先搜索遍历325

10.3.4 广度优先搜索遍历算法326

10.4 有向图的连通性和最小生成树327

10.4.1 有向图的连通性分析327

10.4.2 连通网的最小生成树问题——通信网络问题328

10.5 图的（最小）生成树问题328

10.5.1 图的生成树328

10.5.2 最小生成树算法——普利姆算法329

10.5.3 最小生成树算法——克鲁斯卡尔算法331

10.6 非连通图的生成森林算法332

10.7 最短路径335

10.7.1 最短路径问题335

10.7.2 从某源点到其余各项点之间的最短路径问题——迪杰斯特拉算法336

10.7.3 每一对顶点之间的最短路径问题——弗洛伊德算法338

10.8 有向无环图及其应用340

10.8.1 有向无环图及其应用问题实例340

10.8.2 AOV网及其特性342

10.8.3 拓扑排序及其算法343

10.8.4 AOE网345

10.8.5 关键路径及有关概念345

10.8.6 关键路径求解及其算法思想346

10.8.7 AOE网关键路径求解算法的数据类型347

10.8.8 AOE网中求解关键路径的算法347

10.8.9 关键路径求解算法分析349

小结350

习题351

第11章 算法性能分析和算法设计方法简介357

11.1 算法和程序357

11.1.1 算法与程序分析357

11.1.2 空间复杂性分析358

11.1.3 时间复杂度分析359

11.2 再谈算法性能问题360

11.2.1 时间复杂度的上限值361

11.2.2 定理11.2的证明361

11.2.3 时间复杂度的下限值362

11.2.4 有关渐进符号的计算362

11.3 算法性能测量问题363

11.3.1 算法性能测量问题分析363

11.3.2 算法性能测量实例363

11.4 算法设计方法简介364

11.4.1 分而治之算法设计方法365

11.4.2 最优化问题简介365

11.4.3 贪婪算法设计方法366

11.4.4 回溯算法设计方法368

11.5 NP问题简介369

11.6 散列表查找性能370

11.7 讨论题371

附录A 本书算法源程序373

参考文献414