语法基础

一．变量，输入输出，表达式，和顺序语句

标准结构

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

using namespace std；用于创建命名空间，cout和cin都属于其中

基本类型

（1）布尔型存储true和flase 1byte

（2）字符型 char 1byte

（3）整型 int 4byte

（4）浮点型实数和科学计数法

float 有效数字6-7位 4byte

double 有效数字15-16位 8byte

long double 18-19位

一个字节有8比特 1byte=8bit 1KB = 1024byte

输入输出

cin>>a>>b;表示输入a和b

cout<<a+b<<endl;表示输出a+b；

常见提交结果

AC accepted

WA wrong answer

time limit error 超时

memory limit error 内存超限

segmentation fault 数组越界

compiler error 编译错误

presentation error 表达错误，格式错误

runtime error string字符串检测到越界

Float Point Exception某处位置存在a%i时，i为0的情况

输出结果为nan（not a number）的原因，所要开根号的数可能是个负数

输入输出同样可以用scanf和printf

万能头文件 <bits/stdc++.h> 包含所有常用的函数

运行速度：<bits/stdc++.h 大于大于

区别在于头文件大小

iostream可以读入各种常见类型的变量，也可以读入string字符串

printf的三种排版格式

1.%5d 每次输出靠右占用五个字符

2.%-5d 每次输出靠左占用五个字符

3.%05d 每次输出靠右占用五个字符，不足五个以0填充

二．判断语句

if语句

1.if语句之后千万不要加分号（如果加了分号表示if执行了一个空语句）

2.其余用法与c语言相同

using namespace std;
int main()
{
    int score;
    cin>>score;
    
    if(score >= 60)
    {
        cout << "及格" << endl;
        
    }
    else
    {
        cout << "不及格" << endl;
    }
    cout << "结束" << endl;
    return 0;
}

注意点：判断语句里判断符号分别为”>”,”<”,“>=”, “<=”,“！=”， “==”

3.逻辑表达式

名称写法另一种写法

（1）逻辑与：&&，and

（2）逻辑或：||， or

（3）逻辑非：！ not

如果直接写if (a >b>c)，其真正意义是，先判断a是否大于b，如果a大于b，则a>b将作为布尔值1与c比较，如果a小于b，则作为布尔值0与c比较

！a等价于a ！= -1

printf等函数使用时会有“%”等特殊符号的使用，在printf函数里，%是指的输出格式，即转义字符，如果仅为了打印“%”，需要将%前加“%”，

例如printf（“sum = %d%%“，sum）；

三．循环结构（基本和c语言相同）

1.while循环：while循环表达式可以嵌入cin等函数， while（cin>>n）,因为cin函数是存在返回值的，如果没有返回值是因为读到文件结束符

小技巧：while 循环输入x时可以写成while （cin>>x&&x）表示输入x且读入x时循环结束

c++中的EOF有准确的值，即-1.

cin和scanf的区别：(1).在输入字符时cin会自动过滤掉空格，而scanf会读入空格

(2).cin的运算效率比scanf慢很多，但如果输入的数是小于10000的情况下，程序员用cin编写代码的效率会更快一些

c++一秒只能运算1亿次，必要的时候需要优化代码

2.reverse函数

·作用：将数组中某一连续的元素旋转比如1 2 3 4 5 逆序一次得到5 4 3 2 1

·函数库函数：

· 函数使用 reverse（a，a+n）

· 说明：将a数组中从首元素到第n个元素的子数组逆序排布

· 旋转：比如数组1 2 3 4 5旋转一次得到5 1 2 3 4，再旋转得到4 5 1 2 3

四．数组

浮点数与整型的存储方式不同，且当运算量过大时都会存在一定误差

mem函数（库函数cstring）

1.memset

1.格式

memset(arr,1,sizeof arr)

2.意义：

将arr数组全部赋值为1 ，sizeof arr并不是代表几个数，而是说没前进一步占几个字节

利用memset对数组赋值会比循环快很多

2.memcpy

1.格式

memcpy(arr1,arr2,sizeof arr2)

意义

将arr1数组赋值为arr2数组中的对应元素

五．字符串

1.字符数组：由若干个字符组成的数组，一种另类的字符串

2.字符串：由若干个字符组成

