数据结构的基础知识

数据结构的理解和相关定义

数据结构的理解

数据结构是指存储和组织数据的方式，它分为物理结构和逻辑结构
（简单来说，数据结构就是设计数据以何种方式组织，何种方式存储在计算机中。比如:列表、集合与字典等都是一种数据结构。）
常用的数据结构有线性表、树等数据结构
^c1d1

数据结构中的物理结构和逻辑结构

数据结构中的逻辑结构的理解

某个数据结构的逻辑结构，就是指在这个数据结构里，数据元素之间的互相关系。
比如说线性表的的逻辑结构就是线性结构，就是表中的的元素之间存在一对一的关系，一个元素后面接着一个，这是线性表的逻辑结构。
再比如二叉树的逻辑结构，元素之间的相互关系，就是一个父亲节点下面有两个子节点，子节点下面又有两个子节点。这就是二叉树的逻辑结构。二叉树虽然可以用数组实现，但是其逻辑结构则是树结构。

数据结构中的物理结构的理解

某个数据结构的物理结构，就是指在这个数据结构里，数据存储在磁盘中的方式。
比如有一个数据结构为线性表，其逻辑结构是线性结构。而线性表根据不同的物理结构，又有两种实现方式。一种实现方式的物理结构是使用顺序存储，线性表的元素连续的的存储在计算机存储器中，这时候这种采用顺序存储结构的线性表就叫顺序表。另一种实现方式的物理结构是使用链式结构，其元素不一定是连续的存储在计算机存储器中 ，而用链式存储结构的线性表也叫链表。

数据结构中的逻辑结构分类

数据结构按照其逻辑结构可分为线性结构、树结构、图结构。
线性结构，数据结构中的元素存在一对一的相互关系。比如列表，一个元素后面接着一个元素。

树结构，数据结构中的元素存在一对多的相互关系。比如二叉树，一个父亲节点后面有两个子节点。

图结构，数据结构中的元素存在多对多的相互关系

物理结构分类

数据结构按照其物理结构可分为顺序存储、链式存储、索引存储以及散列存储。
顺序存储，存储顺序是连续的，在内存中用一组地址连续的存储单元依次存储线性表的各个数据元素。

链式存储，在内存中的存储元素不一定是连续的，用任意地址的存储单元存储元素，元素节点存放数据元素以及通过指针指向相邻元素的地址信息。

索引存储，除建立存储结点信息外，还建立附加的索引表来标识节点的地址。索引表由若干索引项组成。

散列存储，又称Hash存储，由节点的关键码值决定节点的存储地址

注意，
（数据结构学习重点就在数据结构的逻辑结构，物理结构了解即可）

数据结构的常用函数

初始化、释放、增删查遍历

线性表

线性表的基础知识

线性表的理解

线性表是一种常见的数据结构，它是由n个具有相同数据类型的数据元素a1, a2, …, an 组成的有限序列。
线性表的特点是数据元素之间存在一种线性关系，每个数据元素最多只有一个直接前驱和一个直接后继。

线性表的性质

a0为线性表的第一个元素，只有一个后继a1。
an为线性表的最后一个元素，只有一个前驱an-1。
除a0和an外的其它元素ai，既有前驱ai-1，又有后继ai+1。

线性表举例说明


学生情况信息表是一个线性表，表中数据元素的类型为由学号、姓名、性别、年龄、专业等组成的结构体类型，也就是说表的每一行（除第一行）就是一个数据元素，一个数据元素内容包含 学号、姓名、性别、年龄、专业等 内容。

线性表的结构

线性表的逻辑结构是线性结构。线性表根据不同的物理结构，又有两种实现方式。一种实现方式的物理结构是使用顺序存储，线性表的元素连续的的存储在计算机存储器中，这时候这种采用顺序存储结构的线性表就叫顺序表。另一种实现方式的物理结构是使用链式结构，其元素不一定是连续的存储在计算机存储器中 ，而用链式存储结构的线性表也叫链表。

顺序表

顺序表的基础知识

顺序表的理解

顺序表是线性表的一种。线性表根据不同的物理结构，有两种实现方式，当线性表的物理结构是采用顺序存储结构时，线性表就叫顺序表。此时内存中会用地址连续的一块存储空间顺序存放线性表的各元素

顺序表的实现

接口文件SXB.h

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
#pragma once
class SXB
{
private:
    int *dz; //地址，存放数据的地址，他存放数组的首地址，由这个首地址，就可以获得整个数组内容。
	int sl;  //数量，表示存储在当前容器的元素数量
    int rl;  //容量，表示当前容器最大能容纳的元素
  
public:
    //初始构造函数，初始化对象
    SXB();

    //末尾插入函数，在顺序表的末尾插入传入的数值.value是传入顺序表的数值
    bool push_back_SXB(int value);

    //位置删除函数，根据传入的位置，在顺序表中删除该位置的值。pos是传入的位置。
    bool remove_pos_SXB(int pos);

    //值删除函数，根据传入的数值，在顺序表删除该值。value是传入顺序的数值。
    bool remove_value_SXB(int value);

    //查位置函数，根据传入的数值，在顺序表中，查找该该值的位置。value是传入的数值
    int find_pos_SXB(int value);

    //打印函数，输出顺序表的值。
    bool print_SXB();

    //清空函数，清空顺序表的值。
    bool clear_SXB();

    //查容量函数，查找当前顺序表的容量
    int return_rl_SXB();

    //查数量函数，查找当前顺序表存储的元素的数量。
    int return_sl_SXB();
  
    //析构函数
    ~SXB();
};

接口的实现文件 SXB.cpp

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <iostream>
#include "SXB.h"
using namespace std;

//初始构造函数，初始化对象
SXB::SXB()
{
    dz = new int[20];
    rl = 20;
    sl = 0;
}

//末尾插入函数，在顺序表的末尾插入传入的数值.value是传入顺序表的数值
bool SXB::push_back_SXB(int value)
{
    //判断是否顺序表的容量满了。如果满了执行if里的函数
    if (sl == rl)
    {
        //申请一个新的更多大的空间，这个空间是旧的空间的大小的两倍。xdz是新地址用于存储新的空间的地址。
        int *xdz = new int[rl * 2];
        //把旧的空间的数据复制到新的空间
        for (int i = 0; i < sl; i++)
        {
            xdz[i] = dz[i];
        }
        //把旧的空间释放掉
        delete[] dz;
        dz = xdz;

        //更新容量
        rl = rl * 2;
    }

    //在顺序表末尾插入新元素
    dz[sl] = value;
    //更新元素数量
    ++sl;

    return true;
}

//位置删除函数，根据传入的位置，在顺序表中删除该位置的值。pos是传入的位置。
bool SXB::remove_pos_SXB(int pos)
{
    //顺序表元素数量为0，或者传入的位置大于顺序表元素的数量，则则删除失败
    if (sl == 0 || pos > sl || pos <= 0)
        return false;

    //删除元素，就是将顺序表pos位置开始的值（不包括pos位置的值），都往前挪一个位置，自然就删除了pos位置的值
    else
    {
        for (int i = pos - 1; i < sl - 1; i++)
        {
            dz[i] = dz[i + 1];
        }
        return true;
    }
}

//值删除函数，根据传入的数值，在顺序表删第一次出现的该值。value是传入顺序的数值。
bool SXB::remove_value_SXB(int value)
{
    //判断顺序表元素数量是否为0
    if (sl == 0)
        return false;

    //获取该值的位置
    int pos = find_pos_SXB(value);

    //如果找不到该值
    if (pos == 0)
        return false;

    //如果找到该值，用位置删除函数来进行删除。
    else
    {
        remove_pos_SXB(pos);
        return true;
    }
}

//查位置函数，根据传入的数值，在顺序表中，查找该该值的位置，返回的位置是该值在元素表中第一次被找到的位置。value是传入的数值.返回0说明找不到这个值。
int SXB::find_pos_SXB(int value)
{
    //如果顺序表元素为0，则返回0
    if (sl == 0)
    {
        return 0;
    }

    else
    {
        //遍历循环，查找顺序表是否有该值
        for (int i = 0; i < sl; i++)
        {
            if (dz[i] == value)
            {
                return i + 1;
            }
        }

        //找不到该值返回0
        return 0;
    }
}

//打印函数，输出顺序表的值。
bool SXB::print_SXB()
{
    //顺序表元素数量为0，则无法打印。
    if (sl == 0)
    {
        return false;
    }

    //顺序表元素数量不为0，则可以进行打印。
    else
    {
        for (int i = 0; i < sl; i++)
        {
            cout << dz[i] << endl;
        }
        return true;
    }
}

//清空函数，清空顺序表的值。
bool SXB::clear_SXB()
{
    //假如顺序表里已存储元素，不需要把元素清空掉，只要把表示元素数量的变量sl设为0即可。这时候在存储元素，也是从顺序表开头开始存储。
    sl = 0;
    return true;
}

//返回容量函数，返回当前顺序表的容量
int SXB::return_rl_SXB()
{
    return rl;
}

//返回数量函数，返回当前顺序表存储的元素的数量。
int SXB::return_sl_SXB()
{
    return sl;
}

//析构函数,用来释放数组的内存
SXB::~SXB()
{
    delete[] dz;
}

//测试文件 test.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include "SXB.h"
#include "SXB.cpp"
using namespace std;

int main()
{
    SXB a;
    for (int i = 0; i <= 22; i++)
    {
        a.push_back_SXB(i);
    }
    a.push_back_SXB(4);
    a.print_SXB();
    cout << a.return_rl_SXB() << endl;
    cout << a.return_sl_SXB() << endl;

}


单链表

单链表的基础知识

链表的理解

链表是线性表的一种，当线性表的物理结构是采用链式存储结构时，线性表就叫链表。此时其元素不一定是连续的存储在计算机存储器中。

链表的节点理解

在链表中，每个数据元素由一个结点表示。为了建立起数据元素之间的逻辑关系，一个的最基本的链表的节点的组成形式，除了存放数据元素的自身信息外，还需要有一个指针存储其后继元素所在的地址信息。有的其他链表的节点，除了有一个指向其后继元素的指针，可能还会其其他功能的指针。

单链表的理解

单链表是最基本的一种链表，每个数据元素由一个结点表示，节点除了存放数据元素的自身信息，还要含有一个指针使其指向后继元素，这种一个节点只含有一个指针，这个指针向其后继元素的链表表称为单链表。

头指针的理解

在单链表中，由于每个结点的存储地址存放在其前驱结点的next域中,因此第一个结点是没有前驱结点的，它的地址就是整个链表的开始地址,必须将第一个结点的地址放到一个指针变量(如图2-3所示的head)中，该指针变量称为头指针。这样就可以从头指针开始，依次找到每个结点。通常用头指针来标识一个单链表。最后一个结点没有后继,其指针域必须置空(NULL)，表明此单链表到此结束。

头结点的理解

在单链表中，为了方便操作，有时在链表的第一个结点前加入一个头结点,然后让头结点的next指向链表的第一个节点。
头结点的类型与其他数据结点相同，标识链表的头指针变量head 中存放该头结点的地址。这样即使是空表，头指针变量head也不为空了。头结点的加入使得单链表无论是否为空，头指针始终指向头结点，从而使空表和非空表的处理成为一致。

总的来说，头结点的加入完全是为了操作的方便，它的数据域可以不存放任何信息，也可以存放有关链表的整体信息，如表长;指针域中存放的是第一个数据结点的地址,空表时其中为空。

带头节点的单链表图示

单链表数据节点的构建思路

数据
变量data：用模板参数来定义的变量，用来存储各种类型数据
指针next：存储下个数据节点的地址

单链表的构建思路

