1 变量、输入输出、表达式和顺序语句

语法课，题目比较多，需要多练，十个章节

整数可以直接读进double
cpp 平方 不能用^，^表示位运算

一开始先写右括号 可以减少后面移动光标的次数

printf 保留小数
a. %08.3f, 表示最小宽度为8，保留3位小数，当宽度不足时在前面补上0
a. %-8.3f，表示最小宽度为8，保留3位小数，当宽度不足时在后面补上空格
a. %8.3f, 表示这个浮点数的最小宽度为8，保留3位小数，当宽度不足时在前面补空格。

2 判断语句

1. 常用比较运算符
   (1) 大于 >
   (2) 小于 <
   (3) 大于等于 >=
   (4) 小于等于 <=
   (5) 等于 ==
   (6) 不等于 !=

单引号字节
双引号字符串

(1) 与 &&
(2) 或 ||
(3) 非 ！

短路原则，可以使用括号
不能连写

3 循环语句

基本思想：把控制循环次数的变量从循环体中剥离。

for (init-statement : condition: expression)
{
    statement
}

init-statement可以是声明语句、表达式、空语句，一般用来初始化循环变量；
condition 是条件表达式，和while中的条件表达式作用一样；可以为空，空语句表示true
expression 一般负责修改循环变量，可以为空

4 数组

4.1一维数组

4.1.1 数组的定义

4.1.2 数组的初始化

补充：浮点数比较
比较两个double是否相同，通过比较差值是否小于一个小数

eps缩写自epsilon，表示一个小量，但这个小量又要确保远大于浮点运算结果的不确定量。eps最常见的取值是1e-8左右。引入eps后，我们判断两浮点数a、b相等的方式如下:

4.2多维数组

Int arr[10][20][30] = {0}; // 将所有元素初始化为0
// 大小为10的数组，它的每个元素是含有4个整数的数组
// 这些数组的元素是含有30个整数的数组

5字符串

5.1 字符与整数的联系—ASCII码

每个常用字符都对应一个-128~127的数字，二者之间可以相互转化：

#include <iostream>\\
using namespace std;
int main()
{
    char c= 'a';;
    cout << (int)c<<endl;
    int a=66;
    cout << (char)a<< endl;

    return 0;
}

常用ASCII值：’A’-‘Z’ 是65~90，’a’-‘z’是97-122，’0’-‘9’是48-57。
字符可以参与运算，运算时会将其当做整数：

#include <iostream>
using namespace std;
int main()
{

    int a= 'B'-'A';
    int b = 'B'*'A';
    char c= 'A'+2;

    cout << a << endl;
    cout << b << endl;
    cout << c << endl;

    return 0;
}

5.2 字符数组

字符串就是字符数组加上结束符’\0’。
可以使用字符串来初始化字符数组，但此时要注意，每个字符串结尾会暗含一个’\0’字符，因此字符数组的长度至少要比字符串的长度多1！

5.2.1 字符数组的输入输出

#include <iostream>

using namespace std;

int main()
{

    char str[100];
    cin >>str;                //输入字符串，遇到空格或者回车会停止
    cout << str<<endl;        //输出字符串，遇到空格或者回车不会停止
    printf("%s\n",str);12

    return 0;
}

gets() 不安全，已经不能使用

5.2.2 字符数组的常用操作

下面几个函数需要引入头文件:
#include <string.h>

(1) strlen(str)，求字符串的长度
(2) strcmp(a, b)，比较两个字符串的大小，a < b 返回-1，a == b 返回0，a > b返回1。这里的比较方式是字典序！
(3) strcpy(a, b)，将字符串b复制给从a开始的字符数组。

#include <iostream>
#include <string.h>
using namespace std;

int main()
{

    char a[100]= "Hello World!",b[100];
    cout<<strlen(a)<<endl;
    strcpy(b,a);
    cout<<strcmp(a,b)<< endl;
    return 0;
}

5.2.3 遍历字符数组中的字符：

#include <iostream>
#include <string.h>
using namespace std;

int main()
{
    char a[100]="Hello World!!";
    for(int i =0, len= strlen(a);i<len;i++) cout << a[i]<<endl;

    return 0;

}

5.3标准库类型 string

可变长的字符序列，比字符数组更加好用。需要引入头文件：
#include <string>

5.3.1 定义和初始化

5.3.2 string 上的操作

(1) string的读写：

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s1,s2;
    cin>>s1>>s2;
    cout << s1 << s2 <<endl;

    return 0;

}

