寫在前面
近期的學習重點要放在圖論了，之前一直在acwing中學習的資料結構都是陣列模擬，陣列模擬的效率比上stl要快上幾倍，學完過后不久就會忘記，但是忘記也是一種學習，原本準備放棄陣列模擬直接上stl要輕松的多，可是圖論又得用到大量的陣列模擬，最后還是打算攻堅克難把陣列模擬各種資料結構給啃下來，(除此之外還能用來裝*ヾ(?ω?`)o)
陣列模擬（一）
目錄- 寫在前面
- 陣列模擬（一）
- 單鏈表
- 雙鏈表
- 模擬堆疊
- 模擬佇列
單鏈表
// head 表示頭節點
// e[N]用來存盤每個節點的值
// ne[N]存盤每個節點指向的下一個節點
// idx用來動態開辟空間或者理解為當前操作的位置
int head, e[N], ne[N], idx;
// 初始時head指向空節點，這里的-1即為空節點
void init()
{
head = -1;
}
// 向頭節點的后一位插入節點
void add_to_head(int x)
{
e[idx] = x; // 先將該節點的值賦值給待插入的節點idx
ne[idx] = head; // 再將待插入節點的next指標指向head指向的節點
head = idx ++; // 最后改head指向待插入的這個節點
}
// 在第k個插入的元素后面插入節點
void add(int k, int x)
{
e[idx] = x; // 同理先賦值
ne[idx] = ne[k]; // 然后將待插入節點的next指標指向第k個節點指向的節點
ne[k] = idx ++; // 改變k的指向
}
// 洗掉第k個插入的元素后面的節點
void remove(int k)
{
// 讓 k -> next 消失
ne[k] = ne[ne[k]]; // k -> next = k -> next -> next
}
雙鏈表
// 雙鏈表既可以知道前一個節點也可以知道后面一個節點
// l[N]陣串列示左邊的節點，r[N]表示后面一個節點
int e[N], idx, l[N], r[N];
void init()
{
l[1] = 0, r[0] = 1; // 左邊的邊界是0， 右邊的邊界是1
idx = 2; // 0，1都被占用了，這里idx就從2開始
}
// 在k節點的后面插入一個節點
void add(int k, int x)
{
e[idx] = x; // 先賦值
r[idx] = r[k], l[idx] = k; // 待插入節點的左指標指向k，右指標指向k指向的節點
// 下面改變原鏈表的順序，注意下面的順序
// 先把k的節點的左邊指向idx，然后把k右指標指向待插入節點
l[r[k]] = idx, r[k] = idx ++;
}
// 洗掉k節點
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main()
{
// 遍歷
for(int i = r[0]; i != 1; i = r[i])
cout << e[i] << ' ';
return 0;
}
模擬堆疊
實作一個堆疊，堆疊初始為空，支持四種操作：
push x– 向堆疊頂插入一個數 x；pop– 從堆疊頂彈出一個數；empty– 判斷堆疊是否為空；query– 查詢堆疊頂元素
#include <iostream>
using namespace std;
int stk[N], tt; // tt表示堆疊頂
int main()
{
string op; // 操作
int x; // 值
cin >> op;
if (op == "push")
{
cin >> x;
stk[++tt] = x;
}else if (op == "pop")
{
// 出堆疊，下次入堆疊時該位置上的值會被覆寫
tt--;
}
else if (op == "empty")
{
// 堆疊空tt為0
cout << (tt == 0 ? "YES" : "NO") << endl;
}else
{
// 查看堆疊頂元素
cout << stk[tt] << endl;
}
}
模擬佇列
實作一個佇列，佇列初始為空，支持四種操作：
push x– 向隊尾插入一個數 x；pop– 從隊頭彈出一個數；empty– 判斷佇列是否為空；query– 查詢隊頭元素，
#include <iostream>
using namespace std;
// hh表示隊頭，tt表示隊尾，之所以初始化為-1是因為入堆疊時tt會先自增
int q[N], hh, tt = -1;
int main()
{
string op;
int x;
cin >> op;
if (op == "push")
{
cin >> x;
q[++tt] = x; // 隊尾自增
}else if (op == "pop")
{
hh ++; // 拋棄隊頭
}else if (op == "empty")
{
// 當tt == hh 時剛好有一個元素的時候，當隊頭自增時tt < hh，此時沒有元素
cout << (tt >= hh ? : "NO" : "YES") << endl;
}else
{
// 輸出隊頭元素
cout << q[hh] << endl;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/335112.html
標籤：其他