首页 > 代码库 > 7.18线性结构选讲部分代码

7.18线性结构选讲部分代码

技术分享
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int sta[1010],top;int main(){    int n,x,y;cin>>n;    for(int i=1;i<=n;i++)    {        cin>>x;        if(x==1) cin>>y,sta[++top]=y;        else top--;    }    if(top==0)cout<<"impossible!"<<endl;    else cout<<sta[top]<<endl;    return 0;}
栈练习1
技术分享
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int sta[1010],top;int main(){    int n,x,y;cin>>n;    for(int i=1;i<=n;i++)    {        cin>>x;        if(x==1) cin>>y,sta[++top]=y;        else         {            if(top)top--;            else             {                cout<<"impossible!"<<endl;                return 0;            }        }    }    if(top==0)cout<<"impossible!"<<endl;    else cout<<sta[top]<<endl;    return 0;}
栈练习2
技术分享
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int sta[1010],top;int main(){    int n,x,y;cin>>n;    for(int i=1;i<=n;i++)    {        cin>>x;        if(x==1) cin>>y,sta[++top]=y;        if(x==2) top--;        if(x==3) cout<<sta[top]<<endl;    }    return 0;}
栈练习3
技术分享
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int n,top,k,p;char mn;int s[100001],a[100001];int main(){    cin>>n;    for(int i=1; i<=n; i++)    {        cin>>mn;        if(mn==A) a[++p]=++k;        if(mn==B&&top==5)        {            cout<<"No"<<endl;            return 0;        }        if(mn==C&&top==0)        {            cout<<"No"<<endl;            return 0;        }        else        {            if(mn==B) s[++top]=++k;            if(mn==C) a[++p]=s[top--];        }    }    cout<<"Yes"<<endl;    for(int i=1; i<=p; i++)        cout<<a[i]<<endl;    return 0;}
天使之城
技术分享
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int n,top,k,p;char mn;int s[100001],a[100001];int main(){    cin>>n;    for(int i=1; i<=n; i++)    {        cin>>mn;        if(mn==A) a[++p]=++k;        if(mn==B&&top==5)        {            cout<<"No"<<endl;            return 0;        }        if(mn==C&&top==0)        {            cout<<"No"<<endl;            return 0;        }        else        {            if(mn==B) s[++top]=++k;            if(mn==C) a[++p]=s[top--];        }    }    cout<<"Yes"<<endl;    for(int i=1; i<=p; i++)        cout<<a[i]<<endl;    return 0;}
后缀表达式
技术分享
#include <cstring>#include <cstdio>#include <iostream>using namespace std;int n,l,top;char s[3000000],tack[50000];bool checked;int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        memset(s,0,sizeof(s));        top=0;        checked=false;        scanf("%s",s);        l=strlen(s);        if(s[0]==]||s[0]==}||s[0]==)||s[0]==>)        {            printf("FALSE\n");            continue;        }        for(int j=0;j<l;j++)        {            if(s[j]==(||s[j]=={||s[j]==[||s[j]==<)            {                top++;                tack[top]=s[j];            }            if((s[j]==)&&tack[top]!=()||(s[j]==]&&tack[top]!=[)||(s[j]==}&&tack[top]!={)||(s[j]==>&&tack[top]!=<))            {            printf("FALSE\n");            checked=true;            break;            }            if((s[j]==)&&tack[top]==()||(s[j]==]&&tack[top]==[)||(s[j]==}&&tack[top]=={)||(s[j]==>&&tack[top]==<))                top-=1;        }        if(checked)        continue;        if(!top)        printf("TRUE\n");        else        printf("FALSE\n");    }    return 0;}
括号序列

 

 

技术分享
#include<iostream>using namespace std;int q[1001],n,x[1001],y[1001],head,tail;int main(){    cin>>n;    for(int i=0;i<n;i++)    {        cin>>x[i];        if(x[i]==1)            {                cin>>y[i];                q[tail++]=y[i];                continue;            }        if(x[i]==2)            {                if(head==tail){cout<<"impossible!";return 0;}                else head++;continue;            }    }    if(head==tail){cout<<"impossible!";return 0;}    cout<<q[head];}
队列练习1
技术分享
#include<iostream>using namespace std;int q[100001],n,x[100001],y[100001],head,tail;int main(){    cin>>n;    for(int i=0;i<n;i++)    {        cin>>x[i];        if(x[i]==1)            {                cin>>y[i];                q[tail++]=y[i];                continue;            }        if(x[i]==2)            {                if(head>=tail){cout<<"impossible!";return 0;}                else head++;continue;            }    }    if(head==tail){cout<<"impossible!";return 0;}    cout<<q[head];}
队列练习2
技术分享
#include<iostream>using namespace std;int q[100001],n,x[100001],y[100001],head,tail;int main(){    cin>>n;    for(int i=0;i<n;i++)    {        cin>>x[i];        if(x[i]==1)            {                cin>>y[i];                q[tail++]=y[i];                continue;            }        if(x[i]==2)            {                if(head>=tail){cout<<"impossible!";return 0;}                else head++;continue;            }        if(x[i]==3)        {            cout<<q[head]<<endl;        }    }    if(head==tail){cout<<"impossible!";return 0;}}
队列练习3
技术分享
#include<cstdio>int m,n,q[1001],fro,end,x,tot;bool b[1001];//判断是否出现int main(){    scanf("%d%d",&m,&n);fro=1;    for(int i=1;i<=n;i++)    {        scanf("%d",&x);        if(b[x]) continue;        if(end-fro+1==m) b[q[fro]]=0,fro++;        q[++end]=x;tot++;b[x]=1;    }    printf("%d\n",tot);    return 0;}
机器翻译

 

 

技术分享
#include<cstdio>#include<iostream>#include<cstring>#define maxn 100005int last,cur,next[maxn];char s[maxn];int main(){    while (scanf("%s",s+1)==1)    {        int n=strlen(s+1);        last =cur=0;        next[0]=0;        for(int i=1;i<=n;i++)        {            char ch=s[i];            if(ch==[) cur=0;            else if (ch==]) cur =last;            else            {                next[i]=next[cur];                next[cur]=i;                if(cur ==last) last=i;                cur=i;            }        }        for(int i=next [0];i!=0;i=next[i])            printf("%c",s[i]);        printf("\n");    }    return 0;}
破损的键盘
技术分享
#include<cstdio>#include<cstring>using namespace std;#define MAXN 1000010int left[MAXN],right[MAXN],n,i,a,f,m,first=1;int main(){    memset(left,-1,sizeof(left));    memset(right,-1,sizeof(right));    left[1]=right[1]=0;    left[0]=right[0]=1;    scanf("%d",&n);    for(i=2;i<=n;i++)    {        scanf("%d%d",&a,&f);        if(!f)        {            right[left[a]]=i;            left[i]=left[a];            left[a]=i;            right[i]=a;        }        else        {            left[right[a]]=i;            right[i]=right[a];            right[a]=i;            left[i]=a;        }    }    scanf("%d",&m);    for(i=1;i<=m;i++)    {        scanf("%d",&f);        if(left[f]<0)continue;        right[left[f]]=right[f];        left[right[f]]=left[f];        left[f]=right[f]=-1;    }    i=0;    for(;;)    {        if(!right[i]){putchar(\n);return 0;}        if(first){printf("%d",right[i]);first=0;}        else printf(" %d",right[i]);        i=right[i];    }}
队列安排

 

7.18线性结构选讲部分代码