论C++语言在信息学竞赛中的应用pdf.docx

IOI2004 国家集训队论文 韩文弢
论 C++ 论 语言在信息学竞赛中的应用
浙江省余姚中学 韩文弢
摘要 程序设计语言是信息学竞赛的一个重要组成部分，任何算法只有通过程序设计语言
实现之后才能真正解决问题。C++语言凭借其高度的灵活性和强大的功能在大学生竞赛中
被非常广泛地使用，在中学生竞赛中的使用也越来越广泛。本文分为三章，由浅入深地介
绍了 C++语言的基础知识、面向对象编程基础和常用标准库、标准模板库（STL） 。希望本
文能够对想在信息学竞赛中使用 C++语言的读者有所帮助。
关键字 信息学竞赛 C++程序设计语言 标准模板库
目录
前言..................................................................................................................................................2
1 从 Pascal 到 C++..........................................................................................................................3
1.1 世界，你好！ ...................................................................................................................3
1.2 类型和定义 .......................................................................................................................4
1.3 指针、数组和结构 ...........................................................................................................7
1.4 表达式和语句 .................................................................................................................11
1.5 函数 .................................................................................................................................14
1.6 常用的库函数 .................................................................................................................16
1.7 本章小结 .........................................................................................................................17
2 深入 C++语言............................................................................................................................20
2.1 类 .....................................................................................................................................20
2.2 操作符重载 .....................................................................................................................24
2.3 字符串 .............................................................................................................................26
2.4 流 .....................................................................................................................................27
2.5 本章小结 .........................................................................................................................30
3 STL 简介.....................................................................................................................................33
3.1 STL 概述 ..........................................................................................................................33
3.2 迭代器 .............................................................................................................................34
3.3 算法 .................................................................................................................................35
3.4 容器 .................................................................................................................................42
3.5 本章小结 .........................................................................................................................45
总结................................................................................................................................................46
参考文献........................................................................................................................................48
第 1 页 共 48 页

