数据结构与算法 第2版【2025|PDF下载-Epub版本|mobi电子书|kindle百度云盘下载】

数据结构与算法 第2版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算法和算法评价11

1.3.1算法的概念11

1.3.2算法描述工具12

1.3.3算法的性质13

1.3.4算法的评价标准14

1.4算法性能分析15

1.4.1算法的时间性能分析15

1.4.2算法的空间性能分析18

本章小结19

本章习题19

第2章 顺序表及其应用22

2.1顺序表的基本概念22

2.1.1顺序表的定义22

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

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

2.2顺序表基本算法24

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

2.3.1时间性能分析27

2.3.2空间性能分析28

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

2.4.1查找的概念28

2.4.2简单顺序查找算法29

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

2.4.4分块查找算法33

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

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

2.5.1排序的概念35

2.5.2顺序表的数据类型36

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

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

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

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

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

2.5.8归并排序算法47

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

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

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

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

2.6.3顺序串的基本运算52

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

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

2.6.6串的模式匹配算法56

本章小结57

本章习题58

第3章 链表及其应用63

3.1链表的基本概念63

3.1.1链表的定义63

3.1.2链表的逻辑结构63

3.1.3链表的存储结构64

3.1.4静态链表和动态链表64

3.1.5链表基本运算65

3.2单链表的数据结构66

3.2.1单链表的逻辑结构66

3.2.2单链表的存储结构66

3.3单链表基本算法及性能分析67

3.3.1单链表的基本算法67

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

3.4单链表基本运算应用实例71

3.5循环链表73

3.5.1单向循环链表74

3.5.2.双向循环链表75

3.5.3双向循环链表的结点插入算法76

3.5.4双向循环链表的结点删除算法77

3.6链表的应用78

3.6.1多项式相加问题78

3.6.2两个链表的归并问题81

3.6.3箱子排序问题83

3.6.4链表在字符处理方面的应用——链串85

本章小结86

本章习题86

第4章 堆栈及其应用91

4.1堆栈的基本概念91

4.1.1堆栈的定义91

4.1.2堆栈的逻辑结构91

4.1.3堆栈的基本算法92

4.2顺序栈及其基本算法92

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

4.2.2顺序栈的基本算法93

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

4.3链栈及其基本算法94

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

4.3.2链栈的基本算法95

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

4.4堆栈的应用97

4.4.1数制转换问题97

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

4.4.3表达式计算问题99

4.4.4括号匹配问题104

4.4.5汉诺塔问题105

4.4.6火车车厢重排问题109

4.4.7开关盒布线问题113

4.4.8离线等价类问题116

4.4.9迷宫老鼠问题119

本章小结122

本章习题122

第5章 队列及其应用125

5.1队列的基本概念125

5.1.1队列的定义125

5.1.2队列的逻辑结构126

5.1.3队列的基本运算126

5.2顺序队列及其基本运算126

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

5.2.2循环队列127

5.2.3循环队列的基本运算实现129

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

5.3链队列及其基本算法130

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

5.3.2链队列的基本运算实现131

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

5.4基数排序问题133

5.4.1多关键字排序问题133

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

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

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

5.5火车车厢重排问题137

5.5.1问题分析及算法思想137

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

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

5.6电路布线问题140

5.6.1电路布线问题分析140

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

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

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

5.7识别图元问题143

5.7.1识别图元问题分析143

5.7.2识别图元算法设计143

5.7.3识别图元算法及其性能分析144

5.8工厂仿真问题145

5.8.1工厂仿真问题分析145

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

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

本章小结149

本章习题149

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

6.1数组与矩阵152

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

6.1.2数组的存储结构153

6.2特殊矩阵的压缩存储154

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

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

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

6.2.4稀疏矩阵及其存储结构157

6.3矩阵的应用实例161

6.3.1稀疏矩阵的转置问题161

6.3.2稀疏矩阵的加法运算163

6.4广义表167

