C++蓝桥杯基础篇（十一）

片头

嗨~小伙伴们，大家好！今天我们来学习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;		 //返回头节点的下一个节点
}