[C++] LinkList:双向不循环链表的原理和实现(基础)

谁借莪１个温暖的怀抱￠ 2023-01-19 07:18 23阅读 0赞

链表作为计算机中,经典的**数据结构**.

也是程序员的基本功,如果你连链表都不会写,那么最好不要去面试.

它是**抽象层面的线性**表数据结构,在物理上存储,则并不连续.

因为new(malloc)出什么地址,是归计算机分配你只能决定申请多少个,而不是申请什么地址.

附双向不循环链表原理图(使用MicrosoftWindows10自带的pint工具绘制)

[![25E5_258F_258C_25E5_2590_2591_25E4_25B8_258D_25E5_25BE_25AA_25E7_258E_25AF_25E9_2593_25BE_25E8_25A1_25A8.png][]][25E5_258F_258C_25E5_2590_2591_25E4_25B8_258D_25E5_25BE_25AA_25E7_258E_25AF_25E9_2593_25BE_25E8_25A1_25A8.png 1]

//如果图片看不清,推荐使用 [imagus插件][imagus]或者 [下载原理图原件][Link 1]

即便代码部分不熟练,只要记的实现原理,便可以说是掌握链表结构了.

**链表结构分为多种**.

\{ *单向不循环链表,双向不循环链表,单向循环链表,双向循环链表*\}

**如果你从来没写过链表结构,或者学过**.

**我建议你先理解原理图的大致意思,先自己按照原理,实现出大概**.

**然后跟着我一起来写**

当然,**你可以直接下载我写好的成品,但是你不会得到任何的帮助,你只会成为一个三键程序员(Ctrl+C,Ctrl+V)**.

**整个项目源码,下载地址在最下方**

\---------------------------------CODEING---------------------------------

先来定义一个节点类型

注意!我这个是类模板,其中的dataType是为了方便更换数据类型,泛型结构,也是C++中的重要掌握点.

typedef unsigned int uint;
    template < typename dataType >
    class Node
    { 
        // Data Area 数据区
        dataType data;
        // Pointer Area 指针区
        Node* after;   // 后指针
        Node* befor;   // 前指针
    public:
        Node(dataType data = NULL, Node* after = nullptr, Node* befor = nullptr) : data(data), after(after), befor(befor)
            // 在这地方赋值,是类成员赋初值,也就是构造类成员的时候,直接给值,可以提升效率
        { 
            // Constructor 构造函数
             // 如果在这里给类成员变量赋值,则是赋值,也就是先声明定义变量,再到这里赋值
        }
        dataType GetData(void) const    // 函数参数块后面写const 表示这是类内只读函数,不会修改类成员的值
        { 
            return this->data;
        }
        Node* GetAfterPointer(void) const
        { 
            return this->after;
        }
        Node* GetBeforPointer(void) const
        { 
            return this->befor;
        }
        bool SetData(dataType data = NULL);
        bool SetAfterPointer(Node& after = nullptr); // 引用地址(引用的原理,实际上就是指针,只不过写的时候更方便,传参的时候就可以少些一个&符号)
        bool SetBeforPointer(Node& befor = nullptr);
    };
    
    template < typename dataType >
    bool Node<dataType>::SetData(dataType data)
    { 
        this->data = data;
        if (this->data == data)
            return true;
        return false;
    }
    
    template < typename dataType >
    bool Node<dataType>::SetAfterPointer(Node& after)
    { 
        this->after = &after;
        if (this->after) // 如果this->after不是nullptr返回true
            return true;
        return false; // this->after是nullptr返回false
    }
    
    template < typename dataType >
    bool Node<dataType>::SetBeforPointer(Node& befor)
    { 
        this->befor = &befor;
        if (this->befor) // 如果this->befor不是nullptr返回true
            return true;
        return false; // this->befor是nullptr返回false
    }

如果你已经理解了原理图中的节点原理,那么这个节点类,你肯定可以理解.

**别直接复制,最好自己手动的去敲一遍,这样你会加深理解**.

你也可以给他写成struct结构体.

不过C++ 还是写成类比较好

注意!**纯C语言,是不允许struct结构体定义成员函数的**,反之C++允许结构体定义成员函数.

当我们定义好节点类,就可以**手动的去写出一个链表**了.

\---------------------------------CODEING---------------------------------

int main(int argc,char* argv[],char* env[])
    { 
        // 手动编写一个链表结构
        // 拥有3个数据的链表,少了链表编写出现BUG不能直观的反应出来,多了也没必要,3个数据标准链表测试情形
        // Mode 1
        Node<float>headerNode{  1.f,new Node<float>{ 2.f,nullptr,&headerNode},nullptr };
        // 因为是构造函数,是为了动态分配而编写,所以手动构建链表,只能做到一层套娃.
        Node<float>node{  3.f,nullptr,headerNode.GetAfterPointer() }; // header节点的after指针指向的就是第二个节点
        headerNode.GetAfterPointer()->SetAfterPointer(node);
        // mode 2
        Node<int>node1{  1 };
        Node<int>node2{  2 };
        Node<int>node3{  3 };
        node1.SetAfterPointer(node2);   // 让node1的后指针指向node2
        node2.SetAfterPointer(node3);   // 让node2的后指针指向node3
        node2.SetBeforPointer(node1);   // 让node2的前指针指向node1
        node3.SetBeforPointer(node2);   // 让node3的前指针指向node2
        return 0;
    }

