数据结构——链表变形

我们在上次已经了解了单链表，今天我们来了解一下链表的各种变形，如果还没有了解过上面单链表的小伙伴可以点击这里：

https://blog.csdn.net/qq_67693066/article/details/137640481

带尾指针的链表

这里我们介绍带头结点和带尾指针的链表。

首先我们一开始的结点类基本不用改动：

//结点类的定义
template<class T>
struct linkNode
{
    linkNode()
        :_data(T())
        ,_next(nullptr)
    {

    }

    linkNode(const T& data)
        :_data(data)
        ,_next(nullptr)
    {

    }

    //数据域
    T _data;

    //下一个结点的指针
    linkNode<T>* _next;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

这是我们原先的链表结构：

//链表类的定义
template<class T>
class list
{
    typedef linkNode<T> Node;
public:
    list()
    {
        _head = new Node();
    }

    //创建结点
    Node* createNode(const T& data)
    {
        //
        Node* newnode = new Node(data);

        if(newnode == nullptr)
        {
            perror("new fail");
            exit(EXIT_FAILURE);
        }

        return newnode;
    }

private:
    Node* _head;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

这样我们创建一个链表的时候，默认就会有一个头结点：

现在我们想增加一个尾指针，尾指针会指向最后一个元素，这个时候头结点就是最后一个元素，所以我们创建一个尾指针指向head:

同时在构造函数中，在开辟完头结点后，记得把尾指针指向头结点：

尾插的变化

尾插的时候，我们只需要在完成链接之后，将尾指针移动到新结点就行了：

    //尾插
    void TailInsert(const T& data)
    {
        Node* newnode = createNode(data);

        _tail->_next = newnode;
        _tail = newnode;
    }
1
2
3
4
5
6
7
8

移动尾指针：

我们可以测试一下：

#pragma once
#include<iostream>

//结点类的定义
template<class T>
struct linkNode
{
    linkNode()
        :_data(T())
        ,_next(nullptr)
    {

    }

    linkNode(const T& data)
        :_data(data)
        ,_next(nullptr)
    {

    }

    //数据域
    T _data;

    //下一个结点的指针
    linkNode<T>* _next;
};

//链表类的定义
template<class T>
class list
{
    typedef linkNode<T> Node;
public:
    list()
    {
        _head = new Node();
        _tail = _head;
    }

    //创建结点
    Node* createNode(const T& data)
    {
        //
        Node* newnode = new Node(data);

        if(newnode == nullptr)
        {
            perror("new fail");
            exit(EXIT_FAILURE);
        }

        return newnode;
    }

    //尾插
    void TailInsert(const T& data)
    {
        Node* newnode = createNode(data);

        _tail->_next = newnode;
        _tail = newnode;
    }

