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

in 算法编程 with 2 comments

小猫钓鱼算法

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

小猫钓鱼

像这样，如果你即将出手的牌是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;
}

至此，所有操作完成，执行结果像这样：

小猫钓鱼-完成

本文由 花墨 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Apr 6, 2017 at 04:51 pm

← → ↓ ↑
Responses

captcha
请输入验证码

  1. 替天行盗

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

    Reply
  2. 小猫钓鱼

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

    Reply