注意：不能用printf直接输出string，需要写成：printf(“%s”, s.c_str());

(2) 使用getline读取一整行

#include <iostream>
#include <string>
using namespace std;
int main()
{
    string s;
    getline(cin,s);
    cout << s<< endl;
    return 0;
}

(3) string的empty和size操作

（注意size是无符号整数，因此 s.size() <= -1一定成立）：

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s1,s2="abc";
    cout <<s1.empty() << endl;
    cout << s2.empty() << endl;
    cout << s2.size() <<endl;
    return 0;

}

(4) string 的比较

支持 > < >= <= == !=等所有比较操作，按字典序进行比较。

(5) 为string对象赋值

string s1 = “hello,  ”, s2 = “world\n”;
string s3 = s1 + s2;                    // s3的内容是 hello, world\n
s1 += s2;                                // s1 = s1 + s2

(6) 两个string对象相加

string s1 = “hello,  ”, s2 = “world\n”;
string s3 = s1 + s2;                    // s3的内容是 hello, world\n
s1 += s2;                                // s1 = s1 + s2

(7) 字面值和string对象相加：

做加法运算时，字面值和字符都会被转化成string对象，因此直接相加就是将这些字面值串联起来：

string s1 = “hello”, s2 = “world”;        // 在s1和s2中都没有标点符号
string s3 = s1 + “, “ + s2 + ‘\n’;

当把string对象和字符字面值及字符串字面值混在一条语句中使用时，必须确保每个加法运算符的两侧的运算对象至少有一个是string：

string s4 = s1 + “, “;    // 正确：把一个string对象和有一个字面值相加
string s5 = “hello” +”, “; // 错误：两个运算对象都不是string

string s6 = s1 + “, “ + “world”;  // 正确，每个加法运算都有一个运算符是string
string s7 = “hello” + “, “ + s2;  // 错误：不能把字面值直接相加，运算是从左到右进行的

5.3.3 处理string对象中的字符

可以将string对象当成字符数组来处理：

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s= "Hello World";
    for(int i =0; i <s.size();i++) cout << s[i]<<endl;

    return 0;

}

或者使用基于范围的for语句：

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s= "Hello World";
    for(char c : s) cout << c <<endl;

    for(char &c :s )c ='a';
    cout << s <<endl;

    return 0;

}

string.h
string.h是C语言里面关于字符数组的函数定义的头文件，常用函数有strlen、strcmp、strcpy等等，更详细的信息可以自己查看（面向过程）
cstring
CString常用于MFC编程中，是属于MFC的类，如从对话框中利用GetWindowText得到的字符串就是CString类型，CString定义在afx.h头文件中。CString为Visual C++中最常用的字符串类，继承自CSimpleStringT类，主要应用在MFC和ATL编程中，所以使用CString时要包含afx.h文件。
string
string是C++标准库(STL)中的类型，它是定义的一个类，定义在string头文件中。里面包含了对字符串的各种常用操作，它较char*的优势是内容可以动态拓展，以及对字符串操作的方便快捷，用+号进行字符串的连接是最常用的操作。

6 C++中的函数

6.1 函数基础

一个典型的函数定义包括以下部分：返回类型、函数名字、由0个或多个形参组成的列表以及函数体。

6.1.1 编写函数

一个求阶乘的程序。程序如下所示：

int fact(int val)
{
    int ret = 1;
    while (val > 1)
        ret *= val -- ;
    return ret;
}

函数名字是fact，它作用于一个整型参数，返回一个整型值。return语句负责结束fact并返回ret的值。

6.1.2 调用函数

函数要放在main前面否则报错找不到这个函数

int main()
{
    int j = fact(5);
    cout << "5! is " << j << endl;

    return 0;
}

函数的调用完成两项工作：
一是用实参初始化函数对应的形参，
二是将控制权转移给被调用函数。
此时，主调函数的执行被暂时中断，被调函数开始执行。

6.1.3 形参和实参

实参是形参的初始值。第一个实参初始化第一个形参，第二个实参初始化第二个形参，依次类推。形参和实参的类型和个数必须匹配。

fact(“hello”);        // 错误：实参类型不正确
fact();             // 错误：实参数量不足
fact(42, 10, 0);     // 错误：实参数量过多
fact(3.14);         // 正确：该实参能转换成int类型，等价于fact(3);

形参也可以设置默认值，但所有默认值必须是最后几个。当传入的实参个数少于形参个数时，最后没有被传入值的形参会使用默认值。

