一、 问题描述

  N个人围城一桌（首位相连），约定从1报数，报到数为k的人出局，然后下一位又从1开始报，以此类推。直到全部出局。求出局顺序
 
  如图:
    以5人维圈，报三出局为例

二、详细讲解

1️⃣题目解析

💤思考一：约瑟夫环的本质是什么❓

 
约瑟夫环既然被称为环，本质上就是一个循环链表，由于是一个方向的，所以采用 单向循环链表
 
约瑟夫环可以简化为：围桌、报数、出局

1. 💡围桌：所有人都上桌  ——>  单链表的插入
2. 💡报数：依次从1到K报数 ——> 单链表的遍历
3. 💡出局：报到K走人    ——> 单链表的删除
    

✅答案：约瑟夫环的问题我们就转化为了的循环链插、遍历、删除表的相关问题

2️⃣代码解析

由思考一可以知道，核心代码为：插入、循环、删除，下面我们一一讲解。

约瑟夫环的核心代码为插入、删除

2.1 插入代码（尾插）

1. 图解

   

2. 代码讲解

       LNode* head = (LNode*)malloc(sizeof(LNode));//创建头结点
       head->next = NULL;//将指针域设置为空
       LNode* p = head; //便于尾插法的操作
       for (int i = 1; i <= e; i++)//e表示：围桌的人数
       {
           LNode* node = (LNode*)malloc(sizeof(LNode));//开拓新空间
           node->data = i;//将编码放进数字域
           node->next = head;  //单循环链表
           p->next = node;  
           p = node;          //使p指针保持在最后，方便下次循环
       }
       p->next = head->next;  //删除头指针
       free(head);           //删除头结点，形成约瑟夫环
       *L = p->next;
   

3. 重点讲解

    p = node;    和   p->next = node;
   

   p = node;的作用：将 p 置于最后一个指针上，在下次循环时，可以将单链表链接在一起。如下图;
   

       p->next = head->next;  //删除头指针
       free(head);           //删除头结点，形成约瑟夫环
       *L = p->next;
   

   在插入最后，要删除头结点，因为头结点的数字域中没有存放元素，删除之后便可以形成约瑟夫环

2.2 删除代码

1. 图解

   

2. 代码讲解

       LinkList p = L, q = NULL;
       printf("\t\t出局的人依次为：  ");
       while (e >= 1)
       {
           for (int i = 1; i < m - 1; i++)//定位到出局人的前一位  
               p = p->next;
           q = p->next;
           p->next = q->next;
           printf("%d ", q->data);
           free(q);  //释放删除结点的空间   
           p=p->next;   
           e--;
       }
   

3. 重点讲解

          for (int i = 1; i < m - 1; i++)//定位到出局人的前一位  
               p = p->next;
           q = p->next;
   

   for循环的目的：为了将 p 指针指向要删除的元素的前一个元素上。
   并将 q 指向要删除元素利用 p->next = q->next; 使要删除元素出局。
   

四、 完整代码

1. 代码

   #include <stdio.h>
   #include <stdlib.h>
   
   typedef struct LNode
   {
       int data;     //数字域
       struct LNode* next;//指针域
   }LNode, * LinkList;
   
   //尾插
   int CreateList_F(LinkList* L, int e)
   {
       if (e < 1)
           return -1;
       LNode* head = (LNode*)malloc(sizeof(LNode));//创建头结点
       head->next = NULL;
       LNode* p = head;
       int i;
       for (i = 1; i <= e; i++)
       {
           LNode* node = (LNode*)malloc(sizeof(LNode));
           node->data = i;
           node->next = head;  //单循环
           p->next = node;
           p = node;          //使p保持在最后9
       }
       p->next = head->next;
       free(head);           //删除头结点，形成约瑟夫环
       *L = p->next;
       return 1;
     }
   
   //遍历单链表
   void TravleList(LinkList L, int e)
   {
       LinkList p = L;
       printf("\t\t参与的人的编号为：");
       for (int i = 1; i <= e; i++)
       {
           printf("%d ", p->data);
           p = p->next;
       }
        printf("\n");
   }
   
   //删除
   int ListDelete_L(LinkList L, int e, int m) {
       LinkList p = L, q = NULL;
       printf("\t\t出局的人依次为：  ");
       while (e >= 1)
       {
           for (int i = 1; i < m - 1; i++)//定位到出局人的前一位  
               p = p->next;
           q = p->next;
           p->next = q->next;
           printf("%d ", q->data);
           free(q);  //释放删除结点的空间 
           p=p->next;     
           e--;
       }
        return 1;
   }
   
   void menu()
   {
       printf("\t\t******   约瑟夫环   ******\n");
       printf("\t\t       1.程序开始\n");
       printf("\t\t       2.程序继续\n");
        printf("\t\t       0.程序结束\n");
       printf("\t\t**************************\n");
   }
   
   int main()
   {
       menu();
       int m, e, a;
       do {
           printf("\t请输入选择："); scanf_s("%d", &a);
           switch (a) {
           case 1:
           case 2:
            {
               printf("\t\t人数："); scanf_s("%d", &e);
               printf("\t\t密码值："); scanf_s("%d", &m);
               LinkList L;
               CreateList_F(&L, e);       //构建
               TravleList(L, e);          //打印
               if (m != 1)
                   ListDelete_L(L, e, m);     //出局  
               else {
                   printf("\t\t出局的人依次为：  ");
                   for (int i = 1; i <= e; i++)    //注意当m=1时的情况
                       printf("%d ", i);
               }
               printf("\n");
               break;
           }
           case 0:
               printf("\t\t感谢使用！！！\n");
               break;
           default:
               printf("\t输入错误!!!!\n");
               break;
          }
       } while (a != 0);
       return 0;
   }
   

2. 运行代码

   

3. 注意点

   if (m != 1)
        ListDelete_L(L, e, m);     //出局  
    else {
        printf("\t\t出局的人依次为：  ");
        for (int i = 1; i <= e; i++)    //注意当m=1时的情况
            printf("%d ", i);
    }
   
   

   当m=1时并不适合删除代码，所以需要另外列出来