约瑟夫问题经典算法，环形链表的运用

我不是女神ヾ 2023-06-18 04:53 17阅读 0赞

**问题背景：**  
据说在很久很久以前，约瑟夫及其部下被逼退到了一个山洞里面，走头无路，大家又不甘投降叛变，于是大家决定一起赴死，他们一起围成了一个圈，然后准备依次报数，当谁的数字为3的时候就自杀，后面的人从1开始依次报数，遇到3又自杀，如此循环往复，问最后一个自杀的人是谁？例如如下序列：  
![在这里插入图片描述][2019113011255365.png]  
**算法分析**

#include <stdio.h>
    #include <stdlib.h>
    
    //声明结构体
    typedef struct node *Link;
    
    //定义结构体
    struct node {
        
        int number;
        Link next;
    };
    
    //输出测试数据
    void print_data(Link head, int totalNum){
        
        int i;
        Link temp = head;
        for(i = 1; i <= totalNum; i++){
        
            printf("%d ", temp->number);
            temp = temp->next;
        }
    }
    
    int main(void) {
        
        int totalNum = 10;//总共的人数
        int space = 3;//间隔数
        Link head = malloc(sizeof *head);
        Link x = head;
        //将头节点指向自身
        head->number = 1;
        head->next = head;
        
        //开始进行生成一个环形链表
        for(int i = 2 ; i <= totalNum; i++){
        
            x->next = malloc(sizeof *x);
            x->next->next = head;
            x->next->number = i;
            x = x->next;
        }
        
        //打印测试
        printf("队列原始顺序:\n");
        print_data(head, totalNum);
        
        x = head;
        //依次将环形链表中的某个位置的值去掉
        printf("\n死亡士兵的顺序:\n");
        while(x != x->next){
        
            for(int i = 2; i < space; i++){
        
                x = x->next;
            }
            printf("%d ", x->next->number);
            x->next = x->next->next;
            x = x->next;
        }
        printf("\n最后自杀的士兵:\n");
        printf("%d ", x->number);
        return 0;
    }

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