6.4.1广义表的概念167

6.4.2广义表的存储结构168

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

本章小结172

本章习题172

第7章 二叉树及其应用176

7.1二叉树的基本概念176

7.1.1二叉树的定义176

7.1.2二叉树的基本术语177

7.1.3两种特殊的二叉树177

7.1.4二叉树的性质178

7.2二叉树的存储结构179

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

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

7.2.3建立二叉树的算法181

7.3二叉树的遍历算法182

7.3.1二叉树遍历的概念182

7.3.2二叉树遍历递归算法184

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

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

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

7.4线索二叉树188

7.4.1线索二叉树的概念188

7.4.2二叉树的线索化189

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

7.5二叉树的应用1——二叉树遍历的应用实例191

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

7.6.1基本概念193

7.6.2哈夫曼树定义194

7.6.3哈夫曼树的构造过程195

7.6.4哈夫曼树的存储结构及哈夫曼算法思想195

7.6.5哈夫曼算法196

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

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

7.7.1二叉排序树定义198

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

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

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

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

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

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

7.7.8平衡二叉排序树205

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

7.8.1堆和堆排序的概念212

7.8.2堆的调整算法213

7.8.3建堆214

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

本章小结216

本章习题216

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

8.1树和森林的基本概念224

8.1.1树和森林的定义224

8.1.2树的性质225

8.1.3树和森林的遍历226

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

8.2树的存储结构228

8.2.1树的顺序存储结构和建树算法228

8.2.2树的链接存储结构和建树算法229

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

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

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

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

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

8.3.5树的遍历算法235

8.3.6森林的遍历算法235

8.4树的应用——B-树236

8.4.1 B-树的概念236

8.4.2 B-树的数据存储类型237

8.4.3 B-树的查找算法237

8.4.4 B-树的插入算法239

8.4.5 B-树的删除算法及实例243

本章小结244

本章习题245

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

9.1散列结构的基本概念248

9.1.1散列结构的概念248

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

9.1.3散列函数250

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

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

9.2线性探测散列算法255

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

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

9.3链地址法散列算法257

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

9.3.2链地址散列基本算法258

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

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

9.5.1 LZW压缩问题261

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

9.5.3 LZW解压缩问题262

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

本章小结264

本章习题264

第10章 图及其应用267

10.1图的概念267

10.1.1图的定义267

10.1.2图的基础知识268

10.1.3图的基本运算271

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

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

10.2.2基于邻接矩阵的基本算法273

10.2.3邻接表及其数据类型274

10.2.4基于邻接表的基本算法276

10.2.5逆邻接表277

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

10.2.7基于十字链表的基本算法279

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

10.2.9基于邻接多重表的基本算法281

10.3图的遍历及算法283

10.3.1深度优先搜索遍历283

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

10.3.3广度优先搜索遍历284

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

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

10.4.1有向图的连通性分析286

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

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

10.5.1图的生成树287

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

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

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

10.7最短路径293

10.7.1最短路径问题293

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

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

10.8有向无环图及其应用298

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

10.8.2 AOV网及其特性300

10.8.3拓扑排序及其算法300

10.8.4 AOE网302

10.8.5关键路径及有关概念303

10.8.6求解关键路径算法思想303

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

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

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

本章小结307

本章习题308

第11章 算法性能分析和算法设计方法312

11.1算法和程序312

11.1.1算法与程序分析312

11.1.2空间复杂性分析313

11.1.3时间复杂度分析314

11.2再谈算法性能问题315

11.2.1时间复杂度的上限值315

11.2.2时间复杂度的下限值316

11.2.3有关渐进符号的计算317

11.3算法性能测量问题318

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

11.3.2算法性能测量实例318

11.4算法设计方法简介319

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

11.4.2最优化问题简介320

11.4.3贪婪算法设计方法321

11.4.4回溯算法设计方法322

11.5 NP问题简介323

11.6散列表查找性能324

11.7讨论题326