2020-08-21[单循环链表解决魔术师发牌问题]

#include <stdio.h>
#include <stdlib.h>

/**
    单循环链表解决魔术师发牌问题
    */

#define CardNumber 13

typedef struct Node
{
    int data;
    struct Node *Next;
} List;
typedef struct Node* LinkList;

// 创建一个数据域全为0的包含13个元素的单循环链表
void CreateLinkList(LinkList *L)
{
    *L = (LinkList)malloc(sizeof(List));
    LinkList pHead = *L;
    for(int i = 1; i <= CardNumber; i++){
        LinkList pNew = (LinkList)malloc(sizeof(List));
        pNew->data = 0;
        pHead->Next = pNew;
        pHead = pNew;
    }
    pHead->Next = (*L)->Next;
}

// 打印链表
void PrintLinkList(LinkList L)
{
    LinkList p = L->Next;

    while(p->Next != L->Next){
        printf("%d ", p->data);
        p = p->Next;
    }
    printf("%d ", p->data);
    printf("\n");
}

// 魔术师问题算法
// 解决思路：给13张牌赋值，如果遇到已经赋值过的，则跳过，直到13张牌全部赋值完毕结束
void Magician(LinkList *L)
{
    int CountNumber = 2;
    LinkList p = (*L)->Next; // 取第一张牌
    p->data = 1;             // 把1给了他

    while(1){
            // 找第CountNumber张牌
        for(int i = 0; i < CountNumber; i++){
            p = p->Next;
            // 如果翻到的牌有值，则跳过此牌
            if(p->data != 0){
                i--;
            }
        }

        // 如果找到了且牌上无值，则给这张牌赋值
        if(p->data == 0){
            p->data = CountNumber;
            CountNumber++;
            // 如果13张全部赋值，则退出
            if(CountNumber == 14){
                break;
            }
        }
    }
}

int main()
{
    LinkList LL;
    CreateLinkList(&LL);
    Magician(&LL);
    PrintLinkList(LL);
    return 0;
}