C/C++基礎語法

參考資料：

• AcWing
• https://www.w3schools.com/cpp/
• https://cui-jiacai.gitbook.io/c+±stl-tutorial/
• https://www.youtube.com/watch?v=RRVYpIET_RU
• https://takeuforward.org/c/c-stl-tutorial-most-frequent-used-stl-containers/

---

頭文件

#include <cmath>

經典問題

鏈表

#include <iostream>using namespace std;struct Node
{int val;Node *next;Node(int _val) : val(_val), next(NULL) {} // 空指針
};int main()
{Node node = Node(1); // 定義了一個node類型的變量Node *p = &node;//定義完之后用指針指向
}

C++中可以直接生成一個結構體，然后把這個結構體放到指針p中

 Node *p = new Node(1); // 我定義了一個Node類型的變量，他的返回值是這個變量的地址

#include <iostream>using namespace std;struct Node
{int val;Node *next;Node(int _val) : val(_val), next(NULL) {} // 空指針
};int main()
{Node *p = new Node(1); // 我定義了一個Node類型的變量，他的返回值是這個變量的地址auto q = new Node(2);p->next=q;
}

頭節點：第一個節點的地址，而不是他的值

鏈表基礎操作

遍歷，頭插，刪除

運行結果：

秒數轉換

輸入一個整數，表示時間，單位是秒。輸出一個字符串，用”時:分:秒”的形式表示這個時間。

#include <iostream>
#include <cstdio>using namespace std;int main()
{int t;cin >> t;int hours = t / 3600;int minutes = t % 3600 / 60;int seconds = t % 60;printf("%d:%d:%d\n", hours, minutes, seconds);return 0;
}

• int hours = t / 3600; 計算總秒數 t 包含多少完整的小時。因為1小時 = 3600秒，所以使用整數除法 t / 3600 可以得到完整小時數。整數除法的結果是去掉小數部分，僅保留整數部分。
• int minutes = t % 3600 / 60; 首先，t % 3600 計算出除去完整小時后剩余的秒數。然后，將這個剩余的秒數除以60（因為1分鐘 = 60秒）得到完整分鐘數。這里也使用了整數除法，因此結果是剩余秒數中包含的完整分鐘數。
• int seconds = t % 60;使用取模運算 t % 60 計算出除去完整分鐘后剩余的秒數。因為1分鐘是60秒，所以這個操作會得到小于60的秒數，即最后剩余的秒數部分。

閏年

判斷閏年。閏年有兩種情況：
(1) 能被100整除時，必須能被400整除；
(2) 不能被100整除時，被4整除即可。

1. 輸入一個年份，如果是閏年輸出yes，否則輸出no。

#include <iostream>
#include <cstdio>using namespace std;int main()
{int year;cin >> year;if (year % 100 == 0){if (year % 400 == 0) cout << "yes" << endl;else cout << "no" << endl;}else{if (year % 4 == 0) cout << "yes" << endl;else cout << "no" << endl;}return 0;
}

2. 用一條if語句，判斷閏年。

#include <iostream>
#include <cstdio>using namespace std;int main()
{int year;cin >> year;if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0)cout << "yes" << endl;elsecout << "no" << endl;return 0;
}

斐波那契數列

求斐波那契數列的第n項。f(1) = 1, f(2) = 1, f(3) = 2, f(n) = f(n-1) + f(n-2)。

#include <iostream>using namespace std;int main()
{int n;cin >> n;int a = 1, b = 1, i = 1;while (i < n){int c = a + b;a = b;b = c;i ++ ;}cout << a << endl;return 0;
}

打印n階菱形

輸入一個n，打印n階菱形。n是奇數。

#include <iostream>using namespace std;int main()
{int n;cin >> n;int cx = n / 2, cy = n / 2;for (int i = 0; i < n; i ++ ){for (int j = 0; j < n; j ++ )if (abs(i - cx) + abs(j - cy) <= n / 2)cout << '*';else cout << ' ';cout << endl;}return 0;
}

