565-约瑟夫环问题(无头节点的单向循环链表)

- 日理万妓 2022-09-11 11:28 107阅读 0赞

## 约瑟夫环问题(无头节点的单向循环链表)![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16] ##

**我们采用无头节点的单向循环链表解决约瑟夫环问题**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
**假设k=1 , m=3**  
**图中的1个数字代表着1个节点**  
**我们采用双指针，初始化均指向第一个有效节点**  
因为单链表删除节点，用双指针方便  
我们用p专门用来指向要删除的节点  
q专门用来指向要删除的节点的前一个节点  
但是现在比较尴尬的是，它没有头节点，所以一开始只能指向第一个有效节点  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
k=1的话，它们本身就在第一个元素上，从第一个元素开始报数，报道第3个，![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
现在我们要删除3这个节点，3出列。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
然后p指向的是4节点，从1开始报数。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
现在我们要删除6这个节点，6出列  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
p指向7这个节点，从1开始报数  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
现在我们要删除1节点，1出列  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]  
p指向2这个节点，从1开始报数  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]  
现在我们要删除5这个节点，5出列  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]  
p指向的是节点7，从1开始报数  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]  
现在我们要删除2这个节点，2出列  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 12]  
现在我们要删除的节点是8，8出列  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 13]  
p指向的是节点4，从1开始报数  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 14]现在我们要删除的节点是4,4出列  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 15]  
p和q相等的话，就表示就剩下1个节点了，这个节点7就是最后出列的  
![在这里插入图片描述][911d85d8210546eaa1aca5fc02e8f355.png]

## 注意边界的考虑 ##

**如果k=1,m=1**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_15_color_FFFFFF_t_70_g_se_x_16]  
**就发生问题了。**  
我们希望p指向当前节点，q指向p的前一个节点。  
但是没有头节点啊。  
**我们可以这样做！！！**  
**我们初始化让q指向末尾节点！！！**  
**末尾节点的next域就是指向头节点了**

#include <iostream>
    #include <stdlib.h>
    #include <time.h>
    using namespace std;
    
    struct Node
    {
        
        Node(int data = 0) : data_(data), next_(nullptr) {
        }
        int data_;
        Node* next_;
    };
    
    //约瑟夫环问题 - 不带头节点的单项循环链表应用
    void Joseph(Node* head, int k, int m)//head指向的是第一个有效节点 
    {
        
        Node* p = head;
        Node* q = head;
    
        //q指向最后一个
        while (q->next_ != head)
        {
        
            q = q->next_;
        }
    
        //从第k个人开始报数的
        for (int i = 1; i < k; i++)
        {
        
            q = p;
            p = p->next_;
        }
    
        //p -> 第k个人
        for (;;)
        {
        
            for (int i = 1; i < m; i++)
            {
        
                q = p;
                p = p->next_;
            }
    
            //删除p指向的结点
            //q p node
            cout << p->data_ << " ";
    
            if (p == q)
            {
        
                delete p;
                break;
            }
    
            q->next_ = p->next_;
            delete p;
            p = q->next_;
        }
    }
    
    int main()
    {
        
        Node* head = new Node(1);
        Node* n2 = new Node(2);
        Node* n3 = new Node(3);
        Node* n4 = new Node(4);
        Node* n5 = new Node(5);
        Node* n6 = new Node(6);
        Node* n7 = new Node(7);
        Node* n8 = new Node(8);
    
        head->next_ = n2;
        n2->next_ = n3;
        n3->next_ = n4;
        n4->next_ = n5;
        n5->next_ = n6;
        n6->next_ = n7;
        n7->next_ = n8;
        n8->next_ = head;
    
        Joseph(head, 1, 1);
    }

![在这里插入图片描述][a2f4ce972e85453fa984aef088cc12cc.png]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/bed9fe17803f4497918dffd6c352c1d6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/7aaa070263dc49c8abcaf5261eb6aab9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/2bea81568f5241d2a737dc25dc9de530.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/27a036402262441a8f9562cd8eced038.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/416463b3d9bb45df9c2c01c7a4b33e66.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/3e8b0c0515904818afd671b3350ba223.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/6eeeba5a57f04196a1c8bd1d7e1a76e8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/82a0471c90d94622afc56a9ef36086b0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/a718b66bc6764165ba3698dfef8d44b5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/e47f337db7cd4466885ce8aacb4ca570.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/cc5104516886452ba14e82ed66eb37db.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]: /images/20220828/e9bbab85bedc4fe88a26335ed4124aae.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 12]: /images/20220828/f3e5dc743edf4872a84535d11dbbb916.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 13]: /images/20220828/882462f93824491b907c8074f0b5d10e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 14]: /images/20220828/a18e475ea75747b99950211dd460c737.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 15]: /images/20220828/58288f26b7864aefa75e1be9146c0776.png
[911d85d8210546eaa1aca5fc02e8f355.png]: /images/20220828/9660edd8734f45deaeaddcd8938c1b78.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/56e7b42eaf144bf19904b43e5fe1f556.png
[a2f4ce972e85453fa984aef088cc12cc.png]: /images/20220828/f8cc9166bb1d47d6b59a73e87ad3ff09.png