首页 > 其他 > 详细

数据结构之线性表题目总结

时间：2014-01-20 22:32:20      阅读：407      评论：0      收藏：0      [点我收藏+]

题目均出自刘汝佳《算法竞赛入门经典》

题目都是队列，栈，链表挂钩的。做题目过程中STL和数组模拟两种方式交叉使用，便于加深对于数据结构的理解。

"Accordian" Patience uva 127

给一副52张的牌，每张牌如果和他左边或左数第三张牌花色相同或者数字相同就把这张牌放到对应牌的上方。统计最后剩几摞牌，每摞牌有几张。

思路是建立52个栈，模拟操作，从左开始，每操作一次，从左再开始。数组模拟栈。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 55
#define INF 1<<25
#define MAX 0x7fffffff
typedef long long ll;
using namespace std;
struct Card
{
    char a[3];
} card[maxn];
int s[maxn][maxn];
int top[maxn];
bool com(Card x,Card y)
{
    if(x.a[0]==y.a[0]||x.a[1]==y.a[1])
        return 1;
    return 0;
}
int main()
{
    while(1)
    {
        for(int i=0; i<52; i++)
        {
            scanf("%s",card[i].a);
            top[i]=1;
            s[i][1]=i;
            if(card[i].a[0]==‘#‘)
                return 0;
        }
        while(1)
        {
            bool jud=0;
            for(int i=0; i<52; i++)
            {
                if(top[i]>0)
                {
                    int rec=0,s1=-1,s2=-1;
                    for(int j=i-1; j>=0; j--)
                    {
                        if(top[j]>0)
                        {
                            rec++;
                            if(rec==1)
                                s1=j;
                            if(rec==3)
                            {
                                s2=j;
                                break;
                            }
                        }
                    }
                    if(s2!=-1)
                    {
                        if(com(card[s[s2][top[s2]]],card[s[i][top[i]]]))
                        {
                            jud=1;
                            top[s2]++;
                            s[s2][top[s2]]=s[i][top[i]];
                            top[i]--;
                            break;
                        }
                    }
                    if(s1!=-1)
                    {
                        if(com(card[s[s1][top[s1]]],card[s[i][top[i]]]))
                        {
                            jud=1;
                            top[s1]++;
                            s[s1][top[s1]]=s[i][top[i]];
                            top[i]--;
                            break;
                        }
                    }
                }
            }
            if(jud==0)
                    break;
        }
        int ans=0;
        for(int i=0; i<52; i++)
        {
            if(top[i])
                ans++;
        }
        if(ans>1)
        printf("%d piles remaining: ",ans);
        else printf("1 pile remaining: ");
        int jud2=0;
        for(int i=0; i<52; i++)
        {
            if(top[i]&&jud2==0)
            {
                printf("%d",top[i]);
                jud2=1;
            }
            else if(top[i])
                printf(" %d",top[i]);
        }
        printf("\n");
    }
}

The Blocks Problem uva 101

木块游戏，总共四种操作，移动木块。与上题类似，也是栈的操作，分别模拟即可。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 30
#define INF 1<<25
#define MAX 0x7fffffff
typedef long long ll;
using namespace std;
int top[maxn];
int b[maxn][maxn];
int main()
{
    int tot;
    scanf("%d",&tot);
    for(int i=0; i<tot; i++)
    {
        b[i][1]=i;
        top[i]=1;
    }
    char c1[5],c2[5];
    while(scanf("%s",c1)&&c1[0]!=‘q‘)
    {
        int a,c,pa,sa,pc,sc;
        scanf("%d%s%d",&a,c2,&c);
        for(int i=0; i<tot; i++)
        {
            for(int j=1; j<=top[i]; j++)
            {
                if(b[i][j]==a)
                {
                    pa=i;
                    sa=j;
                }
                if(b[i][j]==c)
                {
                    pc=i;
                    sc=j;
                }
            }
        }
        if(c1[0]==‘m‘&&c2[1]==‘n‘)
        {
            if(pc==pa)
                continue;
            for(int i=sa+1; i<=top[pa]; i++)
            {
                top[b[pa][i]]++;
                b[b[pa][i]][top[b[pa][i]]]=b[pa][i];
            }
            for(int i=sc+1; i<=top[pc]; i++)
            {
                top[b[pc][i]]++;
                b[b[pc][i]][top[b[pc][i]]]=b[pc][i];
            }
            top[pc]=sc+1;
            top[pa]=sa-1;
            b[pc][top[pc]]=a;
        }
        if(c1[0]==‘m‘&&c2[1]==‘v‘)
        {
            if(pc==pa)
                continue;
            for(int i=sa+1; i<=top[pa]; i++)
            {
                top[b[pa][i]]++;
                b[b[pa][i]][top[b[pa][i]]]=b[pa][i];
            }
            top[pa]=sa-1;
            top[pc]++;
            b[pc][top[pc]]=a;
        }
        if(c1[0]==‘p‘&&c2[1]==‘n‘)
        {
            if(pc==pa)
                continue;
            for(int i=sc+1; i<=top[pc]; i++)
            {
                top[b[pc][i]]++;
                b[b[pc][i]][top[b[pc][i]]]=b[pc][i];
            }
            top[pc]=sc;
            for(int i=sa; i<=top[pa]; i++)
            {
                top[pc]++;
                b[pc][top[pc]]=b[pa][i];
            }
            top[pa]=sa-1;
        }
        if(c1[0]==‘p‘&&c2[1]==‘v‘)
        {
            if(pc==pa)
                continue;
            for(int i=sa; i<=top[pa]; i++)
            {
                top[pc]++;
                b[pc][top[pc]]=b[pa][i];
            }
            top[pa]=sa-1;
        }
    }
    for(int i=0; i<tot; i++)
    {
        printf("%d:",i);
        for(int j=1; j<=top[i]; j++)
            printf(" %d",b[i][j]);
        printf("\n");
    }
}

The Dole Queue uva 133

两个人数一个队列，一个从头开始数，一个从尾开始数，分别数到第K，M个时，输出该人位置号，然后人出队。是一道链表题目，直接用数组写了。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 30
#define INF 1<<25
#define MAX 0x7fffffff
typedef long long ll;
using namespace std;
int main()
{
    int tot,k,m,rec1,rec2;
    int vv[maxn];
    while(scanf("%d%d%d",&tot,&k,&m))
    {
        if(!tot&&!k&&!m)
            return 0;
        memset(vv,0,sizeof(vv));
        int ans=0,fro=0,las=tot+1,i,j;
        while(ans!=tot)
        {
            i=0;
            j=0;
            while(i<k)
            {
                fro++;
                if(fro>tot)
                    fro-=tot;
                if(!vv[fro])
                    i++;

                if(i==k)
                    rec1=fro;


            }
            while(j<m)
            {
                las--;
                if(las<1)
                    las+=tot;
                if(!vv[las])
                    j++;
                if(j==m)
                    rec2=las;

            }
            vv[rec1]=1;
            vv[rec2]=1;
            if(rec1!=rec2)
            {
                ans+=2;
                if(ans!=tot)
                    printf("%3d%3d,",rec1,rec2);
                else
                    printf("%3d%3d",rec1,rec2);
            }
            else
            {
                ans++;
                if(ans!=tot)
                    printf("%3d,",rec1);
                else printf("%3d",rec1);
            }

        }
        printf("\n");
    }

}

ShellSort uva 10152

给出原来从最上到最下的所有乌龟的名字，然后给出要求的从上到下的所有乌龟的名字。每次操作是把某只乌龟提到队守的位置。要求通过最少次操作来使初始排列变成要求的排列。
这道题我想的时间比较长，刚开始不知道怎么处理，最开始觉得是从两个头开始对比两个队列，发现不同的地方就把要求的那只乌龟提到队首。可以敲出来发现这样是不对的，因为后提的乌龟会到先提的乌龟的上面去，不符合题意。想想发现应该是找到队列是操作之后最后一个存在的不同的乌龟。然后把所求队列里这只乌龟之前的乌龟倒叙输出。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 160
#define INF 1<<25
#define MAX 0x7fffffff
typedef long long ll;
using namespace std;
int main()
{
    char name[205][85];
    char aa[85];
    int pre[205];
    int nex[205];
    int vv[205];
    int tot;
    scanf("%d",&tot);
    for(int ii=0; ii<tot; ii++)
    {
        memset(vv,0,sizeof(vv));
        int tt;
        scanf("%d",&tt);
        getchar();
        for(int i=0; i<tt; i++)
        {
            gets(name[i]);
            pre[i]=i;
        }
        for(int i=0; i<tt; i++)
        {
            gets(aa);
            for(int j=0;j<tt;j++)
            if(strcmp(aa,name[j])==0)
            nex[i]=j;
        }
        int nn=0,pp=0;
        int en=-1;
        while(pp<tt)
        {
            while(pre[nn]!=nex[pp])
            {
                if(vv[pre[nn]]==1)
                {
                    nn++;
                    continue;
                }
                vv[nex[pp]]=1;
                en=pp;
                pp++;
            }
            pp++;
            nn++;
        }
        for(int i=en;i>=0;i--)
        puts(name[nex[i]]);
        printf("\n");
    }
}

Parentheses Balance uva 673

括号匹配问题。给一长列的括号，如果所有的括号都能左右匹配且不出现错误情况如"([)]"的情况，而且没有多余的括号，输出Yes，否则No。思路就是建立一个栈，把每个左半括号进入栈，如果下一个半括号与栈首匹配就出栈继续，如果不匹配返回No。最后如果栈不为空返回No。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 140
#define INF 1<<25
#define MAX 0x7fffffff
typedef long long ll;
using namespace std;
int main()
{
    char aa[maxn];
    int tot;
    scanf("%d",&tot);
    getchar();

    for(int i=0; i<tot; i++)
    {
        gets(aa);
        stack <char>qq;
        while(!qq.empty())
        {
            qq.pop();
        }
        int len=strlen(aa);
        int jud=0;
        for(int i=0; i<len; i++)
        {
            if(qq.empty()&&(aa[i]==‘]‘||aa[i]==‘)‘))
            {
                jud=1;
                break;
            }
            else if(!qq.empty()&&((qq.top()==‘(‘&&aa[i]==‘]‘)||(qq.top()==‘[‘&&aa[i]==‘)‘)))
            {
                jud=1;
                break;
            }
            else if(!qq.empty()&&((qq.top()==‘(‘&&aa[i]==‘)‘)||(qq.top()==‘[‘&&aa[i]==‘]‘)))
            {
                qq.pop();
            }
            else qq.push(aa[i]);
        }
        if(!qq.empty())
        jud=1;
        if(jud==1)
        printf("No\n");
        else printf("Yes\n");
    }
}

