首页 > 代码库 > 约瑟夫环
约瑟夫环
约瑟夫环，已知n个人，（编号从1、2、3、4......n）,围在一张圆桌上，从编号为startnum的人开始报数，报到outnum的人出列，接着从下一个人开始从1报数，数到outnum的人又出列；依次规律重复下去，知道所有人全部出列，请写出出列的依次序号数。
这是一个约瑟夫环问题，用单链表来做，具体地：
1.建立一个无头结点的循环链表，依次编号1、2、3、4......n;
2.将临时首个指针p移动到开始报数的人的位置，以前保存该位置的前驱节点r->next=p（为了方便删除p）；
3.开始报数，同时p和r向后移动，当报到outnum时，将p点删除，然后p重新赋值后面一个节点，r跟上；
4.若所有节点删除完毕，停止；否则继续执行第3部。
具体代码如下：
#include<iostream>using namespace std;struct Node { int data ; Node *next;};//约瑟夫环儿的问题，一共len 个人 从第startnum个人开始报数 //数到outnum的人出列 求 出列序号是什么void josephus(int Len,int startnum,int outnum){ Node *head=(Node*)malloc(sizeof(Node)); if (head==NULL)//判断内存是否申请成功 { return ; } head->next=NULL; head->data=http://www.mamicode.com/1; Node *curr=head;//建立循环链表的时候的临时指针 for (int i=2;i<=Len;i++) { Node* pNew = (Node*)malloc(sizeof(Node)); pNew->data=http://www.mamicode.com/i; curr->next=pNew; curr=pNew; } curr->next=head;//尾节点后继为头指针，构成循环链表 Node *p=head;//删除节点时用的当前指针 Node *r=curr;//r始终是p的前驱 while(--startnum)//将p移动到开始数的位置startnum { r=p; p=p->next; } while (Len--) { for ( int num=outnum;--num;r=p,p=p->next);//寻找要删除的位置 r->next=p->next;//将删除位置的后继位置赋值给前驱的后继指针 cout<<p->data<<" ";//打印删除节点序号 free(p); p=r->next;//将p重新赋值为第一个报数的人 } }void main(){ josephus(12,1,2);}
执行结果如下图：
约瑟夫环
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。