实现约瑟夫环的操作.docx

建立一个有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);
}