约瑟夫问题-循环链表解法

pwnmelife

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

#define ElementType int

typedef struct Node {
        ElementType data;
        struct Node* next;
} Node, *LinkList;

void InitCreateLinkLoopList(LinkList* L);
void CreateLinkLoopList(LinkList* L, int n);
void Josephus(LinkList* L);

/*
 * 3->6->9->12->15->18->21->24->27->30->33->36->39->1->5->10->14->19->23->28->32->37
 * ->41->7->13->20->26->34->40->8->17->29->38->11->25->2->22->4->16->35->31
 */

int main() {
        LinkList* L = (LinkList*)malloc(sizeof(LinkList));
        InitCreateLinkLoopList(L);
        CreateLinkLoopList(L, 41);
        Josephus(L);
        return 0;
}
void InitCreateLinkLoopList(LinkList* L) {
        (*L) = (LinkList)malloc(sizeof(Node));
        (*L)->data = 41;
        (*L)->next = (*L);
}
void CreateLinkLoopList(LinkList* L, int n) {
        LinkList p, r;
        p = (*L);

        for (int i = 1; i <= n; i++) {
                r = (LinkList)malloc(sizeof(Node));
                r->next = p->next;
                r->data = i;
                p->next = r;
                p = r;
        }
}
void Josephus(LinkList* L) {
        LinkList p, r, q;
        r = p = (*L);
        int times = 1;
        int number = 1;
        while (1) {
                for (times = 1; times <= 3; times++) {
                        p = p->next;
                        if ((r == p)||!p->data) {
                                times--;
                        }
                }
                printf("%d ", p->data);
                p->data = 0;
                number++;
                if (number == 42) {
                        break;
                }
        }
}