约瑟夫环的问题
#include<stdio.h>#include<stdlib.h>
typedef void Status;
typedef int ElemType;
typedef struct CLnode
{
ElemType data;
struct CLnode *next;
}CLnode,*CLinkList;
Status InitList(CLinkList &L)
{
L=(CLinkList)malloc(sizeof(CLnode));
L->next=NULL;
}
Status CreateList_L(CLinkList &L,int n)//建立链表
{
CLinkList p;
int i;
InitList(L);
for(i=n;i>0;i--)
{
p=(CLinkList)malloc(sizeof(CLnode));
scanf("%d",&p->data);
p->next=L->next;
L->next=p;
}
}
Status ReverseList_L(CLinkList &L,int n)//倒置
{
CLinkList p;
CLinkList a;
CLinkList b;
a=L;
p=a->next;
a->next=NULL;
b=p->next;
p->next=a;
a=p;
p=b;
while(p->next!=NULL)
{
b=p->next;
p->next=a;
a=p;
p=b;
}
p->next=a;
L->next=p;
p=L->next;
}
Status JOSEPHUS(CLinkList &L,int n,int k,int m)//约瑟夫环环
{
CLinkList p;
CLinkList r;
int i;
p=L->next;
for(i=0;i<k;i++)
{
p=p->next;
}
while(p->next!=p)
{
for(i=0;i<m;i++)
{
if(p->next!=NULL)
{r=p;
p=p->next;}
else
{
p->next=L->next;
r=p;
p=p->next;
}
}
p=p->next;
r->next=p->next;
free(p);
p=r->next;
}
printf("\n最后被删除的元素是：%4d\n",p->data);
}
void main()
{
int n,m,k;
printf("请输入元素的个数:");
scanf("%d",&n);
CLinkList L;
CreateList_L(L,n);
ReverseList_L(L,n);
printf("请输入开始报数的人的序号:");
scanf("%d",&k);
printf("请输入出列者喊出的数:");
scanf("%d",&m);
JOSEPHUS(L,n,k,m);
}
约瑟夫环无法实现??
