数据结构与算法 C++语言描述PDF|Epub|txt|kindle电子书版本网盘下载

数据结构与算法 C++语言描述PDF格式电子书版下载

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

第一部分 基础知识1

第1章　概论3

1.1　算法与数据结构3

1.1.1 算法3

1.1.2　数据结构5

1.1.3　数据的逻辑结构6

1.1.4　数据的存储表示8

1.1.5　数据结构的运算9

1.2　数据抽象和抽象数据类型10

1.2.1　抽象、数据抽象和过程抽象10

1.2.2　封装与信息隐蔽10

1.2.3　数据类型和抽象数据类型11

1.2.4　数据结构与抽象数据类型12

1.3　面向对象方法12

1.3.1　面向对象方法的由来12

1.3.2　面向对象方法的基本思想12

1.3.3　面向对象方法的要素13

1.3.4 面向对象方法和抽象数据类型14

1.4　描述数据结构和算法15

1.4.1　数据结构的规范15

1.4.2　实现数据结构16

本章小结17

习题18

2.1.1 什么是好的算法20

第2章　算法基础20

2.1　算法复杂度20

2.1.2　影响程序运行时间的因素21

2.1.3　算法的时间复杂度21

2.1.4　使用程序步分析算法23

2.1.5　算法的空间复杂度24

2.2　渐近表示法25

2.2.1　大0记号25

2.2.2　Ω记号27

2.2.4　小o记号28

2.2.5　算法按时间复杂度分类28

2.2.3　？记号28

2.3 递归、归纳和递推30

2.3.1 递归30

2.3.2　递归算法示例32

2.3.3　证明方法34

2.3.4　递推关系35

本章小结38

习题38

第二部分 数据结构41

第3章　数组和链表43

3.1 结构和类43

3.1.1 结构43

3.1.2　结构表示元素44

3.2　数组46

3.2.1 一维数组47

3.2.2　二维数组47

3.2.3 多维数组48

3.3　链表49

3.3.1 指针49

3.3.2　单链表53

3.3.3　带表头结点的单链表56

3.3.4　单循环链表57

3.3.5　双向链表57

3.4.2　可用空间表59

3.4.1 结点结构59

3.4　采用模拟指针的链表59

3.5　异常处理62

本章小结63

习题63

第4章　堆栈和队列65

4.1 堆栈65

4.1.1 堆栈ADT65

4.1.2　堆栈的顺序表示66

4.1.3　堆栈的链接表示69

4.2 队列72

4.2.1 队列ADT72

4.2.2　队列的顺序表示73

4.2.3　队列的链接表示76

4.3　表达式计算77

4.3.1 表达式77

4.3.2 中缀表达式转换为后缀表达式78

4.3.3　计算后缀表达式的值81

4.4　实现递归85

4.4.1　子程序调用和系统栈85

4.4.2　递归函数的性能87

4.4.3　尾递归87

4.5　演示与测试88

习题92

本章小结92

第5章 线性表和数组ADT94

5.1 线性表94

5.1.1 线性表ADT94

5.1.2　线性表的顺序表示96

5.1.3　线性表的链接表示99

5.1.4　两种存储表示的比较103

5.2　多项式的算术运算103

5.2.1 多项式ADT103

5.2.2　多项式的链接表示104

5.2.3　项结点类105

5.2.4　多项式类106

5.2.5 多项式的输入和输出107

5.2.6　多项式相加108

5.2.7　重载运算符函数109

5.3　数组作为抽象数据类型110

5.3.1 数组ADT111

5.3.2　一维数组的C++类112

5.4　特殊矩阵113

5.4.1　对称矩阵113

5.4.2　带状矩阵114

5.5　稀疏矩阵115

5.5.1 稀疏矩阵ADT115

5.5.2　稀疏矩阵的顺序表示116

5.5.3　稀疏矩阵转置118

5.5.4　稀疏矩阵的正交链表表示120

5.5.5　建立正交链表124

5.5.6　打印正交链表125

本章小结126

习题126

第6章　字符串和广义表128

6.1 字符串128

6.1.1 字符串ADT128

6.1.2　字符串的存储表示129

6.1.3 串运算的实现130

6.1.4　简单模式匹配算法131

6.1.5　模式匹配的KMP算法134

6.2　广义表139

6.2.1　广义表的概念139

6.2.2　广义表ADT140

6.2.3　广义表的存储表示140

6.2.4　广义表算法142

本章小结142

