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

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

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

第1章 绪论1

1.1　预备知识1

1.1.1　数据抽象1

1.1.2　数据抽象与二元关系3

1.1.3　二元关系的基本性质和几种重要的关系5

1.2　什么是数据结构6

1.2.1　数据结构的引出6

1.2.2　数据的逻辑结构和存储结构8

1.2.3　数据结构的表示11

1.3　抽象数据类型11

1.3.1　什么是抽象数据类型11

1.3.2　面向对象方法与抽象数据类型13

1.3.3　抽象数据类型的实现15

1.4　算法与算法分析17

1.4.1　什么是算法17

1.4.2　算法描述与算法描述语言19

1.4.3　常用的算法设计方法29

1.4.4　算法分析35

习题38

第2章　线性表及其顺序存储42

2.1　线性表的概念42

2.1.1　什么是线性表42

2.1.2　线性表的抽象数据类型44

2.2　线性表的顺序存储及其运算实现45

2.2.1　线性表的顺序存储——顺序表45

2.2.2　顺序表的基本运算47

2.2.3　顺序表的类定义52

2.3　栈53

2.3.1　什么是栈53

2.3.2　栈的抽象数据类型56

2.3.3　栈的顺序存储及其运算56

2.3.4　顺序栈的类定义59

2.4　栈与算法设计60

2.4.1　栈与优先级处理60

2.4.2　栈与回溯法68

2.4.3　栈与分治法73

2.4.4　栈与递归75

2.5 队列85

2.5.1　队列及其抽象数据类型85

2.5.2　顺序队列及其运算87

2.5.3　队列应用例92

2.5.4　优先队列96

2.6　数组与特殊矩阵的表示98

2.6.1　数组的顺序存储98

2.6.2　规则矩阵的压缩存储100

2.6.3　稀疏矩阵的三列二维数组表示——三元组顺序表102

习题105

第3章　链表107

3.1　线性表的链式存储——线性链表107

3.1.1　线性链表的概念107

3.1.2　线性链表的运算109

3.1.3　线性链表的类定义116

3.2　链式栈与链式队列116

3.2.1　链式栈116

3.2.2　链式队列120

3.3　循环链表123

3.3.1　循环链表的结构特点123

3.3.2　循环链表的基本运算124

3.3.3　循环链表应用例128

3.4　双向链表与十字链表136

3.4.1 双向链表136

3.4.2　稀疏矩阵的十字链表表示139

3.5　广义表140

3.5.1　广义表的概念141

3.5.2　广义表的存储方式143

3.5.3　广义表的基本运算144

习题148

第4章　树与二叉树151

4.1　树的基本概念151

4.1.1　什么是树结构151

4.1.2　树的定义与表示154

4.1.3　树的性质156

4.2　二叉树157

4.2.1　二叉树的定义157

4.2.2　二叉树的基本性质158

4.2.3　二叉树的抽象数据类型160

4.2.4　二叉树的存储结构161

4.2.5　二叉树的遍历及其他运算163

4.2.6　线索二叉树168

4.2.7　二叉树的计数172

4.3　二叉树应用174

4.3.1　表达式线性化174

4.3.2　最优二叉树176

4.3.3　二叉搜索树182

4.3.4　堆188

4.3.5　二叉树与减治法195

4.4　树的运算196

4.4.1　树的抽象数据类型197

4.4.2　树的存储结构197

4.4.3　树的遍历199

4.4.4　树的其他运算——树遍历的应用200

4.5　树结构与算法设计203

4.5.1　算法的一种描述方式——决策树203

4.5.2　树与回溯法204

4.5.3　树与划分等价类210

4.6　森林与二叉树213

4.6.1　森林与二叉树的转换213

4.6.2　森林的遍历214

习题215

第5章　图217

5.1　图的基本概念217

5.1.1　图的定义和概念217

5.1.2　图的抽象数据类型221

5.1.3　欧拉路径和汉密尔顿路径222

5.2　图的存储结构224

5.2.1　图的邻接矩阵表示224

5.2.2　图的邻接表表示226

5.2.3　图的其他表示方法229

5.3　图的遍历231

5.3.1　图的深度优先遍历232

5.3.2　图的广度优先遍历233

5.3.3　图遍历的应用234

5.3.4　广义图搜索236

5.3.5　图的连通性237

5.4　有向图与有向无环图238

5.4.1　有向图的连通性和传递闭包238

5.4.2　有向无环图与拓扑排序241

5.4.3　关键路径244

5.5　最小生成树与贪心算法246

5.5.1　图的生成树与最小生成树246

5.5.2　普里姆算法248

5.5.3　克鲁斯卡尔算法250

5.5.4　贪心算法252

5.6　最短路径问题256

5.6.1　单源最短路径256

5.6.2　带负权值边的单源最短路径258

5.6.3　全源最短路径261

5.6.4　动态规划算法264

5.7　图应用例——城市间公路交通网问题269

5.7.1　问题描述269

5.7.2　问题求解思路270

习题270

第6章　查找273

6.1　线性查找表274

6.1.1　顺序查找274

6.1.2　折半查找274

6.1.3　斐波那契查找276

6.1.4　线性查找表的性能比较276

6.2　二叉搜索树的查找性能277

6.3　AVL树279

6.3.1　BST的旋转操作280

6.3.2　AVL树的插入和平衡化旋转281

6.3.3　AVL树的删除283

6.3.4　AVL树的性能285

6.4　B-树286

6.4.1　多路动态搜索树286

6.4.2　B-树的查找287

6.4.3　B-树的插入287

6.4.4　B-树的删除289

6.5　2-3-4树和红黑树291

6.5.1　2-3-4树291

6.5.2　红黑树292

6.6　散列方法296

6.6.1　散列技术296

6.6.2　散列函数297

6.6.3　冲突处理300

6.6.4　散列的删除302

6.6.5　散列的性能302

6.7　静态索引结构303

6.7.1　索引查找303

6.7.2　索引存储方式303

6.7.3　索引文件结构306

6.8　模式匹配算法309

6.8.1 字符串的概念和ADT309

6.8.2　字符串的存储表示310

6.8.3　字符串的模式匹配及简单匹配算法311

6.8.4　KMP算法311

6.8.5　Boyer-Moore算法314

习题317

第7章 排序319

7.1　排序的概念及算法性能分析319

7.2　基本排序方法321

7.2.1 冒泡排序321

7.2.2　插入排序322

7.2.3　直接选择排序326

7.2.4　基本排序方法的比较328

7.3　快速排序328

7.3.1　快速排序的过程329

7.3.2　快速排序的性能分析330

7.3.3　快速排序的改进算法331

7.3.4　三路划分的快速排序算法332

7.4　归并排序334

7.4.1　二路归并334

7.4.2 自底向上的归并排序335

7.4.3 自顶向下的归并排序336

7.5　锦标赛排序337

7.6　堆排序339

7.6.1　堆排序的思想339

7.6.2　堆排序的实现342

7.7　内排序方法分析343

7.7.1　排序方法的下界343

7.7.2 内排序方法的比较345

7.8　线性时间复杂度的排序算法346

7.8.1　计数排序346

7.8.2　箱排序347

7.8.3　基数排序348

7.9　排序网络351

7.9.1　排序网络的概念351

7.9.2 巴彻尔奇偶归并排序353

7.10　外部排序356

7.10.1　外部排序方法357

7.10.2　基于败者树的k路归并算法357

7.10.3　排序-归并的改进359

习题363

参考文献365