第1章 RAPTOR程序设计基础1

1.1 程序与算法的基本概念1

1.1.1 为什么要学习程序设计1

1.1.2 程序设计的发展阶段2

1.1.3 为什么要使用RAPTOR可视化程序设计环境6

1.1.4 程序设计语言的基本概念8

1.1.5 RAPTOR的特点10

1.2 RAPTOR基本程序环境10

1.2.1 基本符号10

1.2.2 变量11

1.2.3 常量15

1.2.4 输入语句15

1.2.5 数据处理语句16

1.2.6 过程调用语句19

1.2.7 输出语句20

1.2.8 注释21

1.3 RAPTOR控制结构23

1.3.1 顺序控制23

1.3.2 选择控制23

1.3.3 决策表达式24

1.3.4 循环控制27

1.4 RAPTOR数组变量31

1.4.1 一维数组的创建32

1.4.2 二维数组的创建33

1.4.3 数组的运算34

1.4.4 如何使用数组变量34

1.4.5 平行数组35

1.4.6 数组应用中的注意事项35

1.5 RAPTOR子程序和子图的定义及调用35

1.6 计算问题求解的一般过程401.6.1 理解问题40

1.6.2 制定计划41

1.6.3 执行计划42

1.6.4 回顾与总结42

1.6.5 使用计算机进行问题求解: 程序开发周期43

1.7 小结与回顾44

习题44

第2章 算法设计与可视化46

2.1 算法初步46

2.1.1 算法的由来与定义46

2.1.2 算法的特性49

2.1.3 算法设计的要求49

2.2 算法效率的度量51

2.2.1 算法效率的基本估算方法51

2.2.2 实验验证方法53

2.3 算法复杂度53

2.3.1 函数的渐近增长54

2.3.2 算法时间复杂度定义54

2.3.3 推算大O阶方法55

2.4 计算的可视化问题57

2.4.1 算法设计的可视化57

2.4.2 计算过程的可视化58

2.4.3 计算问题和结果的可视化60

2.4.4 RAPTOR与流程图规范之间的关系与差别61

2.5 RAPTOR算法设计常用子程序63

2.5.1 随机数的产生与存储63

2.5.2 将计算结果存储到文件64

2.5.3 从文件中读入基础数据65

2.5.4 RAPTOR图形输出67

2.5.5 RAPTOR图形窗口中的用户交互74

2.5.6 图形输出案例: 随机漫步的模拟模型75

2.6 小结与回顾81

习题81

第3章 基本算法和策略83

3.1 基本算法83

3.1.1 蛮力法83

3.1.2 分段函数84

3.1.3 递推法86

3.1.4 模运算89

3.1.5 字符和字符串运算89

3.1.6 递归93

3.1.7 数论问题98

3.1.8 组合计算102

3.1.9 迭代法105

3.2 基本策略108

3.2.1 贪心策略108

3.2.2 分治策略110

3.2.3 回溯策略111

3.2.4 动态规划114

3.2.5 将递归算法转化为非递归的实现117

3.2.6 基本算法策略的讨论119

3.3 小结与回顾121

习题121

第4章 模型化124

4.1 从有限状态机到图灵机124

4.1.1 什么是模型125

4.1.2 如何建立模型126

4.1.3 什么是有限状态机126

4.1.4 如何设计和应用有限状态机129

4.1.5 可视化有限状态机的实现案例: 电子宠物游戏130

4.1.6 什么是图灵机136

4.1.7 如何使用RAPTOR模拟图灵机139

4.1.8 有限状态机与图灵机的比较148

4.2 使用RAPTOR实现抽象数据类型149

4.2.1 对现实世界中的问题进行数据抽象149

4.2.2 使用RAPTOR实现线性表151

4.2.3 使用RAPTOR实现树155

4.3 小结与回顾164

习题164

第5章 排序与查找166

5.1 排序166

5.1.1 计算机如何进行排序167

5.1.2 直接插入排序169

5.1.3 桶排序172

5.1.4 冒泡排序172

5.1.5 快速排序176

5.1.6 归并排序178

5.1.7 排序算法的分析178

5.2 查找180

5.2.1 顺序查找180

5.2.2 二分查找181

5.2.3 分块查找182

5.2.4 哈希查找188

5.2.5 查找算法的分析198

5.3 小结与回顾199

习题199

第6章 信息论、哈夫曼编码与二叉树201

