纸牌游戏-小猫钓鱼（队列与栈综合）

浅浅的花香味﹌ 2023-07-04 14:14 14阅读 0赞

## 游戏规则 ##

某一天张兵和小明在一起玩扑克牌，每个人各自拿取一份扑克牌，张兵先把一张扑克牌放在桌子上，小明再放一张，出牌时  
，如果某人打出的牌与桌上的某张牌的牌面相同，即可将两张相同的牌及其之间所夹的牌全部取走，并依次放到自己手牌的  
末尾，当任意一人的手牌全部出完后，游戏结束，对手获得胜利。  
我们先来分析游戏中的几种操作，分别是出牌和赢牌，每个人的手牌可以设置成队列结构，出牌时从队列首弹出一个元素，  
赢牌时就将赢的牌插入队列尾部。 桌子可设置成一个栈的结构，两人出的牌都进入栈中，当某个输入的元素与栈中的  
某一个元素相同时，将这两个元素及其之间的元素全部出栈，并且入胜利者的对列。

## 解题过程 ##

一 .**首先设置数据结构，即两个队列一个栈**。

struct queue
    {
        
        int data[1000];
        int head;//队首
        int tail;//队尾
    };
    struct stack
    {
        
        int data[10];//默认扑克牌只10种类型。
        int top;//栈顶
    };
    struct queue q1,q2;
    struct stack s;

二.**初始化队列和栈**

q1.head=1; q1.tail=1;
        q2.head=1; q2.tail=1;
        s.top=0;//初始阶段两人手中都没有牌，并且桌上也没有牌。

三.**给两人添加手牌**

for(i=1;i<=10;i++)
        {
        
            scanf("%d",&q1.data[q1.tail]);//读入一个数到队尾
            q1.tail++;//队尾往后挪一位
        }
        for(i=1;i<=10;i++)
        {
        
            scanf("%d",&q2.data[q2.tail]);//读入一个数到队尾
            q2.tail++;//队尾往后挪一位
        }

四.**判断过程**

t=q1.data[q1.head];//打出一张牌
        flag=0;
        for(i=1;i<=s.top;i++)
        {
        
            if(t==s.data[i]){
        flag=1; break;}//枚举桌子上的牌逐一对比
        }
        if(flag==0)
        {
        
            //没能赢牌
            q1.head++;//打出的牌出队
            s.top++;//桌上的牌加1.
            s.data[s.top]=t;//打出的牌放在桌子上。
        }
        if(flag==1)
        {
        
            q1.head++;//打出了一张牌
            q1.data[q1.tail]=t;//把刚刚打出的牌收到手牌的末端
            q1.tail++;
            while(s.data[s.top]!=t)//把之间的牌也加入手牌
            {
        
                q1.data[q1.tail]=s.data[s.top];
                q1.tail++;
                s.top--;
            }
        }

五.**胜利条件判断**

while(q1.head<q1.tail&&q2.head<q2.tail)//两人手牌都不为空则进行游戏

六.**算法优化**  
判断能否赢牌这个算法要依次进行对比，复杂度高，我们可以开一个数组记录桌子上已经有那些牌了，类似于**桶排序**的用法。  
那么代码可以优化为：

int book[10];
    for(i=1;i<=0;i++)
    book[i]=0;
    t=q1.data[q1.head];
    if(book[t]==0)
    {
        
    q1.head++;
    s.top++;s.data[s.top]=t;
    book[t]=1;//标记桌上已经有了面额为t的牌
    }

七.完整代码

#include<bits/stdc++.h>
    struct queue
    {
        
        int data[1000];
        int head;
        int tail;
    };
    struct stack
    {
        
        int data[10];
        int top;
    };
    int main()
    {
        
        struct queue q1,q2;
        struct stack s;
        int i,t;
        int book[10];
        q1.head=1; q1.tail=1;
        q2.head=1; q2.tail=1;
        s.top=0;//初始阶段两人手中都没有牌，并且桌上也没有牌。
        for(i=1;i<=10;i++)
        {
        
            scanf("%d",&q1.data[q1.tail]);//读入一个数到队尾
            q1.tail++;//队尾往后挪一位
        }
        for(i=1;i<=10;i++)
        {
        
            scanf("%d",&q2.data[q2.tail]);//读入一个数到队尾
            q2.tail++;//队尾往后挪一位
        }
        while(q1.head<q1.tail&&q2.head<q2.tail)
        {
        t=q1.data[q1.head];//张兵出一张牌
        if(book[t]==0){
        //这张牌目前桌子上还没有
        q1.head++;//出队
        s.top++;s.data[s.top]=t;//入栈
        book[t]=1;//标记桌上已经有了面额为t的牌
    }
        else
        {
        
         q1.head++;
            q1.data[q1.tail]=t;
            q1.tail++;//收回t牌
            while(s.data[s.top]!=t)//收回t之间的牌
            {
        
                book[s.data[s.top]]=0;//取消标记
                q1.data[q1.tail]=s.data[s.top];
                q1.tail++;
                s.top--;
            }
            book[s.data[s.top]=s.data[s.top];//在收回另一张t牌
            q1.tail++;
            s.top--;
        }
        if(q1.head==q1.tail)break;//张兵没牌了，结束游戏，后面是一样的代码，只是第二个人的过程
        t=q2.data[q2.head];//小明出一张牌
        if(book[t]==0){
        
        q2.head++;
        s.top++;s.data[s.top]=t;
        book[t]=1;//标记桌上已经有了面额为t的牌
    }
        else
        {
        
         q2.head++;
            q2.data[q2.tail]=t;
            q2.tail++;
            while(s.data[s.top]!=t)
            {
        
                book[s.data[s.top]]=0;//取消标记
                q2.data[q2.tail]=s.data[s.top];
                q2.tail++;
                s.top--;
            }
            book[s.data[s.top]=s.data[s.top];
            q2.tail++;
            s.top--;
        }
        }
        if(q2.head==q2.tail)printf("张兵赢了")；
        else{
        printf("小明赢了");}
    }