IOI2004 国家集训队论文 韩文弢
前言
信息学竞赛一般要求在一定的时间内，理解并分析题意，设计符合给定时间和空间复
杂度要求的算法，并在计算机上使用一定的程序设计语言正确地实现算法。由于整个竞赛
存在时间限制（特别是 ACM/ICPC 类竞赛，在解决问题数目相等的情况下以做题累计时间
的多少来决定名次） ，因此所使用的程序设计语言能否正确、快速地实现算法对竞赛的成绩
影响颇大。所以，编程复杂度越来越受到重视。编程复杂度在很大程度上与所选用的程序
设计语言有关。一般信息学竞赛比较常用的程序设计语言有以下几种：BASIC、Pascal、
C/C++、Java，它们的特点如下表所示：
BASIC Pascal C++ Java
学习难度 容易 一般 较难 较难
语言特点 简单 严谨 灵活 高度面向对象
程序运行速度 慢 较快 快 慢
库函数功能 弱 一般 很强 强
在目前的中学生信息学竞赛中，Pascal 语言使用较为广泛。但是 C++语言凭借其本身
所具有的高度的灵活性，以及它所带的库的强大功能，被越来越多的选手所使用。本文就
1 是在这样一个背景下撰写的。在本文中，Pascal 语言以 Free Pascal 为准；而 C++语言则以
标准的 ANSI/ISO C++ 2 为准。
另外，需要注意的一点是，本文并不是参考资料。因此，对于 C++语言，本文不可能
介绍得面面俱到，十分详细。如果想更加深入的学习 C++语言，可以阅读有关资料。
1 原因有二：1、标准 Pascal 所提供的东西实在是太少了；2、Free Pascal 在目前竞赛中使用较为广泛。推荐编译器：Free Pascal 1.0.10 (http://www.freepascal.org)。2 C++标准请参考《C++程序设计语言（特别版） 》 。推荐编译器：gcc 2.95.3(http://www.gnu.org/software/gcc/gcc.html,
第 2 页 共 48 页

IOI2004 国家集训队论文 韩文弢
1 从 从 Pascal 到 到 C++
阅读本章的必要条件：会使用 Pascal 语言、了解一定的算法知识
由于目前中学生信息学竞赛中使用 Pascal 语言的选手较多，本章的目的就是使读者在
已经掌握 Pascal 语言的情况下，能够尽快地从 Pascal 语言转型到 C++语言。如果你已经对
C++语言有一定的了解，可以跳过本章，直接阅读下一章。
1.1 世界，你好！
首先，让我们通过一个非常简单的 C++程序，来初步地了解 C++语言。
//: C01:Hello.cpp
// Hello, world!
#include <iostream>
using namespace std;
int main() {
cout << "Hello, world!" << endl;
} ///:~
这个程序的作用就是在屏幕上输出“Hello, world!”的字样。
第一行、第二行以及最后一行中，从“//”开始到行末的部分都是注释。在 C++中，
注释有两种写法。一种是从 C 中继承的块注释，以“/*”开始，到“*/”结束。另一种
就是新增的行注释，从“//”开始，到行末为止。
3第三行中以“#”开始的内容被称为预处理指令，这一行的作用是把一个叫做 iostream
的头文件包含到我们的程序中来，相当于 Pascal 中使用单元的 uses 语句。不过 Pascal 中默
认使用 System 单元，其中包含了我们常用的绝大多数过程和函数，而 C++默认是不包含任
何头文件的。另外，C 语言中的头文件都是以.h 结尾的，而标准的 C++提倡使用没有扩展
名的头文件。
第四行让我们可以在程序中直接使用 std 名字空间内的标识符。std 名字空间包含了所
有标准 C++提供的类和函数，为了简便起见，一般总在包含头文件的预处理命令后写上这
一行。有关名字空间的详细内容可以参考有关资料。
第五行到第七行就是程序的主体。 在这个程序中， 我们定义了一个名字为 main 的函数。
这个函数就相当于Pascal中的主程序。 任何一个能够独立执行的C++程序都需要有一个main
函数。我们还可以看出，在 C++中， “{”和“}”就相当于 Pascal 中的“begin”和“end” 。
第六行的作用就是向屏幕输出“Hello, world!” ，并换行。其中，cout 就代表标准输出
（一般就是屏幕） ，相当于 Pascal 中的 Output。 “<<”在 C++中本来是位左移运算符，但是
在这里被重新定义为插入符，作用是把一段内容插入到一个输出流中。endl 就是换行的意
思。另外， C++中的字符串是用双引号括起来的，每一个语句也用“;”表示结束。
3 头文件 iostream 中包含了 C++中流的类和相关函数的定义，可以用来进行输入输出。详细的使用方法将
在第二章中进行描述。
第 3 页 共 48 页

IOI2004 国家集训队论文 韩文弢
1.2 类型和定义
类型
与 Pascal 相似，C++也提供了基本类型以及程序员可以自定义的类型。下表展示了 C++
中一些常用的基本类型以及与之对应的 Pascal 类型：
名称 C++类型 Pascal 类型 范围 大小
bool Boolean true / false 1布尔型
char Char1所有单字节字符字符型
char ShortInt -128 .. 127 18 位有符号整型unsigned char Byte 0 .. 255 18 位无符号整型short SmallInt -32768 .. 32767 216 位有符号整型 unsigned short Word 0 .. 65535 216 位无符号整型
int LongInt -2147483648 .. 2147483647 432 位有符号整型
unsigned int LongWord 0 .. 4294967295 432 位无符号整型63 63 -2 long long .. 2 Int64 -1 864 位有符号整型64 QWord 0 .. 2 unsigned long long -1 864 位无符号整型 float Single 1.17e-38 .. 3.40e38 4单精度浮点型
double Double 2.22e-308 .. 1.79e308 8双精度浮点型
long double Extended 3.36e-4932 .. 1.18e4932 10/12扩展浮点型
布尔型
与 Pascal 相似，布尔型用来表示逻辑运算的结果。一个布尔型量的值只可能是 true 或
者 false，true 的数值是 1，而 false 的数值是 0。与 Pascal 不同的是，在 C++中，很多其他
类型的量都可以隐式地转化为布尔型， 这时， 非零的值都被转化成 true， 而零被转化成 false。
字符型
单个字符的常数要用单引号括起来，一些不能显示的字符可以通过转义符来表示（参
见下表） 。另外，从上表中可以看出，在 C++中，字符型和单字节的整型实际上是等价的。
举例来说，'A'的数值就是 65。
名称 ASCII 名称 C++名称NL(LF)\n换行
HT\t水平制表符
VT \v竖直制表符
BS \b退格
CR\r回车
FF\f复位
BEL\a铃声
\ \\反斜杠
? \?问号
第 4 页 共 48 页

IOI2004 国家集训队论文 韩文弢
' \'单引号
" \"双引号
ooo 八进制 ASCII 码 \ooohhh 十六进制 ASCII 码 \xhhh
整型
C++中的整型和 Pascal 差不多，值得注意的是 C++中的各种整型的类型名实际上是由
三部分组成的。首先是 signed 或者 unsigned，表示有符号或者无符号，默认为有符号；其
次是长度的修饰词（char 除外） ，有 short、long、long long，默认为 long；最后就是 int，
在前面有修饰词的情况下可以省略。
在 C++中，整型的常数是由前缀、数字序列以及后缀构成的。前缀用来描述常数所使
用的进制，默认是十进制，以“0”开头的是八进制，以“0x”开头的是十六进制。后缀
描述该常数的长度和有无符号， “l”表示 32 位整数， “ll”表示 64 位整数， “u”表示无
符号整数，可以组合使用。另外，前缀和后缀中的字母大小写不限。
浮点型
C++中的浮点型和 Pascal 也差不多。浮点型的常数也有定点和浮点两种写法。定点数
的写法基本与 Pascal 一致，区别在于在 C++中如果整数部分或者小数部分为零就可以省略，
但是小数点必须保留。例如， “39.”和“.142857”在 C++中都是合法的。浮点数的写法
与 Pascal 相同，底数和阶码之间用“e”分隔。另外，C++中的浮点数还可以带后缀， “f”
表示单精度型， “l”表示扩展型，省略则表示双精度型。
枚举类型
与 Pascal 类似的，C++中也有枚举类型。例如：
enum keyword {ASM, AUTO, BREAK}
其中，该枚举类型的名称是 keyword，值可以是 ASM、AUTO 或者 BREAK。
C++语言没有提供内置的子界和集合类型。另外也没有提供内置字符串类型，但是字
符串处理的方式却有两套。一套是从 C 语言中继承的字符指针的处理方式，比较麻烦，具
体请参考有关资料；另一套则是 C++标准库提供的 string 类，比较方便，将会在 2.3 中详
细描述。
为了了解各种类型实际所占的字节数，我们来看下面这个程序：
//: C01:Types.cpp
// Built-in types
#include <iostream>
using namespace std;
int main() {
cout << "Size of bool: "
<< sizeof(bool) << endl;
cout << "Size of char: "
第 5 页 共 48 页尊敬的用户,免费版软件只能转换5页,如需转换更多页面请升级为VIP用户