#include "stdio.h"
#include "stdlib.h"
typedef struct LNode
{
int pwd;//每个人所持有的密码
int num;//每个人的编号
struct LNode *next;
}LNode,*cirLinkList;
void CreateLinkList(cirLinkList &L, int n)//构造链表并初始化
{
L=(cirLinkList)malloc(sizeof(LNode));
if (!L)
{
printf("\n初始化链表失败!!\n");
exit(1);
}
L->next=L;//构造循环
L->num=1;
printf("请输入第1个人的密码: ");
scanf("%d",&L->pwd);
printf("\n");
cirLinkList p,q;
q=L;
for ( int i=2;i<=n;i++)
{
printf("请输入第%d个人的密码: ",i);
p=(LNode *)malloc(sizeof(LNode));
if (!p)
{
printf("\n申请空间失败!!\n");
exit(1);
}
scanf("%d",&p->pwd);
p->num=i;
L->next=p;
L=p;
printf("\n");
}
L->next=q;
printf("\n");
}
void main()
{
cirLinkList L,p,q;
int n,x;
L=NULL;
printf("请输入总人数:");
scanf("%d",&n);//总共的人数n
printf("\n");
printf("请输入初始报数上限的值:");
scanf("%d",&x);//初始密码为x
printf("\n");
CreateLinkList(L,n);//建立约瑟夫环
p=L;
printf("出列顺序为: ");
for (int i=1;i<=n;i++)
{
for (int j=1;j<x;j++)
{
p=p->next;//指针移动到第x个结点处
}
q=p->next;
x=q->pwd;//把要删除的人的密码作为新密码
printf("%d ",q->num);
p->next=q->next;//删除结点
free(q);//释放结点q
}
printf("\n\n");
}