曼哈頓距離

理解 abs(i - cx) + abs(j - cy) <= n / 2 這個條件的關鍵在于理解曼哈頓距離（Manhattan Distance）的概念，以及如何通過這個距離來定義一個菱形（或者說是正方形對角線方向的正方形）圖案。

曼哈頓距離是在格點坐標系中，兩點在標準的直角坐標系中的絕對軸距總和（只能橫行走和縱向走，走到中心點要幾步）。對于任意兩點 (x1, y1) 和 (x2, y2)，它們的曼哈頓距離是 |x1 - x2| + |y1 - y2|。

在這個程序中，(i, j) 表示當前遍歷到的網格點的坐標，(cx, cy) 是圖案中心點的坐標。abs(i - cx) + abs(j - cy) 計算的就是當前點 (i, j) 到中心點 (cx, cy) 的曼哈頓距離。

菱形圖案的定義

這個條件 abs(i - cx) + abs(j - cy) <= n / 2 用于判斷當前點是否在菱形圖案內部（包括邊界）。這里的 n / 2 實際上定義了菱形的“半徑”，即從中心點到邊界的最大曼哈頓距離。

• 當 abs(i - cx) + abs(j - cy) 的值小于或等于 n / 2 時，這意味著當前點 (i, j) 距離中心點的曼哈頓距離在菱形的半徑范圍內，因此，它位于菱形內部或邊界上，程序應該在這個位置打印一個星號 *。
• 當這個距離大于 n / 2 時，當前點 (i, j) 在菱形外部，程序在這個位置打印一個空格 。
  -

大數計算

計算 2 的 N 次方。N≤10000

#include <iostream>
#include <algorithm>using namespace std;int main()
{int a[10000], size = 1, n;a[0] = 1;cin >> n;while (n -- ){int t = 0;for (int i = 0; i < size; i ++ ){t += a[i] * 2;a[i] = t % 10;t /= 10;}if (t) a[size ++ ] = t;}for (int i = size - 1; i >= 0; i -- ) cout << a[i];cout << endl;return 0;
}

這段代碼是一個計算2的N次方的程序，特別適用于處理大數運算，即當N很大時，直接使用常規數據類型（如int、long）無法存儲結果的情況。這里N可以達到10000。程序通過模擬手工乘法的方式來計算結果，將每一位數字存儲在一個數組a中，數組的每個元素代表結果數的一位，a[0]是結果的最低位，a[size-1]是結果的最高位。

下面是代碼的詳細解釋：

1. 初始化：

   • int a[10000]：定義一個數組a，用于存儲計算過程中的每位數字。
   • size = 1：初始化結果數字的大小為1，因為2的0次方等于1，所以起始時數組只有一位數字1。
   • a[0] = 1：將結果的最低位初始化為1。

2. 讀取輸入：

   • cin >> n：從標準輸入讀取N的值。

3. 計算2的N次方：

   • while (n -- )：循環N次，每次循環相當于將當前結果乘以2。
   • 在每次循環中，使用變量t來存儲進位，初始時進位為0。
   • for (int i = 0; i < size; i ++ )：遍歷數組的每一位，模擬乘法運算。
   • t += a[i] * 2：當前位乘以2加上前一位的進位（如果有）。
   • a[i] = t % 10：更新當前位的值為新計算結果的個位數。
   • t /= 10：計算新的進位值。
   • 如果最后一位運算完后還有進位（t不為0），則將這個進位作為新的最高位添加到數組的末尾，并增加size。

4. 輸出結果：

   • 由于數組中存儲的是倒序的結果（即最低位在數組的開始位置），因此輸出時需要從size - 1開始倒序遍歷數組。
   • for (int i = size - 1; i >= 0; i -- ) cout << a[i];：倒序輸出數組的每一位，即輸出計算得到的2的N次方的結果。
   • cout << endl;：在結果后輸出換行符。

輸入輸出

格式化輸入輸出

