本文目录
约瑟夫环问题 用C语言数据结构数组实现.
#include《iostream》using namespace std;struct Node//循环节点的定义{int number;//编号Node *next;};Node *CreateList(Node *L,int &n,int &m);//建立约瑟夫环函数void Joseph(Node *L,int n,int m);//输出每次出列号数函数Node *DeleteList(Node **L,int i,Node *q);//寻找每次出列人的号数int LengthList(Node *L);//计算环上所有人数函数void main()//主函数{Node *L;L=NULL;//初始化尾指针int n, m;cout《《“请输入人数N：“;cin》》n;//环的长度if(n《1){cout《《“请输入正整数!“;}//人数异常处理else{cout《《“请输入所报数M：“;cin》》m;if(m《1){cout《《“请输入正整数!“;}//号数异常处理else{L=CreateList(L,n,m);//重新给尾指针赋值Joseph(L,n,m);}}system(“pause“);}Node *CreateList(Node *L,int &n,int &m)//建立一个约瑟夫环（尾插法）{Node *q;for(int i=1;i《=n;i++){Node *p;p=new Node;p-》number=i;p-》next=NULL;if(i==1) L=q=p;//工作指针的初始化else {q-》next=p;q=q-》next;}}q-》next=L;if(L!=NULL){return(L);}//返回尾指针else cout《《“尾指针异常!“《《endl;//尾指针异常处理}void Joseph(Node *L,int n,int m)//输出每次出列的人{int k;cout《《“请输入第一个报数人：“;cin》》k;if(k《1||k》n){cout《《“请输入1-“《《n《《“之间的数“《《endl;}else{cout《《“\n出列顺序:\n“;for(int i=1;i《n;i++){Node *q = new Node;if(i==1) q=DeleteList(&L,k+m-1,q);//第一个出列人的号数else q=DeleteList(&L,m,q);cout《《“号数：“《《q-》number《《endl;delete q;//释放出列人的存储空间}cout《《“最后一个出列号数是：“《《L-》number《《endl;;//输出最后出列人的号数}}Node *DeleteList(Node **L,int i,Node *q) //寻找每次出列的人{if(i==1) i+=LengthList(*L);//顺序依次出列情况的处理方式Node *p;p=*L;int j=0;while(j《i-2) {p=p-》next;j++;} q = p-》next;p-》next=p-》next-》next;*L = p-》next;return(q);}int LengthList(Node *L)//计算环上的人数{if(L){cout《《“尾指针错误!“《《endl;}//异常处理else{int i=1;Node *p=L-》next;while(p!=L){i++;p=p-》next;}return(i);}}
模拟约瑟夫环（josephus）问题
#include 《stdio.h》#include 《stdlib.h》typedef struct Lnode{ int data; struct Lnode *next;} Lnode;Lnode* create(int n){//建立共有n个结点的单循环链表h int i; Lnode *h,*p;//p为当前新生成结点的指针 Lnode *r=(Lnode *)malloc(sizeof(Lnode));//r为尾指针 r-》data=n;h=r;//h为头指针 for(i=n-1;i》0;i--)//头插法建立链表 {p=(Lnode *)malloc(sizeof(Lnode)); p-》data=i; p-》next=h; h=p; } r-》next=h ; //形成环 return h; }void jeseph(Lnode *p,int m){//从约瑟夫环中输出出列人的编号Lnode *q; int j=0; printf(“出队序列为:\n“); do{ j++; if (j==m-1) { q=p-》next; p-》next=q-》next; printf(“%d “,q-》data); j=0;free(q); } p=p-》next; }while(p-》next!=p); printf(“%d\n“,p-》data); free(p);}void main(){ Lnode *h; int m,n; printf(“\n请输入n和m的值：“); scanf(“%d,%d“,&n,&m); h=create(n) ; jeseph(h,m);}执行程序结果为：请输入n和m的值：12 , 4出队序列为:4，8，12，5，10，3，11，7，6，9，2，1执行程序结果为：请输入n和m的值：7，20
JAVA还有一个关于约瑟夫环的数据结构实验--我不知道怎么实现计数时跳过标记为null的那个啊！！！
经典的约瑟夫环问题其实就是一个循环链表，从头元素H开始往下数到指定的元素E，你的问题里需要在找到元素E以后加一个判断语句，如果元素E为空则当前指针移动到下一个元素直到元素不为空为止。Java集合类里的LinkedList可以用来作为循环链表，它综合了数组和链表的优点，可以在常数级别的时间复杂度内进行元素的检索、插入、删除。
数据结构 约瑟夫环
你是问这个程序的作用(⊙_⊙)？是这样的：编号为1，2，3......，n的人按顺时针方向围坐一圈，每人持有一个密码，一开始任选一个正整数作为报数上限m，从第一个人开始按顺时针方向自一开始报数，报到m时停止，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个人重新从1报数，如此下去，直到所有人出列。 程序用循环链表做的。
