#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
typedef struct node // 结点的结构定义
{
int num; // 编号子域
int sm; // 密码子域
struct node *link; // 指针域
}JOS;
// 函数声明
JOS *creat();
void outs(JOS *h, int m);
// 主函数
void main()
{
int m; JOS *h;
h=creat();
cout<<endl<<"请输入初始密码(m>1)m=";
cin>>m;
outs(h, m);
} // main
// 生成约瑟夫环
JOS *creat()
{
int i=0, mi;
JOS *neww, *pre, *h;
h=(JOS *)malloc(sizeof(JOS)); // 为头结点申请空间
h->link=h; // 头结点h形成环
pre=h;
cout<<"请输入编号为1的人的密码=";
cin>>mi;
while( mi != -1) // 密码为-1，结束循环
{
neww=(JOS *)malloc(sizeof(JOS)); // 申请数据元素结点空间
i++;
neww->num=i;
neww->sm=mi; // 结点送值
neww->link=h;
pre->link=neww;
pre=neww; // 形成循环链表
cout<<"请输入编号为"<<i+1<<"的人的密码=";
cin>>mi; // 读入下一个密码
} // while
pre->link=h->link; free(h); // 删除头结点h
h=pre->link; return(h); // 头指针指向第一个数据元素结点
} // JOS *creat , 该约瑟夫环无附加头结点
// 按m被叫出列的顺序，输出结点信息
void outs(JOS *h, int m)
{
int i; JOS *q=h,*p;
cout<<endl;
while (q->link!=q)
{
for(i=1;i<m;i++)
{ p=q; q=q->link;} // 报数到第m个人
m=q->sm; //修改值m为第m个人的密码
cout<<q->num<<" "; // 输出第m个人的编号
p->link=q->link; free(q);// 第m个人出列
q=p->link;
}
cout<<q->num<<endl; // 输出最后一个结点的编号值
free(q);
} // outs
