【信息学奥数】—— 第一部分 C++语言 知识总结

C++语言

先学习，再应用。先简单，再复杂。

一、C++语言入门

1、C++程序基本结构。

//头文件(必须)
#include<iostream> //cin cout头文件
#include<cstdio>   //scanf printf头文件
//命名空间(必须)
using namespace std; //C++标准库中所有标识符都被定义在一个名为std的namespace中
//全局变量
vector<vector<int>> result; //诸如此类
//宏定义
#define PI 3.1415 //诸如此类
//函数声明
函数返回值类型 函数名(参数列表);
//主函数(必须)
int main()  //程序入口
{//处理输入//处理输出return 0; //0代表正常结束 非0代表异常
}
//函数定义
函数返回值类型 函数名(参数列表)
{//函数体//返回值
}

//示例
#include<iostream>
using namespace std;
int main()
{cout<<"Hello World"<<endl;return 0;
}

二、顺序结构程序设计

顺序，顾名思义，分析问题，按照步骤顺序，一步一步的执行。

运算符和表达式

1、常见运算符类型以及优先级与结合性。

运算符优先级：各类运算符在同一个表达式中运算先后顺序

运算符结合性：同类运算符在表达式相邻位置运算左右方向

单目运算符优先级 > 双目运算符优先级 > 三目运算符优先级

算术运算符优先级 > 关系运算符优先级 > 逻辑运算符优先级 > 赋值运算符优先级

左结合性：某一个变量左右两个运算符优先级相同，将该变量先与左边的运算符结合，计算完后再与右边的运算符结合，从左向右计算。

右结合性：某一个变量左右两个运算符优先级相同，将该变量先与右边的运算符结合，计算完后再与左边的运算符结合，从右向左计算。

先将表达式中的运算符找出来，然后根据运算符优先级从高到低依次计算，当遇到相邻的优先级相同的运算符时，再根据运算符结合性是左结合性还是右结合性计算。

类型	示例
算术运算符	+、-、*、/、%、++、–
关系运算符	>、<、>=、<=、==、!=
逻辑运算符	&&、||、!
位运算符	&、|、~、^、>>、<<
赋值运算符	=、+=、-=、*=、/=、%=、&=、|=、^=、>>=、<<=

2、赋值运算符。

• 赋值运算符=是右结合性，即a=b=c=d=e=5，等价于(a=(b=(c=(d=(e=5)))))，即e=5、d=e、c=d、b=c、a=b。
• 如果赋值运算符左右两边数据类型不同，系统会自动隐式将赋值运算符右边的数据类型转换为左边的数据类型，也可以手动显式进行数据转换。

3、逗号表达式。

表达式1，表达式2，……，表达式n     逗号表达式的值为表达式n的值

常量和变量

1、常量。

程序中需要经常用到的常量一般使用符号常量来进行保存：一方面可以增加程序的可读性，另一方面可以增加程序的易改性。

2、变量。

变量包含变量名（命名规则）、变量对应的数据类型（数据操作）、变量的取值范围（有效位数）。

类似于鸡兔同笼求解方程问题，使用已知变量表示未知变量，再进行求解即可。

标准数据类型

1、标准数据类型。

数据类型	注意事项
整型 short int long unsigned	先使用sizeof计算字节数a，再乘以8得到位数b，有符号整型范围就是2(b-1)，无符号整型范围就是2b
实型 float double	科学计数法为：aEb，a是十进制表示的小数尾数，E是以10为底的底数，b是十进制表示的整数指数
字符型 char	字符对应ASCII码为整数
布尔型 bool	真为true对应1 假为false对应0

2、数据类型转换。

• 显式转换（人为手动）。
• 隐式转换（程序自动）。

数据输入输出

1、输入输出函数。

• ch=getchar();
• putchar(ch);
• cin>>a;
• cout<<a<<endl;
• scanf(“%d”,&a);
• printf(“%d\n”,a);

2、scanf、printf和cin、cout的区别。

scanf/printf相对于cin/cout的区别：

• 优点：速度快。
• 缺点：写麻烦。

一般数据量较大时使用scanf/printf。

3、printf标准输出格式。