    //打印
    void PrintList()
    {
        Node* cur = _head->_next;

        while(cur != nullptr)
        {
            std::cout<< cur->_data << " ";
            cur=cur->_next;
        }

        std::cout<<"END"<<std::endl;
    }

private:
    Node* _head;
    Node* _tail; //新增尾指针
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

#include "head.h"

int main()
{
    list<int> lt;

    lt.TailInsert(23);
    lt.TailInsert(1);
    lt.TailInsert(4);
    lt.TailInsert(100);

    lt.PrintList();

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

循环

我们现在想实现链表的循环，其实本质就是末尾结点的下一个结点就是头结点：

就算只有头结点一个，也可以自己指向自己：

我们接着用尾指针的链表来改造：

打印结束的条件也应该修改：

#pragma once
#include<iostream>

//结点类的定义
template<class T>
struct linkNode
{
    linkNode()
        :_data(T())
        ,_next(nullptr)
    {

    }

    linkNode(const T& data)
        :_data(data)
        ,_next(nullptr)
    {

    }

    //数据域
    T _data;

    //下一个结点的指针
    linkNode<T>* _next;
};

//链表类的定义
template<class T>
class list
{
    typedef linkNode<T> Node;
public:
    list()
    {
        _head = new Node();
        _tail = _head;
        _tail->_next = _head; //_tail此时指向_head的空间，可以控制_head所指的空间，这个操作是指向自己
    }

    //创建结点
    Node* createNode(const T& data)
    {
        //创建结点
        Node* newnode = new Node(data);

        if(newnode == nullptr)
        {
            perror("new fail");
            exit(EXIT_FAILURE);
        }

        return newnode;
    }

    //尾插
    void TailInsert(const T& data)
    {
        Node* newnode = createNode(data);

        _tail->_next = newnode;

        _tail = newnode;

        _tail->_next = _head; //最后一个结点的下一个结点指向头结点，完成循环
    }

    //打印
    void PrintList()
    {
        Node* cur = _head->_next;

        while(cur != _head)
        {
            std::cout<< cur->_data << " ";
            cur=cur->_next;
        }

        std::cout<<"END"<<std::endl;
    }

private:
    Node* _head;
    Node* _tail; //新增尾指针
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

双向

我们如果要完成双向，一个结点不能只存放后继结点，也要存放它的前驱结点：

所以我们的结点类要进行修改：

//结点类的定义
template<class T>
struct linkNode
{
    linkNode()
        :_data(T())
        ,_next(nullptr)
    {

    }

    linkNode(const T& data)
        :_data(data)
        ,_next(nullptr)
    {

    }

    //数据域
    T _data;

    //下一个结点的指针
    linkNode<T>* _next;
    
    //前一个结点
    linkNode<T>* prve;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

我们在有尾指针的基础上修改：

只有头结点的时候：

尾插的时候：

最后移动尾指针：

#pragma once
#include<iostream>

//结点类的定义
template<class T>
struct linkNode
{
    linkNode()
        :_data(T())
        ,_next(nullptr)
    {

    }

    linkNode(const T& data)
        :_data(data)
        ,_next(nullptr)
    {

    }

    //数据域
    T _data;

    //下一个结点的指针
    linkNode<T>* _next;

    //前一个结点
    linkNode<T>* _prve;
};

//链表类的定义
template<class T>
class list
{
    typedef linkNode<T> Node;
public:
    list()
    {
        _head = new Node();
        _tail = _head;

        _tail->_prve = nullptr; //头结点没有前驱，_prve置为空
        _tail->_next = _head; //_tail此时指向_head的空间，可以控制_head所指的空间，这个操作是指向自己
    }

    //创建结点
    Node* createNode(const T& data)
    {
        //创建结点
        Node* newnode = new Node(data);

        if(newnode == nullptr)
        {
            perror("new fail");
            exit(EXIT_FAILURE);
        }

        return newnode;
    }

    //尾插
    void TailInsert(const T& data)
    {
        Node* newnode = createNode(data);

        _tail->_next = newnode; //修改原先最后结点的后继
        newnode->_prve = _tail; //修改新结点的前驱

        _tail = newnode;

    }

    //打印
    void PrintList()
    {
        Node* cur = _head->_next;

        while(cur != nullptr)
        {
            std::cout<< cur->_data << " ";
            cur=cur->_next;
        }

        std::cout<<"END"<<std::endl;

        //反向打印
        cur = _tail;
        while(cur != _head)
        {
            std::cout<< cur->_data << " ";
            cur=cur->_prve;
        }

        std::cout<<"HEAD"<<std::endl;
    }

private:
    Node* _head;
    Node* _tail; //新增尾指针
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

注意这里，实现双向循环之后，可以实现双向打印：

    //打印
    void PrintList()
    {
        Node* cur = _head->_next;

        while(cur != nullptr)
        {
            std::cout<< cur->_data << " ";
            cur=cur->_next;
        }

        std::cout<<"END"<<std::endl;

        //反向打印
        cur = _tail;
        while(cur != _head)
        {
            std::cout<< cur->_data << " ";
            cur=cur->_prve;
        }

        std::cout<<"HEAD"<<std::endl;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

双向循环

双向循环就是处理了头结点的前驱和最后一个结点的后继：

在双向链表中：

头结点的前驱指向最后一个结点
最后一个结点的后继指向头结点

只有一个结点的时候，前驱和后继都指向自己：

在双向循环中，头结点储存了最后一个结点的信息，所以我们可以去掉尾指针。

#pragma once
#include<iostream>

//结点类的定义
template<class T>
struct linkNode
{
    linkNode()
        :_data(T())
        ,_next(nullptr)
    {

    }

    linkNode(const T& data)
        :_data(data)
        ,_next(nullptr)
    {

    }

    //数据域
    T _data;

    //下一个结点的指针
    linkNode<T>* _next;

    //前一个结点
    linkNode<T>* _prev;
};

//链表类的定义
template<class T>
class list
{
    typedef linkNode<T> Node;
public:
    list()
    {
        _head = new Node();

        _head->_prev = _head; //头结点没有前驱，_prve置为空
        _head->_next = _head; 
    }

    //创建结点
    Node* createNode(const T& data)
    {
        //创建结点
        Node* newnode = new Node(data);

        if(newnode == nullptr)
        {
            perror("new fail");
            exit(EXIT_FAILURE);
        }

        return newnode;
    }

    //尾插
    void TailInsert(const T& data)
    {
        Node* newnode = createNode(data);

        newnode->_prev = _head->_prev; //修改新结点的前驱
        _head->_prev->_next = newnode; //修改原先最后结点的后继

        _head->_prev = newnode; //修改储存信息，指向最新的结点
        newnode->_next = _head; //新结点的后继指向头结点
    }

    //打印
    void PrintList()
    {
        Node* cur = _head->_next;

        while(cur != _head)
        {
            std::cout<< cur->_data << " ";
            cur=cur->_next;
        }

        std::cout<<"END"<<std::endl;

        //反向打印
        cur = _head->_prev;
        while(cur != _head)
        {
            std::cout<< cur->_data << " ";
            cur=cur->_prev;
        }

        std::cout<<"HEAD"<<std::endl;
    }

private:
    Node* _head;
    //Node* _tail; //新增尾指针
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100