CCF中学生计算机程序设计-基础篇

江 涛：全国先进工作者、中学特级教师、全国信息学奥林匹克高级指导教师、佛山市南海区十佳教师

宋新波：全国青少年信息学奥赛金牌指导教师、广东省青少年信息学竞赛优秀辅导员、中山市十大杰出青年，荣获中山市学科竞赛突出贡献奖

朱全民：全国师德先进个人、雅礼中学特级教师、国际金牌指导教师、NOI十大杰出指导教师

第1章?模块化编程—函数

1.1　 自定义函数的引入................................................... 1

1.2　 函数的定义............................................................. 3

1.3　 函数调用与参数传递................................................ 5

1.4　 变量的作用域.......................................................... 9

1.5　 函数的应用........................................................... 11

1.6　 递归函数.............................................................. 20

第2章?字符串处理—string类型

2.1　 string类型的引入................................................... 33

2.2　 string类型的基本操作............................................. 36

2.3　 string类型中字母与数字的关系................................ 41

2.4　 string类型的应用................................................... 48

本章小结...................................................................... 52

第3章?数据类型的组合—结构和联合

3.1　 结构体(struct)的引入............................................. 61

3.2　 结构体(struct)的使用............................................. 66

*3.3　 结构体(struct)的扩展............................................. 72

*3.4　 联合(union)的定义和使用........................................ 76

*3.5　 枚举(enum)的定义和使用........................................ 79

本章小结...................................................................... 81

第4章?功能强大的利器—指针

4.1　 指针概念、定义与内存分配..................................... 85

4.2　 指针的引用与运算.................................................. 87

4.3　 指针与数组........................................................... 90

4.4　 指针与字符串........................................................ 95

*4.5　 函数指针和函数指针数组........................................ 97

4.6　 指针的扩展......................................................... 100

本章小结.................................................................... 104

第5章?数据外部存储—文件

5.1　 数据存储的分类................................................... 109

5.2　 文件类型变量的定义及引用................................... 110

5.3　 文件的重定向...................................................... 116

本章小结.................................................................... 118

第6章?数据结构及其运用

6.1　 什么是数据结构................................................... 125

6.2　 线性表的储存结构及其应用................................... 126

6.3　 队列及其应用...................................................... 138

6.4　 栈及其运用......................................................... 145

6.5　 二分及其快速排序................................................ 151

第7章?简单算法

7.1　 什么是算法......................................................... 169

7.2　 高精度数值处理................................................... 171

7.3　 简单枚举算法...................................................... 178

7.4　 模拟算法............................................................. 184

7.5　 简单动态规划...................................................... 187

7.6　 用递归实现回溯算法............................................. 199

第8章?数学在程序设计中的应用

8.1　 常用数学函数...................................................... 207

8.2　 质因数的分解...................................................... 209

8.3　 最大公约数的欧几里德算法................................... 212

8.4　 加法原理与乘法原理............................................. 216

8.5　 排列与组合......................................................... 219

8.6　 圆排列、可重集排列............................................. 222

第9章?STL（标准模板库）简要说明

9.1　 STL中的一些新概念.............................................. 227

9.2　 几个常见的容器介绍............................................. 232

9.3　 几个常见的算法函数............................................. 240

索引　　　 245

序

由中国计算机学会（CCF）组编的“CCF中学生计算机程序设计教材”面世了。

早在1984年，邓小平就提出“计算机的普及要从娃娃抓起”。这很有先见之明，但这里的“计算机普及”是泛指，并未明确普及哪些内容。在过去的三十多年中，中小学广泛开展了计算机普及活动，2000年教育部也曾发文，要在全国中小学开展信息技术教育。但事实上，现有的所谓“普及”大多成了对计算机工具的认识，而不是对中小学生智力的开发和思维的训练，因而效果不佳。CCF早在1984年就创办了“青少年信息学奥林匹克竞赛NOI”，这是面向那些学有余力的中学生的一项计算机科学（CS）教育活动，但具备开展这项活动的学校并不很多，每年参加NOI联赛的学生不过七八万，比例很小，因而普及的面并不大。

计算机科学教育的核心是算法设计和编程，这要求学生面对一个给定的现实问题要能够找到一个正确和高效的办法（算法）并将其变成计算机能理解的语言（程序设计语言），进而让计算机计算出人们需要的结果来。像快递员最佳路径算法就是一个典型的现实问题。这个过程并不容易，因为将一个问题抽象并构造一个模型，需要一定的数学基础，还得理解计算机的特点，“指挥”计算机干活。这还涉及欲求解问题的“可计算性”，因为并不是任何问题都可以由计算机求解的。计算机也并不知道什么是“问题”，是人告诉计算机，如何按照一步一步的程序求解。这个过程，就会训练一个人求解问题的能力，相应地，其具备的让计算机做事的思维能力称之为“计算思维”（Computational Thinking）。我们平常操作计算机（包括手机这些终端设备）仅仅像开关电灯那样简单，并不会使我们具备计算思维能力，而只有通过上述步骤才能训练这样的能力。随着计算机和网络的发展，未来越来越多的工作将和计算（机）有关（据美国政府的统计是51%以上）。我们必须知道如何让计算机做事，起码知道计算机是如何做事的，这就要求普及计算机科学教育（注意：不是计算机教育，也不是信息技术教育）。

美国政府已经把在中小学普及计算机科学当成一种国策（CS for All，每一个人学习计算机科学），并投入40亿美元落实这一项目。奥巴马总统说“在新经济形态中，计算机科学已不再是可选技能，而是同阅读、写作和算术一样的基础技能……因此，我制定了一项计划，以确保所有孩子都有机会学习计算机科学。”美国政府已明确把计算机教育列入（从幼儿园到12年级）教育体系K12中。英国从2014年起，对中小学的计算机课程进行重大改革，5岁的儿童就开始学写程序。英国教育部启动了“计算机在学校”（Computing at School，CAS）项目。新西兰等国也把计算机编程课当作中学的必修课，并为此投入资金培训教师。未来的竞争不是资源的竞争，而是人才的竞争，如果不具有计算素养和技能，则在未来的社会中处于被动地位。

CCF作为一个负责任的学术社会组织，应该勇于承担起CS普及的任务，这比NOI更加艰巨，更难。不过有NOI三十多年发展的基础，会对未来CS的普及提供有益的经验。

普及计算机科学教育的难点在于师资，而培训师资需要合适的教材。CCF组织富有程序设计教学经验的中学老师编写了“CCF中学生计算机程序设计教材”，分为入门篇、基础篇、提高篇和专业篇，只要有一定数学基础的老师，均可从入门篇修起。学习编程并不像人们想象的那么困难，只要从现实中遇到的（简单）问题出发，循序渐进，通过和计算机的互动，一旦入门就好办了，以后就可以逐步深入下去。

感谢朱全民、陈颖、徐先友、江涛、邱桂香、宋新波、汪星明、屈运华、廖晓刚等老师的贡献，他们花了两年时间写成了这套教材。感谢吴文虎教授、王宏博士审阅本书，在此向他们表示感谢。

杜子德

中国计算机学会秘书长

2016 年8 月29 日