数组定义的字符串的长度一般比真实的长度多一，因为每个字符数组后面都会以‘\0‘这个结束符结尾

读入的字符串较小时适合用字符数组表示，读入的字符串较大时适合用string字符串表示，scanf无法读入string定义的字符串

#include <iostream>
using namespace std;
int main()
{
    char a1[] = {'c','+','+'};			 // 列表初始化，没有空字符
    char a2[] = {'C','+','+','\0'};		 // 列表初始化，含有显示的空字符
    char a3[] = "C++";					// 自动添加字符串结尾的空字符
    char a4[6] = "Daniel";				// 错误，没有足够空间课存放空字符
    
    return 0;
}

a1没有’\0’这个结束符，本质上是一个字符数组

a2有了结束符，可以算作一个字符串

a3以字符串定义，就是字符串，但因为使用数组定义的，长度会多1

3.cin,cout函数本身也是通过地址来读入，打印结果

比如cout<<str<<endl;就是从str的首元素开始打印

而cout<<str+1<<endl;就是从str的第二个元素开始打印
输入字符数组时读到空格时输入会停止，比如输入abc def，真正输入进去只有abc

4.fgets(s,n,stdin) 可以读入空格，不会过滤回车

说明：读入n长度的字符串s，s字符串是

库函数：stdio

5.getline（cin，s）可以读入空格

说明：读入一行字符串s，且字符串s必须用string定义，常用

库函数：iostream

6.c中string库函数

(1).strlen，求出字符串长度，不计‘\0‘

(2).strcmp（arr1，arr2）按字典序比较两个字符串的大小，返回值为1，0，-1

(3).strcpy(arr1,arr2)将arr2字符串复制给arr1

在for循环里用strlen，每次循环都会计算一次strlen，所以需要提前定义一个变量存储长度，减少运算量

7.标准库函数string（可变长的字符序列，比字符数组更好用）

·优点：

（1）

能直接赋值

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int main()
{
string s1; // 默认的空字符串
string s2 = s1; // s2是s1的一个副本
string s3 = "hiya"; // s3是该字符串字面值的一个副本
string s4(10, 'c'); // s4的内容是: cccccccccc I
return 0;
}

（2）可直接输入输出

