数据结构学习(八)栈和队列案例分析

目录介绍:一、栈与队列的定义二、纸牌游戏的规则三、算法分析与实现四、算法优化

前面学习了栈和队列的基本原理,先回忆一下它们的作用:栈主要是解决子程序的调用和返回;而列队主要是解决先来先服务的问题。现在应用栈与队列的原理来解决现实中基本的案例。

一、栈与队列的定义

栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相反,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

队列(queue)是一种先进先出的线性表,简称FIFO。在表一端(表尾)插入,在另一端(表头)删除。表的插入操作称为入队,表的取出操作称为出队。

二、纸牌游戏的规则

记得小时候,我们很喜欢玩一种古老的游戏--小猫钓鱼,它的规则是:

将一副扑克牌平均分成两份,每人拿一份。A先拿出手中的第一张扑克牌放在桌上,然后B也拿出手中的第一张扑克牌,并放在A刚打出的扑克牌的上面。

出牌时,如果某人打出的牌与桌上某张牌的牌面相同,即可将两张相同的牌及其中间所夹的牌全部取走,并依次放在自己手中牌的末尾。当任何一人手中的牌全部出完时,游戏结束,对手获胜。

假如游戏开始时,A手中有6张牌,顺序为 2 4 1 2 5 6,B手中也有6张牌,顺序为 3 1 3 5 6 4,最终谁会获胜呢?

这里我们分析一下游戏有几种操作:分别是出牌和赢牌,用队列来模拟:出牌就是出队,赢牌就是入队,不管是A或是B都是同样的操作。而桌子就相当是一个栈,每打出一张牌放到桌子上就相当于入栈当有人赢牌时,取走桌面的牌,就相当出栈

三、算法分析与实现

根据以上分析,我们需要创建两个队列,一个栈来模拟整个游戏,首先创建一个队列结构来实现出牌及赢牌情况:

struct queue{int data[1000];int head;int tail;}

head 用来存储队头,tail 用来存储队尾。数组 data 用来存储队列中的元素,大小可以设置得更大一些,以防数组越界。

再创建一个结构体来实现栈,相当于放牌的桌子:

struct stack{int data[10];int top;};

top 用来存储栈顶,数组 data 用来存储栈中的元素,大小设置为10,因为这里假设只有9种不同的牌面,所以数组大小设置为10。

假设用q1来模拟A手中的牌,q2用来模拟B手中的牌,同时定义一变量s来放置桌面上的牌,定义以下:

struct queue q1,q2;struct stack s;

接着来初始化一下队列和栈:

//初始化队列q1和q2为空,此时两人手中都还没有牌q1.head=1;q1.tail=1;q2.head=1;q2.tail=1;//初始化栈s为空,最开始的时候桌上也没有牌s.top=0; 

然后读入A和B最初时手中的牌,分两次读入,分别插入q1,q2中

//先读入6张牌,放到 A 手上for(i=1;i<=6;i++){scanf("%d",&q1.data[q1.tail]);//读入一个数到队尾q1.tail++;//队尾往后挪一位 }  //再读入6张牌,放到B手上for(i=1;i<=6;i++){scanf("%d",&q2.data[q2.tail]);//读入一个数到队尾q2.tail++;//队尾往后挪一位 } 

程序准备工作基本上做好了,游戏正式开始,由A先出牌:

temp=q1.data[q1.head];

A打出第一张牌,也就是q1的队首,先将这张牌存放在临时变量temp中,判断桌上的牌与 temp 有没有相同的,枚举桌上的每一张牌与 temp 进行比对:

flag=0;for(i=1;i<=top;i++){if(temp==s[i]){flag=1;break;}}

如果 flag 的值为 0 就说明A没能赢得桌上的牌,将打出的牌留在桌上。