#include <iostream>
#include <cstdio>using namespace std;int main()
{float b = 3.12345678;double c = 3.12345678;printf("%.4f\n", b);printf("%.3lf\n", c);printf("%5d\n", a);printf("%8.4f\n", b);printf("%7.3lf\n", c);printf("%-5d!\n", a);printf("%-8.4f!\n", b); // 如果整個數字（包括小數點和小數部分）不足8個字符，則在右側用空格填充，實現左對齊。printf("%-7.3lf!\n", c);printf("%05d\n", a);printf("%08.4f\n", b);printf("%07.3lf\n", c);return 0;
}

• float, double等輸出保留若干位小數時用：%.4f, %.3lf
• %8.3f, 表示這個浮點數的最小寬度為8，保留3位小數，當寬度不足時在前面補空格。
• %-8.3f，表示最小寬度為8，保留3位小數，當寬度不足時在后面補上空格
• %08.3f, 表示最小寬度為8，保留3位小數，當寬度不足時在前面補上0

getline()函數解決cin只讀入一個單詞的問題

cin 將空格（空格、制表符等）視為終止字符，這意味著它只能存儲單個單詞（即使您鍵入許多單詞）

在處理字符串時，我們經常使用 getline() 函數來讀取一行文本。它以 cin 作為第一個參數，字符串變量作為第二個參數：

string fullName;
cout << "Type your full name: ";
getline (cin, fullName);
cout << "Your name is: " << fullName;

或

    char s[100];cin.getline(s, 100); // 100是這一行最多讀多少個字符cout << s << endl;return 0;

fgets讀入整行

如果題目沒有超時，用getline比較好；如果輸入量比較大用fgets比較好

    char s[100];fgets(s, 100, stdin);//100是最多讀入多少個字符cout << s << endl;

輸出字符數組（兩種方式puts和printf）

    char s[100];cin.getline(s, 100); // 100是這一行最多讀多少個字符puts(s);printf("%s\n",s);//這兩種輸出方式等價return 0;

運算符

賦值運算符

這些賦值運算符是C++（以及C和其他語言）中的復合賦值運算符，它們將算術或位運算和賦值操作結合在一起。每個運算符的作用如下：

1. &= (按位與賦值運算符)

• 語法: x &= 3
• 等效于: x = x & 3
• 作用: 將 x 與 3 進行按位與操作，然后將結果賦值給 x。按位與操作對應位都為1時結果為1，否則為0。

2. |= (按位或賦值運算符)

• 語法: x |= 3
• 等效于: x = x | 3
• 作用: 將 x 與 3 進行按位或操作，然后將結果賦值給 x。按位或操作對應位有一個為1時結果為1，都為0時結果為0。

3. ^= (按位異或賦值運算符)

• 語法: x ^= 3
• 等效于: x = x ^ 3
• 作用: 將 x 與 3 進行按位異或操作，然后將結果賦值給 x。按位異或操作對應位不同為1，相同為0。

4. >>= (右移賦值運算符)

• 語法: x >>= 3
• 等效于: x = x >> 3
• 作用: 將 x 的二進制表示向右移動 3 位，然后將結果賦值給 x。右移操作會將高位丟棄，對于無符號數，低位補0；對于有符號數，低位補充依賴于具體實現（通常是補符號位，即算術右移）。

5. <<= (左移賦值運算符)

• 語法: x <<= 3
• 等效于: x = x << 3
• 作用: 將 x 的二進制表示向左移動 3 位，然后將結果賦值給 x。左移操作會在低位補0，高位丟棄，相當于將 x 乘以 2 的移動位數次方（這里是 2^3 或 8）。

二進制位移操作解釋

Switch

int day = 4;
switch (day) {case 1:cout << "Monday";break;case 2:cout << "Tuesday";break;case 3:cout << "Wednesday";break;case 4:cout << "Thursday";break;case 5:cout << "Friday";break;case 6:cout << "Saturday";break;case 7:cout << "Sunday";break;
}
// Outputs "Thursday" (day 4)

