一、动态链表 - list (了解)

new 和 delete 是非常耗时的操作

在算法比赛中，一般不会使使用 new 和 delete 去模拟实现一个链表。

而且STL 里面的 list 的底层就是动态实现的双向循环链表，增删会涉及 new 和 delete，效率不高，竞赛中一般不会使用，这里了解一下即可。

1.1 创建 list

包含头文件<list>  , 使用方法和vector 差不多

#include <iostream>
#include <cstdio>
#include <list>
using namespace std;int main()
{list<int> lt;//创建一个存储int 类型的链表 return 0;
}

1.2 push_front/push_back

1） push_front ： 头插

2）push_back：尾插

时间复杂度：O（1）

#include <iostream>
#include <cstdio>
#include <list>
using namespace std;void print(list<int>& i)
{for(auto e:i){cout << e << " " ;}cout << endl;
}int main()
{list<int> lt;//创建一个存储int 类型的链表 //尾插for(int i = 1;i<=5 ;i++){lt.push_back(i); print(lt);} //头插for(int i = 1;i <= 5 ; i++){lt.push_front(i);print(lt); } return 0;
}

1.3 pop_front / pop_back

1)pop_front : 头删

2）pop_back:尾删

时间复杂度：O（1）

	  //头删for(int i = 1;i<=6 ; i++){lt.pop_front(); } print(lt);//尾删 for(int i = 1;i<=2;i++){lt.pop_back() ;}print(lt);

1.4 所有测试代码

#include <iostream>
#include <cstdio>
#include <list>
using namespace std;void print(list<int>& i)
{for(auto e:i){cout << e << " " ;}cout << endl;
}int main()
{list<int> lt;//创建一个存储int 类型的链表 //尾插for(int i = 1;i<=5 ;i++){lt.push_back(i); print(lt);} //头插for(int i = 1;i <= 5 ; i++){lt.push_front(i);print(lt); } //头删for(int i = 1;i<=6 ; i++){lt.pop_front(); } print(lt);//尾删 for(int i = 1;i<=2;i++){lt.pop_back() ;}print(lt);return 0;
}

二、算法题

2.1 排列顺序

B3630 排队顺序 - 洛谷

#include <iostream>
#include <cstdio>
using namespace std;const int N = 1e6 + 10;
int n,h;
int ne[N];int main()
{cin >> n;for(int i = 1;i<= n ; i++){cin >> ne[i];}cin >> h;//遍历链表for(int i = h;i;i = ne[i]){cout << i << " ";} return 0;
}

2.2 单向链表

#include <iostream>
#include <cstdio>
using namespace std;const int N = 1e5 + 10;
const int M = 1e6 + 10;//链表
int h,id,e[N],ne[N];
int mp[M];//mp[i]用来标记i 这个元素存储再什么位置 
int main()
{int q; cin >> q;//初始化id++;e[id] = 1;mp[1] = id; while(q--){int op,x,y;cin >> op >> x;int p = mp[x];//x 存的位置 if(op == 1)//尾部插入 {cin >> y;id++;e[id] = y;ne[id] = ne[p];ne[p] = id;mp[y] = id;//标记 y 这个位置 }else if(op == 2){cout << e[ne[p]] << endl;}else//删除 x 后面的元素 {ne[p] = ne[ne[p]];}}return 0;
}

2.3 队列安排

P1160 队列安排 - 洛谷

#include <iostream>
#include <cstdio>
using namespace std;const int N = 1e5 + 10;
//双向链表 
int pre[N],ne[N],h;int n,m;
bool st[N];//st[i] 表示 i 这个同学是否出队 
int main()
{cin >> n;//初始化pre[1] = h;ne[h] = 1;for(int i = 2;i<=n ; i++){int k,p;cin >> k >> p;if(p == 0){//i 放在 k 的左边ne[i] = k;pre[i] = pre[k];ne[pre[k]]	= i;pre[k] = i;}else//i 放在 k 的右边 {pre[i] = k;ne[i] = ne[k];pre[ne[k]] = i;ne[k] = i;}}cin >> m;while(m--){int x;cin >> x;if(st[x]) continue;ne[pre[x]] = ne[x];pre[ne[x]] = pre[x];st[x] = true;//表示X已经删除 }for(int i = ne[h];i ; i = ne[i]){cout << i << " ";}return 0;
} 

 

2.4 约瑟夫问题

P1996 约瑟夫问题 - 洛谷

#include <iostream>
#include <cstdio>
using namespace std;const int N = 110;
int n,m,ne[N];int main()
{cin >> n >> m;//创建循环链表for(int i = 1 ; i < n ; i++){ne[i] = i + 1;	} ne[n] = 1;//模拟游戏过程int t = n;for(int i = 1;i<=n;i++)//执行n次出圈操作 {for(int j = 1; j < m ; j++){t = ne[t];}cout << ne[t] << " ";ne[t] = ne[ne[t]];} 
}