[[单链表框架搭建.mp4#t=01:57.415,02:43.5]]

数据
头指针head：指向头节点的指针。
变量Sl：表示当前表格里元素的数量

节点插入实现思路

[[单链表的实现.mp4#t=07:18.279,09:40]]

节点删除实现思路

[[单链表的实现.mp4#t=11:41.314,12:39]]

链表的释放实现思路

[[单链表的实现.mp4#t=19:48.201,21:36.3]]

单链表的实现

接口文件DLB.h

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
#pragma once
//链表的节点
template <class T>
struct Node
{

    T date;        //用来存储数据
    Node<T> *next; //用来存储
};

template <class T>
class DLB
{
private:
    Node<T> *head;//单链表的头指针，头指针指向的第一个节点为头结点。
    int sl;//数量，表示当前容器的元素数量。

public:

    //链表的初始化函数，用来初始化你的链表。
    DLB();
    
    //插入函数，指定表格的位置，插入你的数值。pos是你指定的位置，value是你要插入的值，既你要把数据插入到第pos-1的结点的后面，如果pos为1，就是要把数据插入到头结点的后面。插入成功返回true，否则返回false；
    bool insert_DLB(int pos, T value);

    //位置删除函数，根据传入的位置，在顺序表中删除该位置的值。pos是传入的位置。成功则返回true，否则返回false
    bool removebypos_DLB(int pos);

    //返回数量函数，返回当前链表存储的元素的数量。
    int return_sl_DLB();
    
    //位置查找函数，根据传入的位置，查找该位置的数据。pos是传入的位置。
    T findbypos_DLB(int pos );

    //打印函数，按顺序打印你的单链表的数据。
    bool print_DLP();

    //链表的释放函数，在链表结束后，用来释放你的链表。
    ~DLB();
};


实现文件DLB.cpp

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include "DLB.h"
#include <iostream>
#include <cstdlib>
using namespace std;

//链表的初始化函数，用来初始化你的链表。
template <class T>
DLB<T>::DLB()
{
    //创建一个链表的头结点。并将头结点指向后继的指针为null
    Node<T> *tjd = new Node<T>;
    tjd->next = NULL;

    //将头指针指向头结点
    head = tjd;
    //初始化sl
    sl = 0;
}

//插入函数，指定表格的位置，插入你的数值。pos是你指定的位置，value是你要插入的值，既你要把数据插入到第pos-1的结点的后面，如果pos为1，就是要把数据插入到头结点的后面。插入成功返回true，否则返回false；
template <class T>
bool DLB<T>::insert_DLB(int pos, T value)
{
    //插入的位置非法则返回空。且我们设定当链表元素数量为n的时候，我们可以把值插入到n+1的位置里。
    if (pos <= 0 || pos > sl + 1)
        return false;

    //插入位置合法，则进行插入
    else
    {
        //创建新的结点，来存储传入的数据
        Node<T> *newnode = new Node<T>;
        newnode->date = value;
        newnode->next = NULL;
        //创建一个指针，用来存储后面我们找到pos-1的位置的节点。里面先暂时存储第0个位置的节点，也就是头结点的位置。
        Node<T> *jd = head;
        //找到第pos-1的位置的节点，把这个节点的位置存储到jd。如果pos-1=0，就不用找，因为jd已经存储第0个节点的位置。
        for (int i = 1; i < pos; i++)
        {
            jd = jd->next;
        }

        //把要插入的节点
        newnode->next = jd->next;
        jd->next = newnode;

        //更新sl
        ++sl;
        return true;
    }
}

//位置删除函数，根据传入的位置，在顺序表中删除该位置的值。pos是传入的位置。成功则返回true，否则返回false
template <class T>
bool DLB<T>::removebypos_DLB(int pos)
{
    //如果表为空，或者删除的位置非法，则返回false
    if (sl == 0 || (pos <= 0 || pos > sl))
    {
        return false;
    }
    //表不为空，且删除的位置合法
    else
    {
        //创建一个指针，用来存储后面我们找到pos-1的位置的节点。里面先暂时存储第0个位置的节点，也就是头结点的位置。
        Node<T> *jd = head;
        //找到第pos-1的位置的节点，把这个节点的位置存储到jd。如果pos-1=0，就不用找，因为jd已经存储第0个节点的位置。
        for (int i = 1; i < pos; i++)
        {
            jd = jd->next;
        }

        //创建一个指针，用来存储删除的节点，也就是pos位置的节点
        Node<T> *nextjd = jd->next;
        //将要删除节点的从表里踢出去
        jd->next = nextjd->next;

        //释放要删除的节点
        delete nextjd;
        //更新sl
        --sl;
        return true;
    }
}

//返回数量函数，返回当前链表存储的元素的数量。
template <class T>
int DLB<T>::return_sl_DLB()
{
    return sl;
}

//位置查找函数，根据传入的位置，查找该位置的数据。pos是传入的位置。
template <class T>
T DLB<T>::findbypos_DLB(int pos)
{
    //如果表为空，或查找的位置非法，则执行终止函数
    if (sl == 0 || (pos <= 0 || pos > sl))
    {
        cout << "操作错误" << endl;
        //非正常退出程序函数
        exit(1);
    }
    else
    {
        //创建一个指针，用来存储后面我们找到pos的位置的节点。里面先暂时存储第0个位置的节点，也就是头结点的位置。
        Node<T> *jd = head;
        //找到第pos的位置的节点，把这个节点的位置存储到jd。
        for (int i = 1; i <= pos; i++)
        {
            jd = jd->next;
        }

        //返回寻找到的值
        return jd->date;
    }
}
//打印函数，按顺序打印你的单链表的数据。
template <class T>
bool DLB<T>::print_DLP()
{
    //查看表是否为空，为空则返回false
    if (sl == 0)
    {
        return false;
    }
    //表不为空，按顺序遍历表格
    else
    {
        //创建一个指针，用来指向表格中的节点，里面先暂时指向头结点
        Node<T> *jd = head;
        //遍历表
        for (int i = 1; i <= sl; i++)
        {
            jd = jd->next;
            cout << i << ":" << jd->date << endl;
        }
    }
}

//链表的释放函数，在链表结束后，用来释放你的链表。
template <class T>
DLB<T>::~DLB()
{
    //创建一个指针，用来指向表格中的节点，里面先暂时指向头结点
    Node<T> *jd = head;
    //用while循环，判断jd所存储的节点地址是否为空，不为空，则找一个节点缓存当前节点的地址。然后让jd存储下一个节点的地址，最后删除当前节点
    while (jd)
    {
        //缓存当前的地址。
        Node<T> *nextjd = jd;
        //让jd存储下一个节点的地址
        jd = jd->next;
       //释放缓存的的地址
        delete nextjd;
    }
}

测试文件test.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include "DLB.h"
#include "DLB.cpp"
using namespace std;
int main()
{
    DLB<int> a;

    for (int i = 1; i <= 10; i++)
    {
        a.insert_DLB(i, i);
    }
    cout << "sl==" << a.return_sl_DLB() << endl;
    cout << "第五个为" << a.findbypos_DLB(5) << endl;
    a.print_DLP();
}

企业链表

企业链表的基础知识

企业链表的理解

[[企业链表构建思路.mp4#t=05:58.605,10:48]]
要想理解企业链表，首先得知道结构体的地址相关知识。假如定义一个结构体，里面有数据a和数据b。那么当你获得这个结构体的数据a的地址，就可以获得这个整个结构体对象的地址。（对象a的首地址和整个结构体对象首地址是一样的，只不过两个数据的地址的类型，即地址长度不一样）

然后可以知道企业链表和单链表之间的区别，普通的单链表的一个数据结点由两部分a和b组成，部分a存储下一个结点的地址（整个结点的地址），而b部分存储数据内容。
企业链表，的一个数据结点也两部分a和b组成，但是a本身也是一个节点，a存储下一个数据结点的里的a节点的地址，而不是像单链表一样存储着整个数据节点的地址，然后b部分依然是只存储数据内容，对比单链表，企业链表a只是存储整个结点中a节点的地址
这么做的好处在于企业链表的指针域和数据域是可以分开写的。
我们可以先把指针节点像普通数据节点一样一样，串连成指针链表。之后我们要把什么数据以链表的形式组织起来，那么就只需要我们把这个类型的数据，挂在已经串联起来的指针节点下面即可。

内核链表和企业链表的区别

[[企业链表构建思路.mp4#t=10:52.580]]

企业链表的实现

接口文件QYLB.h

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
#pragma once
//企业链表小结点，用来串连数据结点
struct Xjd
{
    // next，用来存储下一个数据结点里的小结点的地址。
    Xjd *next;
};

class QYLB
{
private:
    //企业链表的头结点
    Xjd head;

    //数量，表示表格的元素数量
    int sl;

public:
    //链表初始化函数
    QYLB();

    //插入函数，指定表格的位置，插入你的数值。pos是你指定的位置，value是你要插入的值。插入成功返回true，否则返回false；
    bool insert_QYLB(int pos, Xjd *data);

    //位置删除函数，根据传入的位置，在顺序表中删除该位置的值。pos是传入的位置。成功则返回true，否则返回false
    bool removebypos_QYLB(int pos);

    //值查找函数，根据传入的数据节点的小结点，查找该数据的位置,查到返回该数值位置，找不到返回0。data是传入的数据节点的小结点。compare是bool型函数指针，需要用户自定义比较数据节点的函数，然后把该函数地址通过函数指针传入进来，我们就可以依靠函数指针调用用户自定义比较数据节点的函数。
    int findbyvalue_QYLB(Xjd *data, bool (*compare)(Xjd *p1, Xjd *p2));

    //打印函数，按顺序打印你的单链表的数据，print为bool型函数指针，因为该链表的函数操作都是处理小结点的，无法处理数据节点，所以需要用户自定义操作数据节点的函数，然后把该函数地址通过函数指针传入进来，我们就可以依靠函数指针调用用户自定义的函数。
    bool print_QYLB(bool (*prin)(Xjd *));

    //返回数量函数，返回当前链表存储的元素的数量。
    int return_sl_QYLB();

    //链表析函数，在对象结束后，释放你的链表
    ~QYLB();
};

实现文件QYLB.cpp

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include "QYLB.h"
using namespace std;
//链表初始化函数

QYLB::QYLB()
{

    //将头结点指向后继的指针为null
    head.next = NULL;

    //初始化变量sl
    sl = 0;
}

//插入函数，指定表格的位置，插入你的数值。pos是你指定的位置，date是你要插入数据节点的小结点地址。插入成功返回true，否则返回false；
bool QYLB::insert_QYLB(int pos, Xjd *data)
{
    //插入的位置非法则返回空。且我们设定当链表元素数量为n的时候，我们可以把值插入到n+1的位置里。
    if (pos <= 0 || pos > sl + 1)
        return false;

    //插入位置合法，则进行插入
    else
    {

        //创建一个小结点。里面先暂时存储第0个小节点（也就是头结点）的地址。后面我们可以用这个结点来找第pos-1位置小结点地址。
        Xjd *xjd = &head;
        //循环找到第pos-1位置的小结点地址。在下面循环里，i为多少，小结点就是第i个小结点地址。
        for (int i = 1; i < pos; i++)
        {
            xjd = xjd->next;
        }

        //把要插入链表里小结点，存储原pos位置的小结点地址。
        data->next = xjd->next;
        //让pos-1位置的小结点存储，要插入的小结点的地址。
        xjd->next = data;

        //更新sl
        ++sl;
    }
}

//位置删除函数，根据传入的位置，在顺序表中删除该位置的值。pos是传入的位置。成功则返回true，否则返回false
bool QYLB::removebypos_QYLB(int pos)
{
    //如果表为空，或者删除的位置非法，则返回false
    if (sl == 0 || (pos <= 0 || pos > sl))
    {
        return false;
    }
    //表不为空，且删除的位置合法
    else
    {
        //创建一个小结点。用来指向表格中的小结点，里面先暂时指向头结点地址
        Xjd *xjd = &head;

        //找到第pos-1的位置的小节点，把这个小结点的位置存储到xjd。如果pos-1=0，就不用找，因为xjd已经存储第0个小节点的位置。
        for (int i = 1; i < pos; i++)
        {
            //让小结点指向下一个小结点地址。
            xjd = xjd->next;
        }

        //直接把pos-1位置的小结点存储原pos+1位置小结点地址,因为数据节点不是动态申请的，所以不需要对pos位置的数据节点delete掉
        xjd->next = xjd->next->next;

        //更新sl
        --sl;
        return true;
    }
}

//值查找函数，根据传入的数据节点的小结点，查找该数据的位置,查到返回该数值位置，找不到返回0。data是传入的数据节点的小结点。compare是bool型函数指针，需要用户自定义比较数据节点的函数，然后把该函数地址通过函数指针传入进来，我们就可以依靠函数指针调用用户自定义比较数据节点的函数。
int QYLB::findbyvalue_QYLB(Xjd *data, bool (*compare)(Xjd *p1, Xjd *p2))
{
    //如果表为空，或查找的位置非法，则执行终止函数
    if (sl == 0)
    {
        cout << "链表为空" << endl;
        //非正常退出程序函数
        exit(1);
    }

    //列表不为空
    else
    {
        //创建一个小结点指针，用来指向表格中的小结点，里面先暂时指向头结点。
        Xjd *xjd = &head;
        //循环，找到第pos位置的小结点
        for (int i = 1; i <= sl; i++)
        {
            xjd = xjd->next;
            if (compare(xjd, data))
            {
                return i;
            }
        }
        return 0;
    }
}

//打印函数，按顺序打印你的单链表的数据，print为bool型函数指针，因为该链表的函数操作都是处理小结点的，无法处理数据节点，所以需要用户自定义操作数据节点的函数，然后把该函数地址通过函数指针传入进来，我们就可以依靠函数指针调用用户自定义的函数。
bool QYLB::print_QYLB(bool (*prin)(Xjd *))
{
    //查看表是否为空，为空则返回false
    if (sl == 0)
    {
        return false;
    }
    //表不为空，按顺序遍历表格
    else
    { //创建一个小结点。用来指向表格中的小结点，里面先暂时指向头结点地址

        Xjd *xjd = &head;
        //循环遍所有的小结点
        for (int i = 1; i <= sl; i++)
        {
            //让小结点指向下一个小结点地址。
            xjd = xjd->next;
            //调用传入的用户自定义的函数，通过小结点，来打印存储小结点的数据节点的数据。
            prin(xjd);
        }
    }
    return true;
}

//返回数量函数，返回当前链表存储的元素的数量。
int QYLB::return_sl_QYLB()
{
    return sl;
}

//链表析函数，一般是用在对象结束后，释放我们申请的动态内存，因为企业链表没有动态申请内存，所以析构函数不用写。
QYLB::~QYLB()
{
}

测试文件Test.cpp

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
#include <iostream>
#include "QYLB.h"
#include "QYLB.cpp"
using namespace std;
//创建数据节点
struct Data
{
    Xjd xjd;
    int data;
};
//用户自定义的函数，可以通过小结点地址，来找到存储小结点的数据节点，并且打印存储的数据。
bool prin(Xjd *xjd)
{
    Data *p = (Data *)xjd;
    cout << p->data << endl;
}
//用户自定义的函数，可以通过两个小结点地址，来对比两个小结点的对应数据节点存储的数据是否一样，一样返回true，否则返回false。
bool compare(Xjd *p1, Xjd *p2)
{
    Data *p3 = (Data *)p1;
    Data *p4 = (Data *)p2;
    if (p3->data == p4->data)
    {
        return true;
    }
    return false;
}
int main()
{
    //创建数据节点对象，
    Data a[11];
    QYLB b;
    //用循环来对数据节点写入数据，
    for (int i = 1; i <= 10; i++)
    {
        a[i].data = i;
        //要想把数据节点像链表一样串连起来，只需要把数据节点的小结点串连起来，那么我们只需要给插入函数传进去数据节点的小结点
        b.insert_QYLB(i, (Xjd *)&a[i]);
    }

    b.print_QYLB(prin);
    b.removebypos_QYLB(5);
    cout << "sl:" << b.return_sl_QYLB() << endl;
    cout << "find 6:" << b.findbyvalue_QYLB((Xjd *)&a[6], compare) << endl;
}

单向循环链表

单向循环链表的基础知识

单向循环链表的理解

单向循环链表与单链表仅仅有尾部node指针域指向不同的差别，对于单向链表尾部node由于没有后续node，其指针域需指向NULL。而单向循环链表将尾部node的指针域指向头部node，首尾相连构成单向循环链表

单向循环链表图示

单向循环链表数据节点的构建思路

数据
变量data：用模板参数来定义的变量，用来存储各种类型数据
指针next：存储下个数据节点的地址

单链表的构建思路

[[循环链表的构建思路.mp4]]

数据
头指针head：指向头节点的指针。
变量Sl：表示当前表格里元素的数量

单向循环链表的实现

接口文件DXHBLB.h

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
#pragma once
template <class T>
//数据节点
struct Sjjd
{
    //用来存储下一个数据节点的地址
    Sjjd<T> *next;
    //存储数据
    T data;
};

template <class T>
class DXXHLB
{
private:
    //头结点，用来存储数据
    Sjjd<T> *head;
    //数量，表示当前容器的元素数量
    int sl;

public:
    //链表的初始化函数，用来初始化你的链表
    DXXHLB();
    //插入函数，指定表格的位置，插入你的数值。pos是你指定的位置，value是你要插入的值，既你要把数据插入到第pos-1的结点的后面，如果pos为1，就是要把数据插入到头结点的后面。插入成功返回true，否则返回false；
    bool insert_DXXHLB(int pos, T value);

    //位置删除函数，根据传入的位置，在顺序表中删除该位置的值。pos是传入的位置。成功则返回true，否则返回false
    bool removebypos_DXXHLB(int pos);

    //值删除函数，根据传入的值，在顺序表中删除有该值的第一个结点。value是传入要删除的值。成功则返回true，否则返回false
    bool removebyvalue_DXXHLB(T value);

    //返回数量函数，返回当前链表存储的元素的数量。
    int return_sl_DXXHLB();

    //位置查找函数，根据传入的位置，查找该位置的数据。pos是传入的位置。
    T findbypos_DXXHLB(int pos);

    //打印函数，按顺序打印你的单链表的数据。
    bool print_DXXHLB();

    //输出约瑟夫序列函数，解决约瑟夫问题，输出约瑟夫所需要的序列
    void prinysf_DXXHLB(int m);
    //析构函数，释放你的链表
    ~DXXHLB();
};


实现文件DXXHLB.cpp

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
#include <iostream>
#include "DXXHLB.h"
using namespace std;
//链表的初始化函数，用来初始化你的链表
template <class T>
DXXHLB<T>::DXXHLB()
{
    //创建一个链表的头结点。
    head = new Sjjd<T>;

    //将头结点的后继指针，指向自己
    head->next = head;

    //更新sl
    sl = 0;
}
//插入函数，指定表格的位置，插入你的数值。pos是你指定的位置，value是你要插入的值，既你要把数据插入到第pos-1的结点的后面，如果pos为1，就是要把数据插入到头结点的后面。插入成功返回true，否则返回false；
template <class T>
bool DXXHLB<T>::insert_DXXHLB(int pos, T value)
{
    //插入的位置非法则返回空。且我们设定当链表元素数量为n的时候，我们可以把值插入到n+1的位置里。
    if (pos <= 0 || pos > sl + 1)
        return false;

    //插入位置合法，则进行插入
    else
    {
        //创建新的结点，来存储传入的数据
        Sjjd<T> *newnode = new Sjjd<T>;
        newnode->data = value;

        //创建一个指针，用来存储后面我们找到pos-1的位置的节点。里面先暂时存储第0个位置的节点，也就是头结点的位置。
        Sjjd<T> *jd = head;

        //找到第pos-1的位置的节点，把这个节点的位置存储到jd。如果pos-1=0，就不用找，因为jd已经存储第0个节点的位置。
        for (int i = 1; i < pos; i++)
        {
            jd = jd->next;
        }
        //把要插入的节点插入表格里面去
        newnode->next = jd->next;
        jd->next = newnode;

        //更新sl
        ++sl;
        return true;
    }
}

//位置删除函数，根据传入的位置，在顺序表中删除该位置的值。pos是传入的位置。成功则返回true，否则返回false
template <class T>
bool DXXHLB<T>::removebypos_DXXHLB(int pos)
{
    //如果表为空，或者删除的位置非法，则返回false
    if (sl == 0 || (pos <= 0 || pos > sl))
    {
        return false;
    }
    //表不为空，且删除的位置合法
    else
    {
        //创建一个指针，用来存储后面我们找到pos-1的位置的节点。里面先暂时存储第0个位置的节点，也就是头结点的位置。
        Sjjd<T> *jd = head;
        //找到第pos-1的位置的节点，把这个节点的位置存储到xjd。如果pos-1=0，就不用找，因为jd已经存储第0个节点的位置。
        for (int i = 1; i < pos; i++)
        {
            jd = jd->next;
        }
        //创建一个指针，用来存储删除的节点，也就是pos位置的节点
        Sjjd<T> *deletejd = new Sjjd<T>;
        deletejd = jd->next;
        //将要删除节点的从表里踢出去
        jd->next = jd->next->next;
        //释放要删除的节点
        delete deletejd;

        //更新sl
        --sl;
    }
    return true;
}
//值删除函数，根据传入的值，在顺序表中删除有该值的第一个结点。value是传入要删除的值。成功则返回true，否则返回false
template <class T>
bool DXXHLB<T>::removebyvalue_DXXHLB(T value)
{
    //如果表为空，则返回false
    if (sl == 0)
    {
        return false;
    }

    else
    {
        //创建一个指针，用来存储后面我们遍历表的节点，当找到我们要删除的结点的时候，把jd删除。里面先暂时存储第0个位置的节点，也就是头结点。
        Sjjd<T> *jd = head;
        //创建一个指针，先让其存储当前的jd，然后jd就可以存储下一个结点的地址。也就是让lastjd作为jd的上一个结点。的这样删除jd的时候就会很方便。
        Sjjd<T> *lastjd;

        for (int i = 1; i <= sl; i++)
        {
            // lastjd存储当前的jd
            lastjd = jd;
            // jd存储下一个结点的地址
            jd = jd->next;
            if (jd->data == value)
            {
                //让lastjd结点的后继指针指向，要删除的jd结点的下一个结点。
                lastjd->next = jd->next;

                //删除jd
                delete jd;
                return true;
            }
        }
    }

    return false;
}

//返回数量函数，返回当前链表存储的元素的数量。
template <class T>
int DXXHLB<T>::return_sl_DXXHLB()
{
    return sl;
}

//位置查找函数，根据传入的位置，查找该位置的数据。pos是传入的位置。
template <class T>
T DXXHLB<T>::findbypos_DXXHLB(int pos)
{
    //如果表为空，或查找的位置非法，则执行终止函数
    if (sl == 0 || (pos <= 0 || pos > sl))
    {
        cout << "操作错误" << endl;
        //非正常退出程序函数
        exit(1);
    }
    //查找位置合法
    else
    {
        //创建一个指针，用来存储后面我们找到pos的位置的节点。里面先暂时存储第0个位置的节点，也就是头结点的位置。
        Sjjd<T> *jd = head;
        //找到第pos的位置的节点，把这个节点的位置存储到jd。
        for (int i = 1; i <= pos; i++)
        {
            jd = jd->next;
        }
        //返回寻找到的值
        return jd->data;
    }
}

//打印函数，按顺序打印你的单链表的数据。
template <class T>
bool DXXHLB<T>::print_DXXHLB()
{
    //如果表为空，则返回false
    if (sl == 0)
    {
        return false;
    }
    //表不为空，按顺序遍历表格
    else
    {
        //创建一个指针，用来指向表格中的节点，里面先暂时指向头结点
        Sjjd<T> *jd = head;
        //遍历表
        for (int i = 1; i <= sl; i++)
        {
            jd = jd->next;
            cout << i << ":" << jd->data << endl;
        }

        return true;
    }
}

//输出约瑟夫序列函数，解决约瑟夫问题，输出约瑟夫所需要的序列
template <class T>
void DXXHLB<T>::prinysf_DXXHLB(int m)
{
     //创建一个指针，用来指向表格中的节点，里面先暂时指向头结点
    Sjjd<T> *jd = head;
    //index表示jd节点在表格中位置。其表示方法，是到第m个节点的时候index为m，但是下一个节点开始，index会重置为1，然后又到第m+1个节点又重置为1。头结点跳过。
    int index = 0;

    //当表格只剩下一个结点的时候会跳出循环
    while (sl > 1)
    {
        //jd存储下一个节点的位置
        jd = jd->next;
        //如果jd是头结点，则跳过头结点
        if (jd == head)
        {
            jd = jd->next;
        }
        //更新index
        ++index;

        if (index == m)
        {
            //输出第m个结点的数据
            cout << jd->data << " ";

            //存储要删除的结点的数据
            T deletedata = jd->data;
            //jd存储下一个结点的地址
            jd = jd->next;
            //跳过头结点
            if (jd == head)
            {
                jd = jd->next;
            }
            //用值删除函数，删除刚刚输出的结点
            removebyvalue_DXXHLB(deletedata);
            //更新sl和index
            --sl;
            index = 1;
        }
    }
//输出表格剩下的一个结点
    cout << head->next->data << endl;
}

//析构函数，释放你的链表
template <class T>
DXXHLB<T>::~DXXHLB()
{
    //创建一个指针，用来指向表格中的节点，里面先暂时指向头结点
    Sjjd<T> *p = head;
    //注意，在单向循环链表里不能用while（P）判断链表是否为空，因为单向循环链表是头尾循环相连接的。
    //当删除到最后一个结点的时候，p会指向原来头结点地址。而头结点最开已经始释放掉了，而p却仍然存储原来存储头结点的空间地址，
    //所以P指向的不是NULL，而是未知的，这样程序就不会中断。

    for (int i = 0; i <= sl; i++)
    {

        //缓存当前的地址
        Sjjd<T> *deletejd = p;
        //让p存储下一个节点的地址,如果i==sl，说明p已经是要删除的最后一个结点了，就不需要让P存储下一个结点地址了
        if (i != sl)
        {
            p = p->next;
        }

        //释放缓存的的地址
        delete deletejd;
    }
}

测试文件Test.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include "DXXHLB.h"
#include "DXXHLB.cpp"
using namespace std;
int main()
{
    DXXHLB<int> a;

    for (int i = 1; i <= 10; i++)
    {
        a.insert_DXXHLB(i, i);
    }

    cout << "sl==" << a.return_sl_DXXHLB() << endl;
    a.removebypos_DXXHLB(5);
    //打印函数
    a.print_DXXHLB();
    cout << "第五个为" << a.findbypos_DXXHLB(5) << endl;
}

栈

栈的基础知识

栈的理解

栈也是线性表的一种，只不过栈是一种特殊的，受限的线性表。栈是只能在一端进行插入或删除的线性表。允许插入、删除、出去的一端称为栈顶，另一端称为栈底，当栈中没有元素时称为空栈。

栈的性质

后进先出

不支持随机访问和遍历
由于栈的操作规则是只允许在栈顶进行插入和删除操作，因此对于栈而言，不支持随机访问和遍历操作。
如果要遍历所有元素，需要把栈内数据全部拿出访问，这样的话就会改变栈内的数据，这种行为对栈来讲是不被允许的

栈的举例说明


栈中有3个元素，进栈的顺序是a、b、c，当需要出栈时其顺序为c、b、a。

栈的主要操作

栈有插入和删除两个主要的操作。栈的插入操作常称为入栈（压栈)，栈的删除操作常称为出栈（弹栈)。

栈的结构

栈是一种线性表，其逻辑结构为线性结构。栈的物理结构有两种，而根据其实现的物理结构的不同，有两种实现方式。当栈是用顺序存储结构实现，元素连续的的存储在计算机存储器中，栈就叫顺序栈。当栈是用链式存储结构，其元素不一定是连续的存储在计算机存储器中 ，这时候栈就叫链栈

顺序栈

顺序栈的基础知识

顺序栈的理解

顺序栈是指利用顺序存储结构实现的栈，即在计算机中，会用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。

顺序栈的构建思路

数据
数组data：存储数据。一般是数组。一般我们构建的线性表，存储数据的数组，我们一般是把数组尾作为栈顶，数组头作为栈底。也就是只在尾进行插入、删除、取出。
指针top：指向栈顶元素在顺序栈中的位置。

变量sl：用来表示栈内所存储的元素数量

顺序栈的实现

接口文件SXZ.h 

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
#pragma once
template <class T, int Max = 1024>
class SXZ
{
private:
    T data[Max];
    int sl;
    int top;

public:
    //构造函数，初始化栈表
    SXZ();

    //入栈函数，value是传入的数据，将value压入栈
    bool Push_SXZ(T value);

    //出栈函数，将栈顶元素压出栈
    bool Pop_SXZ();
    //返回栈顶函数,返回栈顶的元素
    T Return_Top_SXZ();

    //返回数量函数，返回栈表存储元素数量
    int Return_Sl_SXZ();

    //判断是否为空函数，用来判断栈表是否为空，是返回true，否则返回false
    bool Is_Empty_SXZ();

    //清空函数，清空栈表的元素
    bool Clear_SXZ();

    //析构函数，释放栈表
    ~SXZ();
};


实现文件SXZ.cpp

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
102
103
104
105
106
107
#include <iostream>
#include "SXZ.h"
using namespace std;

//构造函数，初始化栈表
template <class T, int Max>
SXZ<T, Max>::SXZ()
{
    //更新top指针
    top = -1;
    //更新数量
    sl = 0;
}

//入栈函数，value是传入的数据，将value压入栈
template <class T, int Max>
bool SXZ<T, Max>::Push_SXZ(T value)
{
    //当表已满，无法在进行入栈
    if (sl == Max)
    {

        return false;
    }
    //表未满，还可以入栈
    else
    {
        //更新top指针
        ++top;
        //将数据存储进栈
        data[top] = value;
        //更新sl
        ++sl;
    }
}
template <class T, int Max>
//出栈函数，将栈顶元素压出栈
bool SXZ<T, Max>::Pop_SXZ()
{
    //当表为空
    if (sl == 0)
    {
        cout << "栈为空，无法返回栈顶";
        return false;
    }
    //栈不为空
    else
    {

        //直接让指向栈顶元素的指针top减一，就等于删除了栈顶元素。因为top是指向栈顶的元素，当top不在指向原来的栈顶，那个栈顶就等于被删除。在有数据入栈的话，原栈顶也会被覆盖。
        --top;

        //更新sl
        --sl;
        return true;
    }
}

//返回栈顶函数,返回栈顶的元素
template <class T, int Max>
T SXZ<T, Max>::Return_Top_SXZ()
{
    //当表为空
    if (sl == 0)
    {
        cout << "栈为空，无法返回栈顶";

        //退出函数
        exit(1);
    }
    //表不为空，则取出栈顶元素
    else
    {
        return data[top];
    }
}
//返回数量函数，返回栈表存储元素数量
template <class T, int Max>
int SXZ<T, Max>::Return_Sl_SXZ()
{
    return sl;
}

//判断是否为空函数，用来判断栈表是否为空，是返回true，否则返回false
template <class T, int Max>
bool SXZ<T,Max>::Is_Empty_SXZ()
{
    if(sl==0)
    return true;
    return false;
}
//清空函数，清空栈表的元素
template <class T,int Max>
bool SXZ<T,Max>::Clear_SXZ()
{
    //直接把top指向-1，sl更新为0
  sl=0;
  top=-1;
}

//析构函数，释放栈表
template <class T, int Max>
SXZ<T,Max>::~SXZ()
{

}

测试文件Test.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include"SXZ.h"
#include"SXZ.cpp"
using namespace std;
int main()
{
    SXZ<int,20> a;
    for(int i=1;i<=10;i++)
    {
        a.Push_SXZ(i);
    }
    a.Pop_SXZ();
    cout<<"栈顶元素为"<<a.Return_Top_SXZ()<<endl;
    a.Clear_SXZ();
    cout<<"sl:"<<a.Return_Sl_SXZ()<<endl;
    

}

链栈

链栈的基础知识

链栈的理解

链栈是指利用链式存储结构实现的栈，即在计算机中，会用一组地址并不一定连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指针指向栈顶元素。

链栈的数据节点构建思路

数据
变量data：存储数据
指针next：指向下一个数据节点的指针

链栈的构建思路

链栈表的图示

链栈的数据
头指针:指向链栈的头节点。链栈可有头节点，也可以没有头节点。如果链栈不设头节点，则也就不设头指针。
指针top：用来指向栈顶数据节点。在由数据结点构建的链表中，为方便操作，一般是表头作为栈顶，表尾作为栈底，如上图，与顺序栈相反。

链栈的实现

接口文件LZ.h

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
#pragma once
template <class T>
struct Sjjd
{
    Sjjd<T> *next;
    T data;
};

template <class T>
class LZ
{
private:
//指向栈顶元素的指针
    Sjjd<T> *top;
    //数量，表示当前容器的元素数量。
    int sl;

public:
    //构造函数，初始化栈表
    LZ(/* args */);

    //入栈函数，value是传入的数据，将value压入栈
    bool Push_LZ(T value);

    //出栈函数，将栈顶元素压出栈
    bool Pop_LZ();

    //返回栈顶函数,返回栈顶的元素
    T Return_Top_LZ();

    //判断是否为空函数，用来判断栈表是否为空，是返回true，否则返回false
    bool Is_Empty_LZ();
    //析构函数，释放栈表
    ~LZ();
};


实现文件LZ.cpp

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
#include "LZ.h"
#include <iostream>
using namespace std;

//构造函数，初始化栈表
template <class T>
LZ<T>::LZ(/* args */)
{
    // top是指向栈顶元素的指针，初始化时无入栈，因此赋null
    top = NULL;
    //更新sl
    sl = 0;
}

//入栈函数，value是传入的数据，将value压入栈
template <class T>
bool LZ<T>::Push_LZ(T value)
{ //创建一个结点用来存储传入的数据value
    Sjjd<T> *jd = new Sjjd<T>;
    jd->data = value;

    //把要入栈的数据节点，将其后继指针指向当前的栈顶元素
    jd->next = top;
    // top指向刚刚存入的栈顶元素
    top = jd;
    //更新sl
    ++sl;
    return true;
}
//出栈函数，将栈顶元素压出栈
template <class T>
bool LZ<T>::Pop_LZ()
{
    //栈表为空，无法出栈
    if (sl == 0)
    {
        return false;
    }

    //栈表不为空
    else
    {
        //创建一个jd，来存储栈顶元素
        Sjjd<T> *jd = top;
        //让top指针，指向下一个元素。
        top = top->next;
        //删除jd
        delete jd;

        //更新sl
        --sl;
        return true;
    }
}

//返回栈顶函数,返回栈顶的元素
template <class T>
T LZ<T>::Return_Top_LZ()
{
    //栈表为空，无法出栈
    if (sl == 0)
    {
        cout << "表为空，无法返回栈顶元素" << endl;
        exit(1);
    }
    else
    {
        //返回栈顶数据节点存储的数据
        return top->data;
    }
}

//判断是否为空函数，用来判断栈表是否为空，是返回true，否则返回false
template <class T>
bool LZ<T>::Is_Empty_LZ()
{
    if (sl == 0)
        return true;
    return false;
}
//析构函数，释放栈表
template <class T>
LZ<T>::~LZ()
{
    //创建结点jd,用来缓存栈表的元素，里面暂存栈顶元素
    Sjjd<T> *jd = top;
    while (jd)
    {
        //创建lastjd，缓存当前要删除的结点，
        Sjjd<T> *lastjd = jd;
        // jd缓存下个结点地址
        jd = jd->next;

        //删除lastjd
        delete lastjd;
    }
    top = NULL;
}

测试文件Test.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include "LZ.h"
#include "LZ.cpp"
using namespace std;
int main()
{
    LZ<int> a;
    for (int i = 1; i <= 10; i++)
    {
        a.Push_LZ(i);
    }
    a.Pop_LZ();
    cout << "栈顶元素为" << a.Return_Top_LZ() << endl;

    if (a.Is_Empty_LZ())
        cout << "表为空" << endl;
    else
        cout << "表不为空" << endl;
}

队列

队列的基础知识

队列的理解

队列也是线性表的一种，只不过队列是一种特殊的，受限的线性表。
队列是一种在一端进行插人，而在另一端进行删除的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。
队列的插入操作常称为入队，队列的删除操作常称为出队。

队列的性质

先进先出 ( First In First Out，FIFO)，即出队元素只能是位于队头的元素，而入队元素也只能放在队尾位置。

队列的举例


下图所示为有5个元素的队列。入队的顺序依次为a1、a2、a3、a4、a5，出队时的顺序将依然是a1、a2、a3 、a4、a5

队列的结构

队列是一种特殊的线性表，其逻辑结构仍为线性结构。队列的物理结构有两种，而根据其实现的物理结构的不同，有两种实现方式。当队列是用顺序存储结构实现，元素连续的的存储在计算机存储器中，队列就叫顺序队列。当队列是用链式存储结构，其元素不一定是连续的存储在计算机存储器中 ，这时候队列就叫链队

顺序队列

顺序队列的基础知识

顺序队列的理解

顺序队列是指利用顺序存储结构实现的队列，即利用一组连续的存储单元依次存放自队头到对尾的数据元素。

假溢出问题

最开始队空，我们将数组下标0端设为队头，然后最开始将front（队头元素前一个位置的下标标记）,和rear（队尾下标标记都）设为-1。
假设入队操作时，可以先使队尾下标标记移一个位置，rear = rear+1，然后向rear所指向的位置写入新元素;出队操作时，将数据出队后，将front往后移一个位置，即front = front +1。操作如下图

从图3-7中可以看出,如果还有元素需要入队,就会出现假上溢现象。

假溢出问题的解决

我们将数组下标0端设为队头，然后最开始将front,和rear和设为-1。
入队和出队操作中front和rear不是直接加1，而是采用加1取模的方式。入队操作时rear = (rear +1)% MaxSize，出队操作时front = ( front +1) % MaxSize（maxsize为数组长度）

歧义问题


当入队操作和出队操作采用取模的方式，那么会如上图的C和D所示，由于队列为空和为满的条件均为front == rear，会产生歧义。

歧义的解决

方法1：浪费一个元素空间。将图上（c）所示的情况视为队满，此时的状态是队尾指针加1就会从后面赶上队头指针。在这种情况下，队满的条件是( rear + 1 ) % MaxSize == front，这样就能与空队区别开。

方法2：设置一个辅助标志变量flag。例如，当front == rear且flag == false时(此时刚有元素出队列）表示队空;当front == rear 且 flag == true时(此时刚有元素进队列)表示队满。请读者思考仅用标志变量flag 如何判断队列状态。

方法3使用一个计数器记录队列中元素的个数。附设一个存储队中元素个数的变量如num当num ==0时表示队空，当num == MaxSize时表示队满。

顺序队列的构建思路

数据
数组data：存储队列中的元素，数组头做队头或者队尾都可以（这里我们用数组头做队头，数组尾做队尾）。
变量sl：用来表示队内所存储的元素数量
整形变量front：存放队头元素前一个位置的下标,开始时为-1（当队头指针和队尾指针初始化都是-1，如果队头指针是指向队头元素的下标，那么我们写入队操作的时候，多写一些代码进行判断）。
整形变量rear：存放队尾元素的下标

顺序队列的实现

接口文件SXDL.h

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
#pragma once
template <class T, int Max = 1024>
class SXDL
{
private:
    //数组，作为队列，用来存取数据
    T Data[Max];
    //数量，表示当前容器的元素数量。
    int sl;

    //队头变量，存放队头元素前一个位置的下标
    int front;

    //队尾变量,存放队尾元素的下标
    int rear;

public:
    //初始化函数，初始化顺序队列
    SXDL();

    //入队函数，value为传入的要入队的值，将value传入队列。
    bool Push_SXDL(T value);

    //出队函数，将队头元素出队，成功返回true，失败返回false
    bool Pop_SXDL();

    //返回队头元素函数，取队头元素。
    T Return_dt_SXDL();

    //返回数量函数，返回当前队列存储的元素的数量。
    int Return_sl_SXDL();

    //是否为空函数，判断队列元素是否为空，如果为空返回true，否则返回false;
    bool Is_Empty_SXDL();

};

实现文件SXDL.cpp

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
#include <iostream>
#include "SXDL.h"
using namespace std;
//初始化函数，初始化顺序队列
template <class T, int Max>
SXDL<T, Max>::SXDL()
{
    //初始化front和rear，最开始将front,和rear和设为-1。
    front = rear = -1;
    //初始化sl
    sl=0;

}

//入队函数，value为传入的要入队的值，将value传入队列。
template <class T, int Max>
bool SXDL<T, Max>::Push_SXDL(T value)
{
    //当表已满，无法在进行入队
    if (sl == Max)
    {

        return false;
    }
    //表未满，可以入队
    else
    {
        //更新队尾变量，将队尾变量指向下一个新的未存储空间，用来存储新的队尾元素
        rear = (rear + 1) % Max;
        //将数据存储入队
        Data[rear] = value;
        //更新sl
        ++sl;
        return true;
    }
}
//出队函数，将队头元素出队，成功返回true，失败返回false
template <class T, int Max>
bool SXDL<T, Max>::Pop_SXDL()
{

    //当队是空的，无法在进行出队
    if (sl == 0)
    {
        return false;
    }
    //队不是空的，可以进行出队
    else
    {
        //将队头变量+1，指向新的队头元素的前一个位置的下标，这样就等于删除原来的队头元素，虽然该空间仍然有存储数据，但是可以当作空的存储空间
        front = (front + 1) % Max;
        //更新sl
        --sl;
        return true;

    }
}

//返回队头元素函数，取队头元素。
template <class T, int Max>
T SXDL<T, Max>::Return_dt_SXDL()
{
    //当队是空的，无法在取出队头
    if (sl == 0)
    {
        cout << "队是空的，无法取出队头元素" << endl;
        exit(1);
    }
    //队不是空的，可以进行取出队头
    else
    {
        //根据队头变量返回队头元素
        return Data[(front + 1) % Max];
    }
}
//是否为空函数，判断队列元素是否为空，如果为空返回true，否则返回false;
template <class T, int Max>
bool SXDL<T, Max>::Is_Empty_SXDL()
{
    if (sl == 0)
    {
        return true;
    }
    return false;
}

//返回数量函数，返回当前队列存储的元素的数量。
template <class T, int Max>
int SXDL<T, Max>::Return_sl_SXDL()
{
    return sl;
}

测试文件Test.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include "SXDL.h"
#include "SXDL.cpp"
using namespace std;
int main()
{
    SXDL<int, 20> a;
    for (int i = 1; i <= 10; i++)
    {
        a.Push_SXDL(i);
    }
    a.Pop_SXDL();
    cout << "队头元素为" << a.Return_dt_SXDL() << endl;

    cout << "sl:" << a.Return_sl_SXDL() << endl;
    if (a.Is_Empty_SXDL() == false)
    {
        cout << "表不空" << endl;
    }
}

链队列

链队列的基础知识

链队列的理解

链队列是指利用链式存储结构实现的队列，即用一组并不一定连续的存储单依次存放自队头到队尾的数据元素。

链队列图示

链队列的数据节点构建思路

数据
变量data：存储数据
指针next：指向下一个数据节点的指针

链队列的构建思路

数据
队头指针front：指向链表头结点，（队头元素的前一个结点）
队尾指针rear：开始指向链表头结点，后面指向队尾结点（队尾元素）
变量sl：用来表示队内所存储的元素数量

链队列的实现

接口文件LDL.h

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
#pragma once
template <class T>
struct Sjjd
{
    Sjjd<T> *next;
    T Data;
};
template <class T>
class LDL
{
private:
    //队头指针，指向头结点（队头元素的前一个结点）
    Sjjd<T> *front;

    //队尾指针，指向尾结点（队尾元素）
    Sjjd<T> *rear;

    //存储队列的元素数量
    int sl;

public:
    //初始化函数，初始化顺序队列
    LDL();

    //入队函数，value为传入的要入队的值，将value传入队列。
    bool Push_LDL(T value);

    //出队函数，将队头元素出队，成功返回true，失败返回false
    bool Pop_LDL();

    //返回队头元素函数，取队头元素。
    T Return_dt_LDL();

    //返回数量函数，返回当前队列存储的元素的数量。
    int Return_sl_LDL();

    //是否为空函数，判断队列元素是否为空，如果为空返回true，否则返回false;
    bool Is_Empty_LDL();

    //析构函数，释放队列
    ~LDL();
};

实现文件LDL.cpp

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include "LDL.h"
using namespace std;
//初始化函数，初始化顺序队列
template <class T>
LDL<T>::LDL()
{
    //创建一个空的结点，用来当头结点
    Sjjd<T> *jd = new Sjjd<T>;
    //队头指针和队尾指针都指向头结点
    front = rear = jd;

    //更新sl
sl = 0;

}

//入队函数，value为传入的要入队的值，将value传入队列。
template <class T>
bool LDL<T>::Push_LDL(T value)
{
    //创建一个结点来存储传入的数据
    Sjjd<T> *jd = new Sjjd<T>;
    jd->Data = value;
    jd->next = NULL;
    //队尾的后继指针，指向新创建的元素节点
    rear->next = jd;

    //队尾指针指向新的队尾元素。
    rear = jd;

    //更新sl
    ++sl;
    return true;
}

//出队函数，将队头元素出队，成功返回true，失败返回false
template <class T>
bool LDL<T>::Pop_LDL()
{
    //当队是空的，无法在进行出队
    if (sl == 0)
    {
        return false;
    }

    //队不是空的时候
    else
    {
        //创建一个新的节点用来存储队头元素
        Sjjd<T> *jd = front->next;

        //头结点的后继指针，指向新的队头元素
        front->next = jd->next;

        //删除原队头元素
        delete front;

        //更新sl
        --sl;
    }
}

//返回队头元素函数，取队头元素。
template <class T>
T LDL<T>::Return_dt_LDL()
{
    //当队是空的，无法在进行出队
    if (sl == 0)
    {
        cout << "队为空，无法获取队头元素" << endl;
        exit(1);
    }
    //队不空的时候
    else
    {
        //返回队头元素
        return front->next->Data;
    }
}

//返回数量函数，返回当前队列存储的元素的数量。
template <class T>
int LDL<T>::Return_sl_LDL()
{
    return sl;
}

//是否为空函数，判断队列元素是否为空，如果为空返回true，否则返回false;
template <class T>
bool LDL<T>::Is_Empty_LDL()
{
    if (sl == 0)
    {
        return true;
    }
    return false;
}

//析构函数，释放队列
template <class T>
LDL<T>::~LDL()
{
    //创建一个节点来存储队列的所有结点，里面暂存头结点
    Sjjd<T> *jd = front;

    while (jd)
    {
        //用一个新的结点，来缓存当前的结点。然后让jd去去队列下一个元素节点
        Sjjd<T> *lastjd = jd;
        //让jd去去队列下一个元素节点
        jd = jd->next;
        //删除缓存的节点
        delete lastjd;
    }
}

测试文件Test.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include "LDL.h"
#include "LDL.cpp"
using namespace std;
int main()
{
    LDL<int> a;
    for (int i = 1; i <= 10; i++)
    {
        a.Push_LDL(i);
    }
    a.Pop_LDL();
    cout << "队头元素为" << a.Return_dt_LDL() << endl;

    cout << "sl:" << a.Return_sl_LDL() << endl;
    if (a.Is_Empty_LDL() == false)
    {
        cout << "表不空" << endl;
    }
}

树

树的基本知识

树的理解

树是由n个节点组成的集合。n＝0就是空树，n>0的时候存在一个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又可以作为一个树

树的图示

树的结构

树的逻辑结构就叫树结构，其数据结构中的元素存在一对多的相互关系。树的物理结构有两种，而根据其实现的物理结构的不同，有两种实现方式。当树是用顺序存储结构实现，元素连续的的存储在计算机存储器中，树就叫顺序树。当树是用链式存储结构，其元素不一定是连续的存储在计算机存储器中 ，这时候树就叫链树

树的特点

树的定义具有递归性，树中还有树。
树可以为空，即节点个数为0。

有序树和无序树的区别

有序树是具有明确顺序关系的树结构，子节点之间按照某种规定的顺序排列。无序树是没有明确顺序关系的树结构，子节点之间没有明确顺序关系，可以任意排列。

举例

在这个二叉搜索树中，每个节点的值都满足左孩子节点小于节点自身的值，右孩子节点值大于节点自身的值。这是具有明确顺序关系的树结构。这个有序性质使得我们能够快速地找到特定值的节点，例如，如果我们要查找值为6的节点，我们可以从根节点开始比较，因为6比根节点的值大，所以我们知道要在右子树中继续查找。然后，我们在右子树中找到了值为6的节点。


这是普通二叉树，没有明确顺序关系的树结构。们无法根据节点的值来确定节点的位置。

树的相关定义说明

以下面这个树图为例

根节点
上图A点就是根节点

叶子节点
下面没有分叉的节点，如上图B、C、H、I、P、Q等节点

节点的层次
结点的层次（Level）从根开始定义，根为第一层，根的孩子为第二层，以此类推

树的深度
树中所有节点里，最深层的节点第是几层，树的深度就为几层，如上图 就4层

节点的度
就是节点下面分叉多少个节点，如上图节点E，下面分叉I、J,则E节点的 度为2

树的度
树有众多节点，某个节点的度是最大的，那么这个树的度就是这个节点的度。如上图的树，度最大的节点是F节点，度为3，则这个树的度就为3

孩子节点、父节点、兄弟节点
如上图E节点下分叉许I、J这两个节点，则E就为I、J的父节点，I、J就为E的子节点。而I和J是有同一个父节点，所以I和J就是兄弟节点

子树
上图所有节点整一个就是一个大树，而在这个树里，假设E、I、J、P、Q这五个节点组成一个集合，就是这个大树的子树

二叉树的基本知识

二叉树的理解

树的所有的节点的度不超过2的树，就是二叉树，也就是说，二叉树每个节点最多有两个孩子节点，分别为左孩子节点和右孩子节点

二叉树的图示

二叉树的结构

二叉树的逻辑结构，是树结构中的一对二。二叉树物理结构有两种，而根据其实现的物理结构的不同，有两种实现方式。当二叉树的物理结构是采用顺序存储结构时，元素连续的的存储在计算机存储器中，此时的二叉树就是顺序二叉树。当二叉树是用链式存储结构，其元素不一定是连续的存储在计算机存储器中 ，这时候二叉树就叫链二叉树

满二叉树的理解

一个二叉树，每一层的节点数都达到最大值，那么这个二叉树就是满二叉树

完全二叉树的理解

一棵深度为k的有n个结点的二叉树（不一定是满二叉树），对树中的结点按从上至下、从左到右的顺序进行编号（这种编号方法，也叫完全二叉树编号方法），同时也对深度为k的满二叉树用同样的标准进行编号。这个二叉树所有有编号结点，其编号与满二叉树中对应节点编号相同则这棵二叉树称为完全二叉树。
完全二叉树是一种特殊的二叉树，它的特点是除了最后一层外，其他层的节点都是满的，而最后一层的节点尽量靠左排列。

二叉树的性质

1.非空二叉树中,第i层最多有2^(i-1)个结点,其中i≥1。

2.高度为h的二叉树中结点总数最多为2^(h)-1。

3.设某二叉树中叶子结点数为n0，度为2的结点数为n2，则n0 =n2,+1。（设某m叉树，度为i的结点数为ni;，则n0=n2, +2n3+ …+(m - 1 )nm +1。）

4.

5.
注意，这个性质是二叉树编号是从1开始编的。

顺序二叉树

顺序二叉树的基本知识

顺序二叉树的理解

二叉树表根据不同的物理结构，有两种实现方式，当二叉树的物理结构是采用顺序存储结构时，就叫顺序二叉树。此时内存中会用地址连续的一块存储空间顺序存二叉树的元素

顺序二叉树的在数组存储方式

首先创建一个数组，然后将二叉树进行完全二叉树编号（从0开始编号），然后根据二叉树中的元素的编号，存到存到对应下标的数组（此时元素的标号就是数组对应的下标），这就是顺序二叉树的存储方式，如下图

上为二叉树的结构图，下为二叉树应用顺序存储方式存储在数组的数组结构图

顺序二叉树里，父节点和左孩子节点编号的关系

注意，这个性质是二叉树编号是从0开始编的。
父亲节点为i，则左孩子节点为2i+1,所以左孩子节点编号都为单数。
若左孩子节点编号为k,则父亲节点为（k-1）/2

顺序二叉树里，父节点和右孩子节点编号的关系

父亲节点为i，则右孩子节点为2i＋2,所以左孩子节点编号都为双数。
若右孩子节点编号为k,则父亲节点为（k-2）/2

顺序二叉树的局限

对于满二叉树、完全二叉树来说，顺序存储结构的存储效率是极高的，所有的空间仅仅用来存储数据元素的值，结点之间关系的存储未占用任何空间。


但是，对于一般二叉树而言，如何利用完全二叉树的编码规则来存储数据呢?解决的方法是补足不存在的结点，用特殊数据标识这些替补结点，使整棵树在形式上满足完全二叉树的定义。图7-11 （a）所示的不是完全二叉树。经过增补一些虚拟结点后，图7-11 (b）所示成为完全二叉树,其顺序存储结构如图7-11 (c)所示。虽然非完全二叉树采用顺序存储结构存在部分内存空间的浪费，但是如果空间浪费不多,能得到直接存取的优点，那么也是值得的。


对于那些单分支结点较多、高度变化较大的二叉树而言，顺序存储结构是不合适的。如图7-12（a）所示的二叉树每个结点只有右子树，为其增
补虚拟结点后如图7-12(b)所示。为了存储4个数据元素，需要占用15个存储空间，如图7-12 (c) 所示。若二叉树的高度更大，则空间浪费现象将更加惊人。因此，对于一般二叉树通常采用下一小节介绍的链式存储结构。

由于顺序二叉树的局限性，我们队二叉树的存储主要采用链式存储结构，顺序存储结构了解即可

链二叉树

链二叉树的基本知识

链二叉树的理解

二叉树根据不同的物理结构，有两种实现方式，当二叉树的物理结构是采用链式存储结构时，就叫链二叉树。此时内存中会用并不一定连续空间顺序存二叉树的元素

二叉链的理解

链二叉树的数据节点有很多种，其中一种就是每个数据节点都有一个变量存储数据，两个指针，一个指向当前节点的左孩子节点，和右孩子节点。只有两个指针的数据节点，被称为二叉链数据节点，对应的二叉树的链表就就叫二叉链

二叉链的图示

二叉链的数据节点的构建思路

二叉链的构建思路

数据
指针root：指向跟节点的指针。
变量sl：存储表格元素数量。

三叉链表的理解

数据节点有一个变量存储数据，三个指针，分别指向当前节点的左孩子节点，和右孩子节点，已经当前节点的父节点。
有三个指针的数据节点，被称为三叉链数据节点，对应的二叉树的链表就就叫三叉链

三叉链的图示

三叉链的数据节点构建思路

三叉链的构建思路

数据
指针root：指向跟节点的指针。
变量sl：存储表格元素数量。

链表的类图


二叉树的遍历

二叉树遍历的理解

指按某条搜索路线遍访每个结点且不重复(又称周游)。
它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。

遍历方法

具体实现有三种方案。（无论哪种方案牢记一种约定，对每个结点的查看都是“先左后右”）
分别是先序遍历（DLR）、中序遍历（LDR）、后序遍历（LRD），
注:“先、中、后”的意思是指访问根节点时机。
从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。

先序遍历算法步骤

以这个图为例

1若二叉树为空，则遍历结束;
2访问根结点;
3先序遍历根结点的左子树;
4先序遍历根结点的右子树。
总的来先访问根，在访问左子树，最后访问右子树（简写为DLR，D为根，L为左子树，R为右子树）
上图由先序遍历得到的输出序列为abdecf

中序遍历算法算法步骤

以这个图为例

1若二叉树为空，则遍历结束;
2中序遍历根结点的左子树;
3访问根结点;
4中序遍历根结点的右子树。
总的来说先左在中最后在右，LDR
上图输出的序列顺序为dbeafc

后序遍历算法的步骤如下:

以这个图为例

1若二叉树为空，则遍历结束;
2后序遍历根结点的左子树;
3后序遍历根结点的右子树;
4访问根结点。
总的来说先左在右最后在中，LRD
上图输出的序列顺序为debfca

先序遍历的实现举例


先序遍历函数PreOrder是类里的私函数，功能是先序遍历以p为根指针的二叉树，因此也是一个递归函数。
我们要在main函数里使用先序遍历函数，就得先定义他的调用函数，然后在main函数里，通过使用调用函数，来调用先序遍历函数。在调用函数里，我们将二叉树的根结点指针root作为实参传入。
而之所以我们在main函数里得通过调用函数来使用序遍历函数，是因为root是私有数据成员，因此我们无法在main()函数中直接使用先序遍历函数，即不能直接在main函数里执行bitree.PreOrder (bitree.root)。

所以在使用时，我们得将先序遍历函数，也是递归函数定义为私有成员函数，另外再定义一个公有无参函数Pre Order()来作为调用函数，然后在main函数里，通过 PreOrder()函数中调用PreOrder( root)函数即可。

层序遍历的理解

以下图为例

层序遍历则输出abcdef

层序遍历的实现

二叉树的构造

二叉树的构造基础知识

构造的方式

根据一段序列（可能是先序序列，可能是中序序列，可能是后序列），来构造其对应二叉树。

构造的问题

在二叉树的遍历中，无论先序序列、中序序列、后序序列，还是层次序列，和二叉树结构都不存在一一对应的关系。因为每个结点的左、右子树都可能缺失，所以无法确定在遍历序列中的后继结点是左孩子还是右孩子，或是有其他关系的结点。


如图所示的5种二叉树的先序序列都是abc。

空指针标记的先序序列构造

用空指针标记的先序序列构造二叉树的方法

稍微调整一下遍历规则可以建立起遍历序列和二叉树结构的一一对应关系。原遍历算法步骤①规定，若二叉树为空，则遍历结束。调整后的遍历算法步骤①规定，若二叉树为空，输出字符*之后遍历结束。调整后的遍历结果称为带空指针标记的遍历序列。符号*的意义在于标识空指针，它可以是任何一种与结点数据相异的特殊数据。例如，当结点数据都是正数时，可选取负数作为特殊数据来标记空指针。如下图

其先序序列是abdecf，带空指针标记的先序序列是abd * * e ** cf ***。

空指针标记的先序序列构造二叉树的实现



CreateByPre其功能是根据带空指针标记的先序序列创建二叉树。
思想本质，可以理解为用先序遍历遍历一个空的二叉树，再遍历过程，创建数据节点，然后把对应序列的值存进去
由于每次调用CreateByPre()函数都需要引用向量pre 中的下一个数据, 因此将参数pre和i设成引用变量,以达到数据的共享、提高参数传递效率的目的
该函数为其是私函数，不可被用户所调用，因此在要写在私有域内，然后用户可以通过构造函数调用。

两个遍历序列构造

可以唯一确定二叉树的两个遍历序列

知道二叉树树的先序遍历序列和中序遍历序列，是可以唯一确定这颗二叉树的结构。
知道二叉树树后序遍历序列和中序遍历序列，也可以唯一确定这颗二叉树的结构
知道二叉树的先序遍历序列和后序遍历序列是无法唯一确定二叉树的结构。

举例

设已知某二叉树的先序遍历序列是ABHFDECKG，中序遍历序列是HBDFAEKCG,，下面是通过这两个序列求出二叉树的过程

知道一棵树的先序遍历序列（简称先序列），和中序遍历序列（简称中序列），首先可以通过先序列，得出这颗二叉树的根节点，由中序列和根节点，可以得出左子树的中序列和右子树的中序列，以及左子树的节点个数，和右子数的节点个数。
而先序列的遍历顺序是先输出根节点，然后以先序遍历顺序输出左子树的节点，然后以先序遍历序列顺序输出右子树的节点。那么知道在左子树的节点个数，以及右子树的节点个数，就可以得出左子树的先序列，和右子树的先序列。
知道左子树的先序列和中序列，可以推出左子树的根节点和左子树的左右子树的先序列和中序列，同理右子树也是。然后不断的推出子树根节点，最终推出整课二叉树的结构。

总结就是知道一棵树先序列和中序列，结点个数得出这颗树的根节点，和左子树的先序列、中序列，节点个数，以及右子树的先序列、中序列、节点个数。然后以此不断类推出所有子树根节点，最终推出整课二叉树的结构。

先序遍历序列和中序遍历构造二叉树实现



Pre和mid分别存储该二叉树的先序列和中序列，ipre存储当前二叉树的先序列第一个元素的下标，imid存储当前二叉树的中序的第一个元素下标。
n存储当前子树的先序列的元素个数。
Creat该函数为其是私函数，不可被用户所调用，因此在要写在私有域内，然后用户可以通过构造函数调用。

拷贝构造

拷贝构造实现



函数从copy是私函数，p是传入的要copy的二叉树的根节点地址
该函数的作用是根据传入的要copy的二叉树根节点，然后完成对整个二叉树copy，并返回创建的二叉树的根节点。

递归理解该函数
传入：要copy 的二叉树的根节点，
返回：你创建的二叉树的根节点
调用函数，传入要copy二叉树根节点，获得我们创建的二叉树根节点，以这个思维，去构建函数的递归过程，也就是函数里去进行递归调用自身，传入要copy的二叉树的左子树的根节点，获取我们创建的二叉树的左子树的根结点。传入要copy的二叉树的右子树的根节点，获取我们创建的二叉树的右子树的根结点。当我们将递归过程构建完，函数执行过程中，就会不断递归调用，不断创建的二叉树的子树的根节点，最终成功创建整课二叉树。

二叉树的高度计算

二叉树的高度计算代码实现


第一个函数是私有函数，作用是根据传入的树的根节点，返回这棵树的高度。
在计算二叉树高度的过程中，每个结点的高度都被计算了一次。设二叉树中结点数是n，则算法的时间复杂度是O(n)。

递归理解
传入:二叉树的根节点
返回：这颗二叉树的深度
调用函数，传入二叉树根节点，获得当前树深度。函数的代码里，传入左右子树的根节点，获取左右子树的深度。

计算二叉树节点数

计算二叉树节点数代码实现


在第二个函数Count()中，以私有成员变量root为参数调用重载函数，得到当前对象中二叉树的结点数。

查找二叉树节点

查找二叉树结点代码实现


第一个查找结点函数，p是传入的二叉树根节点，e是在这个二叉树里要查找的值，返回是返回查找到的结点。

递归理解
传入：二叉树的根节点，查找的值e
返回：e结点地址

二叉树释放

二叉树释放代码实现

递归理解
传入：二叉树的根结点p
作用：将二叉树p释放掉

链二叉树的实现

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
#include <iostream>
#include <vector>
using namespace std;
template <class T>
//二叉链的数据节点
struct Sjjd
{
    //左孩子指针
    Sjjd<T> *lchild;
    //右孩子指针
    Sjjd<T> *rchild;
    //存储的数据
    T data;
};

template <class T>
class ECL
{
private:
    Sjjd<T> *root;
    int sl;
    //先序创建函数，P是传入的带空指针的先序序列的引用，i是p的下标变量的引用。
    //思想本质，用先序遍历遍历一个空的二叉树，再遍历过程把，创建数据节点，然后把对应序列的值存进去
    //该函数被先序构造函数所调用。因为其是私函数，不可被用户所调用，因此在要写在私有域内，然后用户可以通过构造函数调用。
    Sjjd<T> *creatbypre_ECL(vector<T> &p, int &i);

    //先中序创建函数，Pre和mid分别存储该二叉树的先序列和中序列，ip存储当前二叉树的先序列第一个元素的下标，im存储当前二叉树的中序的第一个元素下标。n存储当前子树的先序列的元素个数。
    //该函数可以通过一颗二叉树的先序列和中序列构建出这颗二叉树的。
    // 该函数为其是私函数，不可被用户所调用，因此在要写在私有域内，然后用户可以通过构造函数调用。
    //思想，就是知道一棵树先序列和中序列，得出这颗树的根节点，和左子树的先序列、中序列，左子树节点个数，以及右子树的先序列、中序列、右子树的个数。然后以此不断类推出所有子树根节点，最终推出整课二叉树的结构。
    Sjjd<T> *creatbypremid_ECL(vector<T> &pre, vector<T> &mid, int ip, int im, int n);

    // copy创造函数，p是传入的要copy的二叉树的根节点地址
    //该函数的作用是根据传入的要copy的二叉树根节点，然后完成对整个二叉树copy，并返回创建的二叉树的根节点。
    //传入要copy二叉树根节点，获得我们创建的二叉树根节点，以及要copy的二叉树的左右孩子节点，最终就可以以此类推，不断推出我们要创建的二叉树的子树的根节点，最终成功创建整课二叉树
    Sjjd<T> *creatbycopy_ECL(Sjjd<T> *gjd);

    //有参先序遍历输出函数,root是要遍历的二叉树的根节点
    // root是私有数据成员，在 main()函数中不能使用，因此把该函数定为类里的私函数，另外再重载定义公有无参函数xxbl_ECL（）来供主调函数调用
    void xxbl_ECL(Sjjd<T> *root);

    //有参的返回深度函数，gjd是传入的根节点
    //作用是根据传入的树的根节点，返回这棵树的高度
    int return_sd_ECL(Sjjd<T> *gjd);

    //查找结点函数，gjd是传入的二叉树根节点，e是在这个二叉树里要查找的值，返回是返回查找到的结点。
    Sjjd<T> *find_jd_ECL(Sjjd<T> *gjd, T e);

    //释放函数，gjd是传入进来要释放的二叉树的根节点
    void free_ECL(Sjjd<T> *gjd);

public:
    //无参构造函数，构造空树
    ECL();

    //先序构造函数，P是存储带空指针的先序序列的一个单链表。
    //用户得先创建一段带空指针的先序序列，然后调用先序构造函数的时候将其传进来，然后先序构造函数调用先序创建函数来构造二叉树，这里规定空指针为-1
    ECL(vector<T> &p);

    //先中序创建函数，Pre和mid分别存储该二叉树的先序列和中序列
    //该函数左右，通过用户传进来一颗二叉树得先序列和中序列，构建出这课二叉树
    ECL(vector<T> &pre, vector<T> &mid);

    //拷贝构造函数,p是传入的要copy的二叉树对象
    //根节点传入的二叉树对象，调用copy创建函数，来创建新的二叉树
    ECL(ECL &p);

    //无参的先序遍历输出函数，其作用是调用有参的先序遍历函数
    void xxbl_ECL();

    //无参的返回深度函数，起作用是调用有参的返回深度函数，求得当前树的深度
    int return_sd_ECL();

    //查找结点函数,e是查找的值
    //调用重载函数查找该节点地址
    Sjjd<T> *find_jd_ECL(T e);

    //析构函数，用来调用释放函数来释放链表
    ~ECL();
};
//先序创建函数，P是传入的带空指针的先序序列的引用，i是p的下标变量的引用。
//思想本质，用先序遍历遍历一个空的二叉树，再遍历过程把，创建数据节点，然后把对应序列的值存进去
//该函数被先序构造函数所调用。因为其是私函数，不可被用户所调用，因此在要写在私有域内，然后用户可以通过构造函数调用。
template <class T>
Sjjd<T> *ECL<T>::creatbypre_ECL(vector<T> &p, int &i)
{
    T data = p[i];
    i++;
    //-1是空指针，说明该节点为空
    if (data == -1)
    {
        return NULL;
    }

    Sjjd<T> *jd = new Sjjd<T>;
    jd->data = data;
    //让变量i指向序列p的下一个元素

    //先序遍历左边的节点，再遍历过程中创建节点。P和i两者合起来，可以当成指向左节点的指针
    jd->lchild = creatbypre_ECL(p, i);

    //创建右子树
    jd->rchild = creatbypre_ECL(p, i);
    return jd;
}

//先中序创建函数，Pre和mid分别存储该二叉树的先序列和中序列，ip存储当前二叉树的先序列第一个元素的下标，im存储当前二叉树的中序的第一个元素下标。n存储当前子树的先序列的元素个数，返回值是当前树的根节点。
//该函数可以通过一颗二叉树的先序列和中序列构建出这颗二叉树的。
//该函数为其是私函数，不可被用户所调用，因此在要写在私有域内，然后用户可以通过构造函数调用。
//思想，就是知道一棵树先序列和中序列，得出这颗树的根节点，和左子树的先序列、中序列，节点个数，以及右子树的先序列、中序列、节点个数。然后以此不断类推出所有子树根节点，最终推出整课二叉树的结构。
template <class T>
Sjjd<T> *ECL<T>::creatbypremid_ECL(vector<T> &pre, vector<T> &mid, int ip, int im, int n)
{
    //当树的结点数为0时，说明该树无根节点，则返回NULL
    if (n == 0)
    {
        return NULL;
    }
    //由先序列，得出当前树的根节点的值，创建数据节点，将其存储起来
    Sjjd<T> *jd = new Sjjd<T>;
    jd->data = pre[ip];

    //通过对比根节点在中序列得位置，得出左右子树的个数
    int i = 0;
    for (; i < n; i++)
    {
        if (pre[ip] == mid[im + i])
        {
            break;
        }
    }

    //由左子树的先序列，中序列，左子树的个数，得出左子树的根节点，也就是当前树的左孩子结点吗，不断的以此类推，递归求出所有子树的根节点，最终构建出整课二叉树
    jd->lchild = creatbypremid_ECL(pre, mid, ip + 1, im, i);
    //同理求出右子树的根节点，也就是当前树的右孩子节点
    jd->rchild = creatbypremid_ECL(pre, mid, ip + i + 1, im + i + 1, n - i - 1);

    //返回当前子树的根节点。
    return jd;
}

// copy创造函数，p是传入的要copy的二叉树的根节点地址
//该函数的作用是根据传入的要copy的二叉树根节点，然后完成对整个二叉树copy，并返回创建的二叉树的根节点。
//传入要copy二叉树根节点，获得我们创建的二叉树根节点，以及要copy的二叉树的左右孩子节点，最终就可以以此类推，不断推出我们要创建的二叉树的子树的根节点，最终成功创建整课二叉树
template <class T>
Sjjd<T> *ECL<T>::creatbycopy_ECL(Sjjd<T> *gjd)
{
    if (gjd == NULL)
        return NULL;
    //根据传入的树的根节点，创建出新的二叉树的根节点
    Sjjd<T> *jd = new Sjjd<T>;
    jd->data = gjd->data;

    //通过传入的树的根节点，获得这棵树的左右子树的根节点，这样我们就可以创建出我们当前树的左右子树的根节点
    jd->lchild = creatbycopy_ECL(gjd->lchild);
    jd->rchild = creatbycopy_ECL(gjd->rchild);
    return jd;
}

//无参构造函数，构造空树
template <class T>
ECL<T>::ECL()
{
    root = NULL;
}
//先序构造函数，P是存储带空指针的先序序列的一个单链表。
//用户得先创建一段带空指针的先序序列，然后调用先序构造函数的时候将其传进来，然后先序构造函数调用先序创建函数来构造二叉树，这里规定空指针为-1
template <class T>
ECL<T>::ECL(vector<T> &p)
{
    //遍历i存储先序序列p的下标，最开始存储第一个元素的下标
    int i = 0;
    //调用先序创建函数来创建二叉树
    root = creatbypre_ECL(p, i);
}

//先中序构造函数，Pre和mid分别存储该二叉树的先序列和中序列
//该函数作用，通过用户传进来一颗二叉树得先序列和中序列，然后调用先中序创建函数，构建出这课二叉树，并将其返回的根节点地址赋值给root。
template <class T>
ECL<T>::ECL(vector<T> &pre, vector<T> &mid)
{
    int n = pre.size();
    root = creatbypremid_ECL(pre, mid, 0, 0, n);
}

//拷贝构造函数,p是传入的要copy的二叉树对象
//根节点传入的二叉树对象，调用copy创建函数，来创建新的二叉树
template <class T>
ECL<T>::ECL(ECL &p)
{
    root = creatbycopy_ECL(p.root);
}

//有参先序遍历输出函数,root是要遍历的二叉树的根节点
// root是私有数据成员，在 main()函数中不能使用，因此把该函数定为类里的私函数，另外再重载定义公有无参函数xxbl_ECL（）来供主调函数调用

template <class T>
void ECL<T>::xxbl_ECL(Sjjd<T> *root)
{
    //树的根节点为空，说明该节点不存在
    if (root == NULL)
        return;
    //根节点不为空
    else
    {
        //输出当前树的根节点
        cout << root->data << endl;

        //先序遍历该节点的左子树
        xxbl_ECL(root->lchild);
        //先序遍历该节点的右子树
        xxbl_ECL(root->rchild);
    }
}
//无参的先序遍历输出函数，其作用是调用有参的先序遍历函数
template <class T>
void ECL<T>::xxbl_ECL()
{

    xxbl_ECL(root);
}

//有参的返回深度函数，gjd是传入的根节点
//作用是根据传入的树的根节点，返回这棵树的高度
template <class T>
int ECL<T>::return_sd_ECL(Sjjd<T> *gjd)
{
    //当树是空的就没有条件
    if (gjd == NULL)
    {
        return 0;
    }

    //根据这个根节点左右子树的根节点，我们可以获得左右子树的深度
    int zzssd = return_sd_ECL(gjd->lchild);
    int yzssd = return_sd_ECL(gjd->rchild);

    //在获得左右子树的深度的情况下，就可以返回当前树的深度，那就是最大的左右子树的深度，加本身节点。
    if (zzssd > yzssd)
    {
        return zzssd + 1;
    }
    return yzssd + 1;
}

//无参的返回深度函数，起作用是调用有参的返回深度函数，求得当前树的深度
template <class T>
int ECL<T>::return_sd_ECL()
{
    return return_sd_ECL(root);
}

//查找结点函数，gjd是传入的二叉树根节点，e是在这个二叉树里要查找的值，返回是返回查找到的结点。
template <class T>
Sjjd<T> *ECL<T>::find_jd_ECL(Sjjd<T> *gjd, T e)
{
    //根节点为空，说明当前树没有该值
    if (gjd == NULL)
        return NULL;
    //找到该值，返回该值的根结点
    if (gjd->data == e)
        return gjd;

    //在左子树查找是否有该根节点,有的话就返回查找的结点
    Sjjd<T> *p = find_jd_ECL(gjd->lchild, e);
    if (p != NULL)
        return p;
    else
        return find_jd_ECL(gjd->rchild, e);
}

//查找结点函数,e是查找的值
//调用重载函数查找该节点地址
template <class T>
Sjjd<T> *ECL<T>::find_jd_ECL(T e)
{
    return find_jd_ECL(root, e);
}
//释放函数，p是传入进来要释放的二叉树的根基的
template <class T>
void ECL<T>::free_ECL(Sjjd<T> *gjd)
{
    //当前树的根节点为空，则不用再释放
    if (gjd == NULL)
        return;
    //释放左右子树的根节点
    free_ECL(gjd->lchild);
    free_ECL(gjd->rchild);
    delete gjd;
}

//析构函数，用来调用释放函数来释放链表
template <class T>
ECL<T>::~ECL()
{
    free_ECL(root);
}
int main()
{

    //测试的带空指针的先序序列为1，2，3，-1，-1，4，-1，-1，5，6，-1，-1，-1
    vector<int> a;
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);
    a.push_back(-1);
    a.push_back(-1);
    a.push_back(4);
    a.push_back(-1);
    a.push_back(-1);
    a.push_back(5);
    a.push_back(6);
    a.push_back(-1);
    a.push_back(-1);
    a.push_back(-1);
    ECL<int> b(a);

    //测试先中序构造二叉树,先序序列为123456，中序列为324165,
    vector<int> pre;
    vector<int> mid;
    pre.push_back(1);
    pre.push_back(2);
    pre.push_back(3);
    pre.push_back(4);
    pre.push_back(5);
    pre.push_back(6);

    mid.push_back(3);
    mid.push_back(2);
    mid.push_back(4);
    mid.push_back(1);
    mid.push_back(6);
    mid.push_back(5);

    ECL<int> c(pre, mid);
    //测试copy构造函数 c2 copy c.
    ECL<int> c2(c);
    c2.xxbl_ECL();
    //测试查找结点的函数
    Sjjd<int> *jd = c2.find_jd_ECL(2);
    cout << jd->data;
}

huffman树

huffman树的基础知识

信息编码的理解

信息编码的方法可分为定长编码和不定长编码两大类。

定长编码是指在编码系统中，每个符号的代码长度相等。例如，在常用的 ASCII码中，每个符号的编码都是一个字节。

不定长编码每个符号的长度不一定相等，其基本思想是根据各种符号出现的频率来编码，使经常出现的符号的编码较短，不常出现的符号的编码较长。由于使用不定长编码的目的是使信息经过编码后的编码文件长度尽可能短，因此也称为统计编码。相比定长编码，不定长编码不仅节省磁盘空间,还能提高传递和运算速度。

平均码长的理解

设某编码系统中有n个符号，每个符号的码长分别是L1,L2，…，Ln，各自出现的频率分别是F1,F2，…，Fn，则

定长编码和不定长编码的举例

假设某信息系统中有4种符号，分别记作A、B、C、D，它们各自出现的统计频率是5% 、2%、45%、48%。

若采用定长编码方式，则每个符号的编码需要2位，如A是00，B是01,C是10，D是11，平均码长是2。

若采用不定长编码方式，假设A是000，B是001,C是01,D是1，则平均码长=3×5% +3×2% +2×45% +1×48% =0.15+0.06+0.9+0.48 = 1.59。显然，在这种情形下,不定长编码的平均码长更短。 相同的信息，平均码长越短，所消耗的资源越少，因此在这个情况下，不定长编码的效率要优于定长编码。

不定长编码可能出现的问题

但是，由于不定长编码的码长不固定，因此在识别编码串时，存在各符号的码串相互混淆的可能。例如，上述不定长编码中，若将D的编码改为0，则编码串“000”的意义既可以是一个符号A，也可以是3个符号D。因此，必须为不定长编码增加如下约束条件:在同一编码系统中，任何符号的编码不能是另一符号编码的前缀。满足此条件的编码也被称为前缀编码.。

二叉树的带权路径长度的理解

在二叉树结构中，设有n个叶子结点，每个叶子结点有一个权值，记作 Wi。 (1≤i≤n)，从根结点到各个叶子结点的路径长度记作Li，则该二叉树的带权路径长度（Weighted Path Length,WPL)

huffman树的理解

huffman树是一种特殊的二叉树，他也被称为最优树。
Huffman 树是在叶子结点集合确定的前提下，所有可能的二叉树形态中，树的带权路径长度最小的二叉树。

huffman树的举例

例如,已知4个叶子结点的权值分别是2、4、5、7,
假设这四个叶子结点只能构造出下面图中3种形态的二叉树。

其中，图a所示的二叉树的WPL=46，图b所示的二叉树的WPL =36，图c所示的二叉树的WPL = 35。
那么图c就是是在叶子结点集和确定的前提，所有可能的二叉树形态中树的带权路径长度最小的二叉树，也就是说图c就是huffman树

huffman编码

当Huffman树进行huffman编码时，叶子结点可以看成是需要编码的符号。此时从根结点开始，将每个结点的左分支记作0，右分支记作1，那么每个叶子结点的路径都可以用一个0/1串的编码来表示，也就是说，每一个叶子结点都可以用0/1串的编码来表示，这种编码称作Huffman编码。
在Huffman编码下，可以理解为，每一个叶子结点就是需要编码的符号。每个叶子结点的权值，就是需要编码的符号的频率。每一个叶子结点可以用他的路径（一个0/1串的编码）来表示，也就是说叶子结点的路径相当于符号的编码，叶子结点的路径长度，就是编码长度。 那么此时Huffman树的带权路径长度，就是这个编码系统的平均码长。

不能将普通结点作为需要编码的符号的原因。

将huffman树叶子结点进行huffman编码，而不将huffman树的普通结点进行huffman编码的原因是，叶子结点的路径不会是另一个叶子结点的路径的前缀，而普通结点的路径，可能会是其他结点的前缀，这样编码就不属于前缀编码，在识别编码时就可能会出现混淆。

使用huffman树进行编码的原因

Huffman树的带权路径长度最小，因此使用Huffman树进行huffman编码的平均码长也是最小。一些压缩/解压缩软件就是基于Huffman编码实现的。

huffman树的构造

huffman树的构造算法

huffman树的构造算法举例说明

假设某信息系统中有5种符号，分别记作A、B、C、D、E，它们各自出现的统计频率是6%、14%、53%、15%、12%。

Huffman树的构造过程如下图




e所示的是最终建成的Huffman树，f是从e中读出的Huffman编码。

数据结构问题

约瑟夫问题

约瑟夫问题描述

n个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数，报到第m 个人，令其出列。然后再从下一个人开始从1顺时针报数，报到第m 个人，再令其出列，如此下去，求出列顺序。

约瑟夫问题举例

N=8
M=3

最终数出来的约瑟夫序列为3 6 1 5 2 8 4 7

实现文件

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
//在单向循环链表里插入该函数
//输出约瑟夫序列函数，解决约瑟夫问题，输出约瑟夫所需要的序列
template <class T>
void DXXHLB<T>::prinysf_DXXHLB(int m)
{
     //创建一个指针，用来指向表格中的节点，里面先暂时指向头结点
    Sjjd<T> *jd = head;
    //index表示jd节点在表格中位置。其表示方法，是到第m个节点的时候index为m，但是下一个节点开始，index会重置为1，然后又到第m+1个节点又重置为1。头结点跳过。
    int index = 0;

    //当表格只剩下一个结点的时候会跳出循环
    while (sl > 1)
    {
        //jd存储下一个节点的位置
        jd = jd->next;
        //如果jd是头结点，则跳过头结点
        if (jd == head)
        {
            jd = jd->next;
        }
        //更新index
        ++index;

        if (index == m)
        {
            //输出第m个结点的数据
            cout << jd->data << " ";

            //存储要删除的结点的数据
            T deletedata = jd->data;
            //jd存储下一个结点的地址
            jd = jd->next;
            //跳过头结点
            if (jd == head)
            {
                jd = jd->next;
            }
            //用值删除函数，删除刚刚输出的结点
            removebyvalue_DXXHLB(deletedata);
            //更新sl和index
            --sl;
            index = 1;
        }
    }
//输出表格剩下的一个结点
    cout << head->next->data << endl;
}

测试文件Yef.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include "DXXHLB.h"
#include "DXXHLB.cpp"
using namespace std;
int main()
{
    DXXHLB<int> a;
    int m, n;
    cout << "n:";
    cin >> n;
    cout << "m:";
    cin >> m;
    for (int i = 1; i <= n; i++)
    {
        a.insert_DXXHLB(i, i);
    }

    a.prinysf_DXXHLB(m);
}