C语言实现约瑟夫

分手后的思念是犯贱 2022-05-06 23:36 156阅读 0赞

**C语言实现约瑟夫环**  
Q：约瑟夫环问题 ：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。  
A:这里采用循环单链表的方法

#include<stdio.h>
    #include<stdlib.h>
    #define LEN sizeof(struct LNode)
    typedef int datatype;
    typedef struct LNode {
    datatype data;
    struct LNode *next;
    }LNode, *LinkList;
     int N, S, M;
        LinkList L, Start;
           void Question();
           void Creat_LinkList(int n);
           void Find_start(int n);
           void Find_delete();
           int main()
           {
             Question();
             Creat_LinkList(N);
             Find_start(S);
             Find_delete(); 
             return 0;
          }
    void Question()
    {
    `   printf("请输入总人数N（N < 50）：");
        scanf("%d", &N);
        printf("\n\n\n\n");
        printf("请输入第一个开始报数的人的编号S：");
        scanf("%d", &S);
        printf("\n\n\n\n");
        printf("请输入报数上限值M：");
        scanf("%d", &M);
        printf("\n\n\n\n");
        printf("依次删除的人的编号：");
        printf("\n\n\n\n");
    }``
    void Creat_LinkList(int n)
    {
        int i = 1;
        LinkList p, q;
        p = (LinkList)malloc(LEN);
        p->data = i++; 
        L = p;
       q = p; 
       while(i <= n)
       {
        p = (LinkList)malloc(LEN);
        p->data = i;
        q->next = p;
        q = p;
        i++;
       }
    q->next = L;
    }
    void Find_start(int n)
    {
    Start = L;
    while (Start->data != n)
        {
           Start = Start->next;
        }
    }
    void Find_delete()
    {
    int i, j, k = 0,num = N;
    LinkList pre = L, s;
    while (num > 1) 
       {
        for(i = 1; i < M; i++) 
         { 
          Start = Start->next;
    }
     printf("%d ", Start->data);
    while(pre->next != Start) 
    {
     pre = pre->next;
    }
     s = pre->next;
     pre->next = s->next;
     free(s);
     Start = pre->next;
     num -= 1;
    }
    printf("\n最后剩余的人的编号：%d\n", Start->data);
    }
    
    
    ![运行图](https://img-blog.csdn.net/20181014153149847?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V0aGFuX1N1/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)