#1nclude <cstd1o>
#include <cstring>
#include <iostream>
using namespace std; ,
int main()
{
	string s1, s2;
	cin>>s1>>s2;
	cout<<s1<<’<<s2<<end1;
return 0;
}

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int main()
{
	string s1, s2;
	cin >> s1;
	printf("%s\n", s1.c_ _str()D
	return 0;
}

其中s1.c_str()返回了一个字符数组

（4）字符串可直接比较，无需strcmp

（5）字符串可以直接相加，即拼接，甚至累加，（string类型）“hello ”+（string类型）“world”-》“Hello World”

字符串相加时必须保证两者之间必须保证有一个字符串属于string类型

最好别用+=来增添字符串

遍历初识：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int main()
{
	string s = "Hello World!";
	for (char c : s) cout << c << endl;
	return 0;
}

顺次遍历s字符串中的每一个元素

该遍历等价于

for(int i = 0;i  < s.size(); i++)
{
    char c = str[i];
}

并同时输出每一次的c，但原先的字符串并不受到影响

8.substr函数

（1）说明，返回特定长度的字符串

（2）格式：str.substr（0，len），返回从str首元素地址开始一直到len的字串,len可以省略即str.substr(0)，指的是返回从下标0开始一直到结束的字符串

（3）库函数：string

9.stringstream ssin函数

(1)说明：将字符串作为字符串流通过空格分隔开，每一个分隔开的字符串作为原字符串的字串

(2)格式stringstream ssin（s）

#include <iostream>
#include <sstream>
using namespace std;
int main()
{
	string s, a, b;
	getline(cin, s);
	cin>>a>>b;
	stringstream ssin(s);
	string str;
	while (ssin >> str)
		if(str == a) cout << b << ' ';
		else cout << str <<' ' ;
	return 0;
}

str被不断赋值成字符串的一个字串

（3）库函数 sstream

10.ssin函数（通常叫ssin，也可以自定义昵称使用）

（1）说明：从字符串流中提取我们需要的信息，可以是各种类型的变量，和cin等价

（2）格式 ssin>>a>>b>>str

int main()
{
	string s;
	getline(cin, s);
	stringstream ssin(s);
	int a, b;
	string str;
	double C;
	ssin >> a >> str >> >b >> C;
	cout << a << endl << str << endl << b<<endl << C << end1;
	return 0;
}

（3）库函数 sstream

11.sscanf函数

（1）说明：作用与ssin相同，但格式上多了一个参数

（2）格式 sscanf（s，“%d %c %s”，&a,&b,&str）;

#include <cstdio>
#include <iostream>
#include <sstream>
using namespace std;
int main()
{
	char s[1000];
	fgets(s, 1000，stdin);
	int a, b;
	char str[1000];
	double c;
	sscanf(s, "%d%s%d%1f", &a, str, &b, &c);
	return 0; 
}

(3)库函数cstdio

back函数

（1） s.back(); 返回字符串s的最后一个元素

（2） s.pop.back();删除字符串s的最后一个元素

（3）库函数 iostream

六．函数(使编代码的过程更加简洁)

组成部分：返回类型，函数名，参数，函数体

函数可以先声明再定义，也可以只是定义，但只有函数定义时函数必须放在main函数之前

函数的形参列表可以为空，但是不能省略

把数组传入函数中，对数组某一元素赋值，原数组会发生相应改变，因为传入函数中的是数组的地址

1.静态变量 static(在函数内部开辟了一个只有该函数所能用的的全局变量)

·说明：每次函数调用所使用的都是同一个变量，只会被定义一次，下次调用定义静态变量时会直接跳过，变量的值会在改变前一直保存下去

·作用：可以检测函数调用的次数

·使用：static int cnt = 0;

int output(void)
{
	static int cnt = 0;
	cnt ++ ;
	cout << "call: " << cnt <<"times" << endl ;
}

当局部变量和全局变量重名时，优先使用局部变量

2.参数传递

（1）传值调用

·相当于拷贝了一份所传的变量，原变量的值不受影响

（2）传址调用，传引用调用

·将变量传到函数内部，传进去的是变量本身，会因函数的过程而改变

int max(int &x,int &y)
{
	x = 10,y = 20;
	if( x > y ) return x;
	return y;
}

（3）数组传参

在函数中对数组的修改，会影响外部的数组

与c同样的，数组的行也可以省略

3.inline修饰函数

·说明：相当于把函数的函数体直接在main函数中展开

·举例：

#include <iostream>
using namespace std;
inline void foo(int b[])
{
	cout << sizeof b << endl; ;
}
int main()
{
	int a[10];
	cout << sizeof a << endl;
	foo(a);
	return 0;
}

·作用：会让程序运行时快一些

4.函数递归

·说明：函数调用函数本身

·缺点：运行速度慢

七．类，结构体，指针与引用

1.类（class）

（1）. 说明：可以将变量，数组和函数完美的打包在一起

(2). 结构：两个主元素private，public

·private只能在类内部

·public可以在外部调用，也可以在内部调用

·private和public可以多次定义

·类中的变量和函数统一称为成员变量

using namespace std;
class Person
{
	private:
		int age, height ;
		double money;|
	public:
		string name;
		void say()
	{
	cout << "I'm"<< name << end1;
	}
	int get_ age()
	{
		return age;
	}
	void add_ money(double x)
	{
		money += X;
	}
	private:
		string books[N]; 
};

注意点：花括号后面一定要加分号

class Person
{

};

(3)类的调用

int main( )
{
    Person C;
    C. name = 'yxc";
    // c.age = 18; //错误!
    cout << c.get_age() << endl ;
    C. add_money(1000000);
}

c.age是错误的，因为age属于类中private的变量，无法在外部调用

2.结构体（与类的用法相同）

3.类与结构体的区别：如果不在内部定义private和public时定义的变量，类默认定义的成员变量属于private，结构体默认定义的成员变量属于public

4.类与结构体可以在内部构造函数

struct Person
{
    int age, height;
    double money;
    Person(int_ age, int_ height, double_ _money) // 构造函数
    {
        age =_ age;
        height =_ height;
        money =_ money;
    }
};
int main()
{
    Person p(18，180，100.0);
    return 0;
}

特殊的赋值方式

Person() {}
    Person(int _age, int _height) : age(_age), height(_height) {}
    Person(int _age, int _height, double _money) : age(_age), height(_height), mmoney(_money) {}
};