格式	含义
%d %f %c %s %e %g	整数 浮点数 字符 字符串 科学计数法 实数(小数尾部不会显示多余的零)
%- %+ %0	左对齐 右对齐 位数不够前方补零
%m.n	m是宽度 n是精度

4、scanf(“%d”,&x)返回值问题。

• scanf(“%d”,&x)==1：表示所输入的数据与格式字符串匹配的次数（一般用于while循环）。
• scanf(“%d”,&x)!=EOF：表示所输入的数据是否到达文件尾部（一般用于while循环）。

三、控制结构程序设计

控制，顾名思义，分析问题，根据情况的不同，按需选择执行。

if语句

if语句适合分支较少的情况。如果是多分支组合情况，可以考虑将复杂的多分支拆分为一个个的单分支。如题目2053三个数和题目1047判断能否被3，5，7整除。

//单分支结构
if(条件表达式)
{语句;
}

//双分支结构    等价于   ?:
if(条件表达式)
{语句;
}
else
{语句;
}

//多分支结构
if(条件表达式)
{语句;
}
else if(条件表达式)
{语句;
}
……
else
{语句;
}

switch语句

switch语句适合分支较多的情况。其首先计算switch变量表达式，然后计算case常量表达式，最后根据两者匹配情况执行对应语句。

switch(expression)
{case (constant-expression):语句;break;……default:语句;(此处是最后一种情况可以不加break)
}

四、循环结构程序设计

循环，顾名思义，分析问题，执行规律性的重复计算。

for语句

for语句适合循环次数确定的情况。分析变量从A到B增量为C。

for(控制变量初始化表达式;条件表达式;增量表达式)
{语句;……
}

while语句

while语句适合循环次数不确定的情况。分析循环条件。

while(条件表达式)
{语句;……
}

do-while语句

do
{语句；……
}
while(条件表达式);

如果单词之间使用空格分割，且至少读入一个单词，那么可以使用do while语句，且while的判断条件是是否输入空格。其他情况一般不常用。

五、数组

如果需要处理的相同类型的数据较多，那么就需要使用数组来存储元素。

一维数组

注意，定义数组时，数组的大小只能是常量表达式，而不能是变量。

const int N=100; int a[N+1]; √ 常量表达式

#define N 100 int a[N+1]; √ 符号常量表达式

int a[101]; √ 常量

int N=100; int a[N+1]; × 变量

二维数组

二维数组主要用于处理矩阵信息。

字符数组

1、字符数组存放若干字符与字符串的区别。

• 字符数组存放若干字符时，其每一个位置均可以存放任意字符，如果字符数组没有存满，那么剩余元素默认为空字符，如果字符数组存满了，那么不能使用printf(“%s\n”,a)打印；
• 字符数组存放字符串时，其最后一个位置必须为结束符’\0’，如果字符数组最后有多个’\0’，那也是字符串，可以使用printf(“%s\n”,a)打印，字符串的结束符’\0’占内存空间，但是不占字符串长度；

2、字符串的输入与输出。(头文件为cstdio)

• scanf(“%s”,字符串名称) //字符串名称前面没有&；scanf读取到空格即结束；
• gets(字符串名称) //gets只能一次读取一个字符串；gets读取到换行即结束；
• printf(“%s\n”,字符串名称) //%s只能输出字符串而不能是字符串元素；
• puts(字符串名称) //与printf等价

如果是需要截取以空格为分割的字符串，那么就使用scanf；

如果是需要一行一行的读取字符串，那么就使用fgets；

注意：gets函数在C++14中被移除了，但是可以使用fgets函数来替代gets函数。

char *fgets(char *str,int n,FILE *stream)//str：指向一个字符数组的指针，该数组存储了要读取的字符串；
//n：要读取的最大字符数（包括最后的空字符），通常使用str的数组长度；
//stream：指向FILE对象的指针，其标识了要从中读取字符的流；//fgets从指定的流stream读取一行并将其存储在str所指向的字符串中，当读取(n-1)个字符时，或者读取到换行符时，或者到达文件尾时，其就会停止；如果读取键盘，那么stream参数应该为stdin；

3、字符串处理函数。(头文件为cstring)

