#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;

// 創(chuàng)造一個包含41個人的單循環(huán)鏈表
// 并給她們按1~41開始編號
void CreatePersonList(PersonList* PL, int n)
{
    int length = 0;
    *PL = (PersonList)malloc(sizeof(Node));
    (*PL)->Next = *PL;
    (*PL)->num = length; // 頭結(jié)點(diǎn)數(shù)據(jù)域保存鏈表的長度 
    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; // 第一個人開始報數(shù)
    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()
{
    /*
        用循環(huán)鏈表模擬約瑟夫問題，把41個人自殺的順序編號輸出
    */
    PersonList pl;

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

    return 0;
}