算法笔记-第二章C/C++快速入门

在学习算法之前,我们需要用一种语言表示算法,因为 C 是最接近操作系统的语言,它的执行效率最高、速度最快。所以,选择它作为学习算法的语言。C++ 和 C 类似但又不完全一样,而 C++ 中有一些很实用的语法特性,在学习 C 的基本知识时会顺带引出 C++ 的部分特性。


先来看一段 C 语言小程序:

#include<stdio.h> //or <cstdio>
int main()
{
	int a, b;
	scanf("%d%d", &a, &b);
	printf("%d", a+b);
	return 0;
}

这个程序分为两个部分:头文件和主函数

  1. 头文件

#include<stdio.h> 这一行就是头文件。其中,stdio.h 是标准输入输出库,如果在程序中需要输入输出,就需要加上这个头文件。因为普遍所有程序都需要输入输出,所以 stdio.h 是每一个 C 程序都要添加的头文件。

stdio 的全称是 standard input outputh 就是 head 的缩写,.h 是头文件的文件格式。还有一些头文件,它们虽然和 stdio.h 的功能各不相同,但是也是 C 程序里不可分割的一部分。例如, math.h 负责一些数学函数,string.h 负责和字符串有关的函数。

此外,在 C++ 标准中, stdio.h 更推荐使用等价写法: cstdio

  1. 主函数
int main()
{
	int a, b;
	scanf("%d%d", &a, &b);
	printf("%d", a+b);
	return 0;
}

以上部分属于主函数。主函数是一个程序的入口位置,整个程序从主函数开始执行。一个程序最多只能有一个主函数。


基本数据类型

变量的定义

变量是在程序运行过程中其值可以改变的量,需要在定义后才能使用,其定义格式为:

变量类型 变量名;

并且,变量可以在定义的时候就赋初值:

变量类型 变量名 = 初值;

当变量名满足以下 3 个条件时,能够任意取值:

  1. 不能是 C 语言标识符。另外,建议取有实际意义是变量名,这样可以提高程序的可读性
  2. 变量名的第一个字符必须是 字母下划线。除第一个字符之外的其他字符必须是 字母数字下划线
  3. 区分大小写

变量类型

四种基本数据类型:

类型 取值范围 大致范围
整型 int -$$2^{31}$$ ~ +($$2^{31}$$-1) -2x$$10^{9}$$ ~ 2x$$10^{9}$$
long long -$$2^{63}$$ ~ +($$2^{63}$$-1) -9x$$10^{18}$$ ~ 9x$$10^{18}$$
浮点型 float -$$2^{128}$$ ~ +$$2^{128}$$(实际精度6~7位) 实际精度6~7位
double -$$2^{1024}$$ ~ +$$2^{1024}$$(实际精度15~16位) 实际精度15~16位
字符型 char -128 ~ +127 -128 ~ +127
布尔型 bool 0(false) or 1(true) 0(false) or 1(true)

整型

  1. 对于 整型 int 来说,一个整数占用 32bit (即32位),也即 4Byte(即4字节),取值范围如上表所示。要记住 绝对值在 $$10^{9}$$ 范围以内的整数都可以定义成 int 型。示例如下:

    int num;
    int num = 5;
    
  2. 对于 长整型 long long 来说,一个整数占用 64bit,也即 8Byte,取值范围见表格。具体来说,如果题目要求的整数取值超过 10^10 或者 10^18,就要用 long long 型来存储。定义举例:

    long long bignum;
    long long bignum = 123456789012345LL;
    

    注意:如果 long long 型赋大于 $$2^{31}$$-1的初值,则需要在初值后面加上 LL;否则会编译错误。

除此之外,对于整型数据,都可以在前面加个 unsigned,以表示无符号型,例如 unsigned int 和 unsigned long long,..占用的位数和原来相同..,但是把负数去掉了。

整型示例:

#include<stdio.h>
int main()
{
    int a = 1, b = 2;
    printf_s("%d", a + b);
    return 0;
}

%d 是 int 型的输出格式。

浮点型

