约瑟夫环------C++

约瑟夫环------C++ 6 joseph 1 编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密 码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 2 利用单向循环链存储结构模拟此过程，按照出列的顺序输出各个人的编 号。 测试数据： m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6, 则正确的输出是什么？ 要求： 输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。 输出形式：建立一个输出函数，将正确的输出序列 #include using namespace std; template struct CircCircListNode { T data; int code; CircCircListNode* link; }; - 1 - template class CircList { public: CircList(const int count );//创建单项循环链表 T Delete(CircCircListNode* ); //删除一个节点 int Josephus(int );//创建约瑟夫环 void Print(); //输出出列顺序 private: CircCircListNode* first,* last; int count; }; //创建单项循环链表 template CircList::CircList(const int count) { CircCircListNode* q=first; if(count==1) { last=first=new CircCircListNode(); first->data=1; //输入data值 cout<<"请输入密码:"<>first->code; first->link=first; } else { last=first=new CircCircListNode(); first->data=1; //输入data值 cout<<"请依次输入各个密码(用空格分开）:"<>first->code; - 2 - q=first; for(int i=1;i* p=new CircCircListNode(); p->data=i+1; //输入data值，有Bug! cin>>p->code; q->link=p; q=p; } q->link=first; } this->count=count; }; //删除一个节点 template T CircList::Delete(CircCircListNode* a) { if(a!=NULL) { if(count==1) return first->data; if(first==a) { CircCircListNode* q=first; while(q->link!=first) { q=q->link; } T value=first->data; q->link=first->link; first=first->link; return value; - 3 - } CircCircListNode* q=first; while(q->link!=a) { q=q->link; } T value=a->data; q->link=a->link; delete a; count--; return value; } return 0; }; //创建约瑟夫环 template int CircList::Josephus(int m) { if(m<=0) cout<<"不合理!"< *q; for(int i=1;ilink; } int a=last->code; q=last; if(last->link!=last) // { last=last->link; - 4 - } else { Print(); //对最后节点的处理 return 0; } cout< void CircList::Print() { CircCircListNode* q=first; while(q->link!=first) { cout<data<<" "; q=q->link; } cout<data<<" "; }; void main() { int num,code; cout<<"请输入Josephus环的元素个数: "; cin>>num; CircList a(num); cout<<"请输入初始密码:"; - 5 - cin>>code; cout<<"出列顺序:"<