6.1 问题的引入201

6.1.1 信息表达203

6.1.2 数字表达204

6.1.3 字符表达205

6.2 信息论基础207

6.2.1 什么是信息207

6.2.2 信息的量化208

6.3 哈夫曼编码212

6.3.1 哈夫曼编码原理213

6.3.2 使用RAPTOR实现哈夫曼编码的算法215

6.4 二叉树220

6.4.1 二叉树的遍历224

6.4.2 堆排序227

6.4.3 二叉搜索树228

6.4.4 平衡二叉树236

6.5 小结和回顾240

习题241

第7章 图论基础与应用243

7.1 图的定义和常用术语244

7.2 图的存储246

7.2.1 邻接矩阵存储原理246

7.2.2 使用RAPTOR建立已知图的邻接矩阵248

7.2.3 邻接表存储原理249

7.2.4 使用RAPTOR建立已知图的邻接表252

7.3 图的遍历253

7.3.1 深度优先搜索254

7.3.2 广度优先搜索255

7.3.3 求图的连通分量 256

7.4 图算法的应用258

7.4.1 最小网络建设成本258

7.4.2 最短的旅行路线260

7.4.3 地图着色问题266

7.4.4 商业网点的最省布点方案269

7.5 在RAPTOR中实现图算法的可视化271

7.5.1 图类算法的问题可视化271

7.5.2 真实的地图与抽象图的叠加274

7.5.3 棋类游戏的实现276

7.6 小结与回顾279

习题279

第8章 计算工具的评估和选择281

8.1 计算工具的精度评估281

8.1.1 误差的来源282

8.1.2 绝对误差、相对误差和有效数字283

8.1.3 计算工具的精度设计与误差284

8.1.4 误差分析与实践289

8.2 从RAPTOR到C++的算法环境转换290

8.2.1 递归程序290

8.2.2 文件输入输出292

8.2.3 图形问题294

8.2.4 RAPTOR的转换和编译问题297

8.2.5 RAPTOR与C/C++的比较与选择300

8.3 面向对象的程序设计与RAPTOR303

8.3.1 OOP的基本概念304

8.3.2 封装304

8.3.3 继承305

8.3.4 多态性305

8.3.5 典型的面向对象的程序语言306

8.3.6 RAPTOR对OOP的支持306

8.4 逆向工程: 从代码到流程图312

8.4.1 CVF介绍312

8.4.2 CVF流程图与RAPTOR的比较315

8.4.3 AutoFlowchart介绍315

8.5 电子表格软件与数值计算316

8.6 小结与回顾320

习题320

附录A RAPTOR图形操作指南322

A.1 RAPTOR图形坐标322

A.2 色彩322

A.2.1 设置颜色323

A.2.2 生成随机色彩323

A.3 绘图操作323

A.3.1 清理窗口324

A.3.2 画弧324

A.3.3 画圆325

A.3.4 画椭圆325

A.3.5 绘制可以旋转角度的椭圆326

A.3.6 绘制位图326

A.3.7 装载位图327

A.3.8 画线327

A.3.9 填色327

A.3.10 取得像素的色彩328

A.3.11 设置像素的色彩328

A.4 键盘操作328

A.4.1 取键值329

A.4.2 取键字符串329

A.4.3 判断某个键是否处于按下状态330

A.4.4 判断某个击键动作是否已经发生过330

A.4.5 等待键入331

A.5 鼠标操作331

A.5.1 取得鼠标按键与指针位置331

A.5.2 取得鼠标指针的X值331

A.5.3 取得鼠标指针的Y值332

A.5.4 判断鼠标键是否处于按下状态332

A.5.5 判断鼠标键是否被按下过332

A.5.6 判断鼠标键是否已经释放333

A.5.7 等待某个鼠标按键动作333

A.6 文本操作333

A.6.1 显示数字334

A.6.2 显示文本334

A.6.3 取得字模的高度334

A.6.4 取得字模的宽度335

A.6.5 设置字号335

A.7 窗口操作335

A.7.1 关闭窗口335

A.7.2 取得窗口的最大高度336

A.7.3 取得窗口的最大宽度336

A.7.4 判断图形窗口是否打开336

A.7.5 打开图形窗口337

A.7.6 设置窗口的标题栏337

A.7.7 平滑动画显示效果337

术语对照表339参考文献348参考网站349

参考文献197