[![2021-05-06.png][]][2021-05-06.png 1]

手动构建了两个链表,成功链接,这证明我们的Node类,写的是完美的

[下载原图][Link 2]

剩下的就很简单了,我们只需要编写一个可以动态分配并链接的LinkList类即可.

\---------------------------------CODEING---------------------------------

template < typename dataType >
    class LinkList
    { 
        Node<dataType>* headerNode; // 指向头节点
        Node<dataType>* tailNode;   // 指向尾结点
    public:
        explicit LinkList(dataType data) :headerNode(new Node<dataType>{  data }), tailNode(headerNode) // 只构建头节点构造函数
        { 
        }
        LinkList(std::vector<dataType>& vecobj):headerNode(nullptr),tailNode(headerNode)
        { 
            AddDataVector(vecobj);
        }
        void AddDataVector(std::vector<dataType>& vecobj)   // 可以将这个函数的大部分代码单独封装成一个AddData函数
        { 
            auto tmp = headerNode;
            for (uint count = 0; count < vecobj.size(); count++)
            { 
                if (!this->headerNode)
                { 
                    this->headerNode = new Node<dataType>{  vecobj[count] };
                    tmp = this->headerNode;
                    continue;
                }
                tmp->SetAfterPointer(* new Node<dataType>{ vecobj[count]});    // 这地方可能会比较绕,但是如果你真真正正的理解了我画的原理图,那么就很好明白
                tmp->GetAfterPointer()->SetBeforPointer(*tmp);               // 这3行代码,实现tmp指针的位移,和节点连接
                tmp = tmp->GetAfterPointer();                                   // 因为Node类实现的SetPointer函数使用了引用,所以New出来的右值,是一级指针,不匹配,得要降级才可以
            }
            this->tailNode = tmp;
        }
    };

这个linklist类只实现了对STL矢量容器内数据的快速添加.

剩下的功能,你可以按照你的需求来进行增减.

比如数据头部插入,数据尾部插入,数据索引,数据删除.

当你会了双向不循环链表后,其余的几种链表类型,你都可以独立的写出来!

源码地址:[https://github.com/Babaoxianyu/BlogSpotSource][https_github.com_Babaoxianyu_BlogSpotSource]

在这个库里,找到LinkList即可

[25E5_258F_258C_25E5_2590_2591_25E4_25B8_258D_25E5_25BE_25AA_25E7_258E_25AF_25E9_2593_25BE_25E8_25A1_25A8.png]: https://1.bp.blogspot.com/-VFCiepsblxM/YJOKciV97OI/AAAAAAAAAJI/VHUf3Ix27rYjyt6CNjSkGXKXU-VLLYyYwCLcBGAsYHQ/w690-h407/%25E5%258F%258C%25E5%2590%2591%25E4%25B8%258D%25E5%25BE%25AA%25E7%258E%25AF%25E9%2593%25BE%25E8%25A1%25A8.png
[25E5_258F_258C_25E5_2590_2591_25E4_25B8_258D_25E5_25BE_25AA_25E7_258E_25AF_25E9_2593_25BE_25E8_25A1_25A8.png 1]: https://1.bp.blogspot.com/-VFCiepsblxM/YJOKciV97OI/AAAAAAAAAJI/VHUf3Ix27rYjyt6CNjSkGXKXU-VLLYyYwCLcBGAsYHQ/s1878/%25E5%258F%258C%25E5%2590%2591%25E4%25B8%258D%25E5%25BE%25AA%25E7%258E%25AF%25E9%2593%25BE%25E8%25A1%25A8.png
[imagus]: https://chrome.google.com/webstore/detail/imagus/immpkjjlgappgfkkfieppnmlhakdmaab?hl=zh-CN
[Link 1]: https://mega.nz/file/6kYznSjI#dlTQykL8S-3PUWHDiLIKZdm3LvrEJjKIUK2Jw21HDXE
[2021-05-06.png]: https://1.bp.blogspot.com/-B1xf_BmAo1A/YJOk1mm8ONI/AAAAAAAAAJQ/B4lfWlCwlHIjcA8dZ1geH6KpVQzopXBawCLcBGAsYHQ/w511-h336/2021-05-06.png
[2021-05-06.png 1]: https://1.bp.blogspot.com/-B1xf_BmAo1A/YJOk1mm8ONI/AAAAAAAAAJQ/B4lfWlCwlHIjcA8dZ1geH6KpVQzopXBawCLcBGAsYHQ/s2048/2021-05-06.png
[Link 2]: https://1drv.ms/u/s!AjXAfKtXoAvckHoccwGl3wRO0X1R?e=CZs9J8
[https_github.com_Babaoxianyu_BlogSpotSource]: https://github.com/Babaoxianyu/BlogSpotSource/tree/master