6.1.4 函数的形参列表

函数的形参列表可以为空，但是不能省略。()或者(void)都可以

void f1() {/* …. */}            // 隐式地定义空形参列表
void f2(void) {/* … */}         // 显式地定义空形参列表

形参列表中的形参通常用逗号隔开，其中每个形参都是含有一个声明符的声明。即使两个形参的类型一样，也必须把两个类型都写出来：

int f3(int v1, v2) {/* … */}         // 错误
int f4(int v1, int v2) {/* … */}     // 正确

6.1.5 函数返回类型

大多数类型都能用作函数的返回类型。一种特殊的返回类型是void，它表示函数不返回任何值。函数的返回类型不能是数组类型或函数类型，但可以是指向数组或者函数的指针。

6.1.6 局部变量、全局变量与静态变量

局部变量只可以在函数内部使用，全局变量可以在所有函数内使用。当局部变量与全局变量重名时，会优先使用局部变量。

6.2 参数传递

6.2.1 传值参数

当初始化一个非引用类型的变量时，初始值被拷贝给变量。此时，对变量的改动不会影响初始值。

#include <iostream>
using namespace std;
int f(int x)
{
    x= 5;
}
int main()
{
    int x =10;
    f(x);
    cout << x <<endl;
    return 0;
}

6.2.2 传引用参数

当函数的形参为引用类型时，对形参的修改会影响实参的值。使用引用的作用：避免拷贝、让函数返回额外信息。

#include <iostream>
using namespace std;
int f(int &x)
{
    x= 5;
}
int main()
{
    int x =10;
    f(x);
    cout << x <<endl;
    return 0;
}

6.2.3 数组形参

在函数中对数组中的值的修改，会影响函数外面的数组。
一维数组形参的写法：

// 尽管形式不同，但这三个print函数是等价的
void print(int *a) {/* … */}
void print(int a[]) {/* … */}
void print(int a[10]) {/* … */}

#include <iostream>
using namespace std;
void print(int a[])
{
    for( int i =0; i<10;i++) cout <<a[i] << endl;
}

int main()
{
    int a[10];
    for(int i =0; i<10;i++) a[i]=i;
    print(a);
    return 0;
}

多维数组形参的写法：

// 多维数组中，除了第一维之外，其余维度的大小必须指定
void print(int (*a)[10]) {/* … */}
void print(int a[][10]) {/* … */}

6.3 返回类型和return语句

6.3.1 无返回值函数

6.3.2 有返回值的函数

6.4 函数递归

在一个函数内部，也可以调用函数本身。

#include <iostream>
using namespace std;

int fact(int n)
{
    if( n <= 1 ) return 1;
    return  n *fact(n-1);
}

int main()
{

    int n;
    cin >> n;
    cout << fact(n) << endl;
    return 0;

}

7 类、结构体、指针、引用

7.1 类与结构体

类的定义：

class Person
{
    private:
        int age, height;
        double money;
        string books[n];

    public:
        string name;

        void say()
        {
            cout << " I'm" << name << endl;
        }

        int get_age()
        {
            return age;
        }

        void add_money(double x)
        {
            money +=x;
        }
};

类中的变量和函数被统一称为类的成员变量。
private后面的内容是私有成员变量，在类的外部不能访问；public后面的内容是公有成员变量，在类的外部可以访问。

类的使用：

#include <iostream>

using namespace std;

const int N = 1000010;

class Person
{
    private:
        int age, height;
        double money;
        string books[100];

    public:
        string name;

        void say()
        {
            cout << "I'm " << name << endl;
        }

        int set_age(int a)
        {
            age = a;
        }

        int get_age()
        {
            return age;
        }

        void add_money(double x)
        {
            money += x;
        }
} person_a, person_b, persons[100];

int main()
{
    Person c;

    c.name = "yxc";      // 正确！访问公有变量
    c.age = 18;          // 错误！访问私有变量
    c.set_age(18);       // 正确！set_age()是共有成员变量
    c.add_money(100);

    c.say();
    cout << c.get_age() << endl;

    return 0;
}

结构体和类的作用是一样的。不同点在于类默认是private，结构体默认是public。

struct Person
{
    private:
        int age,height;
        double money;
        string books[100];

    public:
        string name;

        void say()
        {
            cout <<  "I'm" << name << endl;
        }

        int set_age(int a)
        {
            age =a;
        }