第12行表示定义一个函数，将)_age值赋给age，将 _height赋给height

5.指针

（1）指针所存的就是变量的地址

（2） c++中输出变量的地址

#include <iostream>
using namespace std;
int main( )
{
    char c = 'a';
    cout << (void*)&c << endl;
    return 0;
}

如果定义的变量是连续定义的，那么他们的地址也是连续的

（3）指针的引用

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

int* p = &a表示定义一个整型指针存储a的地址

之后的*p则表示解引用p，对p的地址读取一个值

并且可以修改这个值

数组是一种特殊的指针，数组名存的是数组首元素的地址

每个int型变量有四个字节，所以整型数组每一个元素的地址相差四个字节

（4）指针也可以进行运算

如果运算的指针属于整型，会在运算完之后除以整型字节数4

6.引用

说明：c++指针写法的简化

举例：

int main( )
int a = 10;
int* p = &a;
int& p = a; //引用、别名

此时之后使用的p都是*p，p相当于是a的别名

7.链表

示例

#include <iostreamp
using namespace std;
struct Node
{
    int val;
    Node* next;
    
    Node(int _val) : va1(_val), next(NULL) {}
};
int main()
{
    Node node = Node(1)|
    Node* p = &node;
}

其中定义结构体变量node并用指针获得地址可以写成一段

int main()
{
	Node* p = new Node(1);
}

此时如果要调用结构体内的成员变量，则用->指向该变量

Node* p = new Node(1);
p ->next = p;
p->val;

如果p不是指针，则要用 . 来调用

链表的第一个节点的地址通常称为头节点，我们习惯定义head保存第一个节点的地址

8.链表遍历

使pqo分别为1，2，3节点，定义head作为头节点，将p节点1赋值给head，通过for循环一次遍历每一个节点

·如何将节点删除

本质上是在遍历过程中跳过该节点

9.条件表达式的一种应用

·短路

在a&&b时，只要a条件不成立，则无需判断b是否成立，直接跳过b语句，实际上，这个条件表达式并非一定要放在if表达式中

八． STL

1.vector

一种可以自定义长度的数组

数组定义方式 vector a

定义二维数组 vector a[233] 定义了一个233行长度可以变化的数组

结构体的成员变量也可以动态开辟

接下来镶嵌yxc的讲义（实在太长了）

—————————————————————————————

第八章 C++ STL

STL是提高C++编写效率的一个利器。

——闫学灿

1.#include

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

声明

#include 头文件

vector a; 相当于一个长度动态变化的int数组

vector b[233]; 相当于第一维长233，第二位长度动态变化的int数组

struct rec{…};

vector c; 自定义的结构体类型也可以保存在vector中

size/empty

size函数返回vector的实际长度（包含的元素个数），empty函数返回一个bool类型，表明vector是否为空。二者的时间复杂度都是O(1)。

所有的STL容器都支持这两个方法，含义也相同，之后我们就不再重复给出。

clear

clear函数把vector清空。

迭代器

迭代器就像STL容器的“指针”，可以用星号“*”操作符解除引用。

一个保存int的vector的迭代器声明方法为：

vector::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()。

下面两份代码都遍历了vectora，并输出它的所有元素。

for (int I = 0; I < a.size(); I ++) cout << a[i] << endl;

for (vector::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的最后一个元素。

2.#include

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

声明

queue q;

struct rec{…}; queue q; //结构体rec中必须定义小于号

priority_queue q; // 大根堆

priority_queue<int, vector, greater q; // 小根堆

priority_queue<pair<int, int>>q;

循环队列 queue

push 从队尾插入

pop 从队头弹出

front 返回队头元素

back 返回队尾元素

优先队列 priority_queue

push 把元素插入堆

pop 删除堆顶元素

top 查询堆顶元素（最大值）

3.#include

头文件stack包含栈。声明和前面的容器类似。

push 向栈顶插入

pop 弹出栈顶元素

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 清空队列

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的个数。

#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> test;

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

Insert/erase

与set类似，但其参数均是pair<key_type, value_type>。