單連結清單 —— 模闆題 AcWing 826. 單連結清單
實作一個單連結清單，連結清單初始為空，支援三種操作：
(1) 向連結清單頭插入一個數；
(2) 删除第k個插入的數後面的數；
(3) 在第k個插入的數後插入一個數
現在要對該連結清單進行M次操作，進行完所有操作後，從頭到尾輸出整個連結清單。
注意:題目中第k個插入的數并不是指目前連結清單的第k個數。例如操作過程中一共插入了n個數，則按照插入的時間順序，這n個數依次為：第1個插入的數，第2個插入的數，…第n個插入的數。
輸入格式
第一行包含整數M，表示操作次數。
接下來M行，每行包含一個操作指令，操作指令可能為以下幾種：
(1) “H x”，表示向連結清單頭插入一個數x。
(2) “D k”，表示删除第k個輸入的數後面的數（當k為0時，表示删除頭結點）。
(3) “I k x”，表示在第k個輸入的數後面插入一個數x（此操作中k均大于0）。
輸出格式
共一行，将整個連結清單從頭到尾輸出。
資料範圍
1≤M≤100000
所有操作保證合法。
輸入樣例：
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
輸出樣例：
6 4 6 5
#include<bits/stdc++.h>
#define N 100000+10
using namespace std;
int head=-1,e[N],ne[N],idx=0;
void add_head(int x){
e[idx]=x;
ne[idx]=head;
head=idx++;
}
void insert(int k,int x){
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx++;
}
void del(int k){
ne[k]=ne[ne[k]];
}
int main(){
int m;
cin>>m;
while(m--){
char c;
scanf(" %c",&c);
if (c=='H'){
int t;
scanf("%d",&t);
add_head(t);
}
if (c=='D'){
int t;
scanf("%d",&t);
if (t==0) head=ne[head];
else del(t-1);
}
if (c=='I'){
int k,x;
scanf("%d%d",&k,&x);
insert(k-1,x);
}
}
for (int i=head;i!=-1;i=ne[i])
cout<<e[i]<<' ';
return 0;
}
單連結清單說明
// head存儲連結清單頭
//e[]存儲節點的值
//ne[]存儲節點的next指針
//idx表示目前用到了哪個節點
int head, e[N], ne[N], idx;
// 初始化
void init()
{
head = -1;
idx = 0;
}
// 在連結清單頭插入一個數x
void insert(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
//把x插入到下标是k的點後面
void add(int k,int x){
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx;
idx++;
}
//将下标是k的點的後面一個點删除
void del(int k){
ne[k]=ne[ne[k]];
}
// 将頭結點删除，需要保證頭結點存在
void del_herad()
{
head = ne[head];
}
鄰接表（多個單連結清單，用來在存儲圖和樹）
方法1：
結構體模拟鄰接表：為每個點開個單連結清單，分别存儲該點的所有鄰邊
void insert(int u, int v) {
e[idx].v = v;
e[idx].next = p[u];
p[u] = idx++;
}
代碼解釋
u所連的邊構成了一條連結清單,p[u]是頭節點,表示的是邊的标号
e[i].v表示第 i 條邊所到達的點,
e[i].next是連結清單中的下一個節點,表示的也是邊的标号
方法2：（推薦）
int h[N], e[M], v[M], ne[M], idx; // 數組模拟鄰接表
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 2000010;
int n, m;
int price[N];
int h[N], rh[N], e[M], ne[M], idx;
int dmin[N], dmax[N];
bool st[N];
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++ ;
}
void spfa(int *d, int start, int *h, bool flag)
{
queue<int> q;
memset(st, 0, sizeof st);
if (flag) memset(d, 0x3f, sizeof dmin);
q.push(start);
st[start] = true;
d[start] = price[start];
while (q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (flag && d[j] > min(d[t], price[j]) || !flag && d[j] < max(d[t], price[j]))
{
if (flag) d[j] = min(d[t], price[j]);
else d[j] = max(d[t], price[j]);
if (!st[j])
{
st[j] = true;
q.push(j);
}
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
memset(rh, -1, sizeof rh);
for (int i = 1; i <= n; i ++ ) scanf("%d", &price[i]);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(h, a, b), add(rh, b, a);
if (c == 2) add(h, b, a), add(rh, a, b);
}
spfa(dmin, 1, h, true);
spfa(dmax, n, rh, false);
int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, dmax[i] - dmin[i]);
printf("%d\n", res);
return 0;
}
雙連結清單 —— 模闆題 AcWing 827. 雙連結清單
// e[]表示節點的值，l[]表示節點的左指針，r[]表示節點的右指針，idx表示目前用到了哪個節點
int e[N], l[N], r[N], idx;
// 初始化
void init()
{
//0是左端點，1是右端點
r[0] = 1, l[1] = 0;
idx = 2;
}
// 在節點a的右邊插入一個數x
void insert(int k, int x)
{
e[idx] = x;
l[idx] = k, r[idx] = r[k];
l[r[k]] = idx, r[k] = idx ++ ;
}
// 删除節點k
void remove(int k)
{
l[r[k]] = l[k];
r[l[k]] = r[k];
}