1. 前言

1.1. 目标读者

  • 对C/C++语言有初步了解，能使用g++编译器编译运行C++语言程序。

  • 计划参加NOI、CSP-J/S等认证考试或算法竞赛。

1.2. 代码环境

  • 所有代码符合C++98规范，并在NOI Linux下用g++ 4.8.4编译器编译运行通过。

  • 代码在Windows系统下使用Dev C++编译运行可能会有微小差异。

1.3. 算法编程 vs 工程编程

算法编程和工程编程在编码风格、程序设计等方面存在许多不同之处。从算法编程起步的学习者，常会养成许多被工程编程视为洪水猛兽的“坏习惯”。此处逐一列举说明，以免从一开始就养成一些不好的编码习惯。

  1. 不对输入数据进行有效性检验。算法编程题的输入数据不会存在无效数据，例如格式错误、类型错误、数值超限、遗漏、重复等，因此算法编程在输入数据时不进行数据有效性检验。工程编程则不然，要面对软件用户各种有意无意地输错数据点错按钮等，所以工程编程时对于获得的外部数据总是要进行严格的有效性检验才能使用。在学习算法编程阶段，确实可以不用检验数据有效性，但是如果今后参与工程编程，千万记住绝对不可以读到数据就拿来用。

  2. 代码可读性差。算法编程极少出现多人合作的情况，基本都是独自完成，而且程序一般都是以解决单一问题为目标的简单结构。因此代码可读性往往很差，甚至许多教材上的代码都是极为“丑陋”的，比如：

    • 变量、函数、自定义类型取名简短甚至无意义，例如 int a；

    • 变量命名不符惯例，例如用大写字母命名变量，小写字母命名常量；

    • 代码不写注释，甚至自定义函数、类型都不写注释；

    • 自定义函数不使用原型(prototype)与定义(definition)分离的原则，全部堆积在 main() 函数前直接定义。

    针对这一点，我们建议在算法编程时至少应该做到：除了题目中明确给出了名字的变量以外，其他变量名、函数名、类型名都要遵循C++语言的惯例定义一个好名字，即变量和函数用符合其含义的英语单词、惯例缩写或词组取名，单词之间用下划线连接，全部小写字母，例如 data、exp_table；常量的取名规则相同，但全部用大写字母；自定义类型的名称不用下划线连接单词，而是每个单词首字母大写，单词和单词连在一起，英语缩写的全部用大写，例如 MyDataType、NOIDataType；自定义的函数，除了内联函数以外，其他都要原型与定义分离，原型放在 main() 函数前面，定义放在整个程序的后部。

  3. 大量使用全局变量。算法编程为了方便经常使用全局变量，而工程编程的铁律是“不到万不得已绝不使用全局变量”。算法编程滥用全局变量的原因有：

    • 超大型数组：为了定义局部变量空间不够容纳的超大数组；

    • 避免数据初始化：局部变量必须由程序进行显式的初始化，而全局变量会自动初始化为全0；

    • 减少自定义函数的参数：使自定义函数能直接使用这些变量，而不是通过传递参数，当变量是大数组、大结构体时尤其方便。

    在算法编程这一特殊领域，偶尔使用全局变量确实能带来一些便捷，但若滥用必然弊大于利，不能从一开始就养成这一不良习惯。事实上，就算是算法编程，最好也应该尽量不用全局变量。

1.4. 纯C++ vs C/C++混合

C++语言是C语言的扩展，它不光有自己的一整套完整的编程语言体系和功能强大的STL模板库，而且完全继承了传统的C语言标准库。C标准库虽然功能不如C++的STL库强大，但其库函数的运行速度往往极快，故目前仍被大量使用，不会被淘汰，笔试题也仍然会考传统C语言代码。因此非常有必要学习掌握这些来自传统C语言的内容，至少要学会以下这些部分：

  1. 输入输出：cstdio 库的 printf()、scanf()、getchar()、putchar()、fgets() 函数属于必须掌握的内容，它们的运行速度远远高于C++输入输出流，且格式化输出更方便灵活。

  2. 数据类型：cctype 库的 isXXX() 系列字符种类判断函数，toupper() 和 tolower() 两个大小写转换函数，climits 库的九种基本数据类型最大最小值宏，例如表示 int 型数据最大值的 INT_MAX，这些也是应当掌握的内容。

  3. 字符串：C语言使用字符数组来实现字符串，称为C-string，这是必须掌握的内容，要熟知其概念，并会熟练使用数组操作来进行简单的字符串处理，同时应能熟练使用 cstring 库的 strlen()、strcpy()、strcmp() 三个函数，cstring 库中的其他函数最好也能有一定了解。

也有一些传统的C语言语法是现在C++编程时不建议使用的，包括下面这些：

  1. 动态内存分配：应该使用C++的 new 和 delete 命令来进行动态内存分配，不再使用传统的 malloc() 和 free() 函数；

  2. 指针型函数参数：除了利用指针型参数模拟传数组和C-string以外，其他情况都应使用C++的传引用来代替传指针；

  3. 指针操纵数组：算法编程时尽量不要使用指针来访问数组元素，应该使用下标，尤其是对二维及以上的多维数组，指针操作极其危险。