循環

處理未知數量輸入的幾種常見方法

1. while(cin >> x)
   在C++中，cin >> x 嘗試從標準輸入（通常是鍵盤輸入或重定向的文件輸入）讀取一個值到變量 x 中。如果讀取成功，表達式的值為 true；如果遇到輸入結束（如文件結束或遇到不匹配類型的輸入），表達式的值為 false。因此，while(cin >> x) 循環會持續讀取輸入直到遇到輸入結束。

2. while(scanf("%d", &x) != -1) 和 while(~scanf("%d", &x))
   在C語言中，scanf("%d", &x) 嘗試從標準輸入讀取一個整數到變量 x 中。scanf 函數返回成功讀取的項目數量。如果讀取成功，返回 1；如果遇到輸入結束（EOF），返回 -1。

• while(scanf("%d", &x) != -1) 循環會持續讀取輸入，直到 scanf 返回 -1，即遇到輸入結束。
• while(~scanf("%d", &x)) 利用了位運算符 ~（按位取反）。在大多數系統上，EOF（即 -1）按位取反后的結果是 0，而 0 是邏輯假。因此，這個循環同樣會持續讀取輸入，直到遇到輸入結束。這是一種更為簡潔的寫法。

3. while(cin >> x && x) 和 while(cin >> x, x)
   這兩種形式都用于處理當讀入的最后一個值為 0 且這個 0 不需要處理的情況。

• while(cin >> x && x) 循環會持續讀取并處理非零的輸入。如果 x 為 0 或遇到輸入結束，循環停止。
• while(cin >> x, x) 使用了逗號運算符，該運算符執行其兩邊的表達式，并返回右側表達式的結果。這里先嘗試從輸入讀取一個值到 x，然后通過逗號運算符返回 x 的值作為 while 循環的條件。這個用法較為少見，且可能引起混淆，其效果與 while(cin >> x && x) 相同。

以上這些方法提供了在未知數量輸入的情況下從標準輸入讀取數據的有效手段，以及如何根據特定條件（如輸入的值為 0）結束輸入的方式。

for-each

“for-each 循環”（在 C++ 版本 11 (2011) 中引入，專門用于循環數組（或其他數據集合）中的元素

int myNumbers[5] = {10, 20, 30, 40, 50};
for (int i : myNumbers) {cout << i << "\n";
}

字符

常用 ASCIl 值：‘A’-Z’是65~90， ‘a’-z’是97-182，‘0’-'9’是 48-57。
宇符可以參與運算，運算時會將其當做整數

字符數組的常用操作

下面幾個函數需要引入頭文件:

#include <string.h>//或者
#include <cstring>

1. strlen(str)，求字符串的長度（\0不計入其中）時間復雜度是$O(n)$
2. strcmp(a, b)，比較兩個字符串的大小，a < b返回-1，a == b返回0，a > b返回1。這里的比較方式是字典序！
3. strcpy(a, b)，將字符串b復制給從a開始的字符數組。

字符串String

基本概念

可變長的字符序列，比字符數組更加好用。需要引入頭文件：

#include <string>

• 定義和初始化：

#include <iostream>
#include <string>using namespace std;int main()
{string s1;              // 默認初始化，s1是一個空字符串string s2 = s1;         // s2是s1的副本，注意s2只是與s1的值相同，并不指向同一段地址string s3 = "hiya";     // s3是該字符串字面值的副本string s4(10, 'c');     // s4的內容是 "cccccccccc"return 0;
}

其他數據類型轉變為字符串to_string()

    int c = 10;string num = to_string(c);cout << num << endl;

字符串連接

使用+號或者append()

string firstName = "John";
string lastName = "Doe";
string fullName = firstName + " " + lastName;
fullName = firstName.append(lastName);
cout << fullName;

字符串判空

	string s1, s2 = "abc";cout << s1.empty() << endl;//輸出1cout << s2.empty() << endl;//輸出0

