这可能是史上最详细的『小猫钓鱼』代码解析

in 算法编程

『小猫钓鱼』这名字是我高中时同学告诉我的,我都叫『排火车』,小时候经常和我奶奶玩。规则超级简单,一副牌,两个人平分,牌面朝下,每人只能出手中最上面的牌,已出的牌叠加排放,若正在出的手牌与已出的叠放牌中任一数字相同,则获得从与自己手牌相同数字的牌开始,到最下面的牌(包括中间),赢得的牌放入手牌的最下面,直到一方没有手牌,游戏结束。

小猫钓鱼

像这样,如果你即将出手的牌是5,你发现原牌中有5,那么你将获得从5开始的:5、10、8、7、5这5张牌,放入手牌的最下面,然后再出一张牌。

根据出牌和收牌的规则,可以抽象为两个模型:

叠放牌 -> 栈
手牌 -> 队列

手牌的队列模型定义为:

// 队列节点
typedef struct LinkNode{
    int data;
    struct LinkNode *next;
}LinkNode;

// 头指针和尾指针
typedef struct{
    LinkNode *front,*rear;
    char *name;    // 玩家名字
}LinkQueue;

叠放牌的栈模型为:

// 声明火车节点
typedef struct TrainNode{
    int data;
    struct TrainNode *next;
}TrainNode,*TrainStack;

有了模型定义,接下来要对其初始化,以进行游戏。

// 初始化两个玩家的队列
void initQueue(LinkQueue &player_1,LinkQueue &player_2){
    player_1.front = player_1.rear = (LinkNode*)malloc(sizeof(LinkNode));
    player_1.front->next = NULL;
    player_1.front->data = 0;
    player_1.name = "小明";
    player_2.front = player_2.rear = (LinkNode*)malloc(sizeof(LinkNode));
    player_2.front->next = NULL;
    player_2.front->data = 0;
    player_2.name = "小红";
}

// 初始化火车
void initTrain(TrainStack &train){
    train = (TrainStack)malloc(sizeof(TrainNode));
    train -> data = 0;    // 头节点存储长度
    train -> next = NULL;
}

准备好这些,就要给两位玩家发牌,不牵扯什么洗牌算法,直接暴力分牌,即给两个队列赋上几个初始值,后面出牌、收牌时还会继续给队列赋值,因此可以定义一个添加元素到队列的函数:

// 添加元素到队列
void addQueue(LinkQueue &q,int data){
    LinkNode *node = (LinkNode*)malloc(sizeof(LinkNode));
    node->data = data;
    node->next = NULL;
    q.rear->next = node;
    q.rear = node;
    q.front->data++;
}

有了这个函数,可以继续写初始化玩家手牌的函数:

// 发牌
void deal(LinkQueue &player_1,LinkQueue &player_2){
    int i,p1[5] = {1,2,3,4,5},p2[5] = {4,2,5,1,3};
    for(i = 0;i < 5;i++){
        addQueue(player_1,p1[i]);
        addQueue(player_2,p2[i]);
    }
}

接下来就该你一张我一张地出牌了,也就是火车加节点删手牌,再写个函数:

// 给火车加节点,栈push操作
void pushTrain(TrainStack t_stack,int data){
    TrainNode *node = (TrainNode*)malloc(sizeof(TrainNode));
    node->data = data;
    node->next = t_stack->next;
    t_stack->next = node;
    t_stack->data++;
}
// 删除头元素并返回
int delQueue(LinkQueue &q){
    int re;
    if(q.front->data == 0)
        return 0;
    LinkNode *node = q.front -> next;
    q.front -> next = node->next;
    q.front->data--;
    re = node->data;
    free(node);
    return re;
}

给火车加节点是个持续循环的过程,而加节点的过程是你一张我一张进行的,为了区分,需要加一个Flag来标识该谁出牌了,现在,我们可以写出如下代码:

bool game_status = true;    // true时玩家1出牌,false时玩家2出牌
while(true){
    if(game_status){
        num = delQueue(player_1);
        pushTrain(t_stack,num);
        game_status = false;
    }else{
        num = delQueue(player_2);
        pushTrain(t_stack,num);
        game_status = true;
    }
    getchar();
}

