564-数据结构(单向循环链表)

谁借莪１个温暖的怀抱￠ 2022-09-11 11:25 235阅读 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]  
**如果某个节点的next地址域存储的是头节点的地址。  
此时就证明这个节点是单向循环链表的末尾节点了。**  
为了方便尾插法，我们再定义一个tail指针指向尾节点，这样尾插法的时间复杂度而是O(1)  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]

## 定义单向循环链表 ##

private:
        struct Node//定义节点类型
        {
        
            Node(int data = 0) : data_(data), next_(nullptr) {
        }
            int data_;
            Node* next_;
        };
    
        Node* head_;//指向头节点
        Node* tail_;//指向末尾节点

## 构造函数和析构函数 ##

**构造函数图解：**  
![在这里插入图片描述][7aed6d1db80c4f6cae7548771994437a.png]

//单向循环链表
    class CircleLink
    {
        
    public:
        CircleLink()//构造函数 
        {
        
            head_ = new Node();
            tail_ = head_;
            head_->next_ = head_;
        }
        ~CircleLink()//析构函数 
        {
        
            Node* p = head_->next_;
            while (p != head_)
            {
        
                head_->next_ = p->next_;
                delete p;
                p = head_->next_;
            }
            delete head_;
        }

**析构函数图解：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
**最后删除到只剩下头节点**  
![在这里插入图片描述][c9082b6353b846748c734d370742f6f0.png]

## 尾插法 ##

//尾插法  O(1)
    void InsertTail(int val)
    {
        
        Node* node = new Node(val);
        node->next_ = tail_->next_;//node->next_ = head_;
        tail_->next_ = node;//连起来
        tail_ = node;//更新tail_指针指向新的尾节点
    }

## 头插法 ##

//头插法
    void InsertHead(int val)
    {
        
        Node* node = new Node(val);
        node->next_ = head_->next_;
        head_->next_ = node;
        if (node->next_ == head_)//原本是空链表，现在插入1个新节点，所以要更新tail了
        {
        
            tail_ = node;
        }
    }

**原本是空链表，现在插入1个新节点，所以要更新tail指针了**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
**如果原本不是空链表，头插法就不用更新tail指针了**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]

## 删除节点 ##

**双指针思想**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]  
**如果我们要删除的节点是67，我们现在就可以删除了。**  
**关键是我们还要更新tail指针。**  
**如果我们要删除的是尾节点，就要重置tail了**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]

**所以，我们要判断删除的节点是不是末尾节点**

//删除节点
    void Remove(int val)
    {
        
        Node* q = head_;
        Node* p = head_->next_;
    
        while (p != head_)
        {
        
            if (p->data_ == val)
            {
        
                //找到删除节点   head 
                //                 q     
                q->next_ = p->next_;
                delete p;
                if (q->next_ == head_)//删除的是末尾节点
                {
        
                    tail_ = q;
                }
                return;
            }
            else
            {
        
                q = p;
                p = p->next_;
            }
        }
    }

## 查询 ##

//查询
    bool Find(int val) const
    {
        
        Node* p = head_->next_;
        while (p != head_)
        {
        
            if (p->data_ == val)
            {
        
                return true;
            }
        }
        return false;
    }

## 打印链表 ##

//打印链表
    void Show() const
    {
        
        Node* p = head_->next_;
        while (p != head_)
        {
        
            cout << p->data_ << " ";
            p = p->next_;
        }
        cout << endl;
    }

## 测试代码 ##

#include <iostream>
    #include <stdlib.h>
    #include <time.h>
    using namespace std;
    
    //单向循环链表
    class CircleLink
    {
        
    public:
        CircleLink()//构造函数 
        {
        
            head_ = new Node();
            tail_ = head_;
            head_->next_ = head_;
        }
        ~CircleLink()//析构函数 
        {
        
            Node* p = head_->next_;
            while (p != head_)
            {
        
                head_->next_ = p->next_;
                delete p;
                p = head_->next_;
            }
            delete head_;
        }
    
    public:
        //尾插法  O(1)
        void InsertTail(int val)
        {
        
            Node* node = new Node(val);
            node->next_ = tail_->next_;//node->next_ = head_;
            tail_->next_ = node;//连起来 
            tail_ = node;//更新tail_指针指向新的尾节点
        }
    
        //头插法
        void InsertHead(int val)
        {
        
            Node* node = new Node(val);
            node->next_ = head_->next_;
            head_->next_ = node;
            if (node->next_ == head_)//原本是空链表，现在插入1个新节点，所以要更新tail了
            {
        
                tail_ = node;
            }
        }
    
        //删除节点
        void Remove(int val)//删除的是末尾节点
        {
        
            Node* q = head_;
            Node* p = head_->next_;
    
            while (p != head_)
            {
        
                if (p->data_ == val)
                {
        
                    //找到删除节点   head 
                    //                 q     
                    q->next_ = p->next_;
                    delete p;
                    if (q->next_ == head_)
                    {
        
                        tail_ = q;
                    }
                    return;
                }
                else
                {
        
                    q = p;
                    p = p->next_;
                }
            }
        }
    
        //查询
        bool Find(int val) const
        {
        
            Node* p = head_->next_;
            while (p != head_)
            {
        
                if (p->data_ == val)
                {
        
                    return true;
                }
            }
            return false;
        }
    
        //打印链表
        void Show() const
        {
        
            Node* p = head_->next_;
            while (p != head_)
            {
        
                cout << p->data_ << " ";
                p = p->next_;
            }
            cout << endl;
        }
    
    private:
        struct Node
        {
        
            Node(int data = 0) : data_(data), next_(nullptr) {
        }
            int data_;
            Node* next_;
        };
    
        Node* head_;//指向头节点
        Node* tail_;//指向末尾节点
    };
    
    
    int main()
    {
        
        CircleLink clink;
        srand(time(NULL));
    
        clink.InsertHead(100);
    
        for (int i = 0; i < 10; i++)
        {
        
            clink.InsertTail(rand() % 100);
        }
    
        clink.InsertTail(200);
        clink.Show();
    
        clink.Remove(200);
        clink.Show();
    
        clink.InsertTail(300);
        clink.Show();
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/f7833aa8999b43e0b21f331d31e55363.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/ab473389a7184f6ba2aa04028d058912.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/000c16a3d1074875be0f674a8cf749c9.png
[7aed6d1db80c4f6cae7548771994437a.png]: /images/20220828/6f510aabb8e149d29ce4dfca5785831c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/536d8faf925d4b64a667a20b45651f42.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/2011515e9d4a47138c40137464d5a043.png
[c9082b6353b846748c734d370742f6f0.png]: /images/20220828/819d024fe09b4309abc15c85a1101e62.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/83d4e33db364490c8533edc4be3d33ae.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/81227819755a423082be1abfc50a33e7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/c6bd2e0490da448a89cdc8a6617107c9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/03c30280fd9248f2917d87006a404088.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/d69b1adc18094b088064e15e553e8308.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/942c2a98eb87445bbbd2e68314afa374.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]: /images/20220828/fabac55ef0544bcba276c4f5c4cc7e13.png