数据结构 思想与实现 第2版PDF电子书下载

第1章 引言 1

1.1 算法与数据结构 1

1.1.1 数据的逻辑结构 2

1.1.2 数据结构的运算 3

1.2 存储实现 4

1.3 算法分析 4

1.3.1 时间复杂度的概念 5

1.3.2 算法运算量的计算 6

1.3.3 渐进时间复杂度 7

1.3.4 时间复杂度的计算 9

1.3.5 算法的优化 10

1.3.6 空间复杂度 16

1.4 面向对象方法 16

本书的结构和特点 18

总结 18

练习1 19

第1部分 线性结构 22

第2章 线性表 22

2.1 线性表的定义 22

2.2 线性表的顺序实现 24

2.2.1 顺序表的存储实现 24

2.2.2 顺序表的运算实现 26

2.2.3 顺序实现的性能分析 30

2.2.4 顺序表的简单示例 30

2.3 线性表的链接实现 31

2.3.1 单链表 32

2.3.2 双链表 39

2.3.3 循环链表 45

2.3.4 链表的性能分析 45

2.4 标准模板库（STL）中的线性表 46

2.4.1 容器和迭代器的概念 46

2.4.2 STL中的线性表类 47

2.5 线性表的应用 51

2.5.1 大整数处理 51

2.5.2 多项式求和 58

2.5.3 约瑟夫环 60

2.5.4 动态内存管理 62

总结 65

练习2 65

第3章 栈 68

3.1 栈的定义 68

3.2 栈的顺序实现 70

3.2.1 顺序栈的存储实现 70

3.2.2 顺序栈的运算实现 71

3.2.3 顺序栈性能分析 73

3.2.4 顺序栈的简单示例 73

3.3 栈的链接实现 74

3.3.1 链接栈的存储实现 74

3.3.2 链接栈的运算实现 75

3.3.3 链接栈的简单示例 77

3.4 STL中的栈 78

3.5 栈的应用 79

3.5.1 递归消除 79

3.5.2 括号配对 82

3.5.3 简单的计算器 92

总结 102

练习3 103

第4章 队列 104

4.1 队列的定义 104

4.2 队列的顺序实现 105

4.2.1 顺序队列的存储实现 105

4.2.2 循环队列的运算实现 109

4.2.3 循环队列简单示例 111

4.3 队列的链接实现 113

4.3.1 链接队列的存储实现 113

4.3.2 链接队列的运算实现 115

4.3.3 链接队列简单示例 117

4.4 STL中的队列 119

4.5 队列的应用 120

4.5.1 火车车厢重排问题 120

4.5.2 排队系统的模拟 123

总结 128

练习4 129

第5章 字符串 130

5.1 字符串的定义 130

5.2 字符串的顺序实现 131

5.2.1 顺序串的存储实现 131

5.2.2 顺序串的运算实现 133

5.3 字符串的链接实现 137

5.3.1 链接串的存储实现 137

5.3.2 链接串类的运算实现 140

5.4 字符串的匹配 149

5.5 STL的字符串类 152

总结 153

练习5 153

第2部分 树状结构 156

第6章 树 156

6.1 树的定义 156

6.1.1 树的基本术语 156

6.1.2 树的基本运算 157

6.2 二叉树 158

6.2.1 二叉树的定义 158

6.2.2 二叉树的常用性质 159

6.2.3 二叉树的基本运算 161

6.2.4 二叉树的顺序实现 165

6.2.5 二叉树的链接实现 166

6.2.6 二叉链表类 168

6.3 二叉树的应用：计算表达式 182

6.4 哈夫曼树和哈夫曼编码 194

6.4.1 前缀编码 194

6.4.2 哈夫曼算法 196

6.4.3 哈夫曼树类的实现 196

6.5 树和森林 203

6.5.1 树的存储实现 203

6.5.2 树的遍历 205

6.5.3 树、森林与二叉树的转换 205

总结 207

练习6 208

第7章 优先级队列 210

7.1 基于线性表的优先级队列 210

7.2 基于树的优先级队列 211

7.2.1 优先级队列的存储实现 211

7.2.2 优先级队列的运算实现 213

7.3 D堆 221

7.4 归并优先级队列 221

7.4.1 左堆 221

7.4.2 斜堆 223

7.4.3 二项堆 223

7.5 STL中的优先级队列 226

7.6 优先级队列的应用：排队系统的模拟 227

总结 233

练习7 233

第3部分 集合结构 236

第8章 集合与静态查找表 236

8.1 集合的定义 236

8.2 查找的基本概念 237

8.3 静态查找表 237

8.4 无序表的查找 238

