- 1Tomcat怎么优化
- 2【深度学习】训练时现Interal Error：Blas GEMM launch failed._internal: blas gemm launch failed
- 3java中的switch用法,循环,方法,数组以及类_java switch
- 4vue 访问第三方 跨域, 配置vue.config.js_vue调用第三方接口跨域
- 5国际服务贸易期末考试复习资料_gats的具体义务和特定义务是一样吗?
- 6用DIV+CSS技术设计的个人电影网站（web前端网页制作课作业）_网页设计与制作电影网站
- 7查询电脑配置：CPU信息、内存信息、服务器信息、Java虚拟机、磁盘信息。
- 8ROS回调函数的类方法实现，both in Python 和 C++_ros 回调函数 怎么写
- 9Building wheel for pycocotools (pyproject.toml) ... error错误解决_building wheel for pycrypto (pyproject.toml) did n
- 10Java程序设计入门教程-- switch选择语句
[C++] C++面试试题_c++ 关于switch的题目
赞
踩
1、树的深度、高度
结点的深度：从根结点到该结点路径上的结点的个数。
如上图中D结点的深度为：从根结点A到D结点的路径（A->B->D）上的结点个数，3。
结点的高度：从该结点到达叶子结点的所有路径中，最长的路径上结点的个数。
如上图中D结点的高度为：从D结点到叶子结点的路径有两条（D->G和D->H），最长的路径上结点的个数都是，2。
树的高度：根结点的高度。（根结点到达叶子结点的所有路径中，最长的路径上结点的个数）
树的深度：树中，最大深度结点的深度。
2、不能在C++中重载的运算符
？：（条件运算符）
exp? exp1 : exp2 中的 ? :
- 1
.（成员访问运算符）
class.fun() 中的.
- 1
::（域运算符）
std::cout 中的::
- 1
sizeof（长度运算符）
.*(成员指针访问运算符)
3、枚举类型默认从0开始
enum fruit_set {apple, orange, banana=1, peach, grape}
- 1
枚举常量apple=0,orange=1, banana=1,peach=2,grape=3。
4、默认参数
C++默认参数严格按照从左向右的顺序，不可跳跃。如果从某处开始使用默认值,则右边所有其他参数也必须有默认值
void Fun(int a , int b = 2, int c) //这样是错误的
void Fun(int a , int b=2, int c=3) //这样是正确的
因为C++ 函数调用时，参数是从右到左开始入栈的，在一个个入栈的过程中，当遇到一个没有使用默认值的参数，那就会认为此后的参数也都没有使用默认值
5、new和delete malloc和free配套使用，不能混用
6、同一程序中局部变量和全局变量可以同名
只不过在局部变量作用域内，全局变量会被屏蔽。被屏蔽的全局变量可以通过 :: 访问
#include<iostream> using namespace std; //全局变量a int a=1; int main() { //同名的局部变量a int a = 0; //由于同名，局部变量屏蔽全局变量，赋值的会是局部变量 a = 13; cout << "输出a，由于同名，局部变量屏蔽全局变量，输出的会是局部变量" << endl; cout << a << endl; //通过::访问被屏蔽的全局变量 ::a = 20; cout << "通过::访问被屏蔽的全局变量" << endl; cout << ::a << endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
7、合法的赋值表达式
8、字符串初始化
C++中没有字符串对象，字符串通过字符数组表示。
但字符数组的最后的一个元素必须是"\0"，它标志着这个字符数组是否是字符串。
用字符串初始化字符数组时，"\0"附带在后面与前面的字符一起作为字符数组的元素。
这里需要提一下字符串长度的问题：
sizeof会把末尾附带的 ‘\0’ 也计算在内，而 strlen 不会把末尾附带的 ‘\0’ 计算在内
在内存中，就是根据"\0"来确认字符串，如果找不到就会沿着字符一直找下去。它占用内存空间，但是不计入串长。
如果是用字符初始化数组，则一定要把"\0"作为一个元素放在初始值表中，不然就不会成为一个字符串。
#include<iostream>
using namespace std;
int main()
{
char str[5] = { 'h','e','l','l','o' };
cout << str;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
由于没有结尾符"\0"，会一直输出下去，直到系统错误跳出
正确的初始化：
9、C++运算符优先级
https://blog.csdn.net/caomin1hao/article/details/79510141
10、通过指针完成交换
void swap(int *p, int *q)
{
int temp;
temp = *p;
*p = *q;
*q = temp;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
但是这样会报错：
void swap(int *p, int *q)
{
int *temp;
*temp = *p;
*p = *q;
*q = *temp;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
因为 int *temp是指针，可是没有定义这指针指向哪一块内存区域，即指针没有初始化，所以会报错：
解决方法是提前申请一块内存区域，让temp指向，准备储存数据：
void swap(int *p, int *q)
{
int *temp = (int *)malloc(sizeof(int));
*temp = *p;
*p = *q;
*q = *temp;
free(temp);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
11、switch可以嵌套256层
// 局部变量声明 int a = 128; switch (a) { case 128: std::cout << "a is 128" << std::endl; switch (a) { case 64: std::cout << "a is 64" << std::endl; default: std::cout << "a is not 64" << std::endl; } break; defalt: std::cout << "a is not 128" << std::endl; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
12、进制转换
（1）十进制转二进制
- 用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为小于1时为止。
- 把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。
总结：除2取余，先低后高排列
（2）二进制转十进制
整数最低位是乘 2 0 2^0 20，不足8位的补齐8位
13、卡特兰数
https://leetcode.cn/circle/article/lWYCzv/
补充两个推导：
（1）通项公式
C
2
n
n
−
C
2
n
n
+
1
C_{2n}^{n}-C_{2n}^{n+1}
C2nn−C2nn+1
=
A
2
n
n
A
n
n
−
A
2
n
n
+
1
A
n
+
1
n
+
1
=\frac{A_{2n}^{n}}{A_{n}^n}-\frac{A_{2n}^{n+1}}{A_{n+1}^{n+1}}
=AnnA2nn−An+1n+1A2nn+1
=
(
2
n
)
(
2
n
−
1
)
(
2
n
−
1
)
.
.
.
(
n
+
1
)
1
∗
2
∗
.
.
.
∗
n
−
(
2
n
)
(
2
n
−
1
)
(
2
n
−
1
)
.
.
.
(
n
+
1
)
(
n
)
1
∗
2
∗
.
.
.
∗
n
∗
(
n
+
1
)
=\frac{(2n)(2n-1)(2n-1)...(n+1)}{1*2*...*n}-\frac{(2n)(2n-1)(2n-1)...(n+1)(n)}{1*2*...*n*(n+1)}
=1∗2∗...∗n(2n)(2n−1)(2n−1)...(n+1)−1∗2∗...∗n∗(n+1)(2n)(2n−1)(2n−1)...(n+1)(n)
通分：
=
(
2
n
)
(
2
n
−
1
)
(
2
n
−
1
)
.
.
.
(
n
+
1
)
(
n
+
1
)
1
∗
2
∗
.
.
.
∗
n
∗
(
n
+
1
)
−
(
2
n
)
(
2
n
−
1
)
(
2
n
−
1
)
.
.
.
(
n
+
1
)
(
n
)
1
∗
2
∗
.
.
.
∗
n
∗
(
n
+
1
)
=\frac{(2n)(2n-1)(2n-1)...(n+1)(n+1)}{1*2*...*n*(n+1)}-\frac{(2n)(2n-1)(2n-1)...(n+1)(n)}{1*2*...*n*(n+1)}
=1∗2∗...∗n∗(n+1)(2n)(2n−1)(2n−1)...(n+1)(n+1)−1∗2∗...∗n∗(n+1)(2n)(2n−1)(2n−1)...(n+1)(n)
=
(
2
n
)
(
2
n
−
1
)
.
.
.
(
n
+
1
)
[
(
n
+
1
)
−
n
]
1
∗
2
∗
.
.
.
∗
n
∗
(
n
+
1
)
=\frac{(2n)(2n-1)...(n+1)[(n+1)-n]}{1*2*...*n*(n+1)}
=1∗2∗...∗n∗(n+1)(2n)(2n−1)...(n+1)[(n+1)−n]
=
(
2
n
)
(
2
n
−
1
)
.
.
.
(
n
+
1
)
1
∗
2
∗
.
.
.
∗
n
∗
(
n
+
1
)
=\frac{(2n)(2n-1)...(n+1)}{1*2*...*n*(n+1)}
=1∗2∗...∗n∗(n+1)(2n)(2n−1)...(n+1)
=
(
2
n
)
(
2
n
−
1
)
.
.
.
(
n
+
1
)
1
∗
2
∗
.
.
.
∗
n
∗
1
n
+
1
=\frac{(2n)(2n-1)...(n+1)}{1*2*...*n}*\frac{1}{n+1}
=1∗2∗...∗n(2n)(2n−1)...(n+1)∗n+11
=
A
2
n
n
A
n
n
1
n
+
1
=\frac{A_{2n}^{n}}{A_{n}^{n}}\frac{1}{n+1}
=AnnA2nnn+11
=
C
2
n
n
1
n
+
1
=
C
2
n
n
n
+
1
=C_{2n}^{n}\frac{1}{n+1}=\frac{C_{2n}^{n}}{n+1}
=C2nnn+11=n+1C2nn
（2）递推公式
C
n
=
C
2
n
n
n
+
1
C_n=\frac{C_{2n}^{n}}{n+1}
Cn=n+1C2nn
=
1
n
+
1
⋅
(
2
n
)
(
2
n
−
1
)
.
.
.
(
n
+
1
)
1
∗
2
∗
.
.
.
∗
n
=\frac{1}{n+1}·\frac{(2n)(2n-1)...(n+1)}{1*2*...*n}
=n+11⋅1∗2∗...∗n(2n)(2n−1)...(n+1)
C
n
−
1
=
C
2
(
n
−
1
)
n
−
1
n
=
C
2
n
−
2
n
−
1
n
C_{n-1}=\frac{C_{2(n-1)}^{n-1}}{n}=\frac{C_{2n-2}^{n-1}}{n}
Cn−1=nC2(n−1)n−1=nC2n−2n−1
=
1
n
⋅
(
2
n
−
2
)
(
2
n
−
3
)
.
.
.
(
n
)
1
∗
2
∗
.
.
.
∗
(
n
−
1
)
=\frac{1}{n}·\frac{(2n-2)(2n-3)...(n)}{1*2*...*(n-1)}
=n1⋅1∗2∗...∗(n−1)(2n−2)(2n−3)...(n)
=
(
2
n
−
2
)
(
2
n
−
3
)
.
.
.
(
n
)
1
∗
2
∗
.
.
.
∗
(
n
−
1
)
(
n
)
=\frac{(2n-2)(2n-3)...(n)}{1*2*...*(n-1)(n)}
=1∗2∗...∗(n−1)(n)(2n−2)(2n−3)...(n)
观察，补上个
1
n
+
1
\frac{1}{n+1}
n+11，然后分子左边补上
(
2
n
)
(
2
n
−
1
)
(2n)(2n-1)
(2n)(2n−1)，分子右边除掉
n
n
n，
C
n
−
1
C_{n-1}
Cn−1就可以得到
C
n
C_{n}
Cn了：
C
n
=
1
n
+
1
(
2
n
)
(
2
n
−
1
)
n
C
n
−
1
C_{n}=\frac{1}{n+1}\frac{(2n)(2n-1)}{n}C_{n-1}
Cn=n+11n(2n)(2n−1)Cn−1
=
4
n
−
2
n
+
1
C
n
−
1
=\frac{4n-2}{n+1}C_{n-1}
=n+14n−2Cn−1
另外：
C
1
=
C
2
1
2
=
1
C_1=\frac{C_2^1}{2}=1
C1=2C21=1
14、类的静态成员
https://blog.csdn.net/modi000/article/details/125203165
15、str[]和*str的区别
#include<iostream> using namespace std; int main() { char str1[] = "abc"; char str2[] = "abc"; const char str3[] = "abc"; const char str4[] = "abc"; const char *str5 = "abc"; const char *str6 = "abc"; char *str7 = (char*)"abc"; char *str8 = (char*)"abc"; cout << (str1 == str2) << endl; cout << (str3 == str4) << endl; cout << (str5 == str6) << endl; cout << (str7 == str8) << endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
输出结果：
（1）数组名是指向数组首元素地址的指针
（2）当字符串以数组形式声明并初始化时，会创建新的内存空间
（3）当字符串以指针形式声明时，C++实际上创建了一个string对象“abc”，并将指针指向该对象。如果后续再有新指针的声明，会比较如果存在一样的字符串对象，就将指针指向该对象，实际上是浅拷贝
16、根据后序和中序遍历结果还原二叉树
https://blog.csdn.net/ONEMORE6499/article/details/104730993
17、前缀、中缀、后缀表达式
前缀表达式、中缀表达式、后缀表达式，实际上是通过树来存储计算表达式后，树的三种不同遍历方式得到的序列，分别是树的前序、中序、后序遍历
如表达式： ( a + ( b − c ) ) ∗ d (a+(b-c))*d (a+(b−c))∗d 便是中缀表达式，是人们常见数学书写中的表达式形式
通过带括号的中缀表达式可以建立树：注意运算符的优先顺序和数字在运算符的左右
这棵树的中序遍历结果便是中缀表达式：
a + b − c ∗ d a+b-c*d a+b−c∗d
中缀表达式带有歧义，有时会跟想要的运算顺序不一致，所以需要带上括号：
( a + ( b − c ) ) ∗ d (a+(b-c))*d (a+(b−c))∗d
前缀表达式：前序遍历
∗ + a − b c d *+a-bcd ∗+a−bcd
计算机处理时，从右向左扫描，建栈，数字入栈，遇到运算符时，栈顶两个元素出栈，按照运算符计算结果，运算结果入栈
后缀表达式：后序遍历
a b c − + d ∗ abc-+d* abc−+d∗
计算机处理时，从左向右扫描，建栈
在不建树的情况下，将中缀表达式转化为后缀表达式：
1.初始化两个栈：运算符栈s1和储存中间结果栈s2；
2.从左至右扫描中缀表达式；
3.如果遇到操作数时，将其压入s2；
4.如果遇到运算符，假定运算符为 temp
（1）如果s1为空，或栈顶为左括号“（” ,则直接将 temp 入栈s1；
（2）否则，若 temp 优先级比栈顶运算符高，（即s1不为空，栈顶不是左括号，temp 优先级比s1栈顶运算符的优先级高）也将 temp 压入栈s1；
（3）否则，（即s1不为空，栈顶不是左括号，temp 优先级比s1栈顶运算符优先级低）将s1栈顶的运算符弹出并压入到s2中，再次转到4.1步骤，将 temp 与s1中新的栈顶运算符相比较；
5.如果遇到括号时：
（1）如果是左括号“（” ，则直接压入s1；
（2）如果是右括号“）” ，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃;
6.重复步骤2至5，直到表达式的最右边；
7.将s1中剩余元素依次弹出并压入s2;
8.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式。
18、A a_array[5] 调用5次构造函数
#include<iostream> #include<vector> using namespace std; class A { public: A() { cout << "类A的构造函数" << endl; } }; int main() { A a_array[5]; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
19、int a[][4]
int a[][4] 表明不知道会有多少行，但确定每行有4列
int a[][4]={1,2};
会开辟一行，一共四列，但只初始化了两个元素，因此后面的会是0
int a[][4]={1,2,3,4,5,6,7,8,9};
20、野指针、空指针、悬空指针
根据指针的整个过程来记忆
野指针：指针一开始生成，如果还未被初始化成任何值，就是野指针
int *p;
- 1
空指针：指针生成后，被初始化成nullprt，就是空指针
p=nullptr;
- 1
悬空指针：指针指向确定的内存位置后，该内存位置又被删除或释放了，就是悬空指针
指针指向某块内存位置
p=(int *)malloc(sizeof(int));
这块内存位置又被释放了
free(p)
此时的指针p是悬空指针
- 1
- 2
- 3
- 4
- 5
- 6
- 7
21、链表逆序
设计一个函数，传入链表头指针head，将链表逆序，但头指针仍是head
涉及到函数形参中采用指针传递或引用传递的区别
首先贴一下错误的例子：
void reverse(Node * head) { Node * newhead = nullptr; Node * first = nullptr; while (head) { if (newhead == nullptr) { newhead = head; head = head->next; newhead->next = first; first = newhead; } else { newhead = head; head = head->next; newhead->next = first; first = newhead; } } head = newhead; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
打印原链表，再打印逆序后的链表
Node * print_ptr = head; while (print_ptr) { cout << print_ptr->num <<" "; print_ptr = print_ptr->next; } cout << endl; reverse(head); print_ptr = head; while (print_ptr) { cout << print_ptr->num << " "; print_ptr = print_ptr->next; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
代码看上去很合理，但输出是有问题的
关键在于reverse函数的参数：
为方便理解，改了一下命名
void reverse(Node * temp)
- 1
调用
reverse(head);
- 1
- 2
但函数的形参是指针时，实际上会在函数内部新创建一个临时指针变量 temp ，这个变量接收由 head 传递来的指针内的数值，也就是说，这时候存在两个指针，一个新创建的临时指针 temp ，一个原来的指针 head ，这两个指针都指向同一个内存单元
原链表：
reverse 函数刚开始运行，实参刚传递到形参时：
之后的所有改动都是对 temp 这个指针进行，当函数运行到末尾最后一句：
temp = newhead;
- 1
此时链表内如图，注意每个结点的内存位置并没有改变，函数只改变了结点中 next 的值，即结点的 next 指针的朝向：
当函数结束后，局部变量 temp 和 newhead 均被释放：
此时从 head 开始打印链表，自然只能打印到一个 0
问题核心在于指针传递仍然是值传递，传递的是 head 指针 内保存的地址值，所有改变临时指针 temp 内的值的操作都不会影响到 head 指针 内的值，因此 head 指针仍从始至终指向 0 结点
解决方法：采用C++特有的引用传递
void reverse(Node * &temp)
- 1
调用
reverse(head);
- 1
- 2
这时候，temp 是 对指针 head 的一个别名，所有改变 temp 的值的操作，都会导致 head 的值的改变。
即改变 temp 的指向，也会导致 head 的指向的改变
22、为什么静态成员函数不能是虚函数
结合两个博客理解：
https://blog.csdn.net/flf1234567898/article/details/108396847
https://blog.csdn.net/lyztyycode/article/details/81326699
23、64位、32位机器
https://www.cnblogs.com/HOMEofLowell/p/12944900.html
64位意思是一次能处理64位数据，通常意味着寄存器是64位的
而指针由整数寄存器存储，所以指针的大小都是64位的
（1）64位机器中
short a[3]={1,2};
short *ptr=a;
sizeof(ptr)
- 1
- 2
- 3
此处由于p是指针，自然是64位的， s i z e o f ( p ) sizeof(p) sizeof(p) 即8个字节，所以结果是8
int main()
{
short a[3] = { 1,2 };
short *p = a;
cout<<sizeof(p);
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
（2）64位系统中
char *ptr="Hello";
printf("size=0x%08x,len=%d",sizeof(ptr),strlen(ptr));
- 1
- 2
%08意思是8个字符
x意思是16进制
%08x意思是输出8个字符的16进制数
指针是64位的，8个字节
所以输出是：00000008
strlen(ptr)输出字符串的大小，Hello，一共5个字符，所以输出是：5
int main()
{
char *ptr = (char *)"Hello";
printf("size=0x%08x,len=%d", sizeof(ptr), strlen(ptr));
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
（3）64位编译器
struct A
{
int a;
char b;
short c;
char d;
};
sizeof(struct A);
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
常见变量类型的字节数：
32位中：
char 1字节
short 2字节
int 4字节
long 4字节
long long 8字节
float 4字节
double 8字节
64位中：
char 1字节
short 2字节
int 4字节
long 4字节（Linux64中 8字节）
long long 8字节
float 4字节
double 8字节
因为64位系统一次能读取64位数据，为保证每个变量都能被完整读取，struct会有内存对齐机制：
内存对齐按如下规则：
1.结构体中的第一个成员直接放在结构体内存开始处
2. 其它成员变量要对齐到一个名叫<对齐数>的整数倍的地址处。
对齐数=min（编译器默认的一个对齐数（64位系统中是8），该成员变量大小）
例子中，char的大小是1字节，所以char的<对齐数>是1，地址4是1的整数倍，所以char可以接着int变量继续存储
后续short的大小是2，对齐数是min(2,8)=2，所以short需保存在地址是2的整数倍的内存处，因此地址5需要填充
3.结构体总大小为<最大对齐数>（结构体中，所有成员变量的<对齐数>中的最大的一个）的整数倍
例子中，按规则2，char接在short后面
所有变量都存完了，但此时结构体的<最大对齐数>是int变量的<对齐数>——4，所以结构体的大小应该是4的整数倍，不够的自行填充
4.如果存在了嵌套结构体的情况,嵌套的结构体当作一个变量，它的<对齐数>是自己的<最大对齐数>
如果再补一个struct
struct B
{
short g;
char l;
short o;
};
struct A
{
int a;
char b;
short c;
char d;
struct B k;
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
struct B 的最大对齐数是它其中的变量short的对齐数——2；
因此将struct B当作变量，它的<对齐数>就是2，需要接在2的整数倍处
struct B内自己的内存分布也应该遵循上述规则先行构建
sizeof(A);\\16
- 1
class 的内存对齐遵循同样的规则
当有继承关系时，排完基类的内存后，继续存储派生类内的变量，每个变量遵循同样的规则存储，需要注意的一点是，基类中已被填充的内存空间，派生类的变量即便符合规则也不能存储进去。即便基类中被填充的内存空间是在末尾。
class A
{
public:
int a;
char b;
};
class B :public A
{
public:
char c;
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
24、unordered_map 和 map ，unoreder_set 和 set 的区别
map的数据结构是红黑树。红黑树是一种近似于平衡的二叉查找树，里面的数据是有序的。在红黑树上做查找、插入、删除操作的时间复杂度为O(logN)。
unordered_map的数据结构是哈希表，哈希表的特点就是查找效率高，时间复杂度为常数级别O(1)， 但额外空间复杂度则要高出许多。
map的数据结构是红黑树。
unordered_set的数据结构是哈希表。
set的数据结构是红黑树。
这与map和unordered_map的区别类似。
map跟set的区别在于，map是字典结构，储存key-value对，通过key检索到value。而set就是数学概念中的集合，里面不能有重复元素。
C++定义：
unordered_map<int,int> map;
unordered_set<int> set;
- 1
- 2
25、链表内有环
判断链表内有环
有几个方法，写一下思路跟C++实现
先建立一个有环的链表：
//建立一个普通链表 Node * head = nullptr; Node * last = nullptr; for (int i = 0; i < 6; i++) { if (head == nullptr) { head = new Node; head->num = i; head->next = nullptr; last = head; } else { Node * temp = new Node; temp->num = i; temp->next = nullptr; last->next = temp; last = temp; } } //让链表末尾结点指向链表中某一结点，形成环 Node * p = head; Node * p2 = head; while (p2->num != 2) { p2 = p2->next; } while (p->next) { p = p->next; } p->next = p2;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
（1）暴力双重循环
这个没什么好说的，时间复杂度 O ( n 2 ) O(n^2) O(n2)，空间复杂度 O ( 1 ) O(1) O(1)，用这个估计offer也会遍历到被人那里去了（哭~~）
（2）记录法
主要思路都是在遍历链表的过程中，每当遍历到一个结点，记录这个结点已经被遍历过。
如果在遍历过程中遇到已经被遍历过的结点，就意味着链表内有环
记录的方法可以有很多
- 如果可以在结点内增加 “visit” 域，初始值为0，意思是这个结点从没被遍历过，每当访问过一个结点，就将该结点的 “visit”
值改为1。在遍历过程中首先检查一个结点的 “visit” ，如果为1，意味着链表内有环：
struct Node
{
int num;
Node * next;
int visit=0;
};
- 1
- 2
- 3
- 4
- 5
- 6
bool isRing(Node * head) { while (head) { //如果结点已被访问，意味着链表内有环 if (head->visit == 1)return true; //如果结点没被访问 else { //标记这一结点被访问过了 head->visit = 1; head = head->next; } } return false; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
-
通过数组（vector）记录被访问过的结点，但每次遍历链表时，又需要遍历一遍数组，检查这次遍历到的结点有没有被访问过，时间会成 O ( n 2 ) O(n^2) O(n2) 了，还额外用了空间复杂度 O ( n ) O(n) O(n)，得不偿失
-
用数组记录的时候时间复杂度变成 O ( n 2 ) O(n^2) O(n2) 的原因是数组是顺序存储结构，它的查询本身就需要 O ( n ) O(n) O(n)，所以可以改用 Hash表来存储已经被访问过的结点，Hash 表的查询的时间复杂度是 O ( 1 ) O(1) O(1)，C++中哈希结构是 unordered_map 和 unordered_set ，两者的区别在于 map是 key-value 的，而 set 就是一个集合
bool isRingHash(Node * head) { //建立哈希表 unordered_set<int> record; while (head) { //如果已在哈希表内(已被访问) if (record.count(head->num)) { //链表内有环 return true; } //如果不在哈希表内 else { //添加进哈希表内 record.insert(head->num); head = head->next; } } return false; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
时间复杂度 O ( n ) O(n) O(n)，同样需要 O ( n ) O(n) O(n)的空间复杂度
（3）快慢指针法
创建两个指针p1、p2，同时指向头结点。让快的指针每次向后移动2个结点，让慢的指针每次向后移动1个结点。如果链表中没有环，慢的指针将永远追不上快的指针。但是如果链表中有环，首先指针就会永远往后移动下去，不会停止，其次快的指针会先一步进入环内，并一直在环内循环，直到后续慢指针也进入环内，最终两个指针终会相遇。所以通过判断两个指针能否相遇，能判断链表能是否存在环。时间复杂度同样是 O ( n ) O(n) O(n)，但空间复杂度只有两个指针，不需要额外的内存空间。
bool isRingPtr(Node * head) { Node * fast = head; Node * slow = head; while (fast && slow) { //快指针一次走两步 fast = fast->next->next; //慢指针一次走一步 slow = slow->next; //如果还能相遇，证明有环 if (fast == slow)return true; } return false; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
寻找环的入口结点
https://blog.csdn.net/weixin_44347020/article/details/109061328
计算环的长度
https://blog.csdn.net/weixin_34378767/article/details/91669981
快慢指针在环内相遇，让慢指针在这个相遇结点开始，再跑一圈，重新回到相遇结点，所走过的结点数就是环的长度
26、构造对象数组
class test
{
public:
test(int a, int b)
{
x = a;
y = b;
}
private:
int x;
int y;
};
test t[2]={test(1,2),test(5,6)};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
27、strcpy
char * strcpy(char * dest, const char * src)
把从src地址开始且含有 ‘\0’ 结束符的字符串复制到以dest开始的地址空间
const char * a = "asdaf";
char b[10];
strcpy(b, a);
- 1
- 2
- 3
- 4
- 5
编译器会提示不安全：
不安全的原因：容易造成栈溢出
需要两个隐形要求：
1、dest 有足够的空间装下 src
2、要保证 src 和 dest 指向的空间没有重叠
strcpy_s，用法跟 strcpy 一样，都是用于字符串复制，但strcpy_s有三个参数，且返回值是整数：
返回值：0表示复制成功，非0表示复制不成功，不同的非0值表示不同的错误，具体内容可以查阅MSDN手册
第一个参数 char *：目标字符串指针
第二个参数 size_t ：要为目标字符串开拓的缓冲区大小，通常是源字符串串长+1（“\0”）
第三个参数 const char * ：源字符串指针
const char * str1 = "asdf";
char str2[10];
strcpy_s(str2, strlen(str1) + 1, str1);
- 1
- 2
- 3
- 4
- 5
编写一个代替strcpy的函数：
strcpy函数主要有一个问题就是有可能会有内存重叠
源字符串指针 src 和目标字符串指针 dest 在内存中可能有如下三种情况：
情况一和情况二，在字符串复制过程中，让 *dest=*src，然后 dest++，src++，指向下一个内存单元，都不会有问题
但在情况三中，如图，第一步就会使源字符串中的 a 覆盖掉 源字符串的 d，导致复制出现问题，因此第三种情况需要特殊处理：
情况三中需要从尾部开始复制，首先使 src 指向字符串末尾，使 dest 同样后移相同的距离
然后 *dest=*src，dest–，src–
代码实现：
int my_strcpy(char * dest, const char * src) { //如果源字符串指针或目标字符串指针为空，即不指向实际内存，返回0 if (dest == nullptr || src == nullptr)return 0; //如果目标字符串指针刚好指向源字符串首地址，就是不需要复制，返回1 if (dest == src)return 1; //在复制过程中指针需要移位，d，s用于不改变 源字符串和目标字符串的指针 char * d = dest; char *s = (char *)src; int len = strlen(src) + 1; //src>dest 情况二 //dest >= (src+len) 情况一 if ((src > dest) || dest >= (src + len)) { while (len) { *d = *s; d++; s++; len--; } } //情况三需要特殊处理 else { s += (len - 1); d += (len - 1); while (len) { *d = *s; d--; s--; } } return 2; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
情况三会出问题，我怀疑是内存空间没经过申请不能随意进行写入：
28、双向递增顺序链表插入一个结点
老规矩，先把这链表建出来：
struct Node
{
int data;
Node * next;
Node * pre;
};
- 1
- 2
- 3
- 4
- 5
- 6
Node * head = new Node; head->data = 0; head->next = nullptr; head->pre = nullptr; Node * last = head; for (int i = 3; i < 10; i++) { Node * temp = new Node; temp->data = i; //指针记得初始化 temp->next = nullptr; temp->pre = nullptr; //接在链表末尾 last->next = temp; temp->pre = last; last = temp; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
0 -> 3-> 4-> 5-> 6-> 7-> 8-> 9 -> nullptr
插入结点的函数：
Node * insert(Node * head, Node * a) { Node * p1 = head; //开头 //如果头结点就比a大 //a需要接在头结点前面 if (p1->data > a->data) { a->next = p1; p1->pre = a; a->pre = nullptr; head = a; } Node * last = nullptr; //找到第一个大于等于a的数 //把a结点接在它前面接 while (p1 && p1->data < a->data) { //保留最后一个结点的指针信息 if (p1->next == nullptr)last = p1; p1 = p1->next; } //如果p1不是nullptr，证明是要在链表中间插入 if (p1!=nullptr) { Node * pre = p1->pre; pre->next = a; a->pre = pre; a->next = p1; p1->pre = a; } //如果p1是nullptr,证明是要接在链表末尾 //此时last肯定已经指向链表内最后一个结点 else { last->next = a; a->pre = last; a->next = nullptr; } return head; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
测试一下：
//开头插入
Node temp = { -1,nullptr,nullptr };
head = insert(head, &temp);
//中间插入
Node temp = { 7,nullptr,nullptr };
head = insert(head, &temp);
//末尾插入
Node temp = { 12,nullptr,nullptr };
head = insert(head, &temp);
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
29、C++是不能通过函数返回局部变量的地址的
原因：C++的局部变量存放在栈区，函数执行完毕后，该函数在栈区申请的内存会自动销毁
第一次还能打印正确的数字是因为编译器做了保留
解决方法：将局部变量通过static定义成静态变量，就不会存在栈区，而是存在全局区，便不会随着函数的结束而被销毁
30、智能指针
为什么需要智能指针？
内存泄漏
内存泄漏（Memory Leak）是指程序中已动态分配的堆内存由于某种原因程序未释放或无法释放，造成系统内存的浪费，导致程序运行速度减慢甚至系统崩溃等严重后果。
指针在C++内存结构中是存在栈内存里的，而采用new malloc 等方式申请的内存空间是存在堆内存里的。
栈内存里的指针指向堆内存里的对象，栈内存在函数运行完成后会释放，而在此之前，如果忘记调用指针delete，将会造成内存泄漏（堆内存里申请的内存空间没有释放）。
而使用智能指针能避免此类情况发生，当函数结束，栈内存被释放，不再有指针指向堆内存里的对象时，对象会自动释放资源。
当程序结束时，ptr1和ptr2指针被销毁时，对象ptr1和ptr2会自动调用析构函数去释放所指向的资源，这是智能指针的特点。
【c++复习笔记】——智能指针详细解析(智能指针的使用,原理分析)
https://blog.csdn.net/sjp11/article/details/123899141
31、虚基类
https://zhuanlan.zhihu.com/p/104344453
32、CA a=100；
#include<iostream> using namespace std; class CA { public: int data; CA() { data = 2; } CA(int value) { data = value; } }; int main() { CA a = 100; cout << a.data << endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
可以成功创建对象，并且对象中的 data 成员被成功赋值成100
33、析构函数可以是虚函数
当基类的指针指向派生类的对象，如果删除该指针delete []p，就会调用该指针指向的派生类析构函数，而派生类的析构函数又自动调用基类的析构函数，这样整个派生类的对象完全被释放。
如果析构函数不被声明成虚函数，会造成派生类对象析构不完全。
所以析构函数声明为虚函数是十分必要的。
34、x*=y+8
因为 + 的优先级比 = 高，所以先执行 y+8，再执行 *=
因此相当于 x=x*(y+8)
35、int型静态变量如果没有初始化，会默认初始化成0
int main()
{
static int b[5] = { 1 };
for (int i = 0; i < 5; i++)
{
cout << b[i] << " ";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
5个元素的静态int型数组，只将第一个元素初始化成1，后面的元素由于没有初始化，所以系统默认初始化成0
36、while(k=0)
在条件判断语句中的赋值语句，会首先执行 k=0，完成k的赋值，然后判断 while(k)
int k = 10;
while (k = 0)
{
k = k - 1;
cout << "print" << endl;
}
- 1
- 2
- 3
- 4
- 5
- 6
所以以上语句不会执行
但是，while(k=1)会一直执行循环：
int k = 10;
while (k = 1)
{
k = k - 1;
cout << "print" << endl;
}
- 1
- 2
- 3
- 4
- 5
- 6
37、引用变量的地址
引用变量的地址是取不出来的，取出来的是引用变量所引用的那个变量的地址（因为引用就是给那个变量取一个别名）
int a = 10;
int &b = a;
cout << &a << endl;
cout << &b << endl;
- 1
- 2
- 3
- 4
- 5
38、逻辑运算符两侧的对象可以是任何数据类型的数据
39、内联函数 inline
可以加快运行速度，因为少了指令跳转
https://blog.csdn.net/qq_33757398/article/details/81390151
40、编程题
题目要求：以链表对学生成绩进行排序
输入 “学号，成绩”
输出 排序的结果
输入： “1，90<回车>” “2，80<回车>” “3，100<回车>” “OK”
输出：“2，80” “1，90” “3，100”
几个知识点
首先循环输入，判断有没有输入“OK”，如果有输入“OK”,结束循环，然后输出排序后的结果：
printf("请输入学生学号和成绩，输入OK表示录入完成："); string input; while (cin>>input) { if (input == "OK")break; else { 新结点插入链表 } } 输出排序后的链表 return 0;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
在链表方面，既然需要排序，那干脆就在插入时就维护一个按分数递增的链表：
链表结点：
struct Node
{
int num;
int score;
Node * next;
Node * pre;
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
链表头结点：
//链表头结点
Node *head = new Node;
head->next = nullptr;
head->pre = nullptr;
head->num = -1;
head->score = -1;
- 1
- 2
- 3
- 4
- 5
- 6
新结点插入链表：
//如果链表中还没有结点 if (head->next == nullptr) { head->next = temp; temp->pre = head; temp->next = nullptr; } //如果链表中已经有结点 else { Node * p1 = head->next; //在链表中找到第一个大于 temp 的结点，在它的前面把temp接进去 while (p1->next != nullptr && p1->score < temp->score) { p1 = p1->next; } //如果p1是最后一个结点 if (p1->next == nullptr) { //判断它是否大于 temp if (p1->score > temp->score) { //如果最后一个结点比temp大 //temp接在p1的前面 temp->pre = p1->pre; p1->pre->next = temp; temp->next = p1; p1->pre = temp; } else { //如果最后一个结点比temp小 //temp接在 p1 的后面 p1->next = temp; temp->pre = p1; } } else { //如果p1是中间结点 //temp接在p1的前面 temp->pre = p1->pre; p1->pre->next = temp; temp->next = p1; p1->pre = temp; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
在新结点数据输入方面，由于输入的是 “学号，分数”字符串，需要在字符串中找到“，”所在的位置，并将逗号前半部分拆开并转换成整型的数据——学号，逗号后半部分拆开并转换成整型的数据——分数：
//申请一块内存空间装新的结点
Node * temp = new Node;
//找到逗号所在的位置
int position = input.find(",");
//从0开始，position个字符
temp->num = stoi(input.substr(0, position));
//从position开始，size-1-1个字符
temp->score = stoi(input.substr(position + 1, input.size() - 1 - 1));
temp->next = nullptr;
temp->pre = nullptr;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
由于链表维护的就是递增链表，直接打印：
Node * print = head->next;
while (print)
{
cout << print->num << "," << print->score << endl;
print = print->next;
}
- 1
- 2
- 3
- 4
- 5
- 6
完整代码：
#include<iostream> #include<string> using namespace std; struct Node { int num; int score; Node * next; Node * pre; }; int main() { printf("请输入学生学号和成绩，输入OK表示录入完成："); string input; //链表头结点 Node *head = new Node; head->next = nullptr; head->pre = nullptr; head->num = -1; head->score = -1; while (cin>>input) { if (input == "OK")break; else { //申请一块内存空间装新的结点 Node * temp = new Node; //找到逗号所在的位置 int position = input.find(","); //从0开始，position个字符 temp->num = stoi(input.substr(0, position)); //从position开始，size-1-1个字符 temp->score = stoi(input.substr(position + 1, input.size() - 1 - 1)); temp->next = nullptr; temp->pre = nullptr; //如果链表中还没有结点 if (head->next == nullptr) { head->next = temp; temp->pre = head; temp->next = nullptr; } //如果链表中已经有结点 else { Node * p1 = head->next; //在链表中找到第一个大于 temp 的结点，在它的前面把temp接进去 while (p1->next != nullptr && p1->score < temp->score) { p1 = p1->next; } //如果p1是最后一个结点 if (p1->next == nullptr) { //判断它是否大于 temp if (p1->score > temp->score) { //如果最后一个结点比temp大 //temp接在p1的前面 temp->pre = p1->pre; p1->pre->next = temp; temp->next = p1; p1->pre = temp; } else { //如果最后一个结点比temp小 //temp接在 p1 的后面 p1->next = temp; temp->pre = p1; } } else { //如果p1是中间结点 //temp接在p1的前面 temp->pre = p1->pre; p1->pre->next = temp; temp->next = p1; p1->pre = temp; } } } } cout << "按分数排序后：" << endl; Node * print = head->next; while (print) { cout << print->num << "," << print->score << endl; print = print->next; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