        int get_age()
        {
            return age;
        }

        void add_money(double x)
        {
            money +=x;
        }
} person_a,person_b,persons[100];

7.2 指针和引用

#include <iostream>
using namespace std;

int main()
{
    char c = 'a',d;
    printf("%g\n",&c);
    cout << (void*)&c <<endl;
    cout << (void*)&d <<endl;
    return 0;
}

指针指向存放变量的值的地址。因此我们可以通过指针来修改变量的值。

#include <iostream>
using namespace std;

int main()
{
    int a =10;
    int *p = &a;
    cout << *p <<endl;
    return 0;
}

7.3 链表

8 C++ STL

8.1 #include

vector是变长数组，支持随机访问，不支持在任意位置O(1)插入。为了保证效率，元素的增删一般应该在末尾进行。

声明

#include <vector>     头文件
vector<int> a;        相当于一个长度动态变化的int数组
vector<int> b[233];    相当于第一维长233，第二位长度动态变化的int数组
struct rec{…};
vector<rec> c;        自定义的结构体类型也可以保存在vector中

size/empty

size函数返回vector的实际长度（包含的元素个数），empty函数返回一个bool类型，表明vector是否为空。二者的时间复杂度都是O(1)。
所有的STL容器都支持这两个方法，含义也相同

clear
clear函数把vector清空

迭代器
迭代器就像STL容器的“指针”，可以用星号“*”操作符解除引用。
一个保存int的vector的迭代器声明方法为：
vector<int>::iterator it;
vector的迭代器是“随机访问迭代器”，可以把vector的迭代器与一个整数相加减，其行为和指针的移动类似。可以把vector的两个迭代器相减，其结果也和指针相减类似，得到两个迭代器对应下标之间的距离。

迭代器左开右闭

begin/end
begin函数返回指向vector中第一个元素的迭代器。例如a是一个非空的vector，则*a.begin()与a[0]的作用相同。
所有的容器都可以视作一个“前闭后开”的结构，end函数返回vector的尾部，即第n个元素再往后的“边界”。*a.end()与a[n]都是越界访问，其中n=a.size()。
下面两份代码都遍历了vector<int>a，并输出它的所有元素。

for (int I = 0; I < a.size(); I ++) cout << a[i] << endl;
for (vector<int>::iterator it = a.begin(); it != a.end(); it ++) cout << *it << endl;

front/back
front函数返回vector的第一个元素，等价于*a.begin() 和a[0]。
back函数返回vector的最后一个元素，等价于*==a.end()和 a[a.size() – 1]。

push_back()和 pop_back()
a.push_back(x) 把元素x插入到vector a的尾部。
b.pop_back() 删除vector a的最后一个元素。

8.2 #include

头文件queue主要包括循环队列queue和优先队列priority_queue两个容器。

声明

queue<int> q;
struct rec{…}; queue<rec> q;     //结构体rec中必须定义小于号
priority_queue<int> q;        // 大根堆 默认  
priority_queue<int, vector<int>, greater<int> q;    // 小根堆
priority_queue<pair<int, int>>q;

循环队列 queue

push 从队尾插入
pop从队头弹出
front返回队头元素
back 返回队尾元素

优先队列 priority_queue

push 把元素插入堆
pop 删除堆顶元素(删除最大值)
top 查询堆顶元素（最大值）
清空就重新初始化就可以

8.3 #include

头文件stack包含栈。声明和前面的容器类似。
push 向栈顶插入
pop 弹出栈顶元素

8.4 #include

双端队列deque是一个支持在两端高效插入或删除元素的连续线性存储空间。它就像是vector和queue的结合。与vector相比，deque在头部增删元素仅需要O(1)的时间；与queue相比，deque像数组一样支持随机访问。
[] 随机访问
begin/end，返回deque的头/尾迭代器
front/back 队头/队尾元素
push_back 从队尾入队
push_front 从队头入队
pop_back 从队尾出队
pop_front 从队头出队
clear 清空队列

8.5 #include

头文件set主要包括set和multiset两个容器，分别是“有序集合”和“有序多重集合”，即前者的元素不能重复，而后者可以包含若干个相等的元素。set和multiset的内部实现是一棵红黑树，它们支持的函数基本相同。
声明
set s;
struct rec{…}; set s; // 结构体rec中必须定义小于号
multiset s;

size/empty/clear
与vector类似