Matrix Chain Multiplication uva 442

矩阵链乘问题。也是类似括号匹配的问题来进行矩阵的操作，由于每一次矩阵的乘法都是在一个括号内进行的，所以每出现一个右半括号就从栈中取出两个矩阵进行一次矩阵乘法。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 160
#define INF 1<<25
#define MAX 0x7fffffff
typedef long long ll;
using namespace std;
struct B
{
    char n;
    int x,y;
} b[30];
int main()
{
    int tot;char x;
    char aa[maxn];
    B top1,top2;
    scanf("%d",&tot);
    for(int i=0; i<tot; i++)
    {
        getchar();
        scanf("%c",&x);
        scanf("%d%d",&b[x-‘A‘].x,&b[x-‘A‘].y);
    }
    while(scanf("%s",aa)!=EOF)
    {
        int len=strlen(aa);
        stack <B> qq;
        while(!qq.empty())
        qq.pop();
        int ans=0;
        bool jud=0;
        for(int i=0;i<len;i++)
        {
            if(aa[i]!=‘(‘&&aa[i]!=‘)‘)
            {
                qq.push(b[aa[i]-‘A‘]);
            }
            else if(aa[i]==‘)‘)
            {
                top2=qq.top();
                qq.pop();
                top1=qq.top();
                qq.pop();
                if(top1.y==top2.x)
                {
                    ans+=top1.x*top1.y*top2.y;
                    top1.y=top2.y;
                    qq.push(top1);
                }
                else
                {
                    jud=1;
                    break;
                }
            }
        }
        if(jud==1)
        printf("error\n");
        else printf("%d\n",ans);
    }
}

