单链表解决约瑟夫问题
代码实现：
#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
typedef struct Node
{
DataType data;
struct Node *next;
}ListNode, *LinkList;
LinkList CreateCycList(int n){
LinkList head = NULL;
ListNode *s, *r;
int i;
for (i = 1; i <= n; i++)
{
s = (ListNode*)malloc(sizeof(ListNode));
s->data = i;
s->next = NULL;
if (head == NULL)
head = s;
else
r->next = s;
r = s;
}
r->next = head;
return head;
}
void DisplayCycList(LinkList head){
ListNode *p;
p = head;
if (p == NULL)
{
printf("该链表是空表");
return;
}
while (p->next != head)
{
printf("%2d", p->data);
p = p->next;
}
printf("%2d\n", p->data);
}
void Josephus(LinkList head, int n, int m, int k) {
ListNode *p, *q;
int i;
p = head;
for (i = 1; i<k; i++)
{
q = p;
p = p->next;
}
while (p->next != p)
{
for (i = 1; i<m; i++)
{
q = p;
p = p->next;
}
q->next = p->next;
printf("%2d", p->data);
free(p);
p = q->next;
}
printf("%2d\n", p->data);
}
void main(){
LinkList h;
int n, k, m;
printf("输入环中人的个数，n=");
scanf("%d", &n);
printf("输入开始报数的序号，k=");
scanf("%d", &k);
printf("报数为m的人出列，m=");
scanf("%d", &m);
h = CreateCycList(n);
Josephus(h, n, m, k);
}。