當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

第二章数据结构【完结】

發(fā)布時(shí)間：2025/3/20 编程问答 25 豆豆

生活随笔收集整理的這篇文章主要介紹了第二章数据结构【完结】小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

棧那節(jié)表達(dá)式求值，并查集食物鏈還沒做
堆，哈希表不熟，比賽的時(shí)候也很少遇到，故沒有經(jīng)常的練習(xí)。

單鏈表[靜態(tài)]

模板題 AcWing 826. 單鏈表

y神模板:

// head存儲(chǔ)鏈表頭，e[]存儲(chǔ)節(jié)點(diǎn)的值，ne[]存儲(chǔ)節(jié)點(diǎn)的next指針，idx表示當(dāng)前用到了哪個(gè)節(jié)點(diǎn) int head, e[N], ne[N], idx;// 初始化 void init() {head = -1;idx = 0; }// 在鏈表頭插入一個(gè)數(shù)a void insert(int a) {e[idx] = a, ne[idx] = head, head = idx ++ ; }// 將頭結(jié)點(diǎn)刪除，需要保證頭結(jié)點(diǎn)存在 void remove() {head = ne[head]; }

需要注意的是: idx是一直遞增的
完整的代碼:

#include<cstdio> #include<iostream> using namespace std; const int N=1e5+10; //head 指向頭節(jié)點(diǎn)的指針 //e[N] 保存該節(jié)點(diǎn)的值 //ne[N]保存該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的地址 //idx 表示目前分配到哪里的指針 int head,idx; int e[N],ne[N]; void init()//初始化 {head=-1;idx=0; } void add_to_head(int x)//將x插到頭節(jié)點(diǎn) {ne[idx]=head;e[idx]=x;head=idx;idx++; } void add(int k,int x)//將x插入到下標(biāo)是k的點(diǎn)后面 {ne[idx]=ne[k];e[idx]=x;ne[k]=idx;idx++; } void remove(int k)//將下標(biāo)是k的點(diǎn)的后面的點(diǎn)刪除 {ne[k]=ne[ne[k]]; } int main(void) {int n; cin>>n;init();while(n--){char op; cin>>op;if(op=='H'){int x; cin>>x;add_to_head(x);}if(op=='I'){int k,x; cin>>k>>x;add(k-1,x);}if(op=='D'){int k; cin>>k;if(!k) head=ne[head];remove(k-1);}}for(int i=head;i!=-1;i=ne[i]) cout<<e[i]<<" ";return 0; }

雙鏈表[靜態(tài)]

模板題 AcWing 827. 雙鏈表

雙鏈表的初始狀態(tài)

當(dāng)我們從鏈表的最左邊插入的時(shí)候，是從0的右邊插入的。
當(dāng)我們從鏈表的最右邊插入的時(shí)候，是從1的左邊插入的。

y神模板:

// e[]表示節(jié)點(diǎn)的值，l[]表示節(jié)點(diǎn)的左指針，r[]表示節(jié)點(diǎn)的右指針，idx表示當(dāng)前用到了哪個(gè)節(jié)點(diǎn) int e[N], l[N], r[N], idx;// 初始化 void init() {//0是左端點(diǎn)，1是右端點(diǎn)r[0] = 1, l[1] = 0;idx = 2; }// 在節(jié)點(diǎn)a的右邊插入一個(gè)數(shù)x void insert(int a, int x) {e[idx] = x;l[idx] = a, r[idx] = r[a];l[r[a]] = idx, r[a] = idx ++ ; }// 刪除節(jié)點(diǎn)a void remove(int a) {l[r[a]] = l[a];r[l[a]] = r[a]; }

完整的代碼:

#include<cstdio> #include<iostream> using namespace std; const int N=100010; int m; int e[N],l[N],r[N],idx;//在節(jié)點(diǎn)a的右邊插入一個(gè)數(shù) void insert(int a,int x) {e[idx]=x;l[idx]=a,r[idx]=r[a];l[r[a]]=idx,r[a]=idx++; } //刪除節(jié)點(diǎn) void remove(int a) {l[r[a]]=l[a];r[l[a]]=r[a]; } void init() {r[0]=1,l[1]=0;idx=2; }int main(void) {cin>>m;init();while(m--){string op; cin>>op;int k,x;if(op=="L"){cin>>x;insert(0,x);}if(op=="R"){cin>>x;insert(l[1],x);}if(op=="D"){cin>>k;remove(k+1);}if(op=="IL"){cin>>k>>x;insert(l[k+1],x);}if(op=="IR"){cin>>k>>x;insert(k+1,x);}}for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<" ";cout<<endl; }

