约瑟夫环问题（顺序表和单向链表）

超、凢脫俗 2023-07-05 13:12 23阅读 0赞

问题描述：设有n个人站成一圈，每个人有不同的编号i（1<=i<=n），即i∈\{1，2，3，4，·····，n\}，从编号为1的人开始按顺时针方向“1，2，3，···，m”循环报数，数到m的人出列。然后从出列者的下一个人开始重新报数，数到m的人又出列，如此重复进行，直到n个人都出列为止

解决思路：  
①先对存储人员信息数据结构进行初始化，初始遍历节点为1  
②从遍历节点的人向后遍历m次，定位到要删除的节点，输出相关信息  
③删除节点，调整数据结构，人数减1  
ⅰ若包含人数仍大于0，遍历节点为删除节点后一位，回②  
ⅱ若包含人数为0，结束

具体算法：  
①顺序表

for(int i=0; i<cou; i++) {
    	peop[i] = i+1;
    	 }
     System.out.println("出局顺序为：");
     int oPeo = 0;     //出局位数
    while(cou > 0) {
      	 //从第一个人开始
      	 oPeo = (num + oPeo - 1)%cou;
       	System.out.print(peop[oPeo]+"  ");
      	 //元素前移
       	for(int j=oPeo; j<cou-1; j++)
       	 peop[j] = peop[j+1];
      	 cou--;
      }

运行结果：  
![在这里插入图片描述][20200215112107663.png]  
②单向链表

//建立链表
    Node firstPeople,moveNode;    //定义头节点和移动节点来生成整个链表
    firstPeople = new Node();
    firstPeople.setOrder(1);
    moveNode = firstPeople;
    for(int i=2; i<=cou; i++) {
      	Node midNode = new Node();
      	midNode.setOrder(i);
      	moveNode.setNextPeople(midNode);		
      	moveNode = midNode;
    }
    moveNode.setNextPeople(firstPeople);    //环状链表
    
    //执行游戏
    System.out.println("依次出席的顺序（单向链表）为：");
    while(cou > 0) {              //此处遍历条件使用余数，使得在人数过小时，遍历次数减少
      	for(int j=1; j<=((num-1)%cou); j++) {     //从尾指针开始，定位到要删除结点的前一位
      	moveNode = moveNode.getNextPeople();    
     }
     System.out.print(moveNode.getNextPeople().getOrder()+"  ");
     //删除结点
     moveNode.setNextPeople(moveNode.getNextPeople().getNextPeople());
     cou--;   
    }

运行结果：  
![在这里插入图片描述][20200215112308920.png]

[20200215112107663.png]: https://img-blog.csdnimg.cn/20200215112107663.png
[20200215112308920.png]: https://img-blog.csdnimg.cn/20200215112308920.png