浮点型就是我们通常意义的小数,一般分为单精度(float)和双精度(double)。

  1. 对于 单精度 float 来说,一个浮点数占用 32bit,其中 1bit 作为符号位、8bit 作为指数位、23bit 作为尾数位(了解即可),取值范围见表格。有效精度只有6~7位。定义:

    float fl;
    float fl = 3.1415;
    
  2. 对于 双精度 double 来说,一个浮点数占用 64bit,其中依照浮点数的标准,1bit 作为符号位、11bit 作为指数位、52bit 作为尾数位。有效精度有15~16位。定义:

    double db;
    double db = 3.1415926536;
    

浮点型示例:

#include<stdio.h>
int main()
{
    double a = 3.14, b = 0.12;
    double c = a + b;
    printf("%f", c);
    return 0;
}

不要使用 float,碰到浮点型的数据都应该用 double 来存储%f 是 float 和 double 型的输出格式。

字符型

  1. 字符型和字符变量

    字符型变量定义:

    char c;
    char c = 'e';
    

    四个概念:整型常量、整型变量、字符常量、字符变量。

    小写字母比大写字母的 ASCII 码值大 32 即可

    注意:字符常量必须用单引号标注起来,以区分是作为字符变量还是字符常量出现。在 C 语言中,字符常量(必须是单个字符)必须用 单引号 标注。

    看一个程序:

    #include<stdio.h>
    int main()
    {
        char c1 = 'z', c2 = 'j', c3 = 117;
        printf("%c%c%c", c1, c2, c3);
        return 0;
    }
    

    输出:

    zju
    

    %c 是 char 型的输出格式。

  2. 转义字符

    \n 代表换行
    \0 代表空字符 NULL,其中 ASCII 码为 0,请注意 \0 不是空格
    

    示例程序:

    #include<stdio.h>
    int main()
    {
        int num1 = 1, num2 = 2;
        printf("%d\n\n%d", num1, num2);
        printf("%c", 7);
        return 0;
    }
    

    输出结果:

    1
       
       
    2
    

    第二个 printf 没有任何输出,因为 ASCII 为 7 的字符是控制字符,并且是控制响铃功能的控制字符(电脑在执行时确实响了一下)。

  3. 字符串常量

    字符常量:单个使用单引号标记的字符。

    字符串常量:由双引号标记的字符集,例子"WoAiRenRenBuAiWo"

    字符串常量可以作为初值赋给字符数组,并使用%s的格式输出

    程序:

    #include<stdio.h>
    int main() //这个 main 和 () 之间可以有空格吗
    {
        char str1[25] = "WoAiRenRenBuAiWo";
        char str2[25] = "SoSadAStory";
        printf("%s, %s", str1, str2);
        return 0;
    }
    

    输出:

    WoAiRenRenBuAiWo, SoSadAStory
    

    代码中的 str1[25]str2[25] 均表示由 25 个 char 字符组合而成的字符组合,亦称字符数组

    不能把字符串常量赋值给字符变量,错误的写法:char c = "abc"

  4. 布尔型

    布尔型在 C++ 中可直接使用,但在 C 语言中必须添加 stdbool.h 头文件才可使用。

    布尔型变量又称为“bool 型变量”,它的取值只能是 true 或 false,分别表示非零与零。

    整型变量在赋值给布尔型变量时会自动转换为 true 或 false。“非零”包括正整数和负整数。

    对于计算机来说,true 和 false 在存储时分别为 1 和 0,因为如果使用 %d 输出 bool 型变量,则 true 和 false 会输出 1 和 0。

    程序(文件扩展名为.cpp,.c扩展名时要加入#include<stdbool.h>头文件):

    #include<stdio.h>
    int main()
    {
        bool flag1 = 0, flag2 = true;
        int a = 1, b = 1;
        printf("%d %d %d\n", flag1, flag2, a==b);
        return 0;
    }
    

    输出:

    0 1 1
       
    

强制类型转换

有时候需要把浮点数的小数部分换成整数,或是把整型变成浮点型来方便做除法(因为整数除以整数在计算机中视为整除操作,不会自动变为浮点数),或是在其他很多情况下。都会要用到强制类型转换,即把一种数据类型转换成另一种数据类型。

强制类型转换的格式如下:

(新类型名) 变量名

这其实很简洁,只需要把需要变成的类型用括号括着写在前面就行了。

示例:

#include<cstdio>
int main() {
	double r = 12.56;
	int a= 3, b = 5;
	printf("%d\n", (int)r); // (int)r 把 r 强制转换成 int 型并输出
	printf("%d\n", a / b);
	printf("%.1f", (double) a / (double) b); // %.1f 保留一位小数输出
}

输出:

12
0
0.6

需要指出,如果将一个类型的变量赋值给另一个类型的变量,却没有写强制类型转换操作,那么编译器将会自动进行转换。但是这并不是说任何时候都可以不用写强制类型转换,因为如果是在计算的过程中需要转换类型,那么就不能等它算完再在赋值时转换。

符号常量和 const 常量

符号常量通俗地讲就是 “替换”,即用一个标识符来替代常量,又称为 “宏定义”。其格式如下:

#define 标识符 常量

例如把圆周率 pi 设为 3.14,注意末尾不加分号:

#define pi 3.14

计算半径为 3 的圆的近似面积:

#include<stdio.h>
#define pi 3.14
int main()
{
    double r = 3;
    printf("%.2f\n", pi * r * r);
    return 0;
}

输出:

28.26

另一种定义常量的方法是使用 const,其格式如下:

const 数据类型 变量名 = 常量;

仍用 pi 举例:

const double pi = 3.14;

计算半径为 3 的圆的近似周长:

#include<stdio.h>
const double pi = 3.14;
int main()
{
    double r = 3;
    printf("%.2f\n", 2 * pi * r);
    return 0;
}

输出:

18.84

以上两种写法均可,const 写法更推荐。

define 除了可以定义常量,还可以定义任何语句或片段,其格式如下:

#define 标识符 任何语句或片段

写一个宏定义:

#define ADD(a, b) ((a) + (b))

这样就可以直接使用 ADD(a, b) 来代替 a + b 的功能:

#include<stdio.h>
#define ADD(a, b) ((a) + (b)) //为什么要加那么多括号,a+b不就行了吗
int main()
{
    int num1 = 3, num2 = 5;
    printf("%d", ADD(num1, num2));
    return 0;
}

输出:

8

加括号原因:宏定义是直接将对应的部分替换,然后才进行编译和运行。

如下为错误的操作:

#include<stdio.h>
#define CAL(x) (x * 2 + 1)
int main()
{
    int a = 1;
    printf("%d\n", CAL(a + 1));
    return 0;
}

输出:

4

按照 (( a + 1 ) * 2 + 1 ) 结果应为 5,但是因为缺少必要的括号,实际上该宏定义为(a + 1 * 2 + 1),即为输出的结果。

运算符

运算符就是用来计算的符号。

常用的运算符:算术运算符、关系运算符、逻辑运算符、条件运算符、位运算符。

  1. 算数运算符

    1)+ 加法运算符:将前后两个数相加

    2)- 减法运算符:将前后两个数相减

    3)* 乘法运算符:将前后两个数相乘

    4)/ 除法运算符:取前面的数除以后面的数得到的商

    5)% 取模运算符:取前面的数除以后面的数得到的余数

    6)++ 自增运算符:令一个整型变量增加1

    7)– 自减运算符:令一个整型变量减少1

    1)2)3)可以直接使用,没有需要注意的地方,举例:

    #include<stdio.h>
    int main()
    {
        int a = 3, b = 4;
        double c = 1.23, d = 0.24;
        printf("%d %d\n", a + b, a - b);
        printf("%f\n", c * d);
        return 0;
    }
    

    输出:

    7 -1
    0.295200
       
    

    对于除法运算符,需要注意的是,当被除数和除数都是整型时,并不会得到一个 double 浮点型的数,而是直接舍去小数部分(即向下取整)。举例:

    #include<stdio.h>
    int main()
    {
        int a = 5, b = 4, c = 5, d = 6;
        printf("%d %d %d\n", a / b, a / c, a / d);
        return 0;
    }
    

    输出:

    1 1 0
       
    

    可以看到,5/4 直接舍掉小数部分变成了 1,而 5/6 直接变成了 0。

    如果除数为 0 ,会报 1.#INF00 错误。

    取模运算符返回被除数与除数相除得到的余数,举例:

    #include<stdio.h>
    int main()
    {
        int a = 5, b = 3, c = 5;
        printf("%d %d\n", a % b, a % c);
        return 0;
    }
    

    输出:

    2 0
       
    

    取模运算符的优先级和除法运算符相同。取模运算中的除数不能为 0。

    自增运算符有两种写法:i++++i。两种写法都能使 i+1。区别:i++ 先使用 i 再将 i 加 1,++i 则是先将 i 加 1 再使用 i

    举例:

    #include<stdio.h>
    int main()
    {
        int a = 1, b = 1, n1, n2;
        n1 = a++;
        n2 = ++b;
        printf("%d %d\n", n1, a);
        printf("%d %d\n", n2, b);
        return 0;
    }
    

    输出:

    1 2
    2 2
       
    

    自减运算符和自增运算符一样,也有 i– 和 –i 这两种写法,作用是将 i 减 1,细节上和自增运算符相同。

  2. 关系运算符

    常见的关系运算符有六种:<、>、<=、>=、==、!=,它们的功能及语法见下表:

    运算符 含义 语法 返回值
    < 小于 a<b 表达式成立时返回真(1, true),不成立时返回假(0, false)
    > 大于 a>b 同上
    <= 小于等于 a<=b 同上
    >= 大于等于 a>=b 同上
    == 等于 a==b 同上
    != 不等于 a!=b 同上
  3. 逻辑运算符

    逻辑运算符有 3 种:&&、||、!。分别对应“与”,“或”,“非”,它所实现的功能及语法见下表:

    运算符 含义 语法 返回值
    && a&&b ab都真,则返回真;其他情况均返回假
    || a||b ab都假,则返回假;其他情况均返回真
    ! !a 如果a为真,则返回假;如果a为假,则返回真
  4. 条件运算符

    条件运算符( ? : )是 C 语言中唯一的三目运算符,即需要三个参数的运算符,其格式如下:

    A ? B : C;
    

    其含义是:如果 A 为真,那么执行并返回 B 的结果;如果 A 为假,那么执行并返回 C 的结果。

    举例:

    #include<stdio.h>
    int main()
    {
        int a = 3, b = 5;
        int c = a > b ? 7 : 11;
        printf("%d\n", c);
        return 0;
    }
    

    输出:

    11
       
    

    再举一个例子:

    #include<stdio.h>
    #define MAX(a, b) ((a) > (b) ? (a) : (b))
    int main()
    {
        int a = 4, b = 3;
        printf("%d\n", MAX(a, b));
        return 0;
    }
    

    输出:

    4
       
    

    该例子实现了从两个数中取较大值的功能。

  5. 位运算符

    位运算符有六种,见下表。

    在这六种位运算符中,可能会用到 左移运算符。由于 int 型的上限为 $$2^{31}$$ - 1,因此有时程序中无穷大的数 INF 可以设置成 (1 « 31) - 1 (注意:必须加括号。因为位运算符的优先级没有算术运算符高)。但是一般更常用的是 $$2^{30}$$ - 1,因为它可以避免相加超过 int 的情况。注意:如果把 $$2^{30}$$ - 1 写成二进制的形式就是 0x3fffffff,因此下面两个式子是等价的。

    const int INF = (1 << 30) - 1;
    const int INF = 0x3fffffff;
    
    运算符 含义 语法 效果
    « 左移 a«x 整数a按二进制位左移x位
    » 右移 a»x 整数a按二进制位右移x位
    & 位与 a&b 整数a和b按二进制对齐,按位进行与运算(除了11得1,其他均为0)
    | 位或 a|b 整数a和b按二进制对齐,按位进行或运算(除了00得0,其他均为1)
    ^ 位异或 a^b 整数a和b按二进制对齐,按位进行异或运算(相同为0,不同为1)
    ~ 位取反 ~a 整数a的二进制的每一位进行0变1、1变0的操作

