数据结构-循环单链表之魔术师发牌问题

Dear 丶 2022-05-25 08:05 135阅读 0赞

问题描写叙述：

魔术师手中有A、2、3……J、Q、K十三张黑桃扑克牌。在表演魔术前，魔术师已经将他们依照一定的顺序叠放好（有花色的一面朝下）。魔术表演过程为：一開始，魔术师数1，然后把最上面的那张牌翻过来，是黑桃A；然后将其放到桌面上；第二次,魔术师数1、2；将第一张牌放到这些牌的最以下，将第二张牌翻转过来，正好是黑桃2；第三次，魔术师数1、2、3；将第1、2张牌依次放到这些牌的最以下，将第三张牌翻过来正好是黑桃3；……直到将全部的牌都翻出来为止。问原来牌的顺序是怎样的。

接下来通过c语言简单实现：

#include "stdafx.h"
    #include "stdlib.h"
    
    //声明一个单链表结构体
    typedef struct LNode {
    	int data;		//数据域，数据域的类型为泛型（ElementType）
    	LNode *next;	//指针域,指向下一个node的地址
    }LNode, *LinkList;	//声明2个结构体别名（结构体别名和结构体指针别名），方便在外部直接通过别名定义该结构体类型的变量

/*
    魔术师发牌问题：循环单链表
    */
    /*
    初始化循环单链表n个节点数据为0
    */
    LinkList initList(int n) {
    	if (n < 1) {
    		return NULL;
    	}
    	LNode *s;
    	LNode *p;
    	p = NULL;
    	LNode *r = NULL;
    	int j = 1;
    	while (j<=n)
    	{
    		s = (LinkList)malloc(sizeof(LNode));
    		s->data = 0;
    		if (p == NULL) {
    			p =r = s;
    		}
    		else
    		{
    			r->next = s;
    			r = s;
    		}
    		j++;
    	}
    	r->next = p;
    	return p;
    }
    
    /*
    根据算法规则对相应位置进行数据填充
    */
    LinkList magic(int n) {
    	LNode *L;
    	LinkList p =initList(n);
    	L = p;
    	int j = 1;
    	while (true)
    	{	
    		//第一个节点数据为1
    		if (j == 1) {
    			p->data = j;
    			j++;
    			continue;
    		}
    		int k = j;//临时存储节点需要偏移的次数
    		for (int i = 1; i <= k; i++)
    		{		
    			p = p->next;
    			if (p->data != 0) {
    				//判断该节点是否已有数据，如果有则需要跳过该节点即多向后移动一次
    				k++;
    			}
    		}
    		p->data = j;//赋值
    		j++;
    		if (j > n) {
    			break;
    		}
    	}
    	return L;
    }

主函数：

void main() {
    	int n = 10;
    	LinkList L = magic(n);
    	int j = 1;
    	while (L!=NULL)
    	{
    		printf_s("%d\t", L->data);
    		if (j < n) {
    			L = L->next;
    		}
    		else
    		{
    			break;
    		}
    		j++;
    	}
    }

输出结果：

![70][]

以上只是我个人设计的一种实现，如果发散思维肯定还有很多种写法呢！

[70]: /images/20220525/a2fc873cf5c643cda2524694f0957615.png