数据结构约瑟夫循环
#include <stdio.h>
typedef struct Node
{
int data;
struct Node * next;
}Node,*LinkList;
/**********创建约瑟夫环****************
* *
* 参数：单链表头指针CL，结点个数n *
* *
* 返回值：返回头指针 *
* *
**************************************/
LinkList InitRing(int n)
{
LinkList CL;
Node *p,*q;
int i;
CL=p=(Node*)malloc(sizeof(Node));
p->data=1;
for(i=2;i<=n;i++)
{
q=(Node *)malloc(sizeof(Node));
q->data=i;
p->next=q;
p=q;
}
q->next=CL;
return CL;
}
/**********输出约瑟夫环****************
* *
* 参数：单链表头指针CL *
* *
* 无返回值 *
* *
**************************************/
void PrintLink(LinkList CL)
{
Node *p;
p=CL;
printf("循环单链表数据：");
do
{
printf("%5d",p->data);
p=p->next;
}while(p!=CL);
printf("\n\n");
}
/****************报数******************
* *
* 参数：单链表头指针CL，报数上限m *
* *
* 无返回值 *
* *
**************************************/
void Delete(LinkList CL,int m)
{
int i;
Node *p,*q; //p用于指向待删除结点的前驱结点，q用于指向待删除结点
printf("报数输出序列：");
p=CL;
q=NULL;
while(p->next!=p)//若链表为空，则报数结束
{
for(i=2;i<m;i++)
{
p=p->next;
}
q=p->next;
p->next=q->next;
printf("%4d",q->data);
free(q);
//上一轮报数结束，需调整p的指向，指向新一轮报数的起点
p=p->next;
}
printf("%4d",p->data);
free(p);
printf("\n\n");
}
void main()
{
LinkList CL;
int n,m;
printf("请输入约瑟夫总人数：");
scanf("%d",&n);
CL=InitRing(n);
PrintLink(CL);
printf("请输入报数上限:");
scanf("%d",&m);
Delete(CL,7);
}
