566-数据结构(双向链表)

亦凉 2022-09-11 12:26 184阅读 0赞

## 双向链表 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][0fc7f3301a96447ca8f72cb8a4f51282.png]  
![在这里插入图片描述][9baf55c3275242c48a02c39755c8cfd7.png]  
**节点可以向后遍历，也可以向前遍历**

## 节点的定义 ##

//定义双向链表的节点类型
    struct Node
    {
        
        Node(int data=0)
            : data_(data)
            , next_(nullptr)
            , pre_(nullptr)
        {
        }
        int data_;//数据域
        Node* next_;//指向下一个节点
        Node* pre_;//指向前一个节点
    };
    
    //双向链表
    class DoubleLink
    {
        
    private:
        Node* head_;//指向头节点

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

public:
        DoubleLink()//构造函数 
        {
        
            head_ = new Node();
        }
        ~DoubleLink()//析构函数 
        {
        
            Node* p = head_;
            while (p != nullptr)
            {
        
                head_ = head_->next_;
                delete p;
                p = head_;
            }
        }

## 头插法 ##

**假如现在只有1个头节点，是空链表**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_11_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]  
**我们要改33节点的pre指针域和head头节点的next指针域**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
**假如现在我们还要再头插1个节点**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]

**33的pre指针域和25的next指针域和25的pre指针域和head头节点的next指针域都要修改！！！**

**我们得先修改新生成节点node的前后指针域**  
33节点地址在head头节点的next域存储着呢。  
我们修改25节点的next域  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
我们修改25节点的pre域  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
然后我们修改33节点的pre域  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
最后我们处理head头节点的next域  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]

//头插法
    void InsertHead(int val)
    {
        
        Node* node = new Node(val);
        node->next_ = head_->next_;
        node->pre_ = head_;
        if (head_->next_ != nullptr)
        {
        
            head_->next_->pre_ = node;
        }
        head_->next_ = node;
    }

**现在的代码是对上面所叙述的两种情况都适用！**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]

## 尾插法 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]  
**我们尾插一个节点66，只需要修改尾结点的next域和新生成的节点66的pre域**

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

//尾插法
    void InsertTail(int val)
    {
        
        Node* p = head_;
        while (p->next_ != nullptr)
        {
        
            p = p->next_;
        }
    
        //p->尾节点
        Node* node = new Node(val);
        node->pre_ = p;
        p->next_ = node;
    }

## 链表节点输出 ##

//链表节点输出
    void Show()
    {
        
        Node* p = head_->next_;
        while (p != nullptr)
        {
        
            cout << p->data_ << " ";
            p = p->next_;
        }
        cout << endl;
    }

## 节点删除 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]  
**假设我们现在要删除节点33**  
**我们定义1个指针找到33这个节点  
这次就不用定义2个指针了。因为33节点可以向后和向前遍历。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 12]  
**我们把33节点删除了，要把25节点和66节点要连起来，25的next域记录66节点的地址，然后66的pre域记录25节点的地址。**

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

//节点删除
    void Remove(int val)
    {
        
        Node* p = head_->next_;
        while (p != nullptr)
        {
        
            if (p->data_ == val)
            {
        
                //删除p指向的节点
                p->pre_->next_ = p->next_;
                if (p->next_ != nullptr)
                {
        
                    p->next_->pre_ = p->pre_;
                }
                //Node* next = p->next_;//删除所有值为val的节点
                delete p;
                //p = next;//删除所有值为val的节点
                return;
            }
            else
            {
        
                p = p->next_;
            }
        }
    }

## 节点搜索 ##

//节点搜索
    bool Find(int val)
    {
        
        Node* p = head_->next_;
        while (p != nullptr)
        {
        
            if (p->data_ == val)
            {
        
                return true;
            }
            else
            {
        
                p = p->next_;
            }
        }
        return false;
    }

## 测试代码 ##

