第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