1.優缺點總述

STL中各容器對比圖

各類線性數據結構優缺點

1.數組

1.優點

1.簡單，容易理解

2.訪問快捷，只需要用下標就可以

3.有某些應用場景直接對應，例如二維數組對應平面

2.缺點

刪除和插入數據非常耗時

2.鏈表

1.優點

插入和刪除數據很便捷

2.缺點

定位數據比較耗時，要從鏈表頭開始沿著指針一個一個走。

3.隊列

有自己的使用場景，無優缺點

3.棧

有自己的使用場景，無優缺點

各類非線性數據結構優缺點

1.二叉樹

2.哈希表

2.數組和高精度

1.大數組的使用

在大賽中經常用大數組，注意以下情況

1.建議不要用malloc（）動態分配，因為動態分配需要多寫代碼而且容易出錯。

2.大數組應該定義成全局靜態數組，而且不需要初始化為零，因為全局變量在初始化時自動賦值為零。因為定義到函數內部，可能會導致棧溢出。

2.對各種存儲域的補充

1.棧

存儲局部變量和函數調用信息等，容量較小

2.堆

由malloc，calloc，realloc等分配，需要手動釋放。

3.數據段

存放已經初始化的全局變量與靜態變量

4.bss段

存放未初始化的全局變量或靜態變量。這些變量會被自動初始化0或NULL。

3.高精度算法

在計算機科學中，標準的數據類型如整型（int）、長整型（long）（long long）等都有其表示范圍的限制。當需要處理比這些類型所能表示的范圍更大的數字時，就需要使用高精度算法。

高精度算法這個過程類似于我們在學校里學習的手工算數，將數的每一位都存入數組，從最低位開始逐位處理，并處理進位。

除了C語言的靜態數組，還可以用vector來定義大數組

1.代碼演示高精度加法

#include<iostream>
using namespace std;
char a[1005],b[1005];//1005是防止有進位
string fun(string as, string bs)
{//注意不能寫到主函數內，要寫成子函數，因為a和b目前是指針類型，不能使用sizestring ss;//返回值int lmax;//兩數組最長長度int lena = as.size(), lenb = bs.size();//長度for(int i=0;i<lena;i++){a[lena - i - 1] = as[i] - '0';}for (int i = 0; i < lenb; i++){b[lenb - i - 1] = bs[i] - '0';}lmax = lena > lenb ? lena:lenb;for (int i = 0; i < lmax; i++){//這樣就不用區分那個數字較大了a[i] += b[i];a[i + 1] += a[i] / 10;a[i] %= 10;}if (a[lmax])//如果非零，則有進位{lmax++;}for (int i = lmax - 1; i >= 0; i--){ss += a[i] + '0';//將數字轉化成字符，并且反轉}return ss;
}
int main()
{string as, bs;cin >> as;cin >> bs;cout << fun(as,bs) << endl;return 0;
}

2.代碼演示高精度減法

3.STL概述

1.string庫

語法詳情見STL-string容器

案例1

1.題目

問題描述

在燼寂海中居住著某種智慧生物。它們的文明發展程度相當于地球上的中世紀，但是它們擁有強大的科技與魔法。

一天，王國的法師得到了一段古老的魔法咒文，咒文中似乎隱藏著巨大的能量，但是咒文中有很多相似的字符串片段，法師們相信這些片段與魔法的啟動有關。

現在，國王決定招募聰明的你，使用你的技術能力來幫助法師們解開這個謎團。

現在給你一個字符串?SS（主串），還有若干個模式串?PP。你需要統計每一個模式串在主串中出現的次數。

輸入格式

第一行：一個字符串?SS，表示主串，只包含小寫英文字母。

第二行：一個整數?nn，表示有?nn?個模式串。

接下來的?nn?行：每行一個字符串，代表一個模式串?PP，只包含小寫英文字母。

輸出格式

nn?行，每行一個整數，表示對應模式串在主串中出現的次數。

樣例輸入

bluemooninthedarkmoon
3
moon
blue
dark

?

樣例輸出

2
1
1

?

