约瑟夫环问题——legend



约瑟夫环问题：
（一）问题：
已知有n个人（编号为1,2,3...n)围坐在一个圆桌周围，从编号为k的人开始报数，数到m的那个人出队，出队的下一个位置的人继续从k开始数数，数到m的那个人继续出队，。。。,知道所有的人都出队了，求出队序列。

（二）方法一：循环链表。
（1）步骤：
1.构造一个有n个元素的循环链表，无头节点。
2.确定第一个报数人的位置；
3.不断从链表中删除节点；

（2）代码实现：

typedef struct linkNode{
  DataType data;
  linkNode* next;
 }linkNode* creatLoopLink(int n){
  static linkNode * pnode;
  pnode=(linkNode*) malloc(sizeof(linkNode));//产生一个新节点；
  pnode->data=1;
  pnode->next=NULL; LinkNode* curNode,*lastNode=pnode;
 for(int i=2;i<=n;i++){
   curNode=(linkNode*) malloc(sizeof(linkNode));//产生一个新节点
   curNode->data=i;
   curNode->next=NULL;  lastNode->next=curNode;//尾接法创建一个链表
   lastNode=curNode;
  } lastNode->next=pnode;//最后一个节点的尾部连接头。
 return pnode;
 } /*
 从循环链表link中，不断删除编号为m的节点。
 k表示起始读数；
 m要删除的编号
 n为节点个数
 */
 deleteNode_m(linkNode* link, int k, int m ,int n){
  
  linkNode* pre,cur=link;
  for(int i=1;i<=k;i++){//定位到第k个节点,即第一个报数的人。
   pre=cur;
   cur=cur->next;
  } for(int i=n;i>=1;i--){//计算出队序列
   for(int j=k;j<=m;j++){//从k定位到m
    pre=cur;
    cur=cur->next;
   }  pre->next=cur->next;
   visit(cur->data);
   free(cur);  cur=pre->next;//下一个从删除节点的下一个开始数数。
  }
 }

（三）方法二：循环队列

（1）步骤：
1.初始化队列：
将编号为1，2,3....n的人依次入队；
2.定位k：
依次出队，直到m,并且将出队的元素同时插入到队尾。
3.删除m：
从k到m-1，依次出队，并且入队到队尾，m直接出队，不再入队。

4.下一个k的位置，就是不再入队的m的下一个元素。循环3、直到全部删除。