函数格式	函数功能
strcat(字符串名1，字符串名2)	将字符串2连接到字符串1后面并返回字符串1的值
strncat(字符串名1，字符串名2，长度n)	将字符串2前n个字符连接到字符串1后面并返回字符串1的值
strcpy(字符串名1，字符串名2)	将字符串2复制到字符串1并返回字符串1的值
strncpy(字符串名1，字符串名2，长度n)	将字符串2前n个字符复制到字符串1并返回字符串1的值
strcmp(字符串名1，字符串名2)	比较字符串1和2的大小：1>2则返回正整数；1=2则返回0；1<2则返回负整数
strncmp(字符串名1，字符串名2，长度n)	比较字符串1和2的前n个字符的大小
strlen(字符串名)	计算字符串的长度，终止符’\0’不算在长度内
strlwr(字符串名)	将字符串中大写字母转换为小写字母
strupr(字符串名)	将字符串中小写字母转换为大写字母
strstr(字符串1，字符串2)	在字符串1中查找第一次出现字符串2的位置，未找到则为null

字符串相关题目先考虑所需功能是否可以使用库函数，如果不可以再考虑可以由什么实现。

字符数组一般容易出错，之后可以使用string来替代。

六、函数

//函数声明返回值 函数名(形参列表);//函数定义返回值 函数名(形参列表)
{函数体……return ……
}//函数调用函数名(实参列表)函数调用将流程从主调函数转向被调函数，函数返回将流程从被调函数转向主调函数。

1、函数调用方式。

• 传值调用：将实参值拷贝一个副本传递给形参；形参值可以改变，但不影响主调函数的实参值；
• 传址调用：将实参变量的地址值传递给形参；形参值改变，实参值也会相应的改变；

//传值调用void swap(int a,int b){}//传址调用void swap(int &a,int &b){}

2、递归算法。

递归函数，即在函数内部直接或者间接的调用函数自身。递归，即一条路走到黑然后到底了再返回。

递归三部曲：

• 递推公式（函数体）。
• 函数参数以及返回值（函数头）。
• 终止条件（函数边界）。

七、文件和结构体

文件

C++把每一个文件都看成是一个有序的字节流，每一个文件都以文件结束标志结束。如果要操作某一个文件，程序必须首先打开文件，当一个文件被打开后，该文件就和一个流关联起来，这里的流其实是一个字节序列。

文件操作的基本步骤：

• 打开文件，将文件指针指向文件，决定打开文件类型。
• 对文件进行读、写操作。
• 使用完文件后，关闭文件。

1、常见的文件操作函数。

FILE *freopen(const char *filename,const char *mode,FILE *stream)//filename表示要打开的文件名
//mode表示文件打开的模式
//stream表示文件指针 stdin标准输入流 stdout标准输出流 stderr标准错误流//引号内是读取的对象 引号外是输出结果的地方
freopen("in.txt","r",stdin); //输入文件 从in.txt文件读入输出到stdin
freopen("out.txt","w",stdout); //输出文件 从out.txt文件读入输出到stdout
//使用scanf以及printf即可
fclose(stdin);
fclose(stdout);

FILE *fopen(const char *filename,const char *mode)//filename表示要打开的文件名
//mode表示文件打开的模式FILE *fin,*fout;
fin=fopen("in.txt","rb");  //输入文件
fout=fopen("out.txt","wb"); //输出文件
//使用fscanf(fin,)和fprintf(fout,)即可
fclose(fin);
fclose(fout);

ifstream fin("输入文件名.扩展名"); //文件输入流
ofstream fout("输出文件名.扩展名"); //文件输出流
//使用fin>>和fout<<即可
fin.close();
fout.close();

结构体

当一组数据有不同的数据类型是使用结构体。

struct 结构体类型名
{成员表;成员函数;
}结构体变量表;struct 结构体类型名
{成员表;成员函数;
};
结构体类型名 结构体变量表;//使用.访问结构体成员

八、指针及其应用

1、指针定义。

类型说明符 *变量名;
//*表示这是一个指针，变量名是指针名字，类型说明符是指针变量所指向的变量的数据类型int *p=&a;&a表示取地址；
*p表示取值；p++表示根据类型sizeof(类型)增加一个单位；
p--表示根据类型sizeof(类型)减少一个单位；指针本身是地址；数组名本身也是地址；