这里用了while(true)来循环,但游戏总有结束的时候,结束的标识是一方没有手牌,也就是队列为空,再写一个判断游戏是否结束的函数:

// 判断游戏是否结束
bool check(LinkQueue player_1,LinkQueue player_2){
    if(player_1.front->data == 0){
        printf("\n%s胜!\n",player_2.name);
        return false;
    }else if(player_2.front->data == 0){
        printf("\n%s胜!\n",player_1.name);
        return false;
    }else
        return true;
}

刚才的while(true)可以改进为:

while(check(player_1,player_2)){
  ……
}

为了方便查看玩家手牌和叠放牌的当前情况,我们可以再写两个函数对其输出:

// 输出叠放牌
void printTrain(TrainStack train){
    TrainNode *t = train->next;
    int i = 0;
    printf("\n当前火车情况:");
    for(;i < train->data;i++,t = t -> next)
        printf("%d  ",t -> data);
}
// 输出玩家手牌
// 输出玩家手牌
void printer(LinkQueue q){
    LinkNode *node;
    printf("\n当前玩家{%s}情况:",q.name);
    for(node = q.front->next;node != NULL;node = node->next)
        printf("%d  ",node->data);
}

写完这些,程序会像这样运行:

小猫钓鱼-判断游戏结束

现在就剩最后一个步骤了,判断叠放牌中有没有自己即将放入的牌,有的话就收走,没有就算了,这里牵扯到三个操作:

  1. 遍历栈
  2. 删除栈元素
  3. 加入队列

遍历栈的时候有个注意点,因为玩家是将手中的牌放入叠放牌后,才检查能不能收牌,所以遍历栈的动作是在出牌之后,并且如果能收牌,需要再出一张牌,因此这个操作用do while循环比较容易实现,代码再改进就是:

while(check(player_1,player_2)){
    int num;
    if(game_status){
        do{
            num = delQueue(player_1);
            pushTrain(t_stack,num);
        }while(遍历栈());
        game_status = false;
    }else{
        do{
            num = delQueue(player_2);
            pushTrain(t_stack,num);
        }while(遍历栈());
        game_status = true;
    }
    printTrain(t_stack);
    printer(player_1);
    printer(player_2);
    getchar();
}

遍历栈函数也很容易写出:

bool findTrain(TrainStack t_stack,int data,LinkQueue &q){
    TrainNode *node = t_stack->next->next;
    while(node != NULL){
        if(node->data == data)
            return true;
        node = node->next;
    }
    return false;
}

这里还有个问题,这个遍历函数检测到可以收牌时仅仅返回True,我们还需要有个收牌的动作,遍历栈时检测到可以收牌时就直接调用收牌函数:

bool findTrain(TrainStack t_stack,int data,LinkQueue &q){
    TrainNode *node = t_stack->next->next;
    while(node != NULL){
        if(node->data == data){
            收牌();
            return true;
        }
        node = node->next;
    }
    return false;
}

收牌函数:

void getTrainNode(TrainStack &t_stack,int data,LinkQueue &q){
    int num = popTrain(t_stack);
    addQueue(q,num);    // 将刚放进去的手牌收回
    while(t_stack->next->data != data){
        num = popTrain(t_stack);
        addQueue(q,num);
    }
    num = popTrain(t_stack);
    addQueue(q,num);    // 跟第一次收回的牌相同的牌
}

当然,收牌了就得从叠放牌中删除这张牌,也就是出栈操作:

int popTrain(TrainStack &t_stack){
    if(t_stack->data == 0)
        return 0;
    TrainNode *node = t_stack->next;
    t_stack->next = t_stack->next->next;
    t_stack->data--;
    int num = node->data;
    free(node);
    return num;
}

至此,所有操作完成,执行结果像这样:

小猫钓鱼-完成

Responses
  1. 替天行盗

    好文,拜读,以后常看学习。

    Reply
  2. 小猫钓鱼

    这确实是我见过最详细的小猫钓鱼代码实现了,感谢博主

    Reply