语法课第七节 结构体 类 指针 引用（知识点+题目）
类可以将变量、数组和函数完美地打包在一起。——闫学灿
1. 类与结构体
类的定义：
一定要注意：中括号最后必须有分号
class Person
{
private:
int age, height;
double money;
string books[100];
public:
string name;
void say()
{
cout << "I'm " << name << endl;
}
int get_age()
{
return age;
}
void add_money(double x)
{
money += x;
}
};
类中的变量和函数被统一称为类的成员变量。
private后面的内容是私有成员变量，在类的外部不能访问；public后面的内容是公有成员变量，在类的外部可以访问。
private和public里面都可以定义函数，而且private 和public都可以定义多个
类的使用：
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];
关于结构体定义构造函数：
构造的函数名称和结构体名称是完全一样的，构造函数是没有类型的；构造函数里面是可以写参数的，可以在函数内部将变量进行赋值；
上面这个是有参数的函数，也可以是没有参数的：例如Person p;
这里要注意的就是：
函数定义的时候有几个参数，后面调用的时候就是几个参数，形式要完全一样，不然就会报错。
2. 指针和引用
指针指向存放变量的值的地址。因此我们可以通过指针来修改变量的值。
#include <iostream>
using namespace std;
int main()
{
int a = 10;
int *p = &a;
//int*是代表指针类型，p是名称；int *p=&a；是这个指针等于a的地址；
cout<<*p<<endl;//这个输出的就是p的地址里面对应的具体的数值；输出结果是10；
*p += 5;
cout << a << endl;
return 0;
}
上图代码中的*p=12；是修改指针的值；输出结果：10 12 12
通过修改指针的值能将a的值改变；
关于指针的运算：
p+1就是说他跟类型有关，char类型是一个字节，int是四个字节，long long是八个字节；所以在运算的时候，是在地址上加具体的字节；
输出cout<<p<<endl;//这个输出是输出p（也就是a的）的地址；
输出cout<<p+1<<endl;//这个输出是输出p+1的地址；但是这个p+1的话实际的运算是要看他是哪种类型，
char类型加一就是加一，int 类型加一就相当于+4；
cout<<*p<<endl;//是输出的具体的值；
cout<<*(a+2)<<endl;//是默认从a[0]开始，+2；所以代表输出a[2]也就是3；
上述写法与scanf("%d",&a[1]);等价
扩展：
不允许两个类型不同的指针进行运算
数组名是一种特殊的指针。指针可以做运算：
#include <iostream>
using namespace std;
int main()
{
int a[5] = {1, 2, 3, 4, 5};//数组初始化；
for (int i = 0; i < 5; i ++ )
cout << *(a + i) << endl;
return 0;
}
引用和指针类似，相当于给变量起了个别名。
#include <iostream>
using namespace std;
int main()
{
int a = 10;
int &p = a;//引用；p和a存的是一个地址
p += 5;
cout << a << endl;
return 0;
}
3. 链表
#include <iostream>
using namespace std;
struct Node
{
int val;
Node* next;
} *head;
int main()
{
for (int i = 1; i <= 5; i ++ )
{
Node* p = new Node();//有这个new返回值是Node的地址；如果不加new,返回值就是Node的具体的数值；
p->val = i;//因为p是指针类型，所以是这样调用函数；
//扩展：如果是Node p= new Node();此时p不是指针类型，那么调用函数的时候就是： p.val=p;
p->next = head;
head = p;
}
for (Node* p = head; p; p = p->next)
cout << p->val << ' ';
cout << endl;
return 0;
}
Node* p = new Node();//有这个new返回值是Node的地址；如果不加new,返回值就是Node的具体的数值；
p->val = i;//因为p是指针类型，所以是这样调用函数；
//扩展：如果是Node p= new Node();此时p不是指针类型，那么调用函数的时候就是： p.val=p;
auto代表的是计算机可以自己去猜测他是什么类型
关于遍历链表：
关于链表添加节点：
关于链表的删除：
本来是：
删除后：（直接跳过去）
相关代码：
关机代码：
头文件里加上：
只要在下面主函数内出现：
就会自动关机；
第一行printf等价于输出下面那个
21. 斐波那契数列
输入一个整数 n ，求斐波那契数列的第 n 项。
假定从 0 开始，第 0 项为 0。
数据范围
0≤n≤39
样例
输入整数 n=5
返回 5
16. 替换空格
请实现一个函数，把字符串中的每个空格替换成"%20"。
数据范围
0≤ 输入字符串的长度 ≤1000。
注意输出字符串的长度可能大于 1000。
样例
输入：“We are happy.”
输出：“We%20are%20happy.”
84. 求1+2+…+n
求 1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句 (A?B:C)。
数据范围
1≤n≤50000。
样例
输入：10
输出：55
28. 在O(1)时间删除链表结点
给定单向链表的一个节点指针，定义一个函数在O(1)时间删除该结点。
假设链表一定存在，并且该节点一定不是尾节点。
数据范围
链表长度 [1,500]。
样例
输入：链表 1->4->6->8
删掉节点：第2个节点即6（头节点为第0个节点）
输出：新链表 1->4->8
36. 合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。
数据范围
链表长度 [0,500]。
样例
输入：1->3->5 , 2->4->5
输出：1->2->3->4->5->5
78. 左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。
请定义一个函数实现字符串左旋转操作的功能。
比如输入字符串"abcdefg"和数字 2，该函数将返回左旋转 2 位得到的结果"cdefgab"。
注意：
数据保证 n 小于等于输入字符串的长度。
数据范围
输入字符串长度 [0,1000]。
样例
输入：“abcdefg” , n=2
输出：“cdefgab”
87. 把字符串转换成整数
请你写一个函数 StrToInt，实现把字符串转换成整数这个功能。
当然，不能使用 atoi 或者其他类似的库函数。
数据范围
输入字符串长度 [0,20]。
样例
输入：“123”
输出：123
注意:
你的函数应满足下列条件：
1忽略所有行首空格，找到第一个非空格字符，可以是 ‘+/−’ 表示是正数或者负数，紧随其后找到最长的一串连续数字，将其解析成一个整数；
2整数后可能有任意非数字字符，请将其忽略；
3如果整数长度为 0，则返回 0；
4如果整数大于 INT_MAX(231−1)，请返回 INT_MAX；如果整数小于INT_MIN(−231) ，请返回 INT_MIN；
35. 反转链表
定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
思考题：
请同时实现迭代版本和递归版本。
数据范围
链表长度 [0,30]。
样例
输入:1->2->3->4->5->NULL
输出:5->4->3->2->1->NULL
66. 两个链表的第一个公共结点
输入两个链表，找出它们的第一个公共结点。
当不存在公共节点时，返回空节点。
数据范围
链表长度 [1,2000]。
保证两个链表不完全相同，即两链表的头结点不相同。
样例
给出两个链表如下所示：
A： a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
输出第一个公共节点c1
29. 删除链表中重复的节点
在一个排序的链表中，存在重复的节点，请删除该链表中重复的节点，重复的节点不保留。
数据范围
链表中节点 val 值取值范围 [0,100]。
链表长度 [0,100]。
样例1
输入：1->2->3->3->4->4->5
输出：1->2->5
样例2
输入：1->1->1->2->3
输出：2->3