#include <iostream>
    using namespace std;
    
    //定义双向链表的节点类型
    struct Node
    {
        
        Node(int data=0)
            : data_(data)
            , next_(nullptr)
            , pre_(nullptr)
        {
        }
        int data_;//数据域
        Node* next_;//指向下一个节点
        Node* pre_;//指向前一个节点
    };
    
    //双向链表
    class DoubleLink
    {
        
    public:
        DoubleLink()//构造函数 
        {
        
            head_ = new Node();
        }
        ~DoubleLink()//析构函数 
        {
        
            Node* p = head_;
            while (p != nullptr)
            {
        
                head_ = head_->next_;
                delete p;
                p = head_;
            }
        }
    
    public:
        //头插法
        void InsertHead(int val)
        {
        
            Node* node = new Node(val);
            node->next_ = head_->next_;
            node->pre_ = head_;
            if (head_->next_ != nullptr)
            {
        
                head_->next_->pre_ = node;
            }
            head_->next_ = node;
        }
    
        //尾插法
        void InsertTail(int val)
        {
        
            Node* p = head_;
            while (p->next_ != nullptr)
            {
        
                p = p->next_;
            }
    
            //p->尾节点
            Node* node = new Node(val);
            node->pre_ = p;
            p->next_ = node;
        }
    
        //节点删除
        void Remove(int val)
        {
        
            Node* p = head_->next_;
            while (p != nullptr)
            {
        
                if (p->data_ == val)
                {
        
                    //删除p指向的节点
                    p->pre_->next_ = p->next_;
                    if (p->next_ != nullptr)
                    {
        
                        p->next_->pre_ = p->pre_;
                    }
                    //Node* next = p->next_;
                    delete p;
                    //p = next;
                    return;
                }
                else
                {
        
                    p = p->next_;
                }
            }
        }
    
        //节点搜索
        bool Find(int val)
        {
        
            Node* p = head_->next_;
            while (p != nullptr)
            {
        
                if (p->data_ == val)
                {
        
                    return true;
                }
                else
                {
        
                    p = p->next_;
                }
            }
            return false;
        }
    
        //链表节点输出
        void Show()
        {
        
            Node* p = head_->next_;
            while (p != nullptr)
            {
        
                cout << p->data_ << " ";
                p = p->next_;
            }
            cout << endl;
        }
    
    private:
        Node* head_;//指向头节点
    };
    
    int main()
    {
        
        DoubleLink dlink;
    
        dlink.InsertHead(100);
    
        dlink.InsertTail(20);
        dlink.InsertTail(12);
        dlink.InsertTail(78);
        dlink.InsertTail(32);
        dlink.InsertTail(7);
        dlink.InsertTail(90);
        dlink.Show();
    
        dlink.InsertHead(200);
        dlink.Show();
    
        dlink.Remove(200);
        dlink.Show();
    
        dlink.Remove(90);
        dlink.Show();
    
        dlink.Remove(78);
        dlink.Show();
    }

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

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/f9cafbb7f9724ee8b652d66a6fd71f31.png
[0fc7f3301a96447ca8f72cb8a4f51282.png]: /images/20220828/adf5d878c71948cbbb4f19b016650cae.png
[9baf55c3275242c48a02c39755c8cfd7.png]: /images/20220828/1f545a61ae8a4078870eaf2a5ac1b241.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_11_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/1dfbc985fc674aba9e68a24c9b3f8de9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/72768782a41e4b64a98af208adc629f5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/07580b1f10fa4d3c92f43dbd0b173212.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/e94f0e0f6f454998a2fa59d89f3f3be8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/ba82bf4010fa48faad25650d7922a043.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/090dba28ef6946c2abb29b58aeb79151.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/8e9bf62e134c458d8c4be6babd2264ca.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/90c7edb62e1c4681887b544dcab16677.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/6331ed2d8b554bc9ba33af374be35453.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/f62948ade3a5444c9910a6bf979b1115.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/b2bea322e69e4031b36a9b53e32f3f40.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 11]: /images/20220828/41fa5e5af11248ceb34d657275dabb67.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 12]: /images/20220828/b3a3539884f04360bb2b4638dec4430b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/3687c07644a847aab8c0f5a2006b518f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 13]: /images/20220828/8854384f3e564b76b6ec6267c965caa9.png