if(flag==0){//A 此轮没有赢牌q1.head++;//A已经打出一张牌,所以要把打出的牌出队 s.top++;s.data[s.top]=temp; //再把打出的牌放到桌上,即入栈 }

如果 flag 的值为 1,就表明 A 可以赢得桌上的牌,注意:首先把刚才打出的牌先放到手中牌的末尾,再把将赢得的牌依次放入 A 的手中。

if(flag==1){//A 此轮可以赢牌q1.head++;// A 已经打出一张牌,所以要把打出的牌出队q1.data[q1.tail]=temp;//因为此轮可以赢牌,所以紧接着把刚才打出的牌又放到手中牌的末尾q1.tail++;while(s.data[s.top]!=temp)//把桌上可以赢得的牌(从当前桌面最顶部的一张牌开始取,直到取到与打出的牌相同为止//依次放到手中牌的末尾{q1.data[q1.tail]=s.data[s.top];//依次放入队尾q1.tail++;s.top--;//栈中少了一张牌,所以栈顶要减 1  } } 

A出牌的所有步骤模拟完了,B的出牌结果也是这样,接下来要判断游戏怎么结束?两个人中只要一个人的牌出完了,游戏也就结束了。因此,需要在模拟两人出牌代码的外面加一个while循环来判断。

while(q1.head

最后一步,打印出谁最终赢得了游戏,以及游戏结束后获胜者手中的牌和桌上的牌。假如A获胜了那么B的手中一定是没有牌了(队列q2 为空)。

if(q2.head==q2.tail){printf("A赢了
");printf("A当前手中的牌是");for(i=q1.head;i<=q1.tail-1;i++)    printf(" %d",q1.data[i]);if(s.top>0)//如果桌上有牌则依次输出桌上的牌{printf("
桌上的牌是");for(i=1;i<=s.top;i++) printf(" %d",s.data[i]); } else {    printf("
桌上已经没有牌了");   }

四、算法优化

在上面算法分析中,判断能否赢牌,是通过枚举桌上每一张牌来实现的,即用了一个for循环来依次判断桌上的每一张牌是否与打出的牌相同。其实这个步骤还可以优化,就是用一个数组来记录桌上有哪些牌,因为牌面有9种,就是1-9,因此:int book[10]。

刚开始桌面上一张牌也没有,所以book[1]-book[10]都初始化为0:

for(i=1;i<=9;i++) book[i]=0;

接着,如果桌面增加一张牌面为“3”的牌,那就需要将book[3]设置为1,表示桌面已经有“3”的这张牌。如果这张“3”的牌被拿走,book[3]重新设置为0。

if(book[temp]==0)//表明桌上没有牌面为 temp 的牌{//A 此轮没有赢牌q1.head++;//A 已经打出一张牌,所以要把打出的牌出队 s.top++;s.data[s.top]=t;//再把打出的牌放到桌上,即入栈book[temp]=1;//标记桌上现在已经有牌面为 t 的牌 } 

小猫钓鱼游戏算法讨论这里,具体实现方法都说完了,下面给合完整代码:

#include 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 book[10];    int i,temp;    //初始化队列    q1.head=1;    q1.tail=1;    q2.head=1;    q2.tail=1;    //初始化栈    s.top=0;    //初始化用来标记的数组,用来标记哪些牌已经在桌上    for(i=1;i<=9;i++)        book[i]=0;    //依次向队列插入6个数    // A手上的6张牌    for(i=1;i<=6;i++){        scanf("%d",&q1.data[q1.tail]);        q1.tail++;    }    //B手上的6张牌    for(i=1;i<=6;i++){        scanf("%d",&q2.data[q2.tail]);        q2.tail++;    }    while(q1.head0)        {            printf("
桌上的牌是");            for(i=1;i<=s.top;i++)                printf(" %d",s.data[i]);        }        else            printf("
桌上已经没有牌了");    }    else{        printf("B赢了
");        printf("B当前手中的牌是");        for(i=q2.head;i<=q2.tail-1;i++)            printf(" %d",q2.data[i]);        if(s.top>0){            printf("
桌上的书是");            for(i=1;i<=s.top;i++)                printf(" %d",s.data[i]);        }        else            printf("
桌上已经没牌了");    }    return 0;}

测试结果如下:

【参考文献】数据结构(C语言版)、《啊哈!算法》

发表评论
留言与评论(共有 0 条评论) “”
   
验证码:

相关文章

推荐文章