0411代码,备战蓝桥杯基础数据结构
1.单链表
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int N = 1000010;
int h,e[N],ne[N],idx;
int m;
void addhead(int x){
e[idx] = x;
ne[idx] = h;
h = idx ++;
}
void add(int k,int x){
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx ++;
}
void delete1(int k){
ne[k] = ne[ne[k]];
}
int main()
{
cin>>m;
char op[2];
h = -1;
while(m--){
scanf("%s",&op);
if(op[0] == 'H'){
int x;
cin>>x;
addhead(x);
}
if(op[0] == 'I'){
int k,x;
cin>>k>>x;
add(k-1,x);
}
if(op[0] == 'D'){
int k;
cin>>k;
if (k == 0) h = ne[h];//删除头节点要特判！！！！
delete1(k-1);
}
}
for(int i=h;i!=-1;i=ne[i]){
int j = e[i];
cout<<j<<' ';
}
return 0;
}
2.栈：读入string要用cin
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int N = 1000010;
int m;
int st[N];
int tt = -1;
int main()
{
cin>>m;
while(m--)
{
string op;
cin>>op;
if(op == "push"){
int x;
cin>>x;
st[++tt] = x;
}
if(op == "empty"){
if(tt==-1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
if(op == "query"){
cout<<st[tt]<<endl;
}
if(op == "pop"){
tt--;
}
}
return 0;
}
3.队列
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int N = 1000010;
int m;
int q[N];
int tt = -1,hh;
int main()
{
cin>>m;
while(m--)
{
string op;
cin>>op;
if(op == "push"){
int x;
cin>>x;
q[++tt] = x;
}
if(op == "empty"){
if(hh>tt) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
if(op == "query"){
cout<<q[hh]<<endl;
}
if(op == "pop"){
hh++;
}
}
return 0;
} 4.单调栈
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int N = 1000010;
int n;
int st[N];
int tt;
int main()
{
cin>>n;
for(int i=0;i<n;i++){
int x;
cin>>x;
while(tt && st[tt] >= x){
tt--;
}
if(tt) cout<<st[tt]<<' ';//第一个数序号是0，输出-1
else cout<<"-1"<<' ';
st[++tt] = x;
}
return 0;
}
5.单调队列：注意第二次更新hh=0,tt=-1
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int N = 1000010;
int n,k;
int q[N],hh,tt=-1;
int a[N];
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
//找最小值
for(int i=0;i<n;i++){
while(hh<=tt && i-k+1 > q[hh]){
hh++;//q数组是下标
}
while(hh<=tt && a[q[tt]] >= a[i]){
tt--;//则不可能作为答案输出
}
q[++tt] = i;//要先添加进来，在窗口里，可能作为答案输出
if(i >= k-1){
cout<<a[q[hh]]<<' ';
}
}
cout<<endl;
//找最大值
int hh=0,tt=-1;
for(int i=0;i<n;i++){
while(hh<=tt && i-k+1 > q[hh]){
hh++;//q数组是下标
}
while(hh<=tt && a[i] >= a[q[tt]]){
tt--;//则不可能作为答案输出
}
q[++tt] = i;//要先添加进来，在窗口里，可能作为答案输出
if(i >= k-1){
cout<<a[q[hh]]<<' ';
}
}
return 0;
} 6.kmp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int M = 1000010;
const int N = 100010;
int n,m;
char p[N];
char s[M];
int ne[N];
int main()
{
cin>>n>>p+1>>m>>s+1;
//求ne数组
for(int i=2,j=0;i<=n;i++){//从2开始求ne数组
//回退
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<=m;i++){//从第一个开始比对
while(j && s[i]!=p[j+1]){
j=ne[j];
}
if(s[i] == p[j+1]) j++;
if(j==n){//比对成功
cout<<i-n<<' ';
j=ne[j];//成功之后要回退！！！！！！！！！
}
}
return 0;
}
7.trie字典树
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int M = 1000010;
const int N = 100010;
int son[N][26],cnt[N],idx;
int n;
void insert(char str[]){
int p=0;
for(int i=0;str[i];i++){
int u=str[i] - '0';
if(!son[p][u]){
son[p][u] = ++idx;//不存在就创建
}
p = son[p][u];
}
cnt[p]++;
return;
}
int query(char str[]){
int p=0;
for(int i=0;str[i];i++){
int u = str[i]-'0';
if(!son[p][u]) return 0;
p=son[p][u];
}
return cnt[p];
}
int main()
{
cin>>n;
char op[2];
char a[N];
while(n--){
cin>>op;
if(op[0] == 'I'){
cin>>a;
insert(a);
}
if(op[0] == 'Q'){
cin>>a;
cout<<query(a)<<endl;
}
}
}8.并查集
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int M = 1000010;
const int N = 100010;
int n,m;
int p[N];
int find1(int x){
if(p[x] != x) p[x] = find1(p[x]);
return p[x];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
p[i] = i;//最开始自己是自己的父亲
}
char op[2];
while(m--){
cin>>op;
if(op[0] == 'M'){
int a,b;
cin>>a>>b;
if(p[find1(a)] == p[find1(b)]) continue;
p[find1(a)] = find1(b);
}
if(op[0] == 'Q'){
int a,b;
cin>>a>>b;
if(p[find1(a)] == p[find1(b)]) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}
9.并查集的连通块
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int M = 1000010;
const int N = 100010;
int n,m;
int p[N],size1[N];
int find1(int x){
if(p[x] != x) p[x] = find1(p[x]);
return p[x];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
p[i] = i;//最开始自己是自己的父亲
size1[i] = 1;
}
char op[2];
while(m--){
cin>>op;
if(op[0] == 'C'){
int a,b;
cin>>a>>b;
if(p[find1(a)] == p[find1(b)]) continue;
size1[find1(b)]+=size1[find1(a)];
p[find1(a)] = find1(b);
}
else if(op[1] == '1'){
int a,b;
cin>>a>>b;
if(p[find1(a)] == p[find1(b)]) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
else{
int a;
cin>>a;
int fa = size1[find1(a)];
cout<<fa<<endl;
}
}
return 0;
}10.堆排序数组模拟
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int M = 1000010;
const int N = 100010;
int n,m;
int heap[N],cnt;
void down(int u){
int t=u;
if(u*2 <= cnt && heap[u*2] < heap[t]){
t=u*2;
}
if(u*2+1 <= cnt && heap[u*2+1] < heap[t]){
t=u*2+1;
}
if(t!=u){
swap(heap[u],heap[t]);
down(t);
}
return;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>heap[i];
}
cnt=n;
for(int i=n/2;i;i--) down(i);
while(m--){
cout<<heap[1]<<' ';
heap[1] = heap[cnt--];
down(1);
}
return 0;
}原文地址：https://blog.csdn.net/2401_82736456/article/details/137655009
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！