測評數據規模

主串的長度：∣S∣≤1×105∣S∣≤1×105。

模式串的數量：1≤n≤1001≤n≤100。

模式串的長度：∣P∣≤1000∣P∣≤1000。

運行限制

語言	最大運行時間	最大運行內存
C++	3s	128M
C	3s	128M
Java	5s	128M
Python3	7s	128M
PyPy3	7s	128M
Go	7s	128M
JavaScript	7s	128M

2.作答（第一版）

#include <bits/stdc++.h>
using namespace std;
int main()
{// 請在此輸入您的代碼string s;cin >> s;int n;cin >> n;int sumz[200]={0};for (int i = 0; i < n; i++){string p;int posint = 0;int sum = 0;cin >> p;while (s.find(p,posint) != -1){sum++;posint = s.find(p,posint);posint += p.size();}sumz[i] = sum;}for (int i = 0; i < n; i++){cout << sumz[i] << endl;}return 0;
}

這一版只能通過百分之八十的案例，因為在第二十一行代碼沒有考慮到S為“aaaa”，P為“aa”，這樣aa根據posint+=p.size();的話只能計數兩次，應該改為posint++；這樣就可以計數三次。

第二個問題是使用了靜態數組sumz，浪費了空間，應該使用動態數組vector來節省空間。

3.作答（第二版）

#include <iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{// 請在此輸入您的代碼string s;cin >> s;int n;cin >> n;vector<int> sumz;for (int i = 0; i < n; i++){string p;int posint = 0;int sum = 0;cin >> p;while (s.find(p,posint) != -1){sum++;posint = s.find(p,posint);posint ++;}sumz.push_back(sum);}for (int i = 0; i < n; i++){cout << sumz[i] << endl;}return 0;
}

4.官方題解

#include <iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{string s;int n;vector<int> sum;cin >> s >> n;int n1 = n;while (n--){string p;cin >> p;int cnt = 0;for (int i = 0; i < s.length() - p.length() + 1; i++){if (p == s.substr(i, p.length()))cnt++;}sum.push_back(cnt);}for (int i = 0; i < n1; i++){cout << sum[i] << endl;}return 0;
}

使用了暴力算法

i <?s.length() - p.length() + 1?的含義

• 這里的條件是?i <?s.length() - p.length() + 1。

• s.length()?是主字符串?s?的長度，p.length()?是子字符串?p?的長度。

• s.length() - p.length() + 1?表示的是主字符串中最后一個可能與子字符串匹配的起始位置。

4.比較

時間復雜度比較

1. 官方題解：

   • 外層循環執行?n?次（每個子字符串?p?都需要處理一次）。
   • 內層循環的次數為?s.length() - p.length() + 1，每次調用?substr?提取子串并進行比較。
   • 假設主字符串?s?的長度為?m，子字符串?p?的平均長度為?k，則內層循環的時間復雜度為?O(m?k)O(m?k)。
   • 總時間復雜度為：O(n?m?k)O(n?m?k)。

2. 第二版：

   • 外層循環同樣執行?n?次。
   • 內層使用?find?函數查找子字符串的位置。find?函數在最壞情況下需要掃描整個主字符串?s，其時間復雜度為?O(m)O(m)。
   • 如果子字符串匹配多次，find?會被調用多次，但總體上不會超過?m?次。
   • 總時間復雜度為：O(n?m)O(n?m)。

---

結果

• 官方題解的時間復雜度為?O(n?m?k)O(n?m?k)。
• 第二版的時間復雜度為?O(n?m)O(n?m)。

因此，第二段代碼的時間復雜度更低，效率更高。

案例2

1.題目

元音大寫

問題描述

輸入一個由小寫英文字母組成的字符串，請將其中的元音字母?(a,e,i,o,u)(a,e,i,o,u)?轉換成大寫，其它字母仍然保持小寫。

輸入格式

輸入一行包含一個字符串。

輸出格式

輸出轉換后的字符串。

樣例輸入

lanqiao

?

樣例輸出

lAnqIAO

?

評測用例規模與約定