字符串長度

使用length()或size()，和strlen()不同，size()的時間復雜度是O(1)的

string txt = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
cout << "The length of the txt string is: " << txt.length();
cout << "The length of the txt string is: " << txt.size();

注意size是無符號整數，因此 s.size() <= -1一定成立

字符串輸入輸出

string不可以用scanf讀

#include <iostream>
#include <cstring>using namespace std;int main()
{string s;cin >> s; // string不可以用scanf讀printf("%s\n", s.c_str()); // 返回字符串所存的字符數組的首地址puts(s.c_str());return 0;
}

讀入一行

    string s1;getline(cin, s1);cout << s1 << endl;

string的比較：

支持 >, <, >=, <=, ==, !=等所有比較操作，按字典序進行比較。

為string對象賦值：

string s1(10, 'c'), s2;     // s1的內容是 cccccccccc；s2是一個空字符串
s1 = s2;                    // 賦值：用s2的副本替換s1的副本// 此時s1和s2都是空字符串

兩個string對象相加：

psptring s1 = "hello,  "", s2 = "world\n";
string s3 = s1 + s2;                    // s3的內容是 hello, world\n
s1 += s2;                               // s1 = s1 + s2

字面值和string對象相加：

做加法運算時，字面值和字符都會被轉化成string對象，因此直接相加就是將這些字面值串聯起來：

string s1 = "hello", s2 = "world";      // 在s1和s2中都沒有標點符號
string s3 = s1 + ", " + s2 + '\n';

當把string對象和字符字面值及字符串字面值混在一條語句中使用時，必須確保每個加法運算符的兩側的運算對象至少有一個是string：

string s4 = s1 + ", ";  // 正確：把一個string對象和有一個字面值相加
string s5 = "hello" + ", "; // 錯誤：兩個運算對象都不是stringstring s6 = s1 + ", " + "world";  // 正確，每個加法運算都有一個運算符是string
string s7 = "hello" + ", " + s2;  // 錯誤：不能把字面值直接相加，運算是從左到右進行的

遍歷數組

可以將string對象當成字符數組來處理：

#include <iostream>
#include <string>using namespace std;int main()
{string s = "hello world";for (int i = 0; i < s.size(); i ++ )cout << s[i] << endl;return 0;
}

或者使用基于范圍的for語句：

#include <iostream>
#include <string>using namespace std;int main()
{string s = "hello world";for (char c: s) cout << c << endl;for (char& c: s) c = 'a';//想在改變c的同時改變s[i]，在前面加上引用符號&使c等價于s[i]cout << s << endl;return 0;
}

數組

初始化memset

memset 函數是C和C++標準庫中的一個函數，用于將一塊內存中的每個字節都設置為一個給定的值。它通常用于初始化數組或者內存塊。memset 函數的原型定義在 <cstring>（在C++中）或 <string.h>（在C中）頭文件中。

#include <iostream>
#include <cstring>
using namespace std;
int main()
{int a[10];// memset(a, 0, 40);memset(a, 0, sizeof a); // sizeof a 返回a所占用的字節數量return 0;
}

將數組中的每一個字節設置為這個值。


因此，memset一般設置為0或者-1（補碼，每一位都是1）

函數原型

在C和C++中，memset 函數的原型如下：

void *memset(void *s, int c, size_t n);

參數

• void *s：指向要填充的內存塊的指針。
• int c：是一個值，表示要設置的值。盡管這個參數的類型是 int，但實際上只有最低的8位（一個字節）會被用于設置內存塊中的值。
• size_t n：內存塊的大小，即要設置的字節數。

返回值

memset 函數返回一個指向內存塊 s 的指針。

使用示例

假設有一個字符數組 arr，我們想將其所有元素初始化為0：

char arr[100];
memset(arr, 0, sizeof(arr));

這段代碼將 arr 數組的所有100個字節都設置為0。

注意事項