迭代器
set和multiset的迭代器称为“双向访问迭代器”，不支持“随机访问”，支持星号(*)解除引用，仅支持”++”和—“两个与算术相关的操作。
设it是一个迭代器，例如set::iterator it;
若把it++，则it会指向“下一个”元素。这里的“下一个”元素是指在元素从小到大排序的结果中，排在it下一名的元素。同理，若把it—，则it将会指向排在“上一个”的元素。

begin/end
返回集合的首、尾迭代器，时间复杂度均为O(1)。
s.begin() 是指向集合中最小元素的迭代器。
s.end() 是指向集合中最大元素的下一个位置的迭代器。换言之，就像vector一样，是一个“前闭后开”的形式。因此—s.end()是指向集合中最大元素的迭代器。

insert
s.insert(x)把一个元素x插入到集合s中，时间复杂度为O(logn)。
在set中，若元素已存在，则不会重复插入该元素，对集合的状态无影响。

find
s.find(x) 在集合s中查找等于x的元素，并返回指向该元素的迭代器。若不存在，则返回s.end()。时间复杂度为O(logn)。

lower_bound/upper_bound
这两个函数的用法与find类似，但查找的条件略有不同，时间复杂度为 O(logn)。
s.lower_bound(x) 查找大于等于x的元素中最小的一个，并返回指向该元素的迭代器。
s.upper_bound(x) 查找大于x的元素中最小的一个，并返回指向该元素的迭代器。

erase
设it是一个迭代器，s.erase(it) 从s中删除迭代器it指向的元素，时间复杂度为O(logn)
设x是一个元素，s.erase(x) 从s中删除所有等于x的元素，时间复杂度为O(k+logn)，其中k是被删除的元素个数。

count
s.count(x) 返回集合s中等于x的元素个数，时间复杂度为 O(k +logn)，其中k为元素x的个数。

8.6 #include

map容器是一个键值对key-value的映射，其内部实现是一棵以key为关键码的红黑树。Map的key和value可以是任意类型，其中key必须定义小于号运算符。

声明

map<key_type, value_type> name;

例如：

map<long, long, bool> vis;
map<string, int> hash;
map<pair<int, int>, vector<int>> test;

size/empty/clear/begin/end均与set类似。

Insert/erase
与set类似，但其参数均是pair。

find
h.find(x) 在变量名为h的map中查找key为x的二元组。

[]操作符
h[key]返回key映射的value的引用，时间复杂度为O(logn)。
[]操作符是map最吸引人的地方。我们可以很方便地通过h[key]来得到key对应的value，还可以对h[key]进行赋值操作，改变key对应的value。

8.7 #include

8.8 #include

8.9 #include

9 位运算与常用库函数

9.1 位运算、

& 与
| 或
~ 非
^ 异或
>> 右移
<< 左移

常用操作：
(1) 求x的第k位数字 x >> k & 1
(2) lowbit(x) = x & -x，返回x的最后一位

9.2 常用库函数

(1) reverse 翻转

翻转一个vector：
reverse(a.begin(), a.end());
翻转一个数组，元素存放在下标1~n：
reverse(a + 1, a + 1 + n);

(2) unique 去重

(3) random_shuffle 随机打乱

(4) sort

对两个迭代器（或指针）指定的部分进行快速排序。可以在第三个参数传入定义大小比较的函数，或者重载“小于号”运算符。

把一个int数组（元素存放在下标1~n）从大到小排序，传入比较函数：

int a[MAX_SIZE];
bool cmp(int a, int b) {return a > b; }
sort(a + 1, a + 1 + n, cmp);

把自定义的结构体vector排序，重载“小于号”运算符：

struct rec{ int id, x, y; }
vector<rec> a;
bool operator <(const rec &a, const rec &b) {
return a.x < b.x || a.x == b.x && a.y < b.y;
}
sort(a.begin(), a.end());

(5) lower_bound/upper_bound 二分

lower_bound的第三个参数传入一个元素x，在两个迭代器（指针）指定的部分上执行二分查找，返回指向第一个大于等于x的元素的位置的迭代器（指针）。
upper_bound的用法和lower_bound大致相同，唯一的区别是查找第一个大于x的元素。当然，两个迭代器（指针）指定的部分应该是提前排好序的。

在有序int数组（元素存放在下标1~n）中查找大于等于x的最小整数的下标：

int I = lower_bound(a + 1, a + 1 + n,. x) – a;

在有序vector 中查找小于等于x的最大整数（假设一定存在）：

int y = *--upper_bound(a.begin(), a.end(), x);