魔术师发牌问题 解法

计机羊咩咩

我自己也不造写得好不好撒  有疑问或者建议请积极联系我撒  {:1_1:}
希望下列源码能帮助到各位  (最好拉到编译器debug分析  光看代码看不到啥)

下面是魔术师发牌问题：

人工倒推的方法是：在桌子上放13空盒子排成一圈，从1开始顺序编号，将黑桃A放入1号盒子中，从下一个空盒子开始对空的盒子计数，当数到第二个空盒子时，将黑桃2放入空盒子中，然后再从下一个空盒子开始对空盒子计数，顺序放入3、4、5...，直到放入全部3张牌。注意在计数时要跳过非空的盒子，只对空盒子计数。最后牌在盒子中的顺序，就是魔术师手中原来牌的顺序。

魔术师发牌问题其实是约瑟夫问题的另一面   解法相似！

源代码：
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX 13

typedef struct List
{
        int Num;
        int Size;
        struct List *Next;
}LIST;

LIST *CreateList(void);
void Magic(LIST *Tail);
void DestroyList(LIST *Head);
int main(void)
{
        LIST *Tail;
        Tail = CreateList();
        Magic(Tail);
        DestroyList(Tail);
        return 0;
}

LIST *CreateList(void)
{
        //此函数创建环链表后返回链尾！
       
        LIST *Head,*Tail,*Temp;
        int Count = 1;
        if (NULL == (Temp = malloc(sizeof(LIST))))
        {
                printf("Creating failure!\n");
                exit(1);
        }

        Head = Temp;
        Head->Num = FALSE;
        Head->Size = Count++;
        while (Count <= MAX)                       //1开始  13结束  刚好13个数
        {
                if (NULL == (Temp->Next = malloc(sizeof(LIST))))
                {
                        printf("No more memory!\n");
                        exit(1);
                }

                Temp = Temp->Next;
                Temp->Num = FALSE;
                Temp->Size = Count++;
        }
        Tail = Temp;
        Temp->Next = Head;
        printf("Creating completed!\n");

        return Tail;
}

void Magic(LIST *Tail)
{
        LIST *Flag = Tail,*Head = Tail->Next;
        int Gap = 1;

        while (Gap <= MAX)
        {
                for (int Turn = 1; Turn < Gap; Turn++)
                {
                        Head = Head->Next;
                        while(FALSE != Head->Num)            //关键1！！！
                                Head = Head->Next;                 //排除已存在值的节点，从下一个不存在值得节点开始计算！
                }
                Head->Num = Gap++;                //间距增加
                while (FALSE != Head->Num && Gap <= MAX)    //关键2！！！   不加Gap <= MAX的话  当链表填满后会出现死循环
                        Head = Head->Next;                // 获取下一个空值的节点
        }
       
        Head = Flag->Next;
        while (Flag != Head)                   //这个循环不会输出最后一个节点的信息
        {
                printf("%d(%d) ",Head->Num,Head->Size);
                Head = Head->Next;
        }
        printf("%d(%d)\n",Head->Num,Head->Size);      //输出最后一个节点的信息
}

void DestroyList(LIST *Head)            //释放环链表  通用函数
{
        LIST *Flag = Head, *Temp = Head->Next;

        while (1)
        {
                if (Flag == Temp)break;
                else if (NULL == Flag || NULL == Temp)
                {
                        printf("There is no loop chain!\n");
                        exit(1);
                }
                Temp = Temp->Next->Next;
                Flag = Flag->Next;
        }

        Flag = Head;
        Temp = Head = Head->Next;           //从“标记”节点的下一个节点开始循环释放

        while (Flag != Head)
        {
                Head = Head->Next;
                free(Temp);
                Temp = Head;
        }
        free(Flag);
        printf("\nRelease completed!\n");
}