顺序结构

赋值和表达式

在 C 语言中,“=”表示赋值:

int n = 5;

给多个变量赋同一个值:

int n, m;
n = m = 5;

等式右边也可以是一个表达式:

#include<stdio.h>
int main()
{
    int n = 3 * 2 + 1;
    int m = (n > 6) && (n < 8);
    n = n + 2;
    printf("%d %d\n", n, m);
    return 0;
}

输出:

9 1

赋值运算符可以通过将其他运算符放在前面来实现赋值操作的简化

n += 2 <=> n = n + 2
n -= 2 <=> n = n - 2
n *= 2 <=> n = n * 2
n /= 2 <=> n = n / 2
n %= 2 <=> n = n % 2

举例:

#include<stdio.h>
int main()
{
    int n = 12, m = 3;
    n /= m + 1;
    m %= 2;
    printf("%d %d\n", n, m);
    return 0;
}

输出:

3 1

初学者应尽量写简化的形式,这样可以避免因为基础不好而产生的一些错误。

这种复合赋值运算符在程序中会被经常使用,并且可以加快编译速度、提高代码可读性,因此初学者即使没办法马上接受,也应尽量去学着写。

使用 scanf 和 printf 输入 / 输出

C 语言的 stdio.h 库函数中提供了 scanf 和 printf 函数,分别对应输入和输出。

  1. scanf 函数的使用

    scanf 是输入函数,其格式如下:

    scanf("格式控制", 变量地址);
    scanf("%d", &n);
    

    &n 的含义:在 C 语言中,变量在定义之后,就会在计算机内存中分配一块空间给这个变量,该空间在内存中的地址称为变量的地址。为了得到变量的地址,需在变量前加 & (称为取地址运算符),即为如上所示写法。

    常见数据类型变量的 scanf 格式符
    数据类型 格式符 举例
    int %d scanf("%d”, &n);
    long long %lld scanf("%lld”, &n);
    float %f scanf("%f”, &fl);
    double %lf scanf("%lf”, &db);
    char %c scanf("%c”, &c);
    字符串(char 数组) %s scanf("%s”, str);

    在上表中,数组名 str 前面并没有 & 取地址运算符,这是因为数组比较特殊,数组名称本身就代表了这个数组第一个元素的地址,所以不需要再加地址运算符。在 scanf 中,除了 char 数组整个输入的情况不加 & 外,其他变量类型都要加 &

    那么,如果想要输入类似“12:56:12”的时间,应该怎么做?可以使用如下代码方法:

    int hh, mm, ss;
    scanf("%5d:%d:%d", &hh, &mm, &ss);
    

    scanf 的双引号的内容其实就是整个输入,只不过把数据转换成它们对应的格式符并把变量的地址按次序写在后面而已

    如果要输入 12,18.23,t 这种格式的数据,那么就把 12 替换成 %d、18.23 替换成 %lf、t 替换成 %c 即可:

    int a;
    double b;
    char c;
    scanf("%d,%lf,%c", &a, &b, &c);
    

    如果要输入“3 4”这种用空格隔开的数字,两个%d之间可以不加空格:

    int a, b;
    scanf("%d%d", &a, &b);
    

    可以不加空格的原因:除了%c以外,scanf 对其他格式符(如%d)的输入是以空白符(即空格、换行等)为结束判断标志的,因此除非使用%c把空格按字符读入,其他情况都会自动跳过空格。另外,字符数组使用%s读入的时候以空格跟换行为读入结束的标志,如下面的代码所示:

    #include<stdio.h>
    int main()
    {
        char str[10];
        scanf("%s", str);
        printf("%s", str);
        return 0;
    }
    

    输入数据:

    abcd efg
    

    输出结果:

    abcd
    

    scanf 的%c格式是可以读入空格和换行的,因此下面例子中的字符c是一个空格,请读者认真研究这个例子:

    #include<stdio.h>
    int main()
    {
        int a;
        char c, str[10];
        scanf("%d%c%s", &a, &c, str);
        return 0;
    }
    

    输入数据:

    1 a bcd
    

    输出结果:

    a=1,c= ,str=a
    

    特别提醒:初学者特别容易在写scanf时漏写&,因此如果在输入数据后程序异常退出,要马上考虑是否是在scanf中漏写了&。

  2. printf 函数的使用

    printf 是输出函数,其格式如下:

    printf("格式控制", 变量地址);
    int n = 5;
    printf("%d", n);
    

    常见类型的格式符,printf 和 scanf 仅有一处区别:对于 double 型变量,其输出格式变成了%f,而在 scanf 中却是 %lf。

打开微信扫一扫或者输入“代码者”即可订阅博客