對于所有評測用例，字符串的長度不超過?100100。

2.作答

#include <bits/stdc++.h>
using namespace std;
int main()
{// 請在此輸入您的代碼string s;cin >> s;for (int i = 0; i < s.size(); i++){if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u'){s[i] -= 32;}}cout << s << endl;return 0;
}

3.解答

題目設計數據限制較小直接用暴力即可。

2.迭代器

1.auto

補充：auto可以自動推導數據類型。

auto 關鍵字是 C++11 引入的一個非常有用的特性，它允許編譯器自動推導變量的類型。使用 auto 可以簡化代碼，尤其是在處理復雜類型（如迭代器、模板實例化類型等）時。下面詳細介紹 auto 的用法及其適用場景。

基本用法

當你聲明一個變量并初始化它時，可以使用 auto 來讓編譯器根據初始化表達式的類型自動推導出變量的類型。

示例 1：基礎類型

auto x = 5;       // x 是 int 類型
auto y = 3.14;    // y 是 double 類型
auto z = 'a';     // z 是 char 類型
auto str = "Hello"; // str 是 const char* 類型

示例 2：復雜類型

std::vector<int> vec = {1, 2, 3, 4};
auto it = vec.begin(); // it 是 std::vector<int>::iterator 類型

auto?結合引用和指針

auto 還可以與引用和指針結合使用，但需要注意的是，auto 默認不會推導出引用或指針類型。如果你希望得到引用或指針類型的變量，需要顯式指定。

示例 3：引用

int a = 10;
auto b = a;        // b 是 int 類型，值為 10
auto& c = a;       // c 是 int& 類型，它是 a 的引用
c = 20;            // 修改 c 實際上修改了 a
std::cout << a << std::endl; // 輸出 20

示例 4：指針

cpp

深色版本

int x = 10;
auto p = &x;       // p 是 int* 類型，指向 x
*p = 20;           // 修改 x 的值
std::cout << x << std::endl; // 輸出 20

auto?結合常量

當初始化表達式是一個常量時，auto 推導出的類型也會是一個常量類型。

示例 5：常量

cpp

深色版本

const int ci = 10;
auto aci = ci;     // aci 是 int 類型，而不是 const int
const auto caci = ci; // caci 是 const int 類型

auto?結合模板

在模板編程中，auto 可以極大地簡化代碼，特別是在定義模板函數返回類型或模板參數類型時。

示例 6：模板中的?auto

cpp

深色版本

template <typename T>
auto get_value(T t) -> decltype(t + 1) {return t + 1;
}

auto?在范圍循環中的應用

auto 在范圍循環中特別有用，它可以讓你輕松遍歷容器中的元素，而無需顯式聲明迭代器類型。

示例 7：范圍循環

cpp

深色版本

std::vector<int> vec = {1, 2, 3, 4, 5};// 使用 auto 遍歷 vector 中的每個元素
for (auto elem : vec) {std::cout << elem << " "; // 輸出 1 2 3 4 5
}
std::cout << std::endl;// 如果你想要修改元素，可以使用引用
for (auto& elem : vec) {elem *= 2; // 將每個元素乘以 2
}for (auto elem : vec) {std::cout << elem << " "; // 輸出 2 4 6 8 10
}
std::cout << std::endl;

注意事項

1. 類型推導規則：

   • auto?會忽略頂層?const?和引用，因此你需要顯式添加它們。

   • 例如，auto x = 5;?推導出?int?而不是?const int?或?int&。

2. 復合類型：

   • 對于復合類型（如數組、函數指針等），直接使用?auto?可能會導致意外的結果。

   • 可以使用?decltype?輔助進行更復雜的類型推導。

3. 調試和可讀性：

   • 雖然?auto?可以減少重復代碼，但在某些情況下可能會影響代碼的可讀性。確保使用?auto?不會降低代碼的理解難度。

總結

• auto?是一個強大的工具，用于簡化代碼并提高開發效率。

• 它可以自動推導變量的類型，尤其適用于復雜類型或模板編程。

