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;		 //返回頭節點的下一個節點
}