Generalized Matrioshkas uva 11111

题目讲的是“套娃”的活动，每个套娃可以套住总大小小于本身的若干个套娃。问给出的套娃组合是不是能完成一次正确匹配。问题和括号匹配类似，只是判断条件有所改变，变成了大小的判断，与自身的判断两部分。栈的应用。
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 160
#define INF 1<<25
#define MAX 0x7fffffff
typedef long long ll;
using namespace std;
int main()
{
    int num[50005],hold[50005],t[50005];
    char a;
    int ii=0,jud=0,top=0;
    memset(num,0,sizeof(num));
    memset(hold,0,sizeof(hold));
    memset(t,0,sizeof(t));
    while(scanf("%d%c",&num[ii],&a)!=EOF)
    {
        top=0;
        if(a==‘ ‘)
        {
            ii++;
            continue;
        }
        t[0]=MAX;
        for(int i=0; i<=ii; i++)
        {
            if(num[i]<0)
            {
                top++;
                t[top]=num[i]*(-1);
                hold[top]=0;
            }
            if(num[i]>0)
            {
                if(top<=0)
                {
                    jud=1;
                    break;
                }
                if(num[i]-t[top]!=0)
                {
                    jud=1;
                    break;
                }
                top--;
                hold[top]+=t[top+1];
                if(hold[top]>=t[top])
                {
                    jud=1;
                    break;
                }
            }
        }
        if(top!=0)
        jud=1;
        if(jud)
            printf(":-( Try again.\n");
        else printf(":-) Matrioshka!\n");
        ii=0;
        jud=0;
        top=0;
        memset(num,0,sizeof(num));
        memset(hold,0,sizeof(hold));
        memset(t,0,sizeof(t));

    }
}

