#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node
{
    int num;
    struct Node* Next;
} Person;

typedef struct Node* PersonList;

// 创造一个包含41个人的单循环链表
// 并给她们按1~41开始编号
void CreatePersonList(PersonList* PL, int n)
{
    int length = 0;
    *PL = (PersonList)malloc(sizeof(Node));
    (*PL)->Next = *PL;
    (*PL)->num = length; // 头结点数据域保存链表的长度 
    PersonList pHead = *PL;
    PersonList pNew;
    int i = 1;
    while(i <= n){
        length++; 
        pNew = (PersonList)malloc(sizeof(Node));
        pNew->num = i++;
        pHead->Next = pNew;
        pHead = pNew;
    }

    pNew->Next = (*PL)->Next;
    (*PL)->num = length;
}

// 打印链表
void PrintList(PersonList L)
{
    PersonList pt = L->Next;

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

// 约瑟夫问题
// 打印死亡编号
void PrintDeadNo(PersonList *PL)
{
    PersonList p = *PL; // 第一个人开始报数
    PersonList q;
    int i = 0;
    
    printf("死者编号：");
    while (p != p->Next) {
        p = p->Next;
        i++;
        if (i == 2) {
            i = 0;
            q = p->Next;
            printf("%d ", q->num);
            p->Next = q->Next;
            free(q);
            (*PL)->num--;
            if((*PL)->num < 3){
                break;
            }
        }
    }
    printf("\n幸存者：");
    for(int i = 0; i < (*PL)->num; i++){
        q = p->Next;
        printf("%d ", q->num);
        p->Next = q->Next;
    }
    printf("\n");
}

int main()
{
    /*
        用循环链表模拟约瑟夫问题，把41个人自杀的顺序编号输出
    */
    PersonList pl;

    CreatePersonList(&pl, 41);
    
    PrintDeadNo(&pl);

    return 0;
}