《算法笔记》C与C++语言相关

这是一篇学习笔记，基于胡凡主编的《算法笔记》的第二章“C/C++快速入门”。

在学习那一章的过程中，我将其中之后用的到的内容整理为这篇笔记，适合了解C和C++语言的人用于复习其语法中与做算法题相关的特性与技巧。

本文中部分内容经过顺序调整和补充，不完全按照原书内容。详细内容请看原书。

变量类型

整型

%d为int输出格式。

%lld为long long输出格式

• 32位或者$10^9$以内的整数：int
• 64位或者$10^{18}$以内的整数：long long。且字面量后面要加上LL后缀

浮点型

%f为float和double的输出格式。

%lf为double输入格式。

都用double型就好。float型只有6-7位有效精度，double型有15-16位。

字符型

%c为char型输出格式。

%s为char数组输出格式。

布尔型

c++中直接用，c中得添加stdbool.h头文件。

整型常量赋值给布尔变量时0为false，非0为true。

作为整型数据输出时，true为1，false为0。

强制类型转换

(新类型名)变量名//C中的转换
新类型名(变量名)//C++才能用

无穷大的表示

无穷大INF可以设置为int型的最大值，即$(1<<31)-1$。

但更常用$2^{30}-1$以避免相加之后溢出，它的十六进制形式：0x3fffffff

const int INF = (1<<31)-1;
const int INF = 0x3fffffff;

条件表达式的简化

• 条件表达式为表达式!=0可以省略!=0
• 条件表达式为表达式==0时可以省略==0并取反，即变为!表达式

常用math函数

头文件:math.h

函数	说明
fabs(double x)	对double变量取绝对值
floor(double x)、ceil(double x)	对double变量向下取整、向上取整，但返回值为double型
pow(double r,double p)	返回$r^p$
sqrt(double x)	返回x的算术平方根
log(double x)	返回$lnx$,需要用换底公式$\log_ab=\frac{lnb}{lna}$得到其他底数的对数
sin(double x)等三角函数
asin(double x)等反三角函数
round(double x)	返回保留整数部分的四舍五入后的x，但返回值为double型

常用字符串函数

头文件：string.h

函数	说明
strlen(字符数组)	返回字符串长度，不含\0
strcmp(字符数组1,字符数组2)	按字典序比较大小，串1大于串2返回正整数，小于则返回负整数，等于则返回0
strcpy(字符数组1,字符数组2)	将字符数组2的内容复制到字符数组1，包括\0
strcat(字符数组1,字符数组2)	将字符数组2接到字符数组1后面

数组

数组初始化

定义数组时初始化

/*一维数组*/
int a[10] = {1,2,3,4};//其余元素（a[4]~a[9]）被赋值为0
int b[10] = {0};//声明一个长度为10的数组并将a[0]赋值为0，并使得其余元素默认为0
//若不赋予初值，则元素初值为随机值
int c[10] = {};//c++才能这么写，c中会报错
/*二维数组*/
int d[5][6] = {{3,1,2},{8,4},{},{1,2,3,4,5}};//其余元素被赋值为0，同样的，空{}在c中报错
/*字符数组*/
char str1[6] = {'H','e','l','l','0','\0'};//同整数数组
char str2[6] = "Hello"//这种方式字符串以\0结尾

若数组大小过大（$10^6$级别），需要将其定义在主函数外面。

因为函数内部局部变量使用系统栈，空间较小，容易栈溢；

而函数外部全局变量使用静态存储区，空间较大。

#include <stdio.h>
int a[1000000];//10^6级别定义在外部
int main()
{
    return 0;
}

利用memset函数初始化

头文件：string.h

用于给某个范围内的内存区域的每个字节赋相同的值。

memset(首地址,每个字节的值,区域长度);
//初始化数组。多维数组与之相同
memset(数组名,值,sizeof(数组名));//给数组的每个元素赋相同的值。一般赋值0或-1，不容易出错。

由于0的补码为全0,-1的补码为全1，不容易赋值错误，尽量只用memset设置这两种初值，赋其他值使用fill函数。

以数组作为函数参数

• 参数中数组的第一维可以省略。但第二维以及更高维的长度不可省略。
• 数组作为参数时，对数组元素的修改等同于对原数组元素的修改。（我的理解：数组名仍然是值传递，但是复制给形参的只不过是数组首地址，根据这个首地址对数组元素寻址到的数组元素就是原本的数组元素）

浮点数比较

由于浮点数存储的误差，不能直接用==来比较两个浮点数是否相等，需要用一个极小数eps来修正。

const double eps = 1e-8;//10^-8
//为了方便使用，可以定义如下的宏
#define Equ(a,b) ((fabs((a)-(b)))<(eps))
#define More(a,b) ((a)-(b)>(eps))
#define Less(a,b) ((a)-(b)<(-eps))
#define MoreEqu(a,b) ((a)-(b)>(-eps))
#define LessEqu(a,b) ((a)-(b)<(eps))
//圆周率
const double PI = acos(-1.0);

复杂度

一般的OJ系统一秒运算次数约为$10^7-10^8$.

因此$O(n^2)$的复杂度在n=1000时是可以承受的（$10^6$级别），n=100000时是不可承受的（$10^{10}$级别）

指针

int *p1,p2;//注意：p1为int*，但p2为int
int *p3,*p4;//这样才是将二者都定义为int*
int a=1,b=2;
int *p5 = &a, *p6 = &b;//用取址符&取变量地址并赋值给指针变量
(*p5)++;//将p5指向的存储空间内的值自增1
printf("%d %d",*p5,*p6);//用取值符*取地址对应的值，这里输出"2 2"