• 注意使用?auto?時要理解其推導規則，并在必要時顯式指定引用或指針類型，以避免潛在的錯誤

#include <iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{vector<int> s;s.push_back(1);s.push_back(2);s.push_back(3);s.push_back(4);s.push_back(5);s.push_back(6);auto it = s.begin();it += 5;cout << *it << endl;return 0;
}

?目前藍橋杯支持C++11標準庫，支持auto關鍵字

3.容器

1.各個容器對比圖

對比圖

2.vector

vector詳解

3.set

set詳解

4.map

map詳解

5.鏈表

1.手搓單鏈表

此次使用數組模擬靜態鏈表，即邏輯上是鏈表，物理上是數組

#include<stdio.h>
using namespace std;
#include<iostream>
const int N = 10000;
struct cll
{int id;int data;int nextid;
}nodes[N];//nodes是結點的復數
int main()
{int n = 5;//構造鏈表nodes[0].id = 0;//顯式賦值，將代碼更加可視化。吐過不添加這串代碼也沒事，因為頭節點會被隱式賦值，會自動賦值為0。nodes[0].nextid = 1;for (int i = 1; i <= n; i++){nodes[i].id = i;nodes[i].nextid = i + 1;nodes[i].data = i * 10;}//定義為循環鏈表，尾指向頭nodes[n].nextid = nodes[0].nextid;//刪除鏈表節點cout << "是否刪除" << endl;int bool1 = 0;cin >> bool1;if (bool1 == 1){int nowid = 0;cout << "刪除" << endl;cin >> nowid;//輸入當前節點位置nodes[nowid - 1].nextid = nowid + 1;//定義為循環鏈表，尾指向頭nodes[n].nextid = nodes[0].nextid;}//插入鏈表節點cout << "是否插入" << endl;int bool2 = 0;cin >> bool2;if (bool2 == 1){cout << "插入位置" << endl;int n1 = n;int insert = 0;cin >> insert;nodes[++n1].id = n1;nodes[n1].data = 666;nodes[n1].nextid = nodes[insert].nextid;nodes[insert].nextid = nodes[n1].id;if (insert == 0){//定義為循環鏈表，尾指向頭nodes[n].nextid = nodes[0].nextid;}}//遍歷鏈表int current = nodes[0].nextid;  // 從第一個數據節點開始do {printf("Node ID: %d, Data: %d\n", nodes[current].id, nodes[current].data);current = nodes[current].nextid;  // 移動到下一個節點} while (current != nodes[0].nextid);
}

對于插入操作中判斷isnert==0的操作，是為了防止破壞鏈表結構

不更新鏈表結構的話，會導致無限循環

2.單鏈表題目

小王子單鏈表

題目描述

小王子有一天迷上了排隊的游戲，桌子上有標號為?1?101?10?的?1010?個玩具，現在小王子將他們排成一列，可小王子還是太小了，他不確定他到底想把那個玩具擺在哪里，直到最后才能排成一條直線，求玩具的編號。已知他排了?MM?次，每次都是選取標號為?XX?個放到最前面，求每次排完后玩具的編號序列。

要求一：采用單鏈表解決

輸入描述

第一行是一個整數?MM，表示小王子排玩具的次數。

隨后?MM?行每行包含一個整數?XX，表示小王子要把編號為?XX?的玩具放在最前面。

輸出描述

共?MM?行，第?ii?行輸出小王子第?ii?次排完序后玩具的編號序列。

輸入輸出樣例

示例 1

輸入

5
3
2
3
4
2

輸出

3 1 2 4 5 6 7 8 9 10
2 3 1 4 5 6 7 8 9 10
3 2 1 4 5 6 7 8 9 10
4 3 2 1 5 6 7 8 9 10
2 4 3 1 5 6 7 8 9 10

運行限制

• 最大運行時間：1s
• 最大運行內存: 128M

本題的解題思路是先刪除再插入，不過由于是單鏈表，需要通過一個遍歷算法算得到前面的節點id

3.手搓雙向鏈表

