约瑟夫环（一道题）
/*----------------------------------------------------------------------------------------------------------实验三 （附加） 约瑟夫环
【问题描述】
编号为1，2… n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，
从第一个人开始按顺时针方向自1开始顺序报数， 报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时
针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。
【基本要求】
(1) 利用单循环链表作为存储结构模拟此过程；
(2) 键盘输入总人数、初始报数上限值m及各人密码；
(3) 按照出列顺序输出各人的编号。
【测试数据】
m的初值为20；n=7,7个人的密码依次为:3,1,7,2,4,8,4,首先m值为6（正确的出列顺序为6,1,4,7,2,3,5）。
【实现提示】
此题所用的循环链表中不需要“头结点”。
【选作内容】
用顺序表解决约瑟夫问题。
-------------------------------------------------------------------------------------------------------------*/
程序代码：
/* 约瑟夫环--by hoodlum1980 2008年10月7日*/
#include <stdio.h>
#include <stdlib.h>
typedef struct tnode
{
int key; /*密码*/
int index; /*编号*/
struct tnode* next;
} NODE;
/* entry point */
int main()
{
int i,j,m,n;
NODE *head=NULL, *cur=NULL, *last=NULL;
/*输入有多少个人--------------------------------------*/
printf("input n=?\n");
scanf("%d",&n);
/*输入初始密码----------------------------------------*/
printf("input m=?\n");
scanf("%d",&m);
/*输入n个密码-----------------------------------------*/
printf("input %d keys: \n", n);
for(i=0;i<n;i++)
{
cur=(NODE*)malloc(sizeof(NODE));
scanf("%d",&(cur->key));
cur->index=i+1; /*编号以1为起始*/
cur->next = NULL;
if(i==0)
{
head=last=cur;
}
else
{
last->next=cur;/*挂接*/
}
last=cur;
}
/*连成环*/
if(last!=NULL) last->next=head;
/*初始化-----------------------------------------------*/
/*
cur(head) last
| |
O - O - O - ... - O
*/
cur=head; /*此时，cur指向head节点，last指向尾部节点*/
/*开始报数----------------------------------------------*/
printf("\nExit Order: ");
for(i=0;i<n;i++)
{
/*依次报数到第m个节点*/
for(j=1;j<m;j++)
{
last=cur;
cur=cur->next;
}
/*出列*/
m=cur->key;/*更新key*/
printf("%d,", cur->index);
/*脱链*/
last->next=cur->next;
free(cur);
cur=last->next;
}
printf("\n");
return 0;
}
