数据结构与算法 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 堆栈ADT 65

4.1.2　堆栈的顺序表示 66

4.1.3　堆栈的链接表示 69

4.2 队列 72

4.2.1 队列ADT 72

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章 线性表和数组ADT 94

5.1 线性表 94

5.1.1 线性表ADT 94

5.1.2　线性表的顺序表示 96

5.1.3　线性表的链接表示 99

5.1.4　两种存储表示的比较 103

5.2　多项式的算术运算 103

5.2.1 多项式ADT 103

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 数组ADT 111

5.3.2　一维数组的C++类 112

5.4　特殊矩阵 113

5.4.1　对称矩阵 113

5.4.2　带状矩阵 114

5.5　稀疏矩阵 115

5.5.1 稀疏矩阵ADT 115

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 字符串ADT 128

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　广义表ADT 140

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 二叉树ADT 149

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　优先权队列ADT 175

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 并查集ADT 184

7.9.2　并查集的存储表示 185

7.9.4　函数Union和Find 186

7.9.3 并查集类 186

7.9.5　改进的函数Union和Find 187

7.9.6　按等价关系分组 188

本章小结 189

习题 189

第8章　集合和搜索 192

8.1　集合和搜索 192

8.1.1 集合和搜索的概念 192

8.1.2　动态集ADT 194

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 图ADT 273

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