改编约瑟夫环问题及其程序.doc

程序一:循环链表实现,将编号当做密码
#include<stdio.h>
typedef struct _node
{
int num;
struct node* next;
}node,*pnode;
node* mkring(int persions)
{
int i;
pnode p,head;
p=head=(node*)malloc(sizeof(node));
head->num=1;
for(i=1;i<persions;i++)
{
p->next=(node*)malloc(sizeof(node));
p=p->next;
p->num=i+1;
}
p->next=head;
return head;
}
int printring(pnode head)
{
pnode p=head;
while(p->next!=head)
{
printf("%d ",p->num);
p=p->next;
}
printf("%d \n",p->num);
}
int main()
{
int m,i,n;
pnode p,r;
printf("n m ");
scanf("%d %d",&n,&m);
r=p=mkring(n);
//打印之前的序列
printring(r);
//打印出局序列
while(p->next!=p)
{
for(i=1;i<m;i++)
{
r=p;
p=p->next;
}
m=p->num;
printf("%d ",p->num);
r->next=p->next;
free(p);
p=r->next;
}
printf("%d \naa",p->num);
free(p);
}