Expressions uva 11234

有在书上见过类似的知识，用栈的输入方式模拟出一颗以小写num为叶，大写字母operation为枝，根的二叉树。只是看很难理解出输出的队列是什么规律，用笔写了一会，发现是层序遍历。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 10005
#define INF 1<<25
#define MAX 0x7fffffff
typedef long long ll;
using namespace std;
int main()
{
    char aa [maxn];
    int head [maxn];
    int top[maxn];
    int tot;
    scanf("%d",&tot);
    for(int ii=0; ii<tot; ii++)
    {
        scanf("%s",aa);
        stack<int>q;
        int len=strlen(aa);
        for(int i=0;i<len;i++)
        {
            head[i]=i;
            top[i]=0;
        }
        for(int i=0;i<len;i++)
        {
            if(islower(aa[i]))
            q.push(i);
            else
            {
                int rec=q.top();
                head[rec]=i;
                q.pop();
                rec=q.top();
                head[rec]=i;
                q.pop();
                q.push(i);
            }
        }
        int m=0;
        for(int i=0;i<len;i++)
        {
            int ans=0;
            int t=i;
            while(head[t]!=t)
            {
                ans++;
                t=head[t];
            }
            top[i]=ans;
            if(ans>m)
            m=ans;
        }
        for(int i=m;i>=0;i--)
        {
            for(int j=len-1;j>=0;j--)
            if(top[j]==i)
            printf("%c",aa[j]);
        }
        printf("\n");
    }
}

Team Queue uva 540

团体队列，这个名称之前没听说过，看了题觉得挺有意思。队列中存在于不同组的数字一定是连续出现的。这样就好处理了，给每个组建立独立队列，然后建立一个队列来记录所有组进队的先后顺序。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 1005
#define INF 1<<25
#define MAX 0x7fffffff
typedef long long ll;
using namespace std;
int bb[maxn*maxn],y;
int tot,tt[maxn];
int main()
{
    char ss[20];
    //int aa[maxn][maxn];
    queue <int> qq[maxn];
    queue <int>pp;
    int ii=0;
    while(scanf("%d",&tot))
    {
        if(tot==0)
            return 0;
        printf("Scenario #%d\n",++ii);
        queue <int> qq[maxn];
        queue <int>pp;
        for(int i=0; i<tot; i++)
        {
            scanf("%d",&tt[i]);
            for(int j=0; j<tt[i]; j++)
            {
                int x;
                scanf("%d",&x);
                bb[x]=i;
            }
        }
        while(scanf("%s",ss))
        {
            if(ss[0]==‘E‘)
            {
                int y;
                scanf("%d",&y);
                if(qq[bb[y]].empty())
                {
                    pp.push(bb[y]);
                    qq[bb[y]].push(y);
                }
                else if(!qq[bb[y]].empty())
                {
                    qq[bb[y]].push(y);
                }
            }
            else if(ss[0]==‘D‘)
            {
                int rec=pp.front();
                printf("%d\n",qq[rec].front());
                qq[rec].pop();
                if(qq[rec].empty())
                {
                    pp.pop();
                }
            }
            else break;
        }
        printf("\n");
    }
}

Hartals uva 10050

好吧，这道题我不知道为什么在这出现了，图看起来挺吓人，题意很简单，就是看1~N 中多少天被party标记过，即pp[ ]的倍数，周末必记。水过...
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 160
#define INF 1<<25
#define MAX 0x7fffffff
typedef long long ll;
using namespace std;
int main()
{
    int tot,pp[105];
    scanf("%d",&tot);
    for(int i=0;i<tot;i++)
    {
        int tt,p;
        scanf("%d%d",&tt,&p);
        for(int i=0;i<p;i++)
        {
            scanf("%d",&pp[i]);
        }
        int ans=0;
        for(int ii=1;ii<=tt;ii++)
        {
            if(ii%7==6||ii%7==0)
            continue;
            else
            {
                for(int i=0;i<p;i++)
                {
                    if(ii%pp[i]==0)
                    {
                        ans++;
                        break;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
}
这些题做完了英语读的我一阵阵吐血啊，看着看着就烦躁了。还要继续跟着书往下做，同时也是锻炼自己的思维。

数据结构之线性表题目总结

原文：http://blog.csdn.net/ooooooooe/article/details/18515487
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！