声明
本系列来至中国大学慕课-阚道宏老师的C++系列课程的相关课堂笔记，阚道宏老师讲解细腻、精准，由浅入深，徐徐渐进，有兴趣的可以去中国大学慕课上查看阚道宏老师的相关课程。
本文仅用于学习交流，若有侵权，请联系我
算法与控制结构
一个完成某种特定任务的过程，可分解成一组操作步骤，这组操作步骤即构成一个算法。
一、算法
程序设计过程中，程序员将完成某种程序功能的过程，分解成一组可被计算机执行的操作步骤，这组操作步骤就叫算法。
1.1 算法设计的方法
- 流程图
- 伪代码
- 自然语言
1.2 算法结构
- 顺序结构：按照书写顺序依次执行操作步骤的算法
- 选择结构：某些操作步骤需要满足特定条件才被执行的算法
- 循环结构：满足特定条件下，将循环执行某些操作步骤的算法
1.3 条件
选择结构和循环结构都需要用到条件，条件成立，我们称这个条件为真，否则称之为假，C++语言使用布尔类型来表达条件的真假，通过关系运算符构成的关系表达式来描述条件。还可以根据逻辑运算符构成的逻辑表达式来符合条件。
- 布尔类型：真（true）/假（false）
- 关系运算符：大于（>）、大于等于（>=）、小于（<）、小于等于（<=）、不等于（!=）、等于（==）
- 逻辑运算符：与（&&）、或（||）、非（!）
使用C++语言，将设计好的算法，编写成一组语句序列，这就是C++源程序，为了描述选择结构和循环结构的算法，C++分别提供了选择语句和循环语句。
二、布尔类型
2.1 布尔类型数据的基本概念
布尔（bool）类型：true、false，true和false都是关键字，可以定义布尔类型变量保存布尔型数据，一个布尔型变量占用1个字节，计算机只能存储数值数据，因此计算机内部以1表示true，0表示false。
#include <iostream>
using namespace std;
int main()
{
bool x = true;//定义一个布尔型变量x，初始值化为true
cout<<x<<endl;//显示变量x的值，true被显示为1
int y; //再定义1个int型变量
y=x;// 将布尔型变量x赋值给int型变量y，C++将自动转化类型，true被转换为1
cout<<y<<endl;//显示y的值，结果为1
x=5; //将int型变量5赋值给布尔型变量，5被转换为true，即非0转换为true，此时编译器会提示warning错误
cout<<x<<endl;//显示变量x的值，true显示被显示为1
return0;
}
在布尔型数据中，true和false是常量。除了赋值运算外，还可以对布尔类型的变量进行关系运算，或者是逻辑运算。
2.2 关系运算符
由关系运算符构成的表达式，就是关系表达式，关系表达式的作用就是比较两个数的大小，比较的结果是布尔类型，结果为true说明条件成立，为false说明条件不成立。
| 关系运算符 | 优先级 | 结合性 |
|---|---|---|
| 大于（>） | 6 | 从左向右 |
| 大于等于（>=） | 6 | 从左向右 |
| 小于（<） | 6 | 从左向右 |
| 小于等于（<=） | 6 | 从左向右 |
| 等于（==） | 7 | 从左向右 |
| 不等于（!=） | 7 | 从左向右 |
2.3 逻辑运算符
逻辑运算符用于判断复合条件是否成立。结果为布尔类型。
| 逻辑运算符 | 优先级 | 运算规则 |
|---|---|---|
| 与（&&） | 11 | 双目运算符，真真为真、否则都为假，相当于并取的意思 |
| 或（||） | 12 | 双目运算符，假假为假，否则都为真，相当于或的意思 |
| 非（!） | 2 | 单目运算符，非假即真，非真即假，相当于求反的意思 |
参与逻辑运算的操作数必须是布尔类型，否则将自动转换，其他类型转为布尔类型的规则是，0转为false，非0转为true。
三、选择语句
算法中某些操作步骤，需要满足特定条件才能执行，比如求变量x的倒数，需要判断x不等于0是否成立，若成立进行算法运算，否则应提示错误信息。
句型：如果......，就......，否则,,,,,,
选择结构/分支结构：如果条件成立，则执行算法分支1，否则执行算法分支2
C++语言提供了2中选择语句句型：
- if—else语句
- switch—case语句
3.1 if—else语句的语法
使用方法：
if(表达式)
{语句1;}
else
{语句2;}
语法说明：
- 表达式：指定一个判断条件，该表达结果应为布尔类型，例如关系表达式或逻辑表达式，非布尔类型表达将被自动转换，0转化为false，非0数值转化为true
- 语句1：描述算法分支1的C++语句序列，即表达式成立时执行的语句
- 语句2：描述算法分支2的C++语句序列，即表达式不成立时执行的语句。如果条件不成立时不需要执行什么处理，则可以省略else和{语句2}
- 语句1、语句2可能包含多条C++语句序列，此时必须用一对大括号”{}“括起来，如果只包含一条语句，则大括号可以省略掉。
- 计算机执行该语句时，首先计算表达式（即判断条件），若结果为true（条件成立），则执行语句1；否则执行else后面的语句2。
/*实例一：求一个数的倒数*/
#include <iostream>
using namespace std;
int main()
{
double x;
cout<<"请输入一个数值："<<endl;
cin>>x;
if (x!=0) //判断条件
/*条件成立，执行以下语句，有3条语句，所以不需大括号括起来*/
{
double y;
y = 1/x;
cout<< "x的倒数为："<<y<<endl;
}
else
cout<<"因为x的值等于0,0没有倒数"<<endl; //else只有1条语句，可以省略大括号
return 0;
}
C++语言将一对大括号括起来的语句称为一条复合语句。C++还要一种特殊的语句，空语句，是由单个；组成的，计算机在执行空语句时不会执行任何操作，空语句也没有任何实际的用途，只是在某些特殊的语法场合需要空语句。
/*实例二：判断一个年份是不是闰年*/
#include <iostream>
using namespace std;
int main()
{
int x;
cout<<"请输入一个年份："<< endl;
cin>>x;
if ((x%100!=0 && x%4==0) || x%400==0) //复合条件判断语句，用括号括起来。
cout<<x<<"是闰年";
else
cout<<x<<"不是闰年";
return 0;
}
复合判断语句用在if后面，用括号括起来。可以多层嵌套。
/*求解符号函数*/
#include <iostream>
using namespace std;
int main()
{
float x; //要判断的数
cout<<"请输入一个实数："<<endl;
cin>>x;
int a; //用来保存结果
if(x==0) //先判断0
cout<<"0没有符号,值为："<<a;
/*复合语句判断x的值，并确定a的值，最后输出提示性语句和a*/
else
{
if(x<0) a=-1;
else a=1;
}
cout<<a<<endl;
return 0;
}
if_else可以多层嵌套，每个else自动的和上面最近的if配对，如果else配对错误，那么执行结果也是错误的。所以为了慎重起见，上层的if_else语句应对添加大括号，将下层的if_else语句括起来
良好的书写习惯可以提供代码的可读性，要合理利用空格、缩进、空行和注释，来区分语句的层次，说明语句的功能和用途。
if_else多层嵌套代码可读性低，C++还提供了一种更加直观简洁的写法if...else if_..._else，的书写方式，求解符号实例可以改造为：
#include <iostream>
using namespace std;
int main()
{
float x; //要判断的数
cout<<"请输入一个实数："<<endl;
cin>>x;
int a; //用来保存结果
if(x==0) a=0;
else if(x>0) a=1;
else a=-1;
cout<<a<<endl;
return 0;
}
if-else if-else语法：
if(表达式1) 语句1;
else if(表达式2) 语句2;
......
else if(表达式n) 语句n;
else 语句n+1
- 表达式1~n分别是依次判定的条件，表达式结果应该为布尔类型，例如关系表达式或逻辑表达式，非布尔类型将自动转换，0转为false，非0值转为true
- 语句1~n表示对应条件成立执行的语句，可以是单条，可以是复合语句或空语句
- 语句n+1，是所有条件都不成立时执行的语句，可以是单条语句或复合语句，如果条件不成立，什么都不需要执行，则可省略else 和（语句n+1）
- 计算机执行语句时从1~n+1逐一判断，直到计算表达式为true，当判断到某条语句为true时，会立即执行对应的语句，后面的语句都会抛弃掉不会再执行，简而言之，计算机只能执行语句1~n+1中的一条语句。
#include <iostream>
using namespace std;
int main()
{
int x;
cout <<"请输入一个数字："<< endl;
cin >> x;
if(x == 1) cout <<"Today is Monday!"<<endl;
else if (x==2) cout <<"Today is Tuesday!"<<endl;
else if (x==3) cout <<"Today is Thursday!"<<endl;
else if (x==4) cout <<"Today is Wednesday!"<<endl;
else if (x==5) cout <<"Today is Friday!"<<endl;
else if (x==6) cout <<"Today is Saturday!"<<endl;
else if (x==7) cout <<"Today is Sunday!"<<endl;
else cout<<"数值超出1-7的范围"<<endl;
return 0;
}
3.2 C++语句条件运算符
符号标识：由问号和冒号组成“?:”
在程序设计中，如果条件成立，则执行算法分支1，否则执行算法分支2，双分的if-else支结构，可以通过条件运算符来实现简单的分支结构。语法规则如下：
表达式1 ? 表达式1 : 表达式2
语法说明：
- 有条件运算符构成的表达式称为条件表达式，其中的表达式指定一个判断条件，该表达式结果应为布尔类型，例如关系表达式或逻辑表达式，非布尔类型将自动转换，0转为false，非0值转为true
- 如果表达式的结果为true，则计算表达式1，将其结果作为整个条件表达的结果，否则计算表达式2，将表达式2的结果作为整个条件表达式的结果。
- 条件运算符是一个3目运算符，优先级为13，结合性从右向左。
int a =5, b = 10, c;a>b ? a:b //这是一个条件表达式，结果为10，数据类型为int型
cout(a>b ? a:b); //显示表达式的结果
c = a>b ? a:b; //将结果赋值给int型变量c
实列：
#include <iostream>
using namespace std;
int main(){
int a=5,b=10,c;
a>b ? a:b;
cout<<c<<endl;
c= (a>b ? a:b);
return 0;
}
3.3 switch-case语句
分支结构算法中，有一类特殊的算法，某一表达式结果，可分成若干种情况，每一种情况，只写一种算法分支，C++语言提供了switch-case结果来描述这种多分支结果。语法形式比if-else更加简洁直观。
语法：
switch(表达式)
{
case 常量表达式1:语句1;
case 常量表达式2:语句2;
......
case 常量表达式n:语句n;
default:语句n+1;
}
说明：
- 计算机执行该语句时，首先计算switch后面的表达式，然后将其结果与各case后的常量表达式结果进行比对。若比对成功，则以比对成功的case语句为起点，顺序执行后面的所有语句，直到整个switch语句结束，或遇到break语句时中途跳出，继续执行switch语句的下一条语句，如果所有比对都不成功，则将default语句作为执行的起点；
- 表达式的结果应当是整型（char、short、int、long），不能是浮点型；
- 常量表达式1~n分别列出上述表达式可能得出的结果，常量表达式只能是常量，或者由常量组成的表达式，各常量表达式的值不能相同，不能重复；
- 语句1~n分别对应常量表达式比对成功时执行的语句，通常最后都增加一条break语句作为本case的结束语句，语句1~n为复合语句时，大括号也可以省略；
- 语句n+1时default后面的语句，所有比对都不成功时应执行的语句，default语句习惯上放在最后。
实例一：有break语句跳出比对的情况
/*有break语句的情况*/
#include <iostream>
using namespace std;
int main(){
int x;
cout<<"请输入一个标识星期几的数值：";
cin>>x;
switch (x) //下列的case语句会根据switch中x的值进行比较
{
case 1:cout<<"Today is Monday!"<<endl ; break;
case 2:cout<<"Today is Tuesday!"<<endl ; break;
case 3:cout<<"Today is Thursday!"<<endl ; break;
case 4:cout<<"Today is Wednesday!"<<endl ; break;
case 5:cout<<"Today is Friday!"<<endl ; break;
case 6:cout<<"Today is Saturday!"<<endl ; break;
case 7:cout<<"Today is Sunday!"<<endl ; break;
default: cout<<"input error"<<endl;
}
//每个case语句只要是执行了cout语句，程序功能就已经完成
//使用break语句中途跳出switch语句，继续执行switch语句的下一条语句，即return语句
return 0;
}
实例二：无break的情况
#include <iostream>
using namespace std;
int main(){
int mouth;
cout<<"请输入一个标识月份的数值：";
cin>>mouth; switch (mouth)
{
case 1:
case 3:
case 5:
case 7:
case 8:
case 10:
case 12:cout<<"这个月是大月，有31天"<<endl; break;
case 4:
case 6:
case 9:
case 11:cout<<"这个月是小月，只有30天"<<endl; break;
case 2:cout<<"2月天数为28天，闰年29天"<<endl; break;
default: cout<<"input error"<<endl;
}
return 0;
}
若多个case的语句一样，可以共用语句。
四、循环语句
有些算法，在满足特定条件下，将重复执行某些操作步骤，这种结构称之为循环结构，循环结构就是在条件成立时，重复执行某个操作，否则结束循环。
循环4要素：循环变量、初始值、循环条件、循环体
循环语句：while语句、do—while语句、for语句
实例分析：求奇数数列1,3,5.......2n-1的前N项累加和，公式，奇数数列前N项的和，是一个重复累积的过程，累加起点就是n=1时，累加条件是n
N，直到这个条件不成立。
4.1 while语句
语法：
while(表达式)
语句
- 表达式指定一个循环条件，该表达式结果应为布尔类型，例如关系表达式或逻辑表达式，非布尔类型将自动转换，0转为false，非0值转为true
- 语句是描述循环体的C++语句，即条件成立时循环执行的语句，如循环条件开始就不成立，则循环体一次也不执行，循环体中应包含循环条趋向于false的语句，否则循环条件一直为true，循环体将无休止执行，俗称“死循环”
- 计算机执行该语句时，首先计算表达式（即循环条件），若结果为true（条件成立），则重复执行循环体语句，否则跳出循环。
/*求奇数数列1,3,5.......2n-1的前N项累加和*/
#include <iostream>
using namespace std;
int main(){
int N,sum=0,n=1; //定义变量，并将用于保存结果的sum初始化为0，开始的n初始化为1
cout<<"请输入计算的值：";
cin>>N; //获取前N项
while (n<=N)
{
sum += 2*n-1; // 等价于sum=sum+2*n-1,
n++; //执行完上一条语句，将n自增1。该条语句用于跳出循环，使得循环条件n<=N趋于false
}
cout<<"前"<<N<<"项的累积结果为："<<sum<<endl; //跳出循环后，执行本条语句，显示变量sum
return 0;
}
4.2 do—while语句
do—while语句是先执行循环体，在判断条件。语法如下：
do
语句
while(表达式);
- 表达式指定一个循环条件，该条件放在循环体语句的后面，即先执行再判断条件，该表达式结果应为布尔类型，例如关系表达式或逻辑表达式，非布尔类型将自动转换，0转为false，非0值转为true
- 语句式描述循环体的C++语言，不管循环条件是否成立，循环体都要执行一次，循环体中应包含使循环条件趋向于false的语句，否则将造成死循环
- 计算机执行该语句时，首先执行一次循环体，然后再计算表达式（即循环条件），若结果为true（条件成立），则重复执行循环体语句，否则结束循环。
/*求奇数数列1,3,5.......2n-1的前N项累加和*/
#include <iostream>
using namespace std;
int main(){
int N,sum=0,n=1;
cout<<"请输入计算的值：";
cin>>N;
do
{
sum += 2*n-1;
n++;
}
while (n<=N);
cout<<"前"<<N<<"项的累积结果为："<<sum<<endl;
return 0;
}
4.3 for语句
for语句语法：
for(表达式1;表达式2;表达式3)
语句
- 表达式1只在正式循环前执行一次，通常用于循环算法的赋初始值
- 表达式2指定一个循环条件，每次循环时，先计算该表达式，如果为true，则执行下面的循环体语句，否则结束循环
- 表达式3是在每次循环体执行结束之后都被执行一次，主要用于修改循环体中的某些变量，使循环条件趋向于false
- 语句是描述循环体的C++语句
- 计算机执行该语句时，首先计算表达式1（通常为赋初始值），再计算表达式2（即循环条件），若结果为true则重复执行循环体语句，每次执行完循环体语句之后计算一次表达式3（通常用于修改循环条件中的某些变量），然后再返回表达式2重新判断，若表达式2结果为true，再次执行上述过程一次，直至表达式2判断为false，跳出循环。
/*求奇数数列1,3,5.......2n-1的前N项累加和*/
#include <iostream>
using namespace std;
int main(){
int N,n,sum=0;
cout<<"请输入计算的值：";
cin>>N;
for(n=1;n<=N;n++) //集中用3个表达式来指定n=1，循环条件n<=N,以及修改循环条件中的变量N，使得循环趋向于false
sum += 2*n-1; //表达式n<=N为true时执行的语句
cout<<"前"<<N<<"项的累积结果为："<<sum<<endl;
return 0;
}
4.4 逗号“,”运算符
逗号运算符，可以将多个表达式链接在一起，构成一个复合的逗号表达式，
表达式1, 表达式2, ......, 表达式n
- 计算机在执行时从左往右依次计算表达式1~n，将最后一个表达式（即表达式n）的结果作为整个逗号表达式的结果
- 逗号运算符的优先级为15级，结合性从左到右
实例说明：
int a,b,c;
a=5, b=10, c=a+b; //依次执行，所以a=5, b=10, c=15，计算机会将最后的表达式计算结果（c=a+b）作为该表达式的结果，故结果为15
cout<<(a,b,c); //显示逗号表达式的结果，结果为15
编写程序时，可以将多个表达式语句用逗号运算符连接起来，构成一个长的表达式语句，使得程序更加紧凑，利用逗号运算符改写求奇数列前N项的累积和程序。
/*求奇数数列1,3,5.......2n-1的前N项累加和*/
#include <iostream>using namespace std;
int main(){
int N,n,sum;
cout<<"请输入计算的值：";
cin>>N;
for(n=1,sum=0;n<=N;n++) //集中用3个表达式来指定n=1，循环条件n<=N,以及修改循环条件中的变量N，使得循环趋向于false
sum += 2*n-1; //表达式n<=N为true时执行的语句
cout<<"前"<<N<<"项的累积结果为："<<sum<<endl;
return 0;
}
4.5 控制语句
计算机通常是按照语句的书写顺序执行程序的，而某些语句，会造成执行顺序的跳转，例如选择语句和循环语句，造成程序执行顺序跳转的语句，统称为控制语句。
-
break语句
break语句的作用就是跳出整个循环，例如，我们设计一个可以求圆的面积和周长的程序，我们一直输入半径，程序就一直计算，而不必每次都打开程序。
#include <iostream> using namespace std; int main(){ const int Pi=3.14; double r,s,c; while(true) //使用关键字true将while设置为死循环，如果不跳出循环的话，while下的语句块会一直执行。 { cout<<"请输入圆的半径:"; cin>>r; s = r*r*Pi; c = 2*r*Pi; if(r<0) break; //break的作用就是跳出整个循环 cout<<"一个半径为："<<r<<"的圆的面积="<<s<<"周长等于"<<c<<endl; } return 0; } -
continue
continue 的作用是跳出当前循环，中途返回，继续执行下一个循环。比如设计一个程序，能显示一个范围内，能被3整除的数。
#include <iostream> using namespace std; int main(){ int a,b; cout<<"请输入取值范围,小的在前，大的在后："; cin>>a>>b; for(a,b;a<=b;a++) { if (a%3!=0) continue; //如果n不能被3整除，则执行continue，跳过此次判断，执行下一个循环语句。 cout<<a<<","; //只返回能被3整除的数。其他的数都被continue跳出时过略掉了。 } return 0; }continue只能在循环语句中使用，而break还能够在switch-case选择语句中使用。
五、算法设计与评价
程序设计中，算法应当时可实现的，算法应当能被计算机执行，算法应当完成某种功能，具有使用价值，因此，我们设计的算法应对具有以下5个特性：
- 有穷性：一个算法必须保证其执行步骤是有限的
- 确定性：算法的每个步骤必须有明确的定义，不能含糊不清，或有二义性
- 有效性：算法每个步骤应该能被计算机执行，并得到有效的结果。
- 输入：算法可以有0个或多个数额u，输入是算法处理的原始数据
- 输出：算法至少要有一个输出，输出是算法处理的结果
如何评判一个算法的优劣，是通过算发杂程度和内存占用量，这是评价一个算法优劣的基本标准。
-
算法复杂度：决定了计算执行该算法所续的时间，完成相同的功能计算复杂度越小，算法执行速度越快，算法就越好。
实列：判断一个数是否是素数
#include <iostream> using namespace std; int main(){ int a; cout<<"请输入一个正整数："; cin>>a; bool yes_no = true; for(int n=2; n<a; n++) { if(a%n==0) { yes_no=false;break; } } if(yes_no==true)cout<<a<<"是素数"; else cout<<a<<"不是素数"; return 0; }在上述实例中，a只需检查能否被n~a/2以内的数整除，就可以判断a是否是素数，降低循环的次数，就可以降低程序的算法复杂程度，从而优化程序。保证正确性的情况下， 程序的执行速度越快越好。
-
内存占用量
内存占用量用于评估计算机执行算法时，所需空间的大小，完成相同的功能，内存占用量空间越小，那么算法就越好。
#include <iostream> using namespace std; int main(){ double a, b, c; double sum; cout<<"请依次输入3个人的成绩："; cin>>a;cin>>b;cin>>c; sum= (a+b+c)/3; cout<<"平均成绩为："<<sum<<endl; return 0; }在该算法中，定义了4个double型变量，每个变量占用8个字节，因此总共占用了32个字节，成绩的取值范围是0-100，使用单精度浮点型float类型完全能够满足需求，每个float型变量只占用4个字节，总共占用16个字节，同时减小变量的定义数量，也可以减少不必要的内存开销。对上述程序进行完善：
#include <iostream> using namespace std; int main(){ float source; float sum = 0; cout<<"请依次输入3个人的成绩："; cin>>source;sum += source; cin>>source;sum += source; cin>>source;sum += source; cout<<"平均成绩为："<<sum/3<<endl; return 0; }通过对程序算法的优化，新程序内存开销仅占用8个字节。
最后的实例：求反正切（arctan）函数的算法设计，计算机只能进行算术运算，关系运算，逻辑运行等基本运算，不能直接运行对数函数这一类的复杂运算，此类复杂运算，需要分解成基本运算进行求解。
公式化解为：，其中记
分子：
分母：
那么：