8.4.1 顺序查找 238

8.4.2 顺序查找的时间复杂度分析 239

8.5 有序表的查找 240

8.5.1 顺序查找 240

8.5.2 二分查找 240

8.5.3 插值查找 242

8.5.4 分块查找 242

8.6 STL中的静态查找表 244

总结 245

练习8 245

第9章 动态查找表 247

9.1 二叉查找树 248

9.1.1 二叉查找树的定义 248

9.1.2 二叉查找树的存储实现 248

9.1.3 二叉查找树的运算实现 250

9.1.4 二叉查找树性能 257

9.2 AVL树 258

9.2.1 AVL树的定义 258

9.2.2 AVL树的存储实现 260

9.2.3 AVL树的运算实现 261

9.3 红黑树 273

9.3.1 红黑树的定义 273

9.3.2 红黑树的存储实现 274

9.3.3 红黑树的运算实现 276

9.4 AA树 291

9.4.1 AA树的定义 291

9.4.2 AA树的存储实现 292

9.4.3 AA树的运算实现 293

9.5 伸展树 301

9.5.1 伸展树的定义 301

9.5.2 伸展操作的实现 303

9.6 散列表 305

9.6.1 散列表的定义 305

9.6.2 线性探测法 308

9.6.3 二次探测法 312

9.6.4 再散列法 314

9.6.5 开散列表 314

9.7 STL中的动态查找表 318

9.7.1 set 318

9.7.2 map 319

总结 321

练习9 321

第10章 排序 324

10.1 排序的基本概念 324

10.2 插入排序 325

10.2.1 直接插入排序 325

10.2.2 二分插入排序 327

10.2.3 希尔排序 327

10.3 选择排序 329

10.3.1 直接选择排序 330

10.3.2 堆排序 331

10.4 交换排序 334

10.4.1 冒泡排序 334

10.4.2 快速排序 335

10.5 归并排序 340

10.6 基数排序 343

10.7 STL中的排序 346

总结 347

练习10 348

第11章 外部查找与排序 350

11.1 主存储器与外存储器 350

11.2 B树 351

11.2.1 B树的定义 351

11.2.2 B树的查找 353

11.2.3 B树的插入 353

11.2.4 B树的删除 354

11.3 B＋树 355

11.3.1 B＋树的定义 355

11.3.2 B＋树的查找 357

11.3.3 B＋树的插入 357

11.3.4 B＋树的删除 359

11.4 外排序 361

11.4.1 置换选择 361

11.4.2 多阶段归并 363

总结 364

练习11 364

第12章 不相交集 366

12.1 等价关系与等价类 366

12.2 不相交集 367

12.3 不相交集的实现 367

12.3.1 不相交集的存储实现 367

12.3.2 不相交集的运算实现 368

12.4 不相交集的应用 372

12.4.1 生成迷宫 372

12.4.2 最近的共同祖先问题 374

总结 375

练习12 375

第4部分 图状结构 378

第13章 图 378

13.1 图的定义 378

13.1.1 图的基本术语 379

13.1.2 图的基本运算 381

13.2 图的存储 382

13.2.1 邻接矩阵表示法 382

13.2.2 邻接表表示法 386

13.3 图的遍历 391

13.3.1 深度优先搜索 391

13.3.2 广度优先搜索 394

13.4 图的遍历的应用 397

13.4.1 无向图的连通性 397

13.4.2 欧拉回路 397

13.4.3 有向图的连通性 402

13.4.4 拓扑排序 403

13.4.5 关键路径 405

总结 409

练习13 410

第14章 最小生成树 413

14.1 生成树和最小生成树 413

14.2 Kruskal算法 414

14.3 Prim算法 417

14.4 算法的正确性 421

总结 422

练习14 422

第15章 最短路径问题 423

15.1 单源最短路径 423

15.1.1 非加权图的最短路径 423

15.1.2 加权图的最短路径 429

15.1.3 带有负权值的图 434

15.1.4 无环图 435

15.2 所有顶点对的最短路径 436

总结 439

练习15 439

第5部分 算法设计基础 442

第16章 算法设计基础 442

16.1 枚举法 442

16.2 贪婪法 444

16.3 分治法 444

16.3.1 整型数的乘法问题 444

16.3.2 平面上的最近点问题 445

16.4 动态规划 446

16.4.1 硬币找零问题 447

16.4.2 最优二叉查找树 449

16.5 回溯法 453

16.5.1 八皇后问题 453

16.5.2 分书问题 456

16.6 随机算法 458

16.6.1 跳表 458

16.6.2 素数检测 460

总结 462

练习16 463

参考文献 465