棧

模板題 AcWing 828. 模擬棧
3302. 表達(dá)式求值不會(huì)

#include <iostream> #include <cstring> #include <algorithm> #include <stack> #include <unordered_map>using namespace std;stack<int> num; stack<char> op;void eval() {auto b = num.top(); num.pop();auto a = num.top(); num.pop();auto c = op.top(); op.pop();int x;if (c == '+') x = a + b;else if (c == '-') x = a - b;else if (c == '*') x = a * b;else x = a / b;num.push(x); }int main() {unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};string str;cin >> str;for (int i = 0; i < str.size(); i ++ ){auto c = str[i];if (isdigit(c)){int x = 0, j = i;while (j < str.size() && isdigit(str[j]))x = x * 10 + str[j ++ ] - '0';i = j - 1;num.push(x);}else if (c == '(') op.push(c);else if (c == ')'){while (op.top() != '(') eval();op.pop();}else{while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();op.push(c);}}while (op.size()) eval();cout << num.top() << endl;return 0; }

y神模板:

// tt表示棧頂 int stk[N], tt = 0;// 向棧頂插入一個(gè)數(shù) stk[ ++ tt] = x;// 從棧頂彈出一個(gè)數(shù) tt -- ;// 棧頂?shù)闹?/span> stk[tt];// 判斷棧是否為空 if (tt > 0) {}

完整代碼:

#include<cstdio> #include<iostream> using namespace std; const int N=1e5+10; int st[N],tt; int main(void) {int m; cin>>m;while(m--){string op; cin>>op;if(op=="push"){int x; cin>>x;st[++tt]=x;}if(op=="pop") tt--;if(op=="query") cout<<st[tt]<<endl;if(op=="empty") if(tt>0) cout<<"NO"<<endl;else cout<<"YES"<<endl;} }

隊(duì)列

模板題 AcWing 829. 模擬隊(duì)列

普通隊(duì)列:

1. 普通隊(duì)列： // hh 表示隊(duì)頭，tt表示隊(duì)尾 int q[N], hh = 0, tt = -1;// 向隊(duì)尾插入一個(gè)數(shù) q[ ++ tt] = x;// 從隊(duì)頭彈出一個(gè)數(shù) hh ++ ;// 隊(duì)頭的值 q[hh];// 判斷隊(duì)列是否為空 if (hh <= tt) {}

完整代碼:

#include<cstdio> #include<iostream> using namespace std; const int N=1e5+10; int q[N],hh,tt=-1; int main(void) {int m; cin>>m;while(m--){string op; cin>>op;if(op=="push"){int x; cin>>x;q[++tt]=x;}if(op=="pop") hh++;if(op=="empty"){if(hh<=tt) cout<<"NO"<<endl;else cout<<"YES"<<endl;}if(op=="query") cout<<q[hh]<<endl;}return 0; }

循環(huán)隊(duì)列

// hh 表示隊(duì)頭，tt表示隊(duì)尾的后一個(gè)位置 int q[N], hh = 0, tt = 0;// 向隊(duì)尾插入一個(gè)數(shù) q[tt ++ ] = x; if (tt == N) tt = 0;// 從隊(duì)頭彈出一個(gè)數(shù) hh ++ ; if (hh == N) hh = 0;// 隊(duì)頭的值 q[hh];// 判斷隊(duì)列是否為空 if (hh != tt) {}

單調(diào)棧

關(guān)于單調(diào)棧的文章

模板題 AcWing 830. 單調(diào)棧

y神模板:

常見模型：找出每個(gè)數(shù)左邊離它最近的比它大/小的數(shù) int tt = 0; for (int i = 1; i <= n; i ++ ) {while (tt && check(stk[tt], i)) tt -- ;stk[ ++ tt] = i; }

完整代碼:

#include<cstdio> #include<iostream> using namespace std; const int N=1e5+10; int st[N],x; int tt=0; int main(void) {int n; cin>>n;while(n--){cin>>x;while(st[tt]>=x) tt--;//棧頂元素大于當(dāng)前元素，則出棧if(!tt) cout<<"-1"<<" ";;//?？?#xff0c;輸出-1if(tt) cout<<st[tt]<<" ";//非空，輸出棧頂元素st[++tt]=x;}return 0; }

單調(diào)隊(duì)列