习题143

第7章　树144

7.1　树的基本概念144

7.1.1　树的定义144

7.1.2　基本术语145

7.2　二叉树146

7.2.1　二叉树的定义147

7.2.2　二叉树的性质148

7.2.3 二叉树ADT149

7.2.4　二叉树的存储表示150

7.2.5　二叉树类151

7.2.6　二叉树基本运算153

7.3　二叉树的遍历155

7.3.1　二叉树遍历算法155

7.3.2　二叉树遍历的递归算法157

7.3.3　二叉树遍历的应用实例158

7.4.1 遍历器类159

7.4　二叉树遍历的非递归算法159

7.4.2　中序遍历器类161

7.5　二叉线索树163

7.5.1 二叉线索树的定义163

7.5.2　构造中序线索树164

7.5.3　遍历二叉线索树165

7.6　树和森林167

7.6.1　森林与二叉树的转换167

7.6.2　树和森林的存储表示168

7.6.3　树和森林的遍历171

7.7　堆和优先权队列172

7.7.1 堆172

7.7.2　优先权队列ADT175

7.7.3　优先权队列类176

7.7.4　实现优先权队列176

7.8　哈夫曼树和哈夫曼编码179

7.8.1　树的路径长度179

7.8.2　哈夫曼树和哈夫曼算法180

7.8.3　哈夫曼树类181

7.8.4　构造哈夫曼树182

7.8.5　哈夫曼编码183

7.9　并查集和等价关系184

7.9.1 并查集ADT184

7.9.2　并查集的存储表示185

7.9.4　函数Union和Find186

7.9.3 并查集类186

7.9.5　改进的函数Union和Find187

7.9.6　按等价关系分组188

本章小结189

习题189

第8章　集合和搜索192

8.1　集合和搜索192

8.1.1 集合和搜索的概念192

8.1.2　动态集ADT194

8.1.3　集合的表示195

8.2.1　无序表的顺序搜索196

8.2.2　有序表的顺序搜索196

8.2　顺序搜索196

8.2.3　平均搜索长度197

8.2.4 自组织表198

8.3　二分搜索198

8.3.1 分治法和二分搜索198

8.3.2　对半搜索200

8.3.3　二叉判定树202

8.3.4　斐波那契搜索204

8.4　搜索算法的时间下界207

本章小结208

习题208

9.1.1　二叉搜索树的定义209

9.1 二叉搜索树209

第9章　动态集和搜索树209

9.1.2　二叉搜索树的搜索210

9.1.3　二叉搜索树的插入211

9.1.4　二叉搜索树的删除213

9.1.5　平均情况时间分析215

9.2　二叉平衡树217

9.2.1　二叉平衡树的定义217

9.2.2　二叉平衡树类217

9.2.3　二叉平衡树的平衡旋转218

9.2.4　二叉平衡树的插入225

9.2.5　二叉平衡树的删除227

9.2.6　二叉平衡树的高度230

9.3　B-树231

9.3.1　m叉搜索树232

9.3.2　B-树的定义234

9.3.3　B-树的高度234

9.3.4　B-树的搜索235

9.3.5　B-树的插入235

9.3.6　B-树的删除238

9.4　键树240

9.4.1　键树的定义240

9.4.2　双链树241

9.4.3　Trie树242

9.5.1　伸展树的伸展操作243

9.5　伸展树243

9.5.2　性能分析245

本章小结247

习题248

第10章　跳表和散列表250

10.1 字典250

10.2　跳表250

10.2.1　什么是跳表251

10.2.2　跳表类253

10.2.3　跳表的搜索255

10.2.4　跳表的插入255

10.2.5　跳表的删除257

10.3　散列表258

10.3.1　散列技术258

10.3.2　散列函数259

10.3.3　拉链法261

10.3.4　开地址法262

10.3.5　线性探查法262

10.3.6　其他开地址法266

10.3.7　性能分析268

本章小结269

习题269

11.1.1 图的定义与术语270

11.1 图的基本概念270

第11章 图270

11.1.2 图ADT273

11.2　图的存储结构274

11.2.1 图的矩阵表示法274

11.2.2 图的邻接矩阵实现276

11.2.3 图的邻接表表示法278

11.2.4　图的邻接表实现279

11.3　图的遍历282

11.3.1 扩充的图类282

11.3.2　深度优先遍历283

11.3.3　宽度优先遍历285

11.3.4　基本遍历方法286

11.4　拓扑排序287

