建立一个有n个结点的循环链表，每个人用链表的一个结点描述。用指针P指向第一个报数的人的位置（编号为k）,用链表模拟从1到m的报数，然后删除报数为m的结点，直到链表中仅剩下一个结点时结束，最后依次输出被删除结点的编号值。 例如n=6，m=5，被删除的结点顺序是：5，4，6，2，3，1。
#include <stdio.h>
#include <malloc.h>
typedef struct Node
{
int data; //数据域
struct Node *next; //指针域
}Node;
void Josephu(int n,int k,int m)
{
Node *head,*p,*q;
int i;
head=NULL; //头指针为空
for(i=1;i<=n;i ) //建立一个循环链表
{
p=(Node*)malloc(sizeof(Node)); //向计算机索要空间
p->data=i; //为新节点的数据域编号
if(head==NULL) //如果头为空
head=p; //p为头
else
q->next=p; //q的下一个为p
q=p; //q变成了新的p
}
p->next=head; //p的下一个成为了头
p=head; //p为head
for(i=1;i<k;i ) //p指向编号为k的结点
{
q=p; //在整个循环链表里面不断移动
p=p->next;
}
printf("出列顺序依次为: ");
while(p!=q) //不断循环数数，将第m个结点删掉
{
for(i=1;i<m;i )
{
q=p;
p=p->next;
}
q->next=p->next; //把结点p删除
printf("%4d",p->data);
free(p); //释放p的空间
p=q->next; //p指向新的结点
}
printf("%4d\n",p->data);
}
void main()
{
int n,k,m;
printf("输入n的值: ");
scanf("%d",&n);
printf("输入k的值: ");
scanf("%d",&k);
printf("输入m的值: ");
scanf("%d",&m);
Josephu(n,k,m);
}
评论