约瑟夫问题-循环链表解法
#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;
}
}
}
页:
[1]