编程珠机

目录 3

前言 3

第1部分　预备知识 3

第1章　开篇 3

1.1　一次友好的对话 3

1.2　精确的问题陈述 4

1.3　程序设计 4

1.5　原则 6

1.4　实现纲要 6

1.6 问题 8

1.7　进阶阅读 9

第2章　啊哈！算法 10

2.1 三个问题 10

2.2　无所不在的二分查找法 10

2.3　原语的力量 12

2.4　归拢：排序 14

2.5 原则 15

2.6 问题 16

2.8 实现变位词程序［补充材料］ 17

2.7　进阶阅读 17

第3章　数据结构程序 20

3.1　调查程序 20

3.2　表单字母编程 22

3.3　数组例子 24

3.4　构造数据 26

3.5 针对特定数据的强大工具 26

3.7 问题 28

3.6 原则 28

3.8　进阶阅读 30

第4章 编写正确的程序 31

4.1　二分查找的挑战 31

4.2　编写程序 32

4.3　理解程序 34

4.4 原则 36

4.5　程序验证的任务 38

4.6 问题 38

4.7　进阶阅读 41

第5章 编程中的次要问题 42

5.1 从伪码到C语言 42

5.2　测试装备 43

5.3　断言的艺术 45

5.4 自动化测试 47

5.5　计时 48

5.6　完整的程序 49

5.7 原则 50

5.8 问题 51

5.9　进阶阅读 52

5.10　调试［补充材料］ 52

第2部分　性能 57

第6章 性能透视 57

6.1 案例研究 57

6.2　设计层次 59

6.3 原则 60

6.5　进阶阅读 61

6.4 问题 61

第7章　封底计算 62

7.1　基本技能 62

7.2　性能估计 65

7.3 安全系数 67

7.4　利特尔法则 68

7.5 原则 69

7.6 问题 69

7.8 日常生活中的快速计算［补充材料］ 70

7.7　进阶阅读 70

第8章　算法设计技术 72

8.1 问题和简单算法 72

8.2　两个二次算法 73

8.3　分治算法 74

8.4　扫描算法 76

8.5　重要性 76

8.6　原则 78

8.7　问题 79

8.8　进阶阅读 80

9.1　一个典型的故事 82

第9章　代码优化 82

9.2　第一个辅助采样器 83

9.3　主要的外科手术——二分查找 87

9.4　原则 90

9.5　问题 91

9.6　进阶阅读 93

第10章　压缩空间 94

10.1 关键——简单性 94

10.2　一个演示问题 95

10.3　数据空间技术 98

10.4　编码空间技术 101

10.5　原则 102

10.6　问题 103

10.7　进阶阅读 104

10.8 巨大的压缩［补充材料］ 105

第3部分　产品 109

第11章　排序 109

11.1 插入排序 109

11.2　简单快速排序 110

11.3　更好的快速排序 113

11.4　原则 116

11.5 问题 116

11.6　进阶阅读 118

第12章　抽样问题 119

12.1　一个实际问题 119

12.2　一种解决方案 120

12.3 设计空间 121

12.4　原则 123

12.5 问题 124

12.6　进阶阅读 125

第13章　查找 126

13.1 接口 126

13.2　线性结构 128

13.3　二分查找树 131

13.4　整数结构 133

13.5　原则 134

13.6 问题 135

13.8 实际查找问题［补充内容］ 136

13.7 进阶阅读 136

14.1　数据结构 140

第14章　堆 140

14.2　两个关键函数 142

14.3　优先队列 144

14.4　排序算法 147

14.5　原则 149

14.6 问题 150

14.7　进阶阅读 151

15.1　单词 152

第15章 珍珠字符串 152

15.2　词组 155

15.3　生成文本 157

15.4　原则 162

15.5　问题 162

15.6　进阶阅读 163

第一版本的尾声 164

第二版的尾声 166

排序 168

附录1 算法分类 168

查找 169

其他集合算法 170

与字符串相关的算法 171

向量和矩阵算法 171

随机对象 171

数值算法 171

附录2　估算测试 172

附录3 时间和空间成本模型 174

用空间换取时间规则 179

附录4　代码优化规则 179

用时间换取空间规则 180

循环规则 180

逻辑规则 181

过程规则 181

表示规则 182

附录5　C++中的查找类 184

部分问题的答案提示 188

部分问题的答案 193