11.4.1　用顶点代表活动的AOV网288

11.4.2　拓扑排序算法289

11.4.3　拓扑排序C++程序290

11.5　关键路径292

11.5.1　用边代表活动的AOE网292

11.5.2　关键路径算法293

11.5.3　关键路径C++程序295

11.6　最小代价生成树296

11.6.1　基本概念296

11.6.2　普里姆算法297

11.6.3　克鲁斯卡尔算法299

11.6.4　最优化问题和贪心法302

11.6.5 贪心法求解最小代价生成树302

11.7　最短路径304

11.7.1 贪心法和单源最短路径304

11.7.2　迪杰斯特拉算法305

11.7.3　所有顶点之间的最短路径309

本章小结311

习题311

第12章　内排序314

12.1 基本概念314

12.2.1　直接插入排序315

12.2　简单排序算法315

12.2.2　简单选择排序318

12.2.3 冒泡排序319

12.3　快速排序321

12.3.1　分治法与快速排序321

12.3.2　快速排序算法322

12.3.3　性能分析324

12.4　两路合并排序326

12.4.1　合并两个有序序列326

12.4.2　分治法和两路合并排序327

12.4.3　合并排序算法328

12.5　堆排序329

12.5.1　堆排序算法329

12.4.4　性能分析329

12.5.2　实现堆排序330

12.5.3　性能分析331

12.6　排序算法的时间下界331

12.7　基数排序333

12.7.1　分配排序333

12.7.2　基数排序算法334

12.7.3　实现基数排序335

本章小结337

习题338

13.1.1 主存储器和辅助存储器340

13.1.2　磁盘存储器340

13.1　辅助存储器简介340

第13章　文件和外排序340

13.2　文件342

13.2.1 文件的基本概念342

13.2.2　文件的组织方式342

13.3　文件的索引结构345

13.3.1　静态索引结构345

13.3.2　动态索引结构346

13.4　外排序347

13.4.1 外排序的基本过程347

13.4.2　初始游程的生成348

13.4.3　多路合并352

13.4.4　最佳合并树354

本章小结355

习题356

第三部分 算法设计与分析357

第14章 问题求解和算法设计359

14.1 问题求解方法359

14.1.1 问题和问题求解359

14.1.2　问题求解过程360

14.1.3　系统生命周期360

14.1.4　问题求解策略361

14.2　分治法361

14.2.1　一般方法361

14.2.2　递推关系362

14.2.3 求最大、最小元363

14.2.4　选择问题366

14.2.5　斯特拉森矩阵相乘369

14.3　贪心法371

14.3.1　一般方法371

14.3.2　最佳合并模式372

14.3.3　背包问题375

14.3.4　贪心法的基本要素378

14.4　动态规划法379

14.4.1 动态规划法的基本要素379

14.4.2　最优二叉搜索树382

14.5.1　一般方法387

14.5 回溯法387

14.5.2　n-皇后问题391

14.5.3　子集和数问题395

14.6　分支限界法399

14.6.1 一般方法399

14.6.2 基于上下界的分支限界法401

14.6.3　0/1背包问题403

14.6.4　旅行商问题408

14.7　随机算法413

14.7.1　基本概念413

14.7.2　拉斯维加斯算法414

14.7.3　蒙特卡罗算法416

14.7.4　舍伍德算法418

本章小结419

习题419

第15章　NP难度和NP完全问题421

15.1 基本概念421

15.1.1 不确定算法和可满足性问题422

15.1.2　P类和NP类问题425

15.1.3　N难度和NP完全问题426

15.1.4　Cook定理426

15.2　一些典型的NP完全问题426

15.2.1　最大集团判定问题427

15.2.2 顶点覆盖判定问题428

15.2.3　3元CNF-可满足性429

15.2.4　图着色数判定问题430

本章小结431

习题432

附录433

附录A　实习要求和实习题433

A.1 面向对象方法概述433

A.2　实习目的435

A.3　实习要求435

A.4　实习步骤435

A.5　实习报告436

A.6　实习题436

附录B C++程序设计概要438

B.1 函数与参数传递439

B.2　动态存储分配442

B.3　类与对象443

B.4　函数和操作符重载444

B.5　继承性和派生类445

B.6　多态性、虚函数和动态联编445

B.7　纯虚函数和抽象类447

B.8　模板函数和模板类448

B.9　友元函数和友元类450

附录C　专有名词中英文对照表452

参考文献460