片头
嗨~小伙伴们，大家好！今天我们来学习C++蓝桥杯基础篇（十一），学习类，结构体，指针相关知识，准备好了吗？咱们开始咯~
一、类与结构体
类的定义：在C++中，类的定义是通过关键字"class"来完成的。一个类定义一舿数据的结构和方法。
class Person {private: //私有的成员变量int age, height;double money;string books[100];public: //公有的成员变量,成员函数string name;void say() {cout << "I'm " << name << endl;}void set_age(int a) {age = a;}int get_age() {return age;}void set_height(int h) {height = h;}int get_height() {return height;}void add_money(double x) {money += x;}
};上面的例子定义了一个名为Person的类，包含了5个数据成员name，age，height，money，books，以及3个成员函数say()用来打招呼，set_age()用来设置年龄，get_age()用来获取年龄，add_money()用来增加零钱的数量。可以通过实例化这个类来创建具体的对象并访问其成员和方法。
类中的变量和函数被统一称为类的成员变量。
private后面的内容是私有成员变量，在类的外部不能访问；public后面的内容是公有成员变量，在类的外部可以访问。
类的使用：
正确示例代码如下：
int main() {Person c;c.name = "小明"; //正确!访问公有变量//c.age = 18; //错误!访问私有变量c.set_age(18); //正确!set_age()是公有成员变量c.set_height(185); //正确!set_height()是公有成员变量c.add_money(100); //设置零钱为100块c.say();cout << c.get_age() << endl;cout << c.get_height() << endl;return 0;
}
结构体和类的作用是一样的。不同点在于，类默认是private，结构体默认是public。
二、构造函数
结构体构造函数是一种特殊的函数，用于创建结构体并对其进行初始化。在C++中，结构体构造函数与类构造函数类似，用于初始化结构体的成员变量，可以通过传入参数来指定初始值。结构体构造函数的名称与结构体本身相同，不需要指定返回类型。
struct Person1 {int age, height;double money;Person1 () {};Person1(int _age, int _height, double _money) {age = _age;height = _height;money = _money;}
};int main() {Person1 p(18,185,100); //调用有参构造cout << p.age << " " << p.height << " " << p.money << endl;Person1 a; //调用无参构造cout << a.age << " " << a.height << " " << a.money << endl;return 0;
}
此外，我们还可以使用初始化列表来初始化成员变量
struct Person2 {int age, height;double money;Person2() {}; //无参构造Person2(int _age, int _height) :age(_age), height(_height) {}; //使用初始化列表构造Person2(int _age, int _height, double _money) :age(_age),height(_height),money(_money) {}
};int main() {Person2 p(18, 185, 100);cout << p.age << " " << p.height << " " << p.money << endl;Person2 a;cout << a.age << " " << a.height << " " << a.money << endl;return 0;
}三、指针和引用
指针指向存放变量的值的地址。因此，我们可以通过指针来修改变量的值。
int main() {int a = 10;int* p = &a;*p += 5;cout << *p << endl; //15cout << a << endl; //15return 0;
}上面代码中，指针p存放的是a的地址，修改*p的值，a的值也会被修改。
数组名是一种特殊的指针。指针可以做运算。
int main() {char c;int a[5] = { 1,2,3,4,5 };printf("%p\n", &c);printf("%p\n", &a);return 0;
}
我们将数组a中每个元素的地址都打印一遍：
int main() {char c;int a[5] = { 1,2,3,4,5 };printf("字符c的地址为: %p\n", &c);printf("数组名a的地址为: %p\n", &a);for (int i = 0; i < 5; i++) {printf("a[%d] = %p\n",i, &a[i]);}cout << endl;return 0;
}
由此，我们发现，数组名和首元素的地址相同。数组名 = 首元素地址。每个地址之间相差4个字节，因为是int类型的数组，每个int类型的整数占4个字节。
我们还可以通过指针+1来访问下一个元素：
int main() {char c;int a[5] = { 1,2,3,4,5 };int* p = a; //p代表首元素a[0]的地址cout << p << endl;cout << p + 1 << endl;return 0;
}
因此，如果我们想直接访问a[2]的话，也可以写成 *(p+2)
int main() {int a[5] = { 1,2,3,4,5 };int* p = a; //p代表首元素a[0]的地址cout << p << endl; //a[0]的地址cout << *p << endl; //a[0]的值cout << p + 1 << endl; //a[1]的地址cout << *(p + 1) << endl; //a[1]的值cout << p + 2 << endl; //a[2]的地址cout << *(p + 2) << endl; //a[2]的值return 0;
}
因此，遍历整个数组的代码如下：
int main() {int a[5] = { 1,2,3,4,5 };int* p = a;//之前的for (int i = 0; i < 5; i++) {cout << a[i] << " ";}cout << endl;//现在的for (int i = 0; i < 5; i++) {cout << *(p + i) << " ";}return 0;
}
同理，输出可以用指针实现，那么输入也可以：
int main() {char c;int a[5] = { 1,2,3,4,5 };scanf("%d", a + 1); //输入a[1]的值//相当于 scanf("%d",&a[1]);//因为数组名 = 首元素的地址//数组名+1 = 下一个元素的地址for (auto e : a) {cout << e << " ";}cout << endl;return 0;
}
那么，难道指针只能进行加法运算码？不是的~ 可以进行减法运算
int main() {int a[5] = { 1,2,3,4,5 };int* p = &a[0];int* q = &a[2];cout << q - p << endl; //2return 0;
}
引用和指针类似，相当于给变量起个别名。
int main() {int a = 10;int& p = a; //p是a的别名p += 5;cout << p << endl; //p的值被修改为15cout << a << endl; //a的值被修改为15return 0;
}
四、链表
单链表在C语言中可以定义为一个结构体，其中包含一个指向下一个节点的指针。
// 定义单链表节点
struct Node {int data; // 节点数据struct Node *next; // 指向下一个节点的指针
};// 定义单链表
struct LinkedList {struct Node *head; // 头节点指针
};
在这个定义中，struct Node 代表单链表的节点，包含节点的数据和指向下一节点的指针。struct LinkedList 代表整个单链表，其中包含一个头节点指针 head，指向链表的第一个节点。
struct Node {int val; //节点里面的值Node* next; //指向下一节点的next指针Node(int _val):val(_val),next(NULL){}
};int main() {Node* p = new Node(1); //创建p节点Node* q = new Node(2); //创建q节点Node* o = new Node(3); //创建o节点p->next = q; //p节点的next指针指向q节点q->next = o; //q节点的next指针指向o节点Node* pcur = p; //pcur节点从第1个节点p开始//链表的遍历方式for (Node* i = pcur; i != NULL; i = i->next) {cout << i->val << " -->" << " ";}cout << "NULL" << endl;return 0;
}
如何在链表中添加节点呢？并且添加在第一个位置，也就是头插
Node* p = new Node(1); //创建p节点Node* q = new Node(2); //创建q节点Node* o = new Node(3); //创建o节点p->next = q; //p节点的next指针指向q节点q->next = o; //q节点的next指针指向o节点Node* head = p; //pcur节点从第1个节点p开始//添加节点Node* u = new Node(4);u->next = head;head = u;
那么如何删除节点呢？删除链表中第2个节点
Node* p = new Node(1); //创建p节点Node* q = new Node(2); //创建q节点Node* o = new Node(3); //创建o节点p->next = q; //p节点的next指针指向q节点q->next = o; //q节点的next指针指向o节点Node* head = p; //pcur节点从第1个节点p开始//删除节点head->next = head->next->next;
五、习题
第1题 斐波那契数列
错误代码如下：
class Solution {
public:int Fibonacci(int n) {if (n <= 2) return 1; //错误,这是第0项为1return Fibonacci(n - 1) + Fibonacci(n - 2);}
};为啥错了呢？因为，题目告诉我们从0开始，第0项为0
因此，正确代码如下：
//f(0)=0,f(1)=1
//f(2)=f(0)+f(1)=1
//f(3)=f(1)+f(2)=2class Solution {
public:int Fibonacci(int n) {if (n <= 1) return n; //当n==0,返回0 //当n==1,返回1return Fibonacci(n - 1) + Fibonacci(n - 2); //从n==2开始,都满足这个规律}
};第2题 替换空格
代码如下：
class Solution {
public:string replaceSpaces(string& str) {string res; //定义res字符串,用来保存最后结果for (auto c : str) {if (c == ' ') res += "%20";else res += c;}return res;}
};第3题 求1+2+3+...+n
题目要求我们不能使用乘除法、for、while、if、else、switch、case以及条件判断语句(A?B:C) ，那么我们可以使用短路与&&和递归来解决此类问题。
sum(n) = n+sum(n-1)，但是要注意终止条件，由于求的是 1+2+3+....+n 的和，所以需要在n=0的时候跳出递归。但是题目要求不能使用if，while等分支判断，可以考虑利用&&短路运算来终止判断。
代码如下：
方法一：
class Solution {
public:int getSum(int n) {int res = n;n > 0 && (res += getSum(n - 1) + n); //短路与&&//只要左边的表达式错误,那么右边也不会再执行//利用短路与&&终止递归return 0;}
};方法二：我们还可以采用函数递归来解决。在外部定义递归函数，内部调用即可。
//调用函数
class Solution {
public:int getSum(int n) {return f(n);}int f(int n) {if (n == 0) return 0;return f(n - 1) + n;}
};第4题 在O(1)时间删除链表结点
代码如下:
struct ListNode {int val;ListNode* next;ListNode(int x):val(x),next(NULL){}
};class Solution {
public:void deleteNode(ListNode* node) {node->val = node->next->val; //伪装成下一个点node->next = node->next->next; //将下一个点删掉}
};还有一种更简便的方法：
struct ListNode {int val;ListNode* next;ListNode(int x):val(x),next(NULL){}
};class Solution {
public:void deleteNode(ListNode* node) {*(node) = *(node->next);}
};第5题 合并两个排序的链表
这道题，我们先来一种易理解的方法：
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if (list1 == NULL)//如果list1为空，则返回list2return list2;if (list2 == NULL)//如果list2为空，则返回list1return list1;ListNode* l1 = list1; //定义l1变量,指向list1ListNode* l2 = list2; //定义l2变量,指向list2ListNode* newHead = NULL; //定义新链表的头节点ListNode* newTail = NULL; //定义新链表的尾节点while (l1 && l2) {if (l1->val < l2->val) {//l1比l2小if (newHead == NULL) {//如果链表为空newHead = newTail = l1;}else {//链表不为空newTail->next = l1;newTail = l1;}l1 = l1->next; //l1指向下一个节点}else {//l2比l1小if (newHead == NULL) {//如果链表为空newHead = newTail = NULL;}else {//链表不为空newTail->next = l2;newTail = l2;}l2 = l2->next; //l2指向下一个节点}}if (l1) {//l1没有遍历完链表newTail->next = l1;}if (l2) {//l2没有遍历完链表newTail->next = l2;}return newHead;//返回头节点
}好啦，这道题我们基本上做完了。但是，看看这代码，有重复冗余的部分，我们如何优化代码呢？
有啦！我们可以定义一个哨兵节点，这个节点可以不存放数据，让它指向新链表的头节点
ListNode* node = (ListNode*)malloc(sizeof(ListNode)); //创建一个哨兵节点ListNode* newHead = node; //头节点指向哨兵节点ListNode* newTail = node; //尾节点指向哨兵节点中间的循环也要进行更改，不用判断链表是否为空了
while (l1 && l2) {if (l1->val < l2->val) {//l1比l2小newTail->next = l1;newTail = l1;l1 = l1->next; //l1指向下一个节点}else {//l2比l1小newTail->next = l2;newTail = l2;l2 = l2->next; //l2指向下一个节点}}malloc了空间，但这块空间实际上用不了，最后我们需要将哨兵节点释放
//malloc了空间，但这块空间实际上用不了，最后我们需要将哨兵节点释放ListNode* ret = newHead->next;free(newHead);return ret; //返回头节点的下一个节点欧克，优化过的代码如下：
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if (list1 == NULL)//如果list1为空，则返回list2return list2;if (list2 == NULL)//如果list2为空，则返回list1return list1;ListNode* l1 = list1; //定义l1变量,指向list1ListNode* l2 = list2; //定义l2变量,指向list2ListNode* node = (ListNode*)malloc(sizeof(ListNode)); //创建一个哨兵节点ListNode* newHead = node; //头节点指向哨兵节点ListNode* newTail = node; //尾节点指向哨兵节点while (l1 && l2) {if (l1->val < l2->val) {//l1比l2小newTail->next = l1;newTail = l1;l1 = l1->next; //l1指向下一个节点}else {//l2比l1小newTail->next = l2;newTail = l2;l2 = l2->next; //l2指向下一个节点}}if (l1) {//l1没有遍历完链表newTail->next = l1;}if (l2) {//l2没有遍历完链表newTail->next = l2;}//malloc了空间，但这块空间实际上用不了，最后我们需要将哨兵节点释放ListNode* ret = newHead->next;free(newHead);return ret; //返回头节点的下一个节点
}片尾
今天我们学习了相关类、结构体、指针相关知识，希望看完这篇文章能对友友们有所帮助！！！
求点赞收藏加关注！！！
谢谢大家！！！