• memset 適用于簡單的數據類型（如字符數組、整數數組等）的初始化，因為它是按字節操作的。對于需要按位初始化的復雜數據類型（如帶有構造函數的C++對象），使用 memset 可能不會得到預期的效果。
• 當使用 memset 設置非零值時，需要注意 c 參數只使用了最低的8位，這意味著如果你想用 memset 來初始化比一個字節更大的數據類型（如 int、float 等），除非你是將其初始化為0或某個字節值的重復（比如 0x01010101），否則結果可能不是你所期望的。
• 由于 memset 是按字節設置值，對于初始化高級數據結構或需要調用構造函數的對象數組，應使用更適合的方法，如循環或標準庫中的 std::fill 或 std::fill_n 函數。

數組復制memcpy

memcpy 函數是C和C++標準庫中用于復制內存塊的函數。它從源內存地址開始復制n個字節到目標內存地址。這個函數對于執行低級別的二進制數據復制非常有效，尤其是當你需要快速復制大量數據時。memcpy函數的原型定義在<cstring>（C++中）或<string.h>（C中）頭文件中。

函數原型

在C和C++中，memcpy函數的原型如下：

void *memcpy(void *dest, const void *src, size_t n);

參數

• void *dest：指向用于存儲復制內容的目標內存塊的指針。
• const void *src：指向要從中復制數據的源內存塊的指針。
• size_t n：要復制的字節數。

返回值

memcpy函數返回一個指向目標內存塊dest的指針。

使用示例

假設你有兩個數組，source和destination，你想將source數組的內容復制到destination數組中：

char source[] = "Hello, World!";
char destination[20];memcpy(destination, source, strlen(source) + 1);

這段代碼將source數組包括結尾的空字符（\0）一共14個字節的內容復制到destination數組中。

注意事項

• memcpy函數不處理源和目標內存塊重疊的情況。如果內存塊重疊，復制的結果是未定義的。對于重疊內存塊的復制，應使用memmove函數。
• 使用memcpy時必須確保目標內存塊足夠大，可以容納要復制的數據，否則可能會導致緩沖區溢出，這是常見的安全漏洞之一。
• memcpy是按字節復制數據，因此它可以用于任何類型的數據復制，包括基本數據類型、結構體、類等，但復制對象時要小心，因為簡單的字節復制可能不會正確處理對象內部的深層復制需求，比如指針成員的正確復制。對于包含動態分配內存或復雜資源管理的對象，使用memcpy可能不適合，應考慮更高級的復制機制。

函數

多維數組形參的寫法

// 多維數組中，除了第一維之外，其余維度的大小必須指定
void print(int (*a)[10]) {/* … */}
void print(int a[][10]) {/* … */}

#include <iostream>using namespace std;void print(int a[][10])
{for (int i = 0; i < 10; i ++ ){for (int j = 0; j < 10; j ++ )cout << a[i][j] << ' ';cout << endl;}
}int main()
{int a[10][10];for (int i = 0; i < 10; i ++ )for (int j = 0; j < 10; j ++ )a[i][j] = j;print(a);return 0;
}

類與結構體

類與結構體的定義與使用

類中的變量和函數被統一稱為類的成員變量。

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];

構造函數

#include <iostream>using namespace std;struct Person
{int age, height;double money;// 特殊的賦值方式Person(int _age, int _height) : age(_age), height(_height){};Person(int _age, int _height, double _money) // 構造函數{age = _age;height = _height;money = _money;}
};int main()
{// 多種初始化方式Person p1(18, 180, 10000);Person p2 = {18, 180, 10000};return 0;
}

指針和引用

指針指向存放變量的值的地址。因此我們可以通過指針來修改變量的值。

#include <iostream>using namespace std;int main()
{int a = 10;int *p = &a;*p += 5;cout << a << endl;return 0;
}

數組名是一種特殊的指針。指針可以做運算：

#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 += 5;cout << a << endl;return 0;
}

STL

multi是可以有重復元素，沒有multi的不能有重復元素