• 指针是一个unsigned类型的整数。
• 指针变量可以进行加法，对int*p来说，p+1代表下一个int型变量地址。支持自增操作。
• 指针变量可以进行减法，减法结果是两个地址偏移的距离，距离以指针的基类型为单位。支持自减操作。

指针与数组

数组名称可作为数组首地址使用，即对于int数组a：a==&a[0]，a+i==&a[i]，*(a+i)==a[i]

int a[10]={0};
int *p=a,*q=&a[5];
printf("%d",q - p);//输出5而非20，因为这里的差值以int为单位

引用

用于产生变量的别名，无法对常量使用。在函数参数类型后加上&，这样就可以将形参作为实参的别名，对形参的修改可以影响到实参。

这是c++的语法，c中会报错。

void change(int &x) {
    x = 1;//可以改变传入的参数
}

指针的引用：

void swap(int* &p1,int* &p2)
{//交换的是传入的两个指针
    int*temp = p1;
    p1 = p2;
    p2 = temp;
}

结构体

定义

//定义举例
struct student{
    int id;
    char name[20];
    student* next;//无法定义自身类型，但是可以定义自身类型的指针。C语言中会报错，C++不会报错。
}stu,*p;//定义完之后可以同时定义对应的变量
p = &stu;
//访问结构体的元素
stu.id = 1;
(*p).id = 2;
p->id = 2;

初始化

构造函数

使用构造函数（C++才有，C没有）。默认会生成无参构造函数，但如果自己定义了，那么就不会生成默认的无参构造函数。构造函数可以重载。

struct student{
    int id;
    char gender;
    student(int _id,char _gender){
        id=_id;gender=_gender;
    }
};
student stu = student(1,'M');

或者用简化版：

struct student{
    int id;
    char gender;
    student(int _id,char _gender):id(_id),gender(_gender){}
};
student stu = student(1,'M');

初始化列表

struct student {
    int id;
    char gender;
};
student stu = { 1,'M' };//顺序对应即可

复制

可以直接用=复制相同类型的结构体变量，C和C++均可。但是这种方式是浅拷贝，对指针成员只复制地址，不复制指向的内容。

#include <stdio.h>
struct student {
    int id;
    char gender;
}stu1,stu2;
int main()
{
    stu1.id = 1;
    stu1.gender = 'M';
    stu2 = stu1;
    printf("%d %c", stu2.id, stu2.gender);//输出"1 M"
}

输入输出

scanf输入

scanf("格式控制串",变量地址);//变量前记得加&取地址，数组名称本身就是地址
scanf("%d:%d:%d",&hh,&mm,&ss);//输入"13:45:20"格式的数据
scanf("%d%d",&a,&b);//输入"3 4"这类空格隔开的数字时，可以省略空格
//因为除了%c之外，对其他格式符的输入以空白符为结束标志
//字符数组使用%s，读入时以空格和换行为结束标志，因此scanf无法直接读入带空格或换行的字符串到一个字符数组中

scanf的返回值为成功赋值的变量个数，如果遇到错误或者EOF，则返回值为EOF

printf输出

double输入用 %lf，输出用%f。

助记：读进来的时候要严格一些，需要知道你是double还是float，但是输出的时候没那么严格，因为可以隐式转换。就像小区保安需要你刷卡进小区，但是出小区时不管你是不是住户，直接给你开门就行。

默认输出6位小数，不足六位以 0 补齐,超过六位按四舍五入截断

#include <stdio.h>
int main()
{
    double a;
    scanf("%lf", &a);//123456789.123456789
    printf("%f", a);//123456789.123457
}

实用输出格式：

输出格式	说明
%md	使不足m位的int变量以m位右对齐输出，高位空格补齐。超过m位保持不变。
%0md	同%md，只不过高位用0补齐而不是空格
%.mf	让浮点数保留m位小数输出，四舍六入五成双，“保留m位小数”用这个即可。不考虑怎么舍入

getchar和putchar

分别为输入和输出单个字符，可接收换行符。

char c;
c = getchar();
putchar(c);

gets和puts

分别为输入和输出一行字符串，并存放在一维数组中。

puts输出时自带换行。

#include <stdio.h>
int main()
{
    char a[] = "abc";
    char b[] = "def";
    puts(a);
    puts(b);//输出结果里b字符串换了一行来显示
    printf("%d", sizeof(a));//输出4而不是3，所以这种初始化方式末尾是带有\0的
}

输出：

abc
def
4

gets以换行符结束，不同于scanf以空白符结束，所以可以读入带空格的字符。

因此scanf完一个整数后，如果要使用gets，需要先用getchar接收整数后的换行符。

gets与scanf都会自动在读入的字符串末尾添加\0

sscanf和sprintf

头文件：string.h

即在scanf和printf前面再加一个字符数组参数，输入输出的源头与目的就变成了该字符数组，用法同scanf和printf

cin和cout

头文件：iostream

命名空间：std

C++输入输出函数，速度比不上scanf和printf，在算法题中一般不用。

cin>>n>>c>>a>>b;//可以连续读入多个变量，无需指定类型
char str[100];
cin.getline(str,100);//读入一整行需要用getline函数
string str2;//STL中的string容器
getline(cin,str);

cout<<a<<b<<c<<d<<endl;//可以连续输出多个变量，无需指定类型。endl表示换行
//格式化输出
#include <iomanip>
cout << setiosflags(ios::fixed) << setprecision(2) << 123.4567 << endl;//输出123.46