循环链表：魔术师发牌问题

偏执的太偏执、 2022-06-01 02:43 167阅读 0赞

# 魔术师发牌问题介绍 #

魔术师发牌问题的简介：一位魔术师掏出一叠扑克牌，魔术师取出其中13张黑桃，洗好后，把牌面朝下。  
说：“我不看牌，只数一数就能知道每张牌是什么？”魔术师口中念一，将第一张牌翻过来看正好是A；  
魔术师将**黑桃A放到桌上**，继续数手里的余牌，  
第二次数1，2，将第一张牌放到这叠牌的下面，将**第二张牌翻开，正好是黑桃2，也把它放在桌子**上。  
第三次数1，2，3，前面二张牌放到这叠牌的下面，**取出第三张牌，正好是黑桃3，**这样依次将13张牌翻出，全部都准确无误。  
求解：魔术师手中牌的原始顺序是什么样子的？

# 魔术师发牌问题分析 #

每数一张没有翻的牌 将其放到这叠牌的下面，不就形成了一个**循环链表**吗，**将翻开的牌 就是知道点数的牌 放桌子上，不就是在循环链表中跳过已经知道数据的结点么，该结点不算作数牌数量中**。

我们只需要将魔术师翻牌的情况反映到牌的点数，也就是我们结点的data数据就ok，结束条件就是数牌 数到第13次 就结束。

**以下三点一定要明确**

**1、采用循环链表进行数据的填充。**

**2、翻过得牌放桌子上，就是有数据的牌 不算作数牌数量，这一点一定要明确，代码中有体现。**

**3、第13次数完 就结束了，所有牌的数据已经填充完毕。**

# 魔术师发牌代码展示 #

代码很详细，只要清晰知道发牌情况的本质，代码就呼之欲出了。

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #define OK 1
    #define ERROR 0
    
    typedef struct Node
    {
    	int data;
    	struct Node* next;
    } Node,*LinkList;
    /*
    创建循环链表
    */
    int CreateCard(Node** circle_list, int num)
    {
    	//创建循环链表头结点
    	Node* head = (Node*)malloc(sizeof(Node));
    	Node* temp = head;// temp 移动指针，指向环中的结点，刚开始指向头结点
    	int i = 0;
    	//创建num个结点的循环链表
    	while (i < num)
    	{
    		//创建新结点并初始化数据
    		Node* node = (Node*)malloc(sizeof(Node));
    		if (node == NULL)
    		{
    			exit(0);
    		}
    
    		node->data = 0;
    		node->next = NULL;
    
    		//将结点加入到链表中
    		temp->next = node;
    		temp = node;
    		i++;
    	}
    	//循环结束 temp 指向最后一个结点
    	//将最后一个结点 指向环中第一个结点，就构成了一个不带头结点的循环单链表
    	temp->next = head->next;
    	//循环链表指向第一个结点
    	*circle_list = head->next;
    
    	//释放头结点
    	free(head);
    	return OK;
    }
    /*
    魔术师发牌情况体现到循环链表的结点数据上。
    魔术师发牌问题的简介：一位魔术师掏出一叠扑克牌，魔术师取出其中13张黑桃，洗好后，把牌面朝下。
    说：“我不看牌，只数一数就能知道每张牌是什么？”魔术师口中念一，将第一张牌翻过来看正好是A；
    魔术师将黑桃A放到桌上，继续数手里的余牌，
    第二次数1，2，将第一张牌放到这叠牌的下面，将第二张牌翻开，正好是黑桃2，也把它放在桌子上。
    第三次数1，2，3，前面二张牌放到这叠牌的下面，取出第三张牌，正好是黑桃3，这样依次将13张牌翻出，全部都准确无误。
    求解：魔术师手中牌的原始顺序是什么样子的？
    */
    int Magician(Node* circle_list)
    {
    	//node指向循环链表
    	Node* node = circle_list;
    	//根据发牌规则，给牌赋值
    	//第一张牌 是1
    	node->data = 1;
    	//数牌的数量，初始化为2 ，数牌数量<=13
    	int cardnum = 2;
    
    	while (1)
    	{
    		//循环进行数牌,注意已经翻过得牌放到桌子上
    		for (size_t i = 0; i < cardnum; i++)
    		{
    			node = node->next;
    			//说明此张牌有数据，已经被翻过，不算作数牌数量
    			if (node->data != 0)
    			{
    				i--;
    			}
    		}
    		//被翻牌的牌点数 = 数牌的数量，第二次 数2张 ，翻第二张 为黑桃2；第三次 数3张 翻第三张 为黑桃3...
    		node->data = cardnum;
    		//牌已经数完了
    		if (cardnum == 13)
    		{
    			break;
    		}
    		cardnum++;
    	}
    	return OK;
    }
    //展示牌的点数
    int ShowCards(Node* circle_list)
    {
    	Node* node = circle_list;//node为移动指针，node 开始指向循环链表第一个结点
    	//循环链表遍历完判断，尾结点的指针域指向第一个结点
    	while (node->next != circle_list)
    	{
    		printf("黑桃:%d\n",node->data);
    		node = node->next;
    	}
    
    	return OK;
    }
    
    int main(int argc, char *argv[])
    {
    	Node* circle_list = NULL;
    	//创建13空牌
    	CreateCard(&circle_list, 13);
    	//根据魔术师翻牌的结果，给牌填充数据
    	Magician(circle_list);
    	//展示牌的点数
    	ShowCards(circle_list);
    	return 0;
    }

# 魔术师发牌问题结果 #

![SouthEast][]

[SouthEast]: /images/20220601/67e41e2ae7034519b2deacc4226d5fc7.png