#include<stdio.h>
using namespace std;
#include<iostream>
const int N = 10000;
struct cll
{int id;int data;int preid;int nextid;
}nodes[N];//nodes是結點的復數
int main()
{int n = 5;//構造鏈表nodes[0].id = 0;//顯式賦值，將代碼更加可視化。吐過不添加這串代碼也沒事，因為頭節點會被隱式賦值，會自動賦值為0。nodes[0].nextid = 1;for (int i = 1; i <= n; i++){nodes[i].preid = i - 1;nodes[i].id = i;nodes[i].nextid = i + 1;nodes[i].data = i * 10;}//定義為循環鏈表，尾指向頭nodes[n].nextid = nodes[0].nextid;//刪除鏈表節點cout << "是否刪除" << endl;int bool1 = 0;cin >> bool1;if (bool1 == 1){int nowid = 0;cout << "刪除" << endl;cin >> nowid;//輸入當前節點位置nodes[nowid - 1].nextid = nowid + 1;nodes[nowid + 1].preid = nodes[nowid - 1].id;//定義為循環鏈表，尾指向頭nodes[n].nextid = nodes[0].nextid;}//插入鏈表節點cout << "是否插入" << endl;int bool2 = 0;cin >> bool2;if (bool2 == 1){cout << "插入位置" << endl;int n1 = n;int insert = 0;cin >> insert;nodes[++n1].id = n1;nodes[n1].data = 666;nodes[n1].preid = nodes[insert].id;nodes[n1].nextid = nodes[insert].nextid;nodes[insert].nextid = nodes[n1].id;if (insert == 0){//定義為循環鏈表，尾指向頭nodes[n].nextid = nodes[0].nextid;}}//遍歷鏈表int current = nodes[0].nextid;  // 從第一個數據節點開始do {printf("Node ID: %d, Data: %d\n", nodes[current].id, nodes[current].data);current = nodes[current].nextid;  // 移動到下一個節點} while (current != nodes[0].nextid);
}

4.極簡鏈表

適合于單一場景，節點即值，值即節點

5.STL的list

list詳解

1.list解決上面單鏈表題目

#include <iostream>
#include<list>
using namespace std;
const int n = 1000;
int main()
{list <int> toy{1,2,3,4,5,6,7,8,9,10};int m;int x;cin>>m;while(m--){cin>>x;toy.remove(x);toy.push_front(x);for(auto i:toy){cout<<i<<" ";}cout<<endl;}return 0;
}

2.list例題2

?問題描述

給定按從小到大的順序排列的數字?11?到?nn，隨后對它們進行?mm?次操作，每次將一個數字?xx?移動到數字?yy?之前或之后。請輸出完成這?mm?次操作后它們的順序。

輸入格式

第一行為兩個數字?n,mn,m，表示初始狀態為?11?到?nn?的從小到大排列，后續有?mm?次操作。

第二行到第?m+1m+1?行，每行三個數?x,y,zx,y,z。當?z=0z=0?時，將?xx?移動到?yy?之后；當?z=1z=1?時，將x移動到?yy?之前。

輸出格式

一行，nn?個數字，中間用空格隔開，表示?mm?次操作完成后的排列順序。

樣例輸入樣例輸出

2 1 3 5 4

?

說明/提示

n≤1e4n≤1e4，m≤1e4m≤1e4。

運行限制

語言	最大運行時間	最大運行內存
C++	1s	256M
C	1s	256M
Java	2s	256M
Python3	3s	256M
PyPy3	3s	256M
Go	3s	256M
JavaScript	3s	256M

#include <iostream>
#include<list>
#include<algorithm>
using namespace std;
int main()
{// 請在此輸入您的代碼list<int>cll;int n, m, x, y, z;cin >> n >> m;for (int i = 1; i <= n; i++){cll.push_back(i);}for (int i = 1; i <= m; i++){cin >> x >> y >> z;cll.remove(x);auto it = find(cll.begin(), cll.end(), y);if (z == 0){cll.insert(++it, x);}else if (z == 1){cll.insert(it, x);}}for (auto i : cll){cout << i << " ";}cout << endl;return 0;
}

6.隊列

未完待續