模板題 AcWing 154. 滑動(dòng)窗口

y神模板:

常見模型：找出滑動(dòng)窗口中的最大值/最小值 int hh = 0, tt = -1; for (int i = 0; i < n; i ++ ) {while (hh <= tt && check_out(q[hh])) hh ++ ; // 判斷隊(duì)頭是否滑出窗口while (hh <= tt && check(q[tt], i)) tt -- ;q[ ++ tt] = i; }

總的代碼:

#include<cstdio> #include<iostream> using namespace std; const int N=1e6+10; int a[N],q[N]; int hh,tt; int n,k; int main(void) {cin>>n>>k;for(int i=0;i<n;i++) scanf("%d",&a[i]);hh=0,tt=-1;for(int i=0;i<n;i++)//這里的q是一個(gè)遞增的序列 , 隊(duì)首元素就是所求的最小值{if(i-k+1>q[hh]) hh++;//窗口出界了while(hh<=tt&&a[i]<=a[q[tt]]) tt--;//不滿足單調(diào)性q[++tt]=i;//q保存的是a數(shù)組的下標(biāo)if(i+1>=k) printf("%d ",a[q[hh]]);}cout<<endl;hh=0,tt=-1;for(int i=0;i<n;i++)//這里的q是一個(gè)遞減的序列{if(i-k+1>q[hh]) hh++;while(hh<=tt&&a[i]>a[q[tt]]) tt--;q[++tt]=i;if(i+1>=k) printf("%d ",a[q[hh]]);}return 0; }

KMP

模板題 AcWing 831. KMP字符串

y神模板:

// s[]是長(zhǎng)文本，p[]是模式串，n是s的長(zhǎng)度，m是p的長(zhǎng)度求模式串的Next數(shù)組： for (int i = 2, j = 0; i <= m; i ++ ) {while (j && p[i] != p[j + 1]) j = ne[j];if (p[i] == p[j + 1]) j ++ ;ne[i] = j; }// 匹配 for (int i = 1, j = 0; i <= n; i ++ ) {while (j && s[i] != p[j + 1]) j = ne[j];if (s[i] == p[j + 1]) j ++ ;if (j == m){j = ne[j];// 匹配成功后的邏輯} }

總的代碼:

#include<cstdio> #include<iostream> using namespace std; const int N=100010,M=1000010;int n,m; int ne[N]; char s[M],p[N]; int main(void) {cin>>n>>p+1>>m>>s+1;//求Next數(shù)組：// s[]是模式串，p[]是模板串, n是s的長(zhǎng)度，m是p的長(zhǎng)度// 為什么要從i = 2開始匹配？因?yàn)閚ext[1] = 0，已經(jīng)確定了，所以應(yīng)該從i = 2開始匹配。// 注意：next[i]的定義是非平凡的最大后綴等于最大前綴，next[i]必須要小于i// 對(duì)于每一個(gè)i開始匹配過程for (int i = 2, j = 0; i <= n; i ++ ){// 如果p[i] != p[j + 1]那么，就跳到ne[j]再進(jìn)行匹配p[i]與p[j + 1]，直到p[i] == p[j + 1]或j = 0為止// j一定要大于0，因?yàn)閖大于0才能跳轉(zhuǎn)到next[j]嘛，ne[0]沒有意義while (j && p[i] != p[j + 1]) j = ne[j]; // 如果一直跳轉(zhuǎn)到 p[i] == p[j + 1]，那么就可以移動(dòng)jif (p[i] == p[j + 1]){j ++ ;ne[i] = j;}// 否則就說明i點(diǎn)沒有最大后綴等于最大前綴else{ne[i] = 0;}}// 匹配for (int i = 1, j = 0; i <= m; i ++ ){while (j && s[i] != p[j + 1]) j = ne[j];if (s[i] == p[j + 1]) j ++ ;if (j == n){printf("%d ",i-n);j = ne[j];// 匹配成功后的邏輯}}return 0; }

Trie

Trie的概念: 高效地存儲(chǔ)和查找字符串集合的數(shù)據(jù)結(jié)構(gòu)。

835. Trie字符串統(tǒng)計(jì)
143. 最大異或?qū)?br /> 240. 食物鏈未解決

y神的模板:

int son[N][26], cnt[N], idx; // 0號(hào)點(diǎn)既是根節(jié)點(diǎn)，又是空節(jié)點(diǎn) // son[][]存儲(chǔ)樹中每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn) // cnt[]存儲(chǔ)以每個(gè)節(jié)點(diǎn)結(jié)尾的單詞數(shù)量// 插入一個(gè)字符串 void insert(char *str) {int p = 0;for (int i = 0; str[i]; i ++ ){int u = str[i] - 'a';if (!son[p][u]) son[p][u] = ++ idx;p = son[p][u];}cnt[p] ++ ; }// 查詢字符串出現(xiàn)的次數(shù) int query(char *str) {int p = 0;for (int i = 0; str[i]; i ++ ){int u = str[i] - 'a';if (!son[p][u]) return 0;p = son[p][u];}return cnt[p]; }

首先要注意的一點(diǎn)就是: N代表的是輸入的字符串總長(zhǎng)度。

也就是說，這個(gè)Trie樹的結(jié)點(diǎn)個(gè)數(shù)和是小于等于N的。

第二點(diǎn) idx的含義：其實(shí)和單鏈表里的那個(gè)含義差不多，如下圖我已經(jīng)用綠筆標(biāo)出了結(jié)點(diǎn)對(duì)應(yīng)的idx的值

需要注意的一點(diǎn)就是我們的每一個(gè)點(diǎn)，對(duì)應(yīng)的idx都是唯一的，這樣我們?cè)僬覂鹤拥倪^程中就不會(huì)有一對(duì)多的情形。

第三點(diǎn)son[N] [26] 的含義
很多小伙伴，不知道這個(gè)的含義是啥。其是只要帶個(gè)案例模擬一邊你就懂了。
例: son[0][u] 這個(gè)的含義就是根節(jié)點(diǎn)它的孩子u結(jié)點(diǎn)的下標(biāo)，跟單鏈表里的next指針其實(shí)是一樣的。
不過有區(qū)別的一點(diǎn)是我們的單鏈表它的孩子只有一個(gè)，是一條鏈子。
但是我們的Trie是后面可能有26個(gè)孩子(因?yàn)橛⑽淖帜钢挥?6個(gè))，即有26種路徑可以選的單鏈表。

例: abc

其實(shí)只要把字符串的每條路徑當(dāng)成一個(gè)單鏈表，就十分的容易理解了。
最后cnt[p] 的含義
就是該字符串出現(xiàn)的次數(shù)。比如上圖的: abc 這條字符串單鏈表已經(jīng)到頭了，那么我們就 cnt[p]++,
p代表的就是c字符所對(duì)應(yīng)的idx,idx我已經(jīng)說了它和一個(gè)字符是唯一對(duì)應(yīng)的，這里的唯一對(duì)應(yīng)不僅是字符對(duì)應(yīng)的關(guān)系還有位置(即樹的層數(shù))。
因?yàn)榈?層的" a " 和第二層的 " a ” 是不同的。
總的代碼:

#include<cstdio> #include<iostream> using namespace std; const int N=100010; int s[N][26],cnt[N],idx; void insert(string str) {int p=0;for(int i=0;str[i];i++){int u=str[i]-'a';if(!s[p][u]) s[p][u]=++idx;p=s[p][u];}cnt[p]++; } int query(string str) {int p=0;for(int i=0;str[i];i++){int u=str[i]-'a';if(!s[p][u]) return 0;//沒有找到p=s[p][u];//下一個(gè)結(jié)點(diǎn)的指針}return cnt[p]; } int main(void) {int n; cin>>n;while(n--){string op,str;cin>>op>>str;if(op=="I") insert(str);else cout<<query(str)<<endl;} }

還有一點(diǎn)就是我們每次是從根節(jié)點(diǎn)開始找的，找到就繼續(xù)找，沒有找到就創(chuàng)建子結(jié)點(diǎn)。

并查集

836. 合并集合
837. 連通塊中點(diǎn)的數(shù)量

y神模板:

(1)樸素并查集：int p[N]; //存儲(chǔ)每個(gè)點(diǎn)的祖宗節(jié)點(diǎn)// 返回x的祖宗節(jié)點(diǎn)int find(int x){if (p[x] != x) p[x] = find(p[x]);return p[x];}// 初始化，假定節(jié)點(diǎn)編號(hào)是1~nfor (int i = 1; i <= n; i ++ ) p[i] = i;// 合并a和b所在的兩個(gè)集合：p[find(a)] = find(b);(2)維護(hù)size的并查集：int p[N], size[N];//p[]存儲(chǔ)每個(gè)點(diǎn)的祖宗節(jié)點(diǎn), size[]只有祖宗節(jié)點(diǎn)的有意義，表示祖宗節(jié)點(diǎn)所在集合中的點(diǎn)的數(shù)量// 返回x的祖宗節(jié)點(diǎn)int find(int x){if (p[x] != x) p[x] = find(p[x]);return p[x];}// 初始化，假定節(jié)點(diǎn)編號(hào)是1~nfor (int i = 1; i <= n; i ++ ){p[i] = i;size[i] = 1;}// 合并a和b所在的兩個(gè)集合：size[find(b)] += size[find(a)];p[find(a)] = find(b);(3)維護(hù)到祖宗節(jié)點(diǎn)距離的并查集：int p[N], d[N];//p[]存儲(chǔ)每個(gè)點(diǎn)的祖宗節(jié)點(diǎn), d[x]存儲(chǔ)x到p[x]的距離// 返回x的祖宗節(jié)點(diǎn)int find(int x){if (p[x] != x){int u = find(p[x]);d[x] += d[p[x]];p[x] = u;}return p[x];}// 初始化，假定節(jié)點(diǎn)編號(hào)是1~nfor (int i = 1; i <= n; i ++ ){p[i] = i;d[i] = 0;}// 合并a和b所在的兩個(gè)集合：p[find(a)] = find(b);d[find(a)] = distance; // 根據(jù)具體問題，初始化find(a)的偏移量

堆

838. 堆排序
839. 模擬堆

y神模板：

// h[N]存儲(chǔ)堆中的值, h[1]是堆頂，x的左兒子是2x, 右兒子是2x + 1 // ph[k]存儲(chǔ)第k個(gè)插入的點(diǎn)在堆中的位置 // hp[k]存儲(chǔ)堆中下標(biāo)是k的點(diǎn)是第幾個(gè)插入的 int h[N], ph[N], hp[N], size;// 交換兩個(gè)點(diǎn)，及其映射關(guān)系 void heap_swap(int a, int b) {swap(ph[hp[a]],ph[hp[b]]);swap(hp[a], hp[b]);swap(h[a], h[b]); }void down(int u) {int t = u;if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;if (u != t){heap_swap(u, t);down(t);} }void up(int u) {while (u / 2 && h[u] < h[u / 2]){heap_swap(u, u / 2);u >>= 1;} }// O(n)建堆 for (int i = n / 2; i; i -- ) down(i);

哈希表

840. 模擬散列表

一般哈希：

(1) 拉鏈法int h[N], e[N], ne[N], idx;// 向哈希表中插入一個(gè)數(shù)void insert(int x){int k = (x % N + N) % N;e[idx] = x;ne[idx] = h[k];h[k] = idx ++ ;}// 在哈希表中查詢某個(gè)數(shù)是否存在bool find(int x){int k = (x % N + N) % N;for (int i = h[k]; i != -1; i = ne[i])if (e[i] == x)return true;return false;}(2) 開放尋址法int h[N];// 如果x在哈希表中，返回x的下標(biāo)；如果x不在哈希表中，返回x應(yīng)該插入的位置int find(int x){int t = (x % N + N) % N;while (h[t] != null && h[t] != x){t ++ ;if (t == N) t = 0;}return t;}

字符串哈希：
841. 字符串哈希
y神模板:

核心思想：將字符串看成P進(jìn)制數(shù)，P的經(jīng)驗(yàn)值是131或13331，取這兩個(gè)值的沖突概率低小技巧：取模的數(shù)用2^64，這樣直接用unsigned long long存儲(chǔ)，溢出的結(jié)果就是取模的結(jié)果typedef unsigned long long ULL; ULL h[N], p[N]; // h[k]存儲(chǔ)字符串前k個(gè)字母的哈希值, p[k]存儲(chǔ) P^k mod 2^64// 初始化 p[0] = 1; for (int i = 1; i <= n; i ++ ) {h[i] = h[i - 1] * P + str[i];p[i] = p[i - 1] * P; }// 計(jì)算子串 str[l ~ r] 的哈希值 ULL get(int l, int r) {return h[r] - h[l - 1] * p[r - l + 1]; }

總結(jié)

以上是生活随笔為你收集整理的第二章数据结构【完结】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

编程问答

第二章 数据结构 【完结】

目錄

單鏈表[靜態(tài)]

雙鏈表[靜態(tài)]

棧

隊(duì)列

單調(diào)棧

單調(diào)隊(duì)列

KMP

Trie

并查集

堆

哈希表

總結(jié)

第二章数据结构【完结】