C++数据结构与程序设计PDF电子书下载

第1章 程序设计原理 1

1.1 简介 1

目录 1

1.2 Life游戏 3

1.3 程序设计风格 9

1.4 编码、测试和进一步细化 17

1.5 程序维护 29

1.6 结论和复习 34

复习题 39

启示和易犯的错误 39

进阶参考书目 40

第2章 栈 43

2.1 栈说明 43

2.2 栈的实现 49

2.3 应用：桌面计算器 57

2.4 应用：括号的匹配 60

2.5 抽象数据类型及其实现 61

启示和易犯的错误 65

进阶参考书目 66

复习题 66

第3章 队列 67

3.1 定义 67

3.2 队列的实现 72

3.3 C＋＋队列的循环实现 75

3.4 演示和测试 78

3.5 队列的应用：模拟 81

启示和易犯的错误 93

复习题 93

进阶参考书目 94

第4章 链栈和链式队列 95

4.1 指针和链式结构 95

4.2 链栈 107

4.3 带保护的链栈 110

4.4 链式队列 115

4.5 应用：多项式运算 119

4.6 抽象数据类型及其实现 128

启示和易犯的错误 130

复习题 130

5.1 递归导言 132

第5章 递归 132

5.2 递归的原理 142

5.3 回溯法：延缓工作 153

5.4 树结构的程序：在游戏中预测 165

启示和易犯的错误 174

复习题 175

进阶参考书目 176

第6章 表和字符串 177

6.1 表的定义 177

6.2 表的实现 181

6.3 字符串 194

6.4 应用：文本编辑器 201

6.5 数组链表 208

6.6 应用：生成排列 216

启示和易犯的错误 220

复习题 221

进阶参考书目 221

第7章 查找 222

7.1 查找：引言和符号 222

7.2 顺序查找 224

7.3 二分查找 229

7.4 比较树 236

7.5 下限 246

7.6 渐近 250

启示和易犯的错误 260

复习题 260

进阶参考书目 261

8.1 引言和符号 262

第8章 排序 262

8.2 插入排序 264

8.3 选择排序 272

8.4 希尔排序 275

8.5 下限 278

8.6 分而治之排序 281

8.7 链表的归并排序 285

8.8 顺序表的快速排序 292

8.9 堆和堆排序 301

8.10 复习：方法比较 308

启示和易犯的错误 311

复习题 312

进阶参考书目 312

第9章 表格和信息检索 314

9.1 引言：突破lgn的障碍 314

9.2 矩形表格 315

9.3 各种形态的表格 317

9.4 表格：一种新的抽象数据类型 321

9.5 应用：基数排序 324

9.6 哈希法 329

9.7 关于哈希的分析 340

9.8 结论：方法的比较 345

9.9 应用：再访Life游戏 346

启示和易犯的错误 353

复习题 354

进阶参考书目 354

第10章 二叉树 356

10.1 二叉树 356

10.2 二叉查找树 368

10.3 建立二叉查找树 384

10.4 高度平衡：AVL树 392

10.5 伸展树：自我调节的数据结构 407

启示和易犯的错误 428

复习题 429

进阶参考书目 430

第11章 多路树 432

11.1 果园、树和二叉树 432

11.2 词典查找树：trie 439

11.3 外部查找：B－树 444

11.4 红－黑树 462

启示和易犯的错误 471

复习题 472

进阶参考书目 472

第12章 图 474

12.1 数学背景 474

12.2 计算机表示 476

12.3 图的遍历 480

12.4 拓扑排序 482

12.5 贪心算法：最短路径 486

12.6 最小生成树 490

12.7 图作为数据结构 496

启示和易犯的错误 498

复习题 498

进阶参考书目 498

第13章 案例研究：波兰表示法 500

13.1 问题 500

13.2 思想 502

13.3 波兰表达式的求值 505

13.4 从中缀式到波兰形式的转换 515

13.5 一个交互式的表达式求值程序 520

进阶参考书目 539

附录A 数学方法 540

A.1 整数幂的和 540

A.2 对数 542

A.3 排列、组合和阶乘 548

A.4 斐波纳契数 550

A. Catalan数 552

进阶参考书目 555

B.2 策略 557

附录B 随机数 557

B.1 介绍 557

B.3 程序设计 558

进阶参考书目 562

附录C 软件包和实用函数 563

C.1 软件包和C＋＋转换单元 563

C.2 课文中的软件包 564

C.3 实用程序软件包 566

C.4 计时方法 567

D.1 数据结构和算法的选择 569

附录D 程序设计规则、启示和易犯的错误 569

D.2 递归 572

D.3 数据结构的设计 572

D.4 算法设计和分析 573

D.5 程序设计 574

D.6 用指针对象进行程序设计 575

D.7 调试和测试 576

D.8 维护 576

术语表 578