最近对Data Structure & Algorithm突然很感兴趣，想找些网课来稍微入门入门。最后找到了两门不错的课，分别是浙大和清华的数据结构。个人认为浙大的课比较适合小白入门，清华的课则会讲得比较深入（包括很多算法讲得很多更具体的应用，以及会将算法与数据结构和计算机组织的知识联系起来，比如一个排序算法是如何和Cache存储机制相关联的）Whatever，觉得对于我这种非科班的同学，浙大的数据结构已经足够入门了。

资源整理

B站

浙江大学数据结构：数据结构-浙江大学哔哩哔哩bilibili

知乎

学习算法的回答一：算法到底应该怎么学？ - 知乎 (zhihu.com)
学习算法的回答二：(46 封私信 / 22 条消息) 如何系统地学习算法？ - 知乎 (zhihu.com)

复杂度的渐进表示

主要分为空间复杂度和时间复杂度，一般算法的时间复杂度尽可能地逼近线性时间复杂度O(n)为好。
复杂度视频链接：数据结构-浙江大学哔哩哔哩bilibili
复杂度与算法设计视频（1&2&3&4）：数据结构-浙江大学哔哩哔哩bilibili

数据结构Data Structure

数组	链表	队列	堆	栈
散列表	二叉树	跳表	树	图

以下是我总结的十大数据结构。所有数据结构的基础就是数组和链表，所以对于掌握所有数据结构，以及从八大基础数据结构衍生出的高级数据结构，熟练掌握数组以及链表的实现至关重要。因为这些数据结构本身不难理解，所以这里只提供简易版的实现代码，相关的资料链接可以在网上自己找。
值得一提的是，学习数据结构时不能只是停留在了解数据结构的特点的层面，还要把该抽象数据类型的相关操作也都实现一下，这个我觉得很重要。

数组（查删插）

代码如下：

#include<iostream>
using namespace std;
class Array
{
    private:
    double a[50];
    int tail;
    public:
    Array()
    {
        for (int i = 0; i < 50; i++)
            a[i] = 0;
        tail = -1;
    }
    void Addnum(double num)
    {
        if (tail >= 49)
        {
            cout << "不能加了！" << endl;
            return;
        }
        else
            a[++tail] = num;
    }
    void Addnum(double num,int pos)
    {
        if (tail >= 49)
        {
            cout << "不能加了！" << endl;
            return;
        }
        if (pos > tail + 1 && pos < 50)
            pos = tail + 1;
        for (int i = tail; i > pos - 1 ; i--)
            a[i+1] = a[i];
        a[pos] = num;
        ++tail;
    }
    void Delnum(int pos)
    {
        if (tail == -1)
        {
            cout << "空数组了！删不了" << endl;
            return;
        }
        if (pos < 0) pos = 0;
        else if (pos > tail)
        {
            tail--;
            return;
        }
        for (int i = pos + 1; i < tail; i++)
            a[i] = a[i + 1];
        tail--;
    }
    double Getnum(int pos)
    {
        if (pos<0 || pos>tail)
        {
            cout << "不在数组有效范围内！" << endl;
            return 0;
        }
        else
            return a[pos];
    }
    void Display()
    {
        for (int i = 0; i <= tail; i++)
            cout<<a[i]<<" ";
        cout << "最后一位索引为 " << this->tail << endl;
    }
};
int main()
{
    Array a;
    a.Addnum(3);
    a.Addnum(5);
    a.Addnum(7);
    a.Addnum(7,1);
    a.Display();
}

链表（查删插）

代码如下：

#include<iostream>
using namespace std;
class Node
{
private:
    double value;
    Node* next;
public:
    Node()
    {
        value = 0;
        next = NULL;
    }
    double Getvalue() { return this->value; }
    Node* Getnext() { return this->next; }
    void Setvalue(double num) { value = num; }
    void Setnext(Node* a) { next = a; }
};
class Nodearray
{
private:
    Node* head;
    Node* tail;
public:
    Nodearray()
    {
        head = NULL;
        tail = NULL;
    }
    void Addnum(double num)
    {
        if (head == NULL)
        {
            head = new Node;
            head->Setvalue(num);
            head->Setnext(NULL);
            tail = head;
        }
        else
        {
            tail->Setnext(new Node);
            (tail->Getnext())->Setvalue(num);
            (tail->Getnext())->Setnext(NULL);
            tail = tail->Getnext();
        }
    }
    void Display()
    {
        Node* p = head;
        if (head == NULL) return;
        else
        {
            while (p != NULL)
            {
                cout << p->Getvalue() << " ";
                p = p->Getnext();
            }
        }
        cout << endl;
    }
    void Getnum(int pos)
    {
        int count = 1;
        Node* p = head;
        while (p != NULL)
        {
            if (count == pos)
            {
                cout << "找到了！ ";
                cout << p->Getvalue() << endl;
                return;
            }
            p = p->Getnext();
            count++;
        }
        cout << "没找到！" << endl;
    }
    void Delnum(double num)
    {
        Node* p1 = head;
        Node* p2 = head;
        if (head == NULL)
        {
            cout << "这是空列表" << endl;
            return;
        }
        else
        {
            if (head->Getvalue() == num)
            {
                head = head->Getnext();
                return;
            }
            else
            {
                p2 = p2->Getnext();
            }
            while (p2 != NULL)
            {
                if (p2->Getvalue() == num)
                {
                    p1->Setnext(p2->Getnext());
                    cout << "删除成功" << endl;
                    return;
                }
                p1 = p1->Getnext();
                p2 = p2->Getnext();
            }
        }
    }
};
int main()
{
    Nodearray a;
    a.Addnum(2);
    a.Addnum(3);
    a.Addnum(4);
    a.Addnum(9);
    a.Addnum(6);
    a.Addnum(5);
    a.Display();
    a.Getnum(2);
    a.Delnum(9);
    a.Display();
    a.Delnum(2);
    a.Display();
}

队列

其实就是一边进另外一边出的线性结构，有数组和链表两种实现方式。具体代码略。

堆栈

其实就是一边进这边也出的线性结构，有数组和链表两种实现方式。具体代码略。

广义表

广义表与多重链表：数据结构-浙江大学哔哩哔哩bilibili
其实就是链表中可以包含子链表，示意图如下：
CS专题——浙大数据结构C 实现 - 图1
代码如下：

#include<iostream>
using namespace std;

enum TYPE
{
    HEAD_TYPE,  //表头
    VALUE_TYPE, //值
    SUB_TYPE,   //子表
};

struct GeneralizedNode
{
    GeneralizedNode(TYPE type, const char& value = 0)
        :_type(type)
        , _next(NULL)
        , _sublink(NULL)
    {
        _value = value;
    }

    TYPE _type;     //类型
    GeneralizedNode* _next; //指向下一个表项
    union
    {
        char _value;
        GeneralizedNode* _sublink;  //指向子表头
    };
    //除头结点外，剩下的节点中每个结点有可能是value也可能是sub，因此用联合
};

class GeneralizedList
{
    typedef GeneralizedNode Node;
public:
    GeneralizedList()
        :_head(NULL)
    {}

    GeneralizedList(const char* str)
        :_head(NULL)
    {
        _head = _CreatList(str);
    }

    GeneralizedList(const GeneralizedList& g)   //拷贝构造
    {
        _head = _copy(g._head);
    }

    ~GeneralizedList()
    {
        Destory(_head);
    }

    GeneralizedList& operator=(const GeneralizedList& g)
    {
        //_head = _assignment(g);
        if (this != &g)
        {
            GeneralizedList tmp(g);
            std::swap(_head, tmp._head);
        }
        return *this;
    }

    size_t Size()
    {
        return _size(_head);
    }
    size_t Depth()
    {
        return _depth(_head);
    }
    void Print()
    {
        _print(_head);
    }
protected:
    bool Judge(const char& value)
    {
        if ((value >= '0' && value <= '9') ||
            (value >= 'a' && value <= 'z') ||
            (value >= 'A' && value <= 'Z'))
            return true;
        else
            return false;
    }
    Node* _CreatList(const char*& str)
    {
        Node* head = new Node(HEAD_TYPE, *str);
        Node* prev = head;
        head->_type = HEAD_TYPE;
        ++str;
        while (*str)
        {
            if (Judge(*str))        //有效值项
            {
                Node* node = new Node(VALUE_TYPE, *str);
                prev->_next = node;
                prev = prev->_next;

                ++str;
            }
            else if (*str == '(')       //有子表项
            {
                Node* node = new Node(SUB_TYPE, *str);
                prev->_next = node;
                prev = prev->_next;
                prev->_sublink = _CreatList(str);
                ++str;
            }
            else if (*str == ')')
            {
                prev->_next = NULL;

                ++str;
                return head;
            }
            else
                ++str;
        }
        return head;
    }
    Node* _copy(Node* copyhead)
    {
        Node* newhead = new Node(HEAD_TYPE, copyhead->_value);  //新表的头
        Node* prev = newhead;
        Node* cur = copyhead->_next;
        while (cur)
        {
            if (cur->_type == VALUE_TYPE)   //拷贝值结点
            {
                Node* tmp = new Node(VALUE_TYPE, cur->_value);
                prev->_next = tmp;
                prev = prev->_next;
                cur = cur->_next;
            }
            else if (cur->_type == SUB_TYPE)        //拷贝子表
            {
                Node* tmp = new Node(SUB_TYPE);
                prev->_next = tmp;
                prev = prev->_next;
                tmp->_sublink = _copy(cur->_sublink);
                cur = cur->_next;
            }
            else
                cur = cur->_next;
        }
        return newhead;
    }
    void Destory(Node* head)
    {
        Node* cur = head;
        while (cur)
        {
            Node* del = cur;
            if (cur->_type == SUB_TYPE)
            {
                Destory(cur->_sublink);
            }
            cur = cur->_next;
            delete[] del;
        }
    }
    Node* _assignment(const GeneralizedList& g)
    {
        if (this != &g)
        {
            Node* newhead = new Node(HEAD_TYPE, g._head->_value);
            Destory(_head);
            _head = newhead;
        }
        return _head;
    }
    size_t _size(Node* head)    //表内有效值的个数
    {
        Node* cur = head;
        size_t count = 0;
        while (cur)
        {
            if (cur->_type == VALUE_TYPE)
            {
                count++;
            }
            else if (cur->_type == SUB_TYPE)
            {
                count += _size(cur->_sublink);
            }
            cur = cur->_next;
        }
        return count;
    }
    size_t _depth(Node* head)   //表的最大深度
    {
        Node* cur = head;
        size_t maxdepth = 1;
        while (cur)
        {
            size_t depth = 1;
            if (cur->_type == SUB_TYPE)
            {
                depth += _depth(cur->_sublink);
                if (depth > maxdepth)
                {
                    maxdepth = depth;
                }
            }
            cur = cur->_next;
        }
        return maxdepth;
    }
    void _print(Node* head)
    {
        Node* cur = head;
        while (cur)
        {
            if (cur->_type == VALUE_TYPE)
            {
                cout << cur->_value;
                if (cur->_next != NULL)
                {
                    cout << ",";
                }
                cur = cur->_next;
            }
            else if (cur->_type == SUB_TYPE)
            {
                _print(cur->_sublink);
                if (cur->_next != NULL)
                {
                    cout << ",";
                }
                cur = cur->_next;
            }
            else
            {
                cout << "(";
                cur = cur->_next;
            }
        }
        cout << ")";
    }
protected:
    Node* _head;
};

散列表

也叫哈希表，其实本质就是数组+链表的实现方式，示意图如下所示：
CS专题——浙大数据结构C 实现 - 图2
代码如下所示：

#include<iostream>
using namespace std;

class Node
{
private:
    double value;
    Node* next;
public:
    Node()
    {
        value = 0;
        next = NULL;
    }
    double Getvalue() { return this->value; }
    Node* Getnext() { return this->next; }
    void Setvalue(double num) { value = num; }
    void Setnext(Node* a) { next = a; }
};

class Nodearray
{
private:
    Node* head;
    Node* tail;
public:
    Nodearray()
    {
        head = NULL;
        tail = NULL;
    }
    Node* Gethead() { return this->head; }
    void Sethead(Node* a) { this->head = a; }
    void Settail(Node* a) { this->tail = a; }
    Node* Gettail() { return this->tail; }
    void Addnum(double num)
    {
        if (head == NULL)
        {
            head = new Node;
            head->Setvalue(num);
            head->Setnext(NULL);
            tail = head;
        }
        else
        {
            tail->Setnext(new Node);
            (tail->Getnext())->Setvalue(num);
            (tail->Getnext())->Setnext(NULL);
            tail = tail->Getnext();
        }
    }
    void Display()
    {
        Node* p = head;
        if (head == NULL) return;
        else
        {
            while (p != NULL)
            {
                cout << p->Getvalue() << " ";
                p = p->Getnext();
            }
        }
        cout << endl;
    }
    void Getnum(int pos)
    {
        int count = 1;
        Node* p = head;
        while (p != NULL)
        {
            if (count == pos)
            {
                cout << "找到了！ ";
                cout << p->Getvalue() << endl;
                return;
            }
            p = p->Getnext();
            count++;
        }
        cout << "没找到！" << endl;
    }
    void Delnum(double num)
    {
        Node* p1 = head;
        Node* p2 = head;
        if (head == NULL)
        {
            cout << "这是空列表" << endl;
            return;
        }
        else
        {
            if (head->Getvalue() == num)
            {
                head = head->Getnext();
                return;
            }
            else
            {
                p2 = p2->Getnext();
            }
            while (p2 != NULL)
            {
                if (p2->Getvalue() == num)
                {
                    p1->Setnext(p2->Getnext());
                    cout << "删除成功" << endl;
                    return;
                }
                p1 = p1->Getnext();
                p2 = p2->Getnext();
            }
        }
    }
};

class Hashtable
{
public:
    Nodearray a[7];
    Hashtable()
    {
        for (int i = 0; i < 7; i++)
        {
            a[i].Sethead(NULL);
            a[i].Settail(NULL);
        }
    }
    void Addnum(int num)
    {
        int p = num / 100 - 1;
        a[p].Addnum(double(num));
    }
    void Display()
    {
        for (int i = 0; i < 7; i++)
            a[i].Display();
    }
};

int main()
{
    Hashtable hash;
    hash.Addnum(703);
    hash.Addnum(121);
    hash.Addnum(317);
    hash.Addnum(405);
    hash.Addnum(705);
    hash.Addnum(318);
    hash.Addnum(719);
    hash.Addnum(203);
    hash.Display();
}

树

主要使用到的是二叉树，前序遍历示意图：
CS专题——浙大数据结构C 实现 - 图3
下面是树的实现代码：

#include<iostream>
#include<cmath>
using namespace std;

class Node
{
private:
    double value;
    Node* leftnode;
    Node* rightnode;
public:
    Node()
    {
        value = 0;
        leftnode = NULL;
        rightnode = NULL;
    }
    double Getvalue() { return this->value; }
    Node* Getleftnode() { return this->leftnode; }
    Node* Getrightnode() { return this->rightnode; }
    void Setvalue(double num) { value = num; }
    void Setleftnode(Node* a) { leftnode = a; }
    void Setrightnode(Node* a) { rightnode = a; }
    ~Node()
    {
        delete leftnode;
        delete rightnode;
    }
};

void Qianxu(Node* p);
void Zhongxu(Node* p);
void Houxu(Node* p);

class Tree
{
public:
    Node* root;
    Tree()
    {
        root = NULL;
    }
    void Addnum(double num,int layer,int pos)
    {
        Node* p = root;
        int count = 1;
        double thresh = pow(2, layer-2);
        if (layer == 1 && pos == 1 && root == NULL)
        {
            root = new Node;
            root->Setvalue(num);
            return;
        }
        while (count != layer - 1)
        {
            count++;
            if (pos > thresh)
            {
                thresh = thresh + pow(2, layer - 3);
                p = p->Getrightnode();
            }
            else
            {
                thresh = thresh - pow(2, layer - 3);
                p = p->Getleftnode();
            }
        }
        if (pos % 2 == 1)
        {
            p->Setleftnode(new Node);
            p = p->Getleftnode();
            p->Setvalue(num);
            return;
        }
        else
        {
            p->Setrightnode(new Node);
            p = p->Getrightnode();
            p->Setvalue(num);
            return;
        }
    }
    void Cengxu()
    {
        Node* temp[20];
        if (this->root == NULL) return;
        else
        {
            int endsok = 0;
            temp[0] = root;
            while (endsok != -1)
            {
                cout << temp[0]->Getvalue() << " ";
                if (temp[0]->Getleftnode() != NULL)
                    temp[++endsok] = temp[0]->Getleftnode();
                if (temp[0]->Getrightnode() != NULL)
                    temp[++endsok] = temp[0]->Getrightnode();
                for (int i = 1; i <= endsok; i++)
                    temp[i - 1] = temp[i];
                endsok--;

            }
        }
    }
    void Display(int way)
    {
        if (way == 1)
            Qianxu(root);
        else if (way == 2)
            Zhongxu(root);
        else if (way == 3)
            Houxu(root);
        else
            Cengxu();
    }
    ~Tree() { delete root; }
};

int main()
{
    Tree a;
    a.Addnum(5, 1, 1);
    a.Addnum(3, 2, 1);
    a.Addnum(2, 2, 2);
    a.Addnum(5, 3, 1);
    a.Addnum(1, 3, 2);
    a.Addnum(10, 3, 3);
    a.Addnum(109, 3, 4);
    a.Addnum(14, 4, 2);
    a.Display(3);
}

void Qianxu(Node* p)
{
    cout << p->Getvalue() << " ";
    if (p->Getleftnode() != NULL)
        Qianxu(p->Getleftnode());
    if (p->Getrightnode() != NULL)
        Qianxu(p->Getrightnode());
}

void Zhongxu(Node* p)
{
    if (p->Getleftnode() != NULL)
        Zhongxu(p->Getleftnode());
    cout << p->Getvalue() << " ";
    if (p->Getrightnode() != NULL)
        Zhongxu(p->Getrightnode());
}

void Houxu(Node* p)
{
    if (p->Getleftnode() != NULL)
        Houxu(p->Getleftnode());
    if (p->Getrightnode() != NULL)
        Houxu(p->Getrightnode());
    cout << p->Getvalue() << " ";
}

树的其他应用还有二叉搜索树、平衡二叉树、哈夫曼树和最大堆/最小堆等。

哈夫曼树

哈夫曼树的定义：数据结构-浙江大学哔哩哔哩bilibili
哈夫曼树的构造：数据结构-浙江大学哔哩哔哩bilibili
哈夫曼树，也称最优树，是很重要的一种数据结构，下面是用选择排序建立哈夫曼树的代码：

#include<iostream>
#include<cmath>
using namespace std;


class Node
{
private:
    double value;
    Node* leftnode;
    Node* rightnode;
    int leftheight;
    int rightheight;
public:
    Node()
    {
        value = 0;
        leftnode = NULL;
        rightnode = NULL;
        leftheight = 0;
        rightheight = 0;
    }
    double Getvalue() { return this->value; }
    int Getleftheight() { return leftheight; }
    int Getrightheight() { return rightheight; }
    Node* Getleftnode() { return this->leftnode; }
    Node* Getrightnode() { return this->rightnode; }
    void Setvalue(double num) { value = num; }
    void Setleftnode(Node* a) { leftnode = a; }
    void Setrightnode(Node* a) { rightnode = a; }
    void Setleftheight(int a) { leftheight = a; }
    void Setrightheight(int a) { rightheight = a; }
};

void Qianxu(Node* p);
void Zhongxu(Node* p);
void Houxu(Node* p);
void AVL(Node* p);
int Setheight(Node* p);
Node* Checks(Node* p,Node* temp);
int scanmaxpos(int* series, int size);
void ChooseSort(int* series, double* series2, int size);

class Tree
{
public:
    Node* root;
    Tree()
    {
        root = NULL;
    }
    Node* Getroot() { return this->root; }
    void Setroot(Node* a) { this->root = a; }
    void Clearroot() { this->root = NULL; }
    void Addnum(double num, int layer, int pos)
    {
        Node* p = root;
        int count = 1;
        double thresh = pow(2, layer - 2);
        if (layer == 1 && pos == 1 && root == NULL)
        {
            root = new Node;
            root->Setvalue(num);
            return;
        }
        while (count != layer - 1)
        {
            count++;
            if (pos > thresh)
            {
                thresh = thresh + pow(2, layer - 3);
                p = p->Getrightnode();
            }
            else
            {
                thresh = thresh - pow(2, layer - 3);
                p = p->Getleftnode();
            }
        }
        if (pos % 2 == 1)
        {
            p->Setleftnode(new Node);
            p = p->Getleftnode();
            p->Setvalue(num);
            return;
        }
        else
        {
            p->Setrightnode(new Node);
            p = p->Getrightnode();
            p->Setvalue(num);
            return;
        }
    }
    void Addnum2(double num)
    {
        if (root == NULL)
        {
            root = new Node;
            root->Setvalue(num);
            return;
        }
        Node* p = root;
        int temp;
        while (true)
        {
            temp = p->Getvalue();
            if (num > temp && p->Getrightnode() == NULL)
            {
                p->Setrightnode(new Node);
                p = p->Getrightnode();
                p->Setvalue(num);
                Check(num);
                return;
            }
            else if (num < temp && p->Getleftnode() == NULL)
            {
                p->Setleftnode(new Node);
                p = p->Getleftnode();
                p->Setvalue(num);
                Check(num);
                return;
            }
            else if(num > temp)
                p = p->Getrightnode();
            else
                p = p->Getleftnode();
        }
    }
    void Cengxu()
    {
        Node* temp[20];
        if (this->root == NULL) return;
        else
        {
            int endsok = 0;
            temp[0] = root;
            while (endsok != -1)
            {
                cout << temp[0]->Getvalue() << " ";
                if (temp[0]->Getleftnode() != NULL)
                    temp[++endsok] = temp[0]->Getleftnode();
                if (temp[0]->Getrightnode() != NULL)
                    temp[++endsok] = temp[0]->Getrightnode();
                for (int i = 1; i <= endsok; i++)
                    temp[i - 1] = temp[i];
                endsok--;

            }
        }
    }
    void Display(int way)
    {
        if (way == 1)
            Qianxu(root);
        else if (way == 2)
            Zhongxu(root);
        else if (way == 3)
            Houxu(root);
        else if (way == 4)
            Cengxu();
        else
            AVL(root);
    }
    void Check(double addnum)
    {
        int temp = Setheight(root);
        Display(5);
        cout << endl;
        Node* p = root;
        Node* tem = NULL;
        if (p->Getleftnode() != NULL)
            tem = Checks(p->Getleftnode(),tem);
        if (p->Getrightnode() != NULL)
            tem = Checks(p->Getrightnode(),tem);
        if (tem == NULL) return;
        else
        {
            cout << "不平衡！" << endl;
            Node* a = NULL;
            if (tem->Getvalue() < addnum)
            {
                if ((tem->Getrightnode())->Getvalue() < addnum)
                {
                    a = tem;
                    tem = tem->Getrightnode();
                    if (a != tem)
                        cout << "1" << endl;
                    tem->Setleftnode(a);
                    a->Setrightnode(NULL);
                }
                else
                {
                    a = tem;
                    tem = (tem->Getrightnode())->Getleftnode();
                    tem->Setleftnode(a);
                    //tem->Setrightnode(a->)
                }
            }
            else
            {
                if ((tem->Getrightnode())->Getvalue() < addnum)
                {
                    a = tem;
                    root->Setrightnode(tem->Getrightnode());
                    (root->Getrightnode())->Setleftnode(a);
                    a->Setrightnode(NULL);
                }
                else
                {
                    a = tem;
                    tem = (tem->Getrightnode())->Getleftnode();
                    (tem->Getrightnode())->Getleftnode()->Setleftnode(a);
                    (tem->Getrightnode())->Getleftnode()->Setrightnode(a->Getrightnode());
                }
            }
        }
    }
    ~Tree() { delete root; }
};

int Setheight(Node* p)
{
    Node* temp;
    Node* temp2;
    if (p == NULL)
    {
        return 0;
    }
    if (p->Getleftnode() == NULL && p->Getrightnode() == NULL)
    {
        p->Setleftheight(1);
        p->Setrightheight(1);
    }
    else if (p->Getleftnode() != NULL && p->Getrightnode() == NULL)
    {
        p->Setrightheight(0);
        temp = p->Getleftnode();
        p->Setleftheight(max(Setheight(temp->Getleftnode()), Setheight(temp->Getrightnode())) + 1);
    }
    else if (p->Getleftnode() == NULL && p->Getrightnode() != NULL)
    {
        p->Setleftheight(0);
        temp2 = p->Getrightnode();
        p->Setrightheight(max(Setheight(temp2->Getleftnode()), Setheight(temp2->Getrightnode())) + 1);
        //cout << "右" << p->Getrightheight() << " ";
    }
    else
    {
        temp = p->Getleftnode();
        p->Setleftheight(max(Setheight(temp->Getleftnode()), Setheight(temp->Getrightnode())) + 1);
        //cout << "左" << p->Getleftheight() << " ";
        temp2 = p->Getrightnode();
        p->Setrightheight(max(Setheight(temp2->Getleftnode()), Setheight(temp2->Getrightnode())) + 1);
        //cout << "右" << p->Getrightheight() << " ";
    }


    return max(p->Getleftheight(), p->Getrightheight());
}

int main()
{
    double a[5] = { 14,7,8,12,5 };
    int b[5] = { 14,32,3,18,30 };
    int count = 0;
    Tree tree1;
    Tree tree2;
    Tree tree3;
    int ind = 0;
    int ind2 = 0;
    while (count != 4)
    {
        ChooseSort(b + count, a + count, 5 - count);
        if (tree2.Getroot() == NULL && tree3.Getroot() == NULL)
        {
            tree1.Addnum(a[count + 1] + a[count], 1, 1);
            tree1.Addnum(a[count], 2, 1);
            tree1.Addnum(a[count + 1], 2, 2);
            tree2.Setroot(tree1.Getroot());
            tree1.Clearroot();
        }
        else
        {   
            if (a[count] == (tree2.Getroot())->Getvalue() && tree3.Getroot() == NULL)
            {
                tree1.Addnum(a[count + 1] + a[count], 1, 1);
                (tree1.Getroot())->Setleftnode(tree2.Getroot());
                tree1.Addnum(a[count + 1], 2, 2);
                tree2.Setroot(tree1.Getroot());
                tree1.Clearroot();
            }
            else if(a[count + 1] == (tree2.Getroot())->Getvalue() && tree3.Getroot() == NULL)
            {
                tree1.Addnum(a[count + 1] + a[count], 1, 1);
                (tree1.Getroot())->Setrightnode(tree2.Getroot());
                tree1.Addnum(a[count], 2, 1);
                tree2.Setroot(tree1.Getroot());
                tree1.Clearroot();
            }
            else if(tree3.Getroot() == NULL)
            {
                tree3.Addnum(a[count + 1] + a[count], 1, 1);
                tree3.Addnum(a[count], 2, 1);
                tree3.Addnum(a[count + 1], 2, 2);
                //tree3.Display(1);

            }
            else if(a[count] == (tree2.Getroot())->Getvalue() && a[count + 1] == (tree3.Getroot())->Getvalue())
            {
                cout << "1" << endl;
                tree1.Setroot(new Node);
                (tree1.Getroot())->Setvalue(a[count + 1] + a[count]);
                (tree1.Getroot())->Setleftnode(tree2.Getroot());
                (tree1.Getroot())->Setrightnode(tree3.Getroot());
                tree2.Setroot(tree1.Getroot());
                tree1.Clearroot();
            }
            else if (a[count] == (tree3.Getroot())->Getvalue() && a[count + 1] == (tree2.Getroot())->Getvalue())
            {
                cout << "2" << endl;
                tree1.Setroot(new Node);
                (tree1.Getroot())->Setleftnode(tree3.Getroot());
                (tree1.Getroot())->Setrightnode(tree2.Getroot());
                tree2.Setroot(tree1.Getroot());
                tree1.Clearroot();
            }
        }
        b[count + 1] = b[count + 1] + b[count];
        ind = b[count + 1];
        a[count + 1] = a[count + 1] + a[count];
        for (int i = 0; i < 5; i++)
            cout << b[i] << " ";
        cout << endl;
        count++;
    }
    tree2.Display(1);
}

void Qianxu(Node* p)
{
    cout << p->Getvalue()<< " ";
    if (p->Getleftnode() != NULL)
        Qianxu(p->Getleftnode());
    if (p->Getrightnode() != NULL)
        Qianxu(p->Getrightnode());
}

void Zhongxu(Node* p)
{
    if (p->Getleftnode() != NULL)
        Zhongxu(p->Getleftnode());
    cout << p->Getvalue() << " ";
    if (p->Getrightnode() != NULL)
        Zhongxu(p->Getrightnode());
}

void Houxu(Node* p)
{
    if (p->Getleftnode() != NULL)
        Houxu(p->Getleftnode());
    if (p->Getrightnode() != NULL)
        Houxu(p->Getrightnode());
    cout << p->Getvalue() << " ";
}

void AVL(Node* p)
{
    int temp = Setheight(p);
    //cout <<"左"<< p->Getleftheight() <<"右"<< p->Getrightheight() << " ";
    cout << p->Getleftheight() - p->Getrightheight() << " ";
    if (p->Getleftnode() != NULL)
        AVL(p->Getleftnode());
    if (p->Getrightnode() != NULL)
        AVL(p->Getrightnode());
}

Node* Checks(Node* p,Node* temp)
{
    //cout <<"左"<< p->Getleftheight() <<"右"<< p->Getrightheight() << " ";
    if (temp != NULL)
        return temp;
    if (p->Getleftheight() - p->Getrightheight() == -2)
        return p;
    if (p->Getleftheight() - p->Getrightheight() == 2)
        return p;
    if (p->Getleftnode() != NULL)
        temp = Checks(p->Getleftnode(),temp);
    if (p->Getrightnode() != NULL)
        temp = Checks(p->Getrightnode(),temp);
    return temp;
}

int scanmaxpos(int* series, int size)
{
    int thresh = series[0];
    int a = 0;
    for (int j = 1; j < size; j++)
    {
        if (series[j] > thresh)
        {
            thresh = series[j];
            a = j;
        }
    }
    return a;
}

void ChooseSort(int* series, double* series2,int size)
{
    int maxpos = 0;
    int temp = 0;
    double temp2 = 0;
    for (int i = 0; i < size - 1; i++)
    {
        maxpos = scanmaxpos(series, size - i);
        temp = series[size - 1 - i];
        temp2 = series2[size - 1  - i];
        series[size - 1 - i] = series[maxpos];
        series2[size - 1 - i] = series2[maxpos];
        series[maxpos] = temp;
        series2[maxpos] = temp2;
    }
}

二叉搜索树

二叉搜索树：数据结构-浙江大学哔哩哔哩bilibili
二叉搜索树建立的代码，二叉搜索树的建立利于二分查找：

#include<iostream>
#include<cmath>
using namespace std;


class Node
{
private:
    double value;
    Node* leftnode;
    Node* rightnode;
public:
    Node()
    {
        value = 0;
        leftnode = NULL;
        rightnode = NULL;
    }
    double Getvalue() { return this->value; }
    Node* Getleftnode() { return this->leftnode; }
    Node* Getrightnode() { return this->rightnode; }
    void Setvalue(double num) { value = num; }
    void Setleftnode(Node* a) { leftnode = a; }
    void Setrightnode(Node* a) { rightnode = a; }
    ~Node()
    {
        delete leftnode;
        delete rightnode;
    }
};

void Qianxu(Node* p);
void Zhongxu(Node* p);
void Houxu(Node* p);

class Tree
{
public:
    Node* root;
    Tree()
    {
        root = NULL;
    }
    void Addnum(double num, int layer, int pos)
    {
        Node* p = root;
        int count = 1;
        double thresh = pow(2, layer - 2);
        if (layer == 1 && pos == 1 && root == NULL)
        {
            root = new Node;
            root->Setvalue(num);
            return;
        }
        while (count != layer - 1)
        {
            count++;
            if (pos > thresh)
            {
                thresh = thresh + pow(2, layer - 3);
                p = p->Getrightnode();
            }
            else
            {
                thresh = thresh - pow(2, layer - 3);
                p = p->Getleftnode();
            }
        }
        if (pos % 2 == 1)
        {
            p->Setleftnode(new Node);
            p = p->Getleftnode();
            p->Setvalue(num);
            return;
        }
        else
        {
            p->Setrightnode(new Node);
            p = p->Getrightnode();
            p->Setvalue(num);
            return;
        }
    }
    void Addnum2(double num)
    {
        if (root == NULL)
        {
            root = new Node;
            root->Setvalue(num);
            return;
        }
        Node* p = root;
        int temp;
        while (true)
        {
            temp = p->Getvalue();
            if (num > temp && p->Getrightnode() == NULL)
            {
                p->Setrightnode(new Node);
                p = p->Getrightnode();
                p->Setvalue(num);
                return;
            }
            else if (num < temp && p->Getleftnode() == NULL)
            {
                p->Setleftnode(new Node);
                p = p->Getleftnode();
                p->Setvalue(num);
                return;
            }
            else if(num > temp)
                p = p->Getrightnode();
            else
                p = p->Getleftnode();
        }
    }
    void Cengxu()
    {
        Node* temp[20];
        if (this->root == NULL) return;
        else
        {
            int endsok = 0;
            temp[0] = root;
            while (endsok != -1)
            {
                cout << temp[0]->Getvalue() << " ";
                if (temp[0]->Getleftnode() != NULL)
                    temp[++endsok] = temp[0]->Getleftnode();
                if (temp[0]->Getrightnode() != NULL)
                    temp[++endsok] = temp[0]->Getrightnode();
                for (int i = 1; i <= endsok; i++)
                    temp[i - 1] = temp[i];
                endsok--;

            }
        }
    }
    void Display(int way)
    {
        if (way == 1)
            Qianxu(root);
        else if (way == 2)
            Zhongxu(root);
        else if (way == 3)
            Houxu(root);
        else
            Cengxu();
    }
    ~Tree() { delete root; }
};

int main()
{
    Tree a;
    //a.Addnum(5, 1, 1);
    //a.Addnum(3, 2, 1);
    //a.Addnum(2, 2, 2);
    //a.Addnum(7, 3, 1);
    //a.Addnum(1, 3, 2);
    //a.Addnum(10, 3, 3);
    //a.Addnum(109, 3, 4);
    //a.Addnum(14, 4, 2);
    a.Addnum2(50);
    a.Addnum2(20);
    a.Addnum2(71);
    a.Addnum2(35);
    a.Addnum2(33);
    a.Addnum2(89);
    a.Addnum2(10);
    a.Display(4);
}

void Qianxu(Node* p)
{
    cout << p->Getvalue() << " ";
    if (p->Getleftnode() != NULL)
        Qianxu(p->Getleftnode());
    if (p->Getrightnode() != NULL)
        Qianxu(p->Getrightnode());
}

void Zhongxu(Node* p)
{
    if (p->Getleftnode() != NULL)
        Zhongxu(p->Getleftnode());
    cout << p->Getvalue() << " ";
    if (p->Getrightnode() != NULL)
        Zhongxu(p->Getrightnode());
}

void Houxu(Node* p)
{
    if (p->Getleftnode() != NULL)
        Houxu(p->Getleftnode());
    if (p->Getrightnode() != NULL)
        Houxu(p->Getrightnode());
    cout << p->Getvalue() << " ";
}

平衡二叉树

平衡二叉树：数据结构-浙江大学哔哩哔哩bilibili
平衡二叉树和二叉搜索树都基于二叉树“左大右小”的规则，平衡二叉树的高度可以达到O(log2n)。
平衡二叉树的不完全代码如下（平衡二叉树的调整部分还没写完）：

#include<iostream>
#include<cmath>
using namespace std;


class Node
{
private:
    double value;
    Node* leftnode;
    Node* rightnode;
    int leftheight;
    int rightheight;
public:
    Node()
    {
        value = 0;
        leftnode = NULL;
        rightnode = NULL;
        leftheight = 0;
        rightheight = 0;
    }
    double Getvalue() { return this->value; }
    int Getleftheight() { return leftheight; }
    int Getrightheight() { return rightheight; }
    Node* Getleftnode() { return this->leftnode; }
    Node* Getrightnode() { return this->rightnode; }
    void Setvalue(double num) { value = num; }
    void Setleftnode(Node* a) { leftnode = a; }
    void Setrightnode(Node* a) { rightnode = a; }
    void Setleftheight(int a) { leftheight = a; }
    void Setrightheight(int a) { rightheight = a; }
    ~Node()
    {
        delete leftnode;
        delete rightnode;
    }
};

void Qianxu(Node* p);
void Zhongxu(Node* p);
void Houxu(Node* p);
void AVL(Node* p);
int Setheight(Node* p);
Node* Checks(Node* p,Node* temp);

class Tree
{
public:
    Node* root;
    Tree()
    {
        root = NULL;
    }
    void Addnum(double num, int layer, int pos)
    {
        Node* p = root;
        int count = 1;
        double thresh = pow(2, layer - 2);
        if (layer == 1 && pos == 1 && root == NULL)
        {
            root = new Node;
            root->Setvalue(num);
            return;
        }
        while (count != layer - 1)
        {
            count++;
            if (pos > thresh)
            {
                thresh = thresh + pow(2, layer - 3);
                p = p->Getrightnode();
            }
            else
            {
                thresh = thresh - pow(2, layer - 3);
                p = p->Getleftnode();
            }
        }
        if (pos % 2 == 1)
        {
            p->Setleftnode(new Node);
            p = p->Getleftnode();
            p->Setvalue(num);
            return;
        }
        else
        {
            p->Setrightnode(new Node);
            p = p->Getrightnode();
            p->Setvalue(num);
            return;
        }
    }
    void Addnum2(double num)
    {
        if (root == NULL)
        {
            root = new Node;
            root->Setvalue(num);
            return;
        }
        Node* p = root;
        int temp;
        while (true)
        {
            temp = p->Getvalue();
            if (num > temp && p->Getrightnode() == NULL)
            {
                p->Setrightnode(new Node);
                p = p->Getrightnode();
                p->Setvalue(num);
                Check(num);
                return;
            }
            else if (num < temp && p->Getleftnode() == NULL)
            {
                p->Setleftnode(new Node);
                p = p->Getleftnode();
                p->Setvalue(num);
                Check(num);
                return;
            }
            else if(num > temp)
                p = p->Getrightnode();
            else
                p = p->Getleftnode();
        }
    }
    void Cengxu()
    {
        Node* temp[20];
        if (this->root == NULL) return;
        else
        {
            int endsok = 0;
            temp[0] = root;
            while (endsok != -1)
            {
                cout << temp[0]->Getvalue() << " ";
                if (temp[0]->Getleftnode() != NULL)
                    temp[++endsok] = temp[0]->Getleftnode();
                if (temp[0]->Getrightnode() != NULL)
                    temp[++endsok] = temp[0]->Getrightnode();
                for (int i = 1; i <= endsok; i++)
                    temp[i - 1] = temp[i];
                endsok--;

            }
        }
    }
    void Display(int way)
    {
        if (way == 1)
            Qianxu(root);
        else if (way == 2)
            Zhongxu(root);
        else if (way == 3)
            Houxu(root);
        else if (way == 4)
            Cengxu();
        else
            AVL(root);
    }
    void Check(double addnum)
    {
        int temp = Setheight(root);
        Display(5);
        cout << endl;
        Node* p = root;
        Node* tem = NULL;
        if (p->Getleftnode() != NULL)
            tem = Checks(p->Getleftnode(),tem);
        if (p->Getrightnode() != NULL)
            tem = Checks(p->Getrightnode(),tem);
        if (tem == NULL) return;
        else
        {
            cout << "不平衡！" << endl;
            Node* a = NULL;
            if (tem->Getvalue() < addnum)
            {
                if ((tem->Getrightnode())->Getvalue() < addnum)
                {
                    a = tem;
                    tem = tem->Getrightnode();
                    if (a != tem)
                        cout << "1" << endl;
                    tem->Setleftnode(a);
                    a->Setrightnode(NULL);
                }
                else
                {
                    a = tem;
                    tem = (tem->Getrightnode())->Getleftnode();
                    tem->Setleftnode(a);
                    //tem->Setrightnode(a->)
                }
            }
            else
            {
                if ((tem->Getrightnode())->Getvalue() < addnum)
                {
                    a = tem;
                    root->Setrightnode(tem->Getrightnode());
                    (root->Getrightnode())->Setleftnode(a);
                    a->Setrightnode(NULL);
                }
                else
                {
                    a = tem;
                    tem = (tem->Getrightnode())->Getleftnode();
                    (tem->Getrightnode())->Getleftnode()->Setleftnode(a);
                    (tem->Getrightnode())->Getleftnode()->Setrightnode(a->Getrightnode());
                }
            }
        }
    }
    ~Tree() { delete root; }
};

int Setheight(Node* p)
{
    Node* temp;
    Node* temp2;
    if (p == NULL)
    {
        return 0;
    }
    if (p->Getleftnode() == NULL && p->Getrightnode() == NULL)
    {
        p->Setleftheight(1);
        p->Setrightheight(1);
    }
    else if (p->Getleftnode() != NULL && p->Getrightnode() == NULL)
    {
        p->Setrightheight(0);
        temp = p->Getleftnode();
        p->Setleftheight(max(Setheight(temp->Getleftnode()), Setheight(temp->Getrightnode())) + 1);
    }
    else if (p->Getleftnode() == NULL && p->Getrightnode() != NULL)
    {
        p->Setleftheight(0);
        temp2 = p->Getrightnode();
        p->Setrightheight(max(Setheight(temp2->Getleftnode()), Setheight(temp2->Getrightnode())) + 1);
        //cout << "右" << p->Getrightheight() << " ";
    }
    else
    {
        temp = p->Getleftnode();
        p->Setleftheight(max(Setheight(temp->Getleftnode()), Setheight(temp->Getrightnode())) + 1);
        //cout << "左" << p->Getleftheight() << " ";
        temp2 = p->Getrightnode();
        p->Setrightheight(max(Setheight(temp2->Getleftnode()), Setheight(temp2->Getrightnode())) + 1);
        //cout << "右" << p->Getrightheight() << " ";
    }


    return max(p->Getleftheight(), p->Getrightheight());
}

int main()
{
    Tree a;
    //a.Addnum(5, 1, 1);
    //a.Addnum(3, 2, 1);
    //a.Addnum(2, 2, 2);
    //a.Addnum(7, 3, 1);
    //a.Addnum(1, 3, 2);
    //a.Addnum(10, 3, 3);
    //a.Addnum(109, 3, 4);
    //a.Addnum(14, 4, 2);
    a.Addnum2(50);
    a.Addnum2(20);
    a.Addnum2(71);
    a.Addnum2(10);
    a.Addnum2(35);
    a.Addnum2(89);
    a.Addnum2(33);
    a.Addnum2(100);
    a.Display(5);
}

void Qianxu(Node* p)
{
    cout << p->Getvalue()<< " ";
    if (p->Getleftnode() != NULL)
        Qianxu(p->Getleftnode());
    if (p->Getrightnode() != NULL)
        Qianxu(p->Getrightnode());
}

void Zhongxu(Node* p)
{
    if (p->Getleftnode() != NULL)
        Zhongxu(p->Getleftnode());
    cout << p->Getvalue() << " ";
    if (p->Getrightnode() != NULL)
        Zhongxu(p->Getrightnode());
}

void Houxu(Node* p)
{
    if (p->Getleftnode() != NULL)
        Houxu(p->Getleftnode());
    if (p->Getrightnode() != NULL)
        Houxu(p->Getrightnode());
    cout << p->Getvalue() << " ";
}

void AVL(Node* p)
{
    int temp = Setheight(p);
    //cout <<"左"<< p->Getleftheight() <<"右"<< p->Getrightheight() << " ";
    cout << p->Getleftheight() - p->Getrightheight() << " ";
    if (p->Getleftnode() != NULL)
        AVL(p->Getleftnode());
    if (p->Getrightnode() != NULL)
        AVL(p->Getrightnode());
}

Node* Checks(Node* p,Node* temp)
{
    //cout <<"左"<< p->Getleftheight() <<"右"<< p->Getrightheight() << " ";
    if (temp != NULL)
        return temp;
    if (p->Getleftheight() - p->Getrightheight() == -2)
        return p;
    if (p->Getleftheight() - p->Getrightheight() == 2)
        return p;
    if (p->Getleftnode() != NULL)
        temp = Checks(p->Getleftnode(),temp);
    if (p->Getrightnode() != NULL)
        temp = Checks(p->Getrightnode(),temp);
    return temp;
}

堆在下面“算法”的堆排序中有提及：堆排序。
集合：与数组和树有关，主要是并查集：

图

图(邻接矩阵实现+必要算法)：(134条消息) 【C++】图(邻接矩阵实现+必要算法)taoxing-CSDN博客邻接矩阵的实现
图的表示方法有很多：

当图为稠密图或者完全图或有向图时，用邻接矩阵
当矩阵为稀疏矩阵时，用邻接表

所以图也可以由前面提及的数据结构来表示，代码如下：

#include<iostream>
#include<cmath>
using namespace std;

class Node{
public:
    Node(int val){
        value=val;
        in=0;
        out=0;
        }
    int value;
    int in; //入度,有多少个边指向此结点
    int out;    //出度，有多少条边由此结点发散
    list<Node*> nexts;  //此结点是from的情况下，邻居结点
    list<Edge*> edges;  //从此结点出发，发散出边的集合

};

class Edge
{
public:
    int weight;
    Node* from;
    Node* to;
    Edge(); 
    Edge(int _weight,Node* _from,Node* _to)
    {
        weight=_weight;
        from=_from;
        to=_to; 
    }   
};

class Graph{
public:
    map<int,Node*> nodes;// 点序号和结点的映射集合
    set<Edge*> edges;   //边的集合

};

Graph* CreateGraph(int matrix[][3],int n)   //n表示边数 即matrix.size()
{ 
    Graph* graph=new Graph;
    for(int i=0;i!=n;i++)
    {
        int weight=matrix[i][0];
        int from=matrix[i][1];
        int to=matrix[i][2];
        if(graph->nodes.find(from)==graph->nodes.end()) 
        {
            graph->nodes[from]=new Node(from);
        }   

        if(graph->nodes.find(to)==graph->nodes.end())   
        {
            graph->nodes[to]=new Node(to);
        }   

        Node* fromnode=graph->nodes[from];
        Node* tonode=graph->nodes[to];

        Edge* newedge=new Edge(weight,fromnode,tonode);
        fromnode->nexts.push_back(tonode);
        fromnode->out++;
        fromnode->edges.push_back(newedge);

        tonode->in++;

        graph->edges.insert(newedge);   

    }
    return graph;
}

图的BFS与DFS：(134条消息) C++DFS与BFS实现炼狱之行的博客-CSDN博客c++dfs
图的广度优先遍历BFS（用队列辅助）：

利用队列实现
从源节点开始依次按照宽度进队列，然后弹出
每弹出一个点，把该点邻接点中没有进过队列的放队列中
直到队列边空（与树的层序遍历相似）

代码如下：

//宽度(广度)优先遍历
void bfs(Node* node)
{
    if(node==NULL)
    {
        return;
    }   
    deque<Node*>    deq;
    set<Node*> set;

    deq.push_back(node);
    set.insert(node);
    while(deq.size()!=0)
    {   
        Node* cur=deq.front();  //保存deq队列首元
        deq.pop_front();//出队列打印
        cout<<cur->value<<" ";
        for(Node* next:cur->nexts)
        {
            if(set.find(next)==set.end())
            {               
                deq.push_back(next);
                set.insert(next);
            }
        }   
    }
    cout<<endl;
}

图的深度优先搜索DFS则主要使用递归，代码如下（与前序遍历类似）：

#include <iostream>

#define N 5
using namespace std;

int maze[N][N] = {
    { 0, 1, 1, 0, 0 },
    { 0, 0, 1, 0, 1 },
    { 0, 0, 1, 0, 0 },
    { 1, 1, 0, 0, 1 },
    { 0, 0, 1, 0, 0 }
};
int visited[N + 1] = { 0, };

void DFS(int start)
{
    visited[start] = 1;
    for (int i = 1; i <= N; i++) {
        if (!visited[i] && maze[start - 1][i - 1] == 1)
            DFS(i);
    }
    cout << start << " ";
}

int main()
{
    for (int i = 1; i <= N; i++) {
        if (visited[i] == 1)
            continue;
        DFS(i);
    }
    system("pause");

    return 0;
}

算法Algorithm

递归	排序	二分查找	搜索	哈希
贪心	分治	回溯	动态规划	字符串匹配

算法主要问题有递归、回溯、贪心、二分查找、排序等，下面是其中几个算法的实现，后续会继续更新：

在线处理

这类方法最大的特点就是可以读入一个数据就处理一个数据，例如找最大值找最小值等，这类方法的算法复杂度是 CS专题——浙大数据结构C 实现 - 图4 。

双指针

这类方法最大的特点是需要从一个给定的序列中得到一个满足条件的子序列，或者需要以某种规则来遍历这个序列，算法复杂度也是 CS专题——浙大数据结构C 实现 - 图5 （而且这列方法常常可以搭配其他的排序算法如堆排序等一起使用）。

Dijkstra最短路算法

链路状态算法，常用的最短路算法，C++代码如下：

#include<iostream>
#include<cmath>
using namespace std;

int dist[6][6] = {
    {100,3,2,5,-1,-1},
    {3,100,-1,1,4,-1},
    {2,-1,100,2,-1,1},
    {5,2,2,100,3,-1},
    {-1,4,-1,3,100,2},
    {-1,-1,1,-1,2,100}
};

class answer
{
public:
    int* answer1;
    int* distance;
    int size;
    answer(int total = 6)
    {
        answer1 = new int[total];
        distance = new int[total];
        size = total;
        for (int i = 0; i < total; i++)
            answer1[i] = distance[i] = 0;
    }
    void display()
    {
        for (int i = 0; i < size; i++)
            cout << answer1[i] << " ";
        cout << endl;
        for (int i = 0; i < size; i++)
            cout << distance[i] << " ";
        cout << endl;
    }
};

int findmin(int* input, int* input2, int size)
{
    int temp = 0;
    int thresh = 0;
    bool on = false;
    for (int i = 0; i < size; i++)
    {
        if (on == false && input[i] > 0 && input2[i] != 1)
        {
            temp = i;
            thresh = input[i];
            on = true;
            continue;
        }
        if (input[i] > 0 && input2[i] != 1 && input[i] < thresh)
        {
            thresh = input[i];
            temp = i;
        }   
    }
    return temp;
}

answer Dijkstra(int total,int point)
{
    int *temp;
    int num = 0;
    temp = new int[total];
    answer a(total);
    for (int i = 0; i < total; i++)
        temp[i] = 0;

    temp[point - 1] = 1;
    a.answer1[point - 1] = point;
    int count = 1;

    for (int i = 0; i < total; i++)
    {
        a.distance[i] = dist[point - 1][i];
        if (a.distance[i] == -1)
        {
            a.distance[i] = 100;
            a.answer1[i] = i + 1;
        }
        else
            a.answer1[i] = point;
    }

    while (count != total)
    {
        num = findmin(a.distance,temp, total);
        temp[num] = 1;
        count++;

        for (int i = 0; i < total; i++)
        {
            if (temp[i] != 1)
            {
                for (int j = 0; j < total; j++)
                {
                    if (i !=j && temp[j] == 1 && dist[i][j] != -1 && dist[i][j] != 100 && (dist[i][j] + a.distance[j] < a.distance[i]))
                    {
                        a.distance[i] = dist[i][j] + a.distance[j];
                        a.answer1[i] = j + 1;
                    }
                }
            }
        }
    }
    a.distance[point - 1] = 0;
    return a;
}

int main()
{
    answer ans;
    ans = Dijkstra(6, 2);
    ans.display();
}

Python代码如下：

import numpy as np

NODES_NUM = 9
DISTANCE_MATRIX = np.array([[0,4,0,0,0,0,0,8,0],
                            [4,0,8,0,0,0,0,3,0],
                            [0,8,0,7,0,4,0,0,2],
                            [0,0,7,0,9,14,0,0,0],
                            [0,0,0,9,0,10,0,0,0],
                            [0,0,4,14,10,0,2,0,0],
                            [0,0,0,0,0,2,0,6,6],
                            [8,3,0,0,0,0,6,0,1],
                            [0,0,2,0,0,0,6,1,0]])

VISITED = np.ones(9)
DISTANCE_TOTAL = np.array([0,100,100,100,100,100,100,100,100])
PARENT = np.array([-1,-1,-1,-1,-1,-1,-1,-1,-1])

#先选取一个起点
parent_now = 0
#实现连接点路径覆盖并在未选过的点集合中选取距离最小的点作为新的起点
#直至遍历所有点（所有点都做过起点）
while (sum(VISITED) != 0):
    VISITED[parent_now] = 0
    source = DISTANCE_TOTAL[parent_now]
    for i in range(NODES_NUM):
        if DISTANCE_MATRIX[parent_now][i] != 0 and VISITED[i] != 0:
            if ((source + DISTANCE_MATRIX[parent_now][i]) < DISTANCE_TOTAL[i]):
                DISTANCE_TOTAL[i] = source + DISTANCE_MATRIX[parent_now][i]
                PARENT[i] = parent_now
            else:
                pass
            temp = []
            sequence = []
            for i in range(NODES_NUM):
                if VISITED[i] != 0:
                    temp.append(DISTANCE_TOTAL[i])
                    sequence.append(i)
                    if len(temp) != 0:
                        index = np.argmin(temp)
                        parent_now = sequence[index]
                        print(DISTANCE_TOTAL)

print('所找到的最短路径长度为:',np.max(DISTANCE_TOTAL))

Floyd-Warshall最短路算法

Floyd-Warshall最短路算法是数模中应用极广的一种算法，可求出任意两点间最短路径距离，很好编写代码。
Floyd-Warshall最短路算法Python实现如下：

import numpy as np

NODES_NUM = 9
DISTANCE_MATRIX = np.array([[60,4,60,60,60,60,60,8,60],
                            [4,60,8,60,60,60,60,3,60],
                            [60,8,60,7,60,4,60,60,2],
                            [60,60,7,60,9,14,60,60,60],
                            [60,60,60,9,60,10,60,60,60],
                            [60,60,4,14,10,60,2,60,60],
                            [60,60,60,60,60,2,60,6,6],
                            [8,3,60,60,60,60,6,60,1],
                            [60,60,2,60,60,60,6,1,60]])

#暴力遍历，根据最短路的子路径也为最短路的法则
for k in range(NODES_NUM):
    for i in range(NODES_NUM):
        for j in range(NODES_NUM):
            DISTANCE_MATRIX[i][j] = min(DISTANCE_MATRIX[i][j],DISTANCE_MATRIX[i][k]+DISTANCE_MATRIX[k][j])

#将所有点到自身的距离修改为0
for i in range(NODES_NUM):
    DISTANCE_MATRIX[i][i] = 0
print(DISTANCE_MATRIX)

Prim算法

#include<iostream>
#include<cmath>
using namespace std;

class MatrixUDG {
    #define MAX    100
    #define INF    (~(0x1<<31))        // 无穷大(即0X7FFFFFFF)
    private:
    char mVexs[MAX];    // 顶点集合
    int mVexNum;             // 顶点数
    int mEdgNum;             // 边数
    int mMatrix[MAX][MAX];   // 邻接矩阵

    public:
    // 创建图(自己输入数据)
    MatrixUDG();
    // 创建图(用已提供的矩阵)
    //MatrixUDG(char vexs[], int vlen, char edges[][2], int elen);
    MatrixUDG(char vexs[], int vlen, int matrix[][9]);
    ~MatrixUDG();

    // 深度优先搜索遍历图
    void DFS();
    // 广度优先搜索（类似于树的层次遍历）
    void BFS();
    // prim最小生成树(从start开始生成最小生成树)
    void prim(int start);
    // 打印矩阵队列图
    void print();

    private:
    // 读取一个输入字符
    char readChar();
    // 返回ch在mMatrix矩阵中的位置
    int getPosition(char ch);
    // 返回顶点v的第一个邻接顶点的索引，失败则返回-1
    int firstVertex(int v);
    // 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1
    int nextVertex(int v, int w);
    // 深度优先搜索遍历图的递归实现
    void DFS(int i, int *visited);

};

/*
* prim最小生成树
*
* 参数说明：
*   start -- 从图中的第start个元素开始，生成最小树
*/
void MatrixUDG::prim(int start)
{
    int min,i,j,k,m,n,sum;
    int index=0;         // prim最小树的索引，即prims数组的索引
    char prims[MAX];     // prim最小树的结果数组
    int weights[MAX];    // 顶点间边的权值

    // prim最小生成树中第一个数是"图中第start个顶点"，因为是从start开始的。
    prims[index++] = mVexs[start];

    // 初始化"顶点的权值数组"，
    // 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。
    for (i = 0; i < mVexNum; i++ )
        weights[i] = mMatrix[start][i];
    // 将第start个顶点的权值初始化为0。
    // 可以理解为"第start个顶点到它自身的距离为0"。
    weights[start] = 0;

    for (i = 0; i < mVexNum; i++)
    {
        // 由于从start开始的，因此不需要再对第start个顶点进行处理。
        if(start == i)
            continue;

        j = 0;
        k = 0;
        min = INF;
        // 在未被加入到最小生成树的顶点中，找出权值最小的顶点。
        while (j < mVexNum)
        {
            // 若weights[j]=0，意味着"第j个节点已经被排序过"(或者说已经加入了最小生成树中)。
            if (weights[j] != 0 && weights[j] < min)
            {
                min = weights[j];
                k = j;
            }
            j++;
        }

        // 经过上面的处理后，在未被加入到最小生成树的顶点中，权值最小的顶点是第k个顶点。
        // 将第k个顶点加入到最小生成树的结果数组中
        prims[index++] = mVexs[k];
        // 将"第k个顶点的权值"标记为0，意味着第k个顶点已经排序过了(或者说已经加入了最小树结果中)。
        weights[k] = 0;
        // 当第k个顶点被加入到最小生成树的结果数组中之后，更新其它顶点的权值。
        for (j = 0 ; j < mVexNum; j++)
        {
            // 当第j个节点没有被处理，并且需要更新时才被更新。
            if (weights[j] != 0 && mMatrix[k][j] < weights[j])
                weights[j] = mMatrix[k][j];
        }
    }

    // 计算最小生成树的权值
    sum = 0;
    for (i = 1; i < index; i++)
    {
        min = INF;
        // 获取prims[i]在mMatrix中的位置
        n = getPosition(prims[i]);
        // 在vexs[0...i]中，找出到j的权值最小的顶点。
        for (j = 0; j < i; j++)
        {
            m = getPosition(prims[j]);
            if (mMatrix[m][n]<min)
                min = mMatrix[m][n];
        }
        sum += min;
    }
    // 打印最小生成树
    cout << "PRIM(" << mVexs[start] << ")=" << sum << ": ";
    for (i = 0; i < index; i++)
        cout << prims[i] << " ";
    cout << endl;
}

Kruscal算法

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct edge
{
    int u, v;
    int weight;
};
vector<int> father; //记录每个节点的父亲
vector<int> result; //存储最后获得的各条边

bool compare(edge a, edge b)
{
    return a.weight < b.weight;
}

int findfather(int a)
{
    while (a != father[a])
    {
        a = father[a];
    }
    return a;
}
void kruskal(int n, vector<edge> Edge)
{
    father.resize(n);
    sort(Edge.begin(), Edge.end(), compare);
    for (int i = 0; i < n; ++i)
    {
        father[i] = i;
    }
    for (int i = 0; i < Edge.size() && result.size() < n-1; ++i)
    {
        int u = Edge[i].u;
        int v = Edge[i].v;
        if (findfather(u) != findfather(v)) //判断父节点是否相同
        {
            result.push_back(Edge[i].weight);
            father[findfather(u)] = father[findfather(v)]; //将两点并入一个集合中
        }
    }
    if (result.size() != n - 1)
    {
        cout <<  result.size()  << "该图不连通" << endl;
        return;
    }
    else
    {
        cout << "最小生成树的各边如下：" << endl;
        for (int i = 0; i < result.size(); ++i)
        {
            cout << result[i] << endl;
        }
    }
}

int main()
{
    int n, m;
    cout << "输入结点数：";
    cin >> n;
    cout << "输入边数：";
    cin >> m;
    vector<edge> Edge(m);
    cout << "输入各条边的信息：" << endl;
    for (int i = 0; i < m; ++i)
    {
        cin >> Edge[i].u >> Edge[i].v >> Edge[i].weight;
    }
    kruskal(n,Edge);
    return 0;
}

二分查找

在树的建立中有使用：树，代码略，视频链接：数据结构-浙江大学哔哩哔哩bilibili

树的四种遍历算法

树的遍历可以分为前序、中序、后序和层序遍历（队列queue辅助实现）。
具体实现可以和上面的树的类定义结合来看，代码如下：

void Qianxu(Node* p)
{
    cout << p->Getvalue() << " ";
    if (p->Getleftnode() != NULL)
        Qianxu(p->Getleftnode());
    if (p->Getrightnode() != NULL)
        Qianxu(p->Getrightnode());
}

void Zhongxu(Node* p)
{
    if (p->Getleftnode() != NULL)
        Zhongxu(p->Getleftnode());
    cout << p->Getvalue() << " ";
    if (p->Getrightnode() != NULL)
        Zhongxu(p->Getrightnode());
}

void Houxu(Node* p)
{
    if (p->Getleftnode() != NULL)
        Houxu(p->Getleftnode());
    if (p->Getrightnode() != NULL)
        Houxu(p->Getrightnode());
    cout << p->Getvalue() << " ";
}

//层序遍历函数要放在tree类内
void Cengxu()
    {
        Node* temp[20];
        if (this->root == NULL) return;
        else
        {
            int endsok = 0;
            temp[0] = root;
            while (endsok != -1)
            {
                cout << temp[0]->Getvalue() << " ";
                if (temp[0]->Getleftnode() != NULL)
                    temp[++endsok] = temp[0]->Getleftnode();
                if (temp[0]->Getrightnode() != NULL)
                    temp[++endsok] = temp[0]->Getrightnode();
                for (int i = 1; i <= endsok; i++)
                    temp[i - 1] = temp[i];
                endsok--;

            }
        }
    }

冒泡排序

最简单的排序方法，时间复杂度O(n平方)，代码如下：

#include<iostream>
#include<cmath>
using namespace std;

void Maopao(int* series)
{
    bool finish = false;
    int temp = 0;
    while (finish != true)
    {
        finish = true;
        for (int i = 0; i < 7; i++)
        {
            for (int j = i; j < 7; j++)
            {
                if (series[j] > series[j+1])
                {
                    temp = series[j];
                    series[j] = series[j + 1];
                    series[j + 1] = temp;
                    finish = false;
                }
            }
        }
    }
}

int main()
{
    int a[8] = { 4,7,8,2,5,1,3,6 };
    for (int i = 0; i < 8; i++)
        cout << a[i] << " ";
    cout << endl;
    Maopao(a);
    for (int i = 0; i < 8; i++)
        cout << a[i] << " ";
}

插入排序

时间复杂度O(n平方)，与冒泡排序一样，代码如下：

#include<iostream>
#include<cmath>
using namespace std;

void Charu(int* series)
{
    int temp = 0;
    int last = 0;
    for (int p = 1; p < 8; p++)
    {
        temp = series[p];
        last = p;
        for (int i = p; i > 0; i--)
        {
            if (series[i - 1] > temp)
            {
                series[i] = series[i - 1];
                last = i - 1;
            }
        }
        series[last] = temp;
    }
}

int main()
{
    int a[8] = { 4,7,8,2,5,1,3,6 };
    for (int i = 0; i < 8; i++)
        cout << a[i] << " ";
    cout << endl;
    Charu(a);
    for (int i = 0; i < 8; i++)
        cout << a[i] << " ";
}

希尔排序

了解一下常用的两种增量序列——Hibbard增量序列和Sedgewick增量序列。
希尔排序的时间复杂度最差为O(n1.5方)，平均为O(n1.25方)，代码如下：

#include<iostream>
#include<cmath>
using namespace std;

void HillSort(int* series)
{
    int temp = 0;
    int last = 0;

    for (int j = 0; j < 5; j++)
    {
        for (int p = 1; p < 3; p++)
        {
            temp = series[p * 5 + j];
            last = p * 5 + j;
            for (int i = p; i > 0; i--)
            {
                if (series[5 * (i - 1) + j] > temp)
                {
                    series[5 * i + j] = series[5 * (i - 1) + j];
                    last = 5 * (i - 1) + j;
                }
            }
            series[last] = temp;
        }
    }

    for (int j = 0; j < 3; j++)
    {
        for (int p = 1; p < 5; p++)
        {
            temp = series[p * 3 + j];
            last = p * 3 + j;
            for (int i = p; i > 0; i--)
            {
                if (series[3 * (i - 1) + j] > temp)
                {
                    series[3 * i + j] = series[3 * (i - 1) + j];
                    last = 3 * (i - 1) + j;
                }
            }
            series[last] = temp;
        }
    }

    for (int p = 1; p < 15; p++)
    {
        temp = series[p];
        last = p;
        for (int i = p; i > 0; i--)
        {
            if (series[i - 1] > temp)
            {
                series[i] = series[i - 1];
                last = i - 1;
            }
        }
        series[last] = temp;
    }
}

int main()
{
    int a[15] = { 14,7,8,12,5,1,13,6,2,3,4,11,10,15,9 };
    for (int i = 0; i < 15; i++)
        cout << a[i] << " ";
    cout << endl;
    HillSort(a);
    for (int i = 0; i < 15; i++)
        cout << a[i] << " ";
}

选择排序

时间复杂度O(n平方)，与冒泡排序一样，代码如下：

#include<iostream>
#include<cmath>
using namespace std;

int scanmaxpos(int* series, int size)
{
    int thresh = series[0];
    int a = 0;
    for (int j = 1; j < size; j++)
    {
        if (series[j] > thresh)
        {
            thresh = series[j];
            a = j;
        }
    }
    return a;
}

void ChooseSort(int* series)
{
    int maxpos = 0;
    int temp = 0;
    for (int i = 0; i < 14; i++)
    {
        maxpos = scanmaxpos(series, 15 - i);
        temp = series[14 - i];
        series[14 - i] = series[maxpos];
        series[maxpos] = temp;
    }
}

int main()
{
    int a[15] = { 14,7,8,12,5,1,13,6,2,3,4,11,10,15,9 };
    for (int i = 0; i < 15; i++)
        cout << a[i] << " ";
    cout << endl;
    ChooseSort(a);
    for (int i = 0; i < 15; i++)
        cout << a[i] << " ";
}

堆排序

基于堆的排序，在了解堆排序前建议先了解堆：

堆本质上是一种树
堆的实现和建立
完全二叉树/最大堆/最小堆
堆的插入和删除

时间复杂度O(nlogn)，本质上就是根据所给序列构建最大堆，然后每次从构建的最大堆中弹出最大或最小值，完整代码如下（只有构建最大堆的代码，省略了排序代码）：

#include<iostream>
#include<cmath>
using namespace std;

int findmin(int a);
int scanmaxpos(int* series, int size);

class Node
{
private:
    double value;
    Node* leftnode;
    Node* rightnode;
public:
    Node()
    {
        value = 0;
        leftnode = NULL;
        rightnode = NULL;
    }
    double Getvalue() { return this->value; }
    Node* Getleftnode() { return this->leftnode; }
    Node* Getrightnode() { return this->rightnode; }
    void Setvalue(double num) { value = num; }
    void Setleftnode(Node* a) { leftnode = a; }
    void Setrightnode(Node* a) { rightnode = a; }
};

void Qianxu(Node* p);
void Zhongxu(Node* p);
void Houxu(Node* p);

class Tree
{
public:
    Node* root;
    Tree()
    {
        root = NULL;
    }
    void Addnum(double num, int layer, int pos)
    {
        Node* p = root;
        int count = 1;
        double thresh = pow(2, layer - 2);
        if (layer == 1 && pos == 1 && root == NULL)
        {
            root = new Node;
            root->Setvalue(num);
            return;
        }
        while (count != layer - 1)
        {
            count++;
            if (pos > thresh)
            {
                thresh = thresh + pow(2, layer - 3);
                p = p->Getrightnode();
            }
            else
            {
                thresh = thresh - pow(2, layer - 3);
                p = p->Getleftnode();
            }
        }
        if (pos % 2 == 1)
        {
            p->Setleftnode(new Node);
            p = p->Getleftnode();
            p->Setvalue(num);
            return;
        }
        else
        {
            p->Setrightnode(new Node);
            p = p->Getrightnode();
            p->Setvalue(num);
            return;
        }
    }
    Node* findpoint(int point)
    {
        int layer, pos;
        layer = findmin(point) + 1;
        pos = point - (int)pow(2, layer - 1) + 1;
        Node* p = root;
        int count = 1;
        double thresh = pow(2, layer - 2);
        if (layer == 1 && pos == 1)
        {
            return root;
        }
        while (count != layer - 1)
        {
            count++;
            if (pos > thresh)
            {
                thresh = thresh + pow(2, layer - 3);
                p = p->Getrightnode();
            }
            else
            {
                thresh = thresh - pow(2, layer - 3);
                p = p->Getleftnode();
            }
        }
        if (pos % 2 == 1)
        {
            p = p->Getleftnode();
            //cout << p->Getvalue() << endl;
            return p;
        }
        else
        {
            p = p->Getrightnode();
            //cout << p->Getvalue() << endl;
            return p;
        }
    }
    void chengdui(Node* input,int a)
    {
        //cout << a;
        int series[3];
        int max = 0;
        int temp = 0;
        if ((input->Getleftnode()) == NULL && (input->Getrightnode()) == NULL) return;
        Node* lnode = input->Getleftnode();
        Node* rnode = input->Getrightnode();
        series[0] = input->Getvalue();
        if ((input->Getleftnode()) == NULL)
            series[1] = 0;
        else
            series[1] = lnode->Getvalue();
        if ((input->Getrightnode()) == NULL)
            series[2] = 0;
        else
            series[2] = rnode->Getvalue();
        max = scanmaxpos(series, 3);
        if (max == 0)
        {
            return;
        }
        else if (max == 1)
        {
            temp = input->Getvalue();
            input->Setvalue(lnode->Getvalue());
            lnode->Setvalue(temp);
            cout << "左大！" << endl;
            chengdui(findpoint(2*a),2*a);
        }
        else
        {
            temp = input->Getvalue();
            input->Setvalue(rnode->Getvalue());
            rnode->Setvalue(temp);
            cout << "右大！" << endl;
            chengdui(findpoint(2 * a + 1), 2 * a + 1);
        }
    }
    void Display(int way)
    {
        if (way == 1)
            Qianxu(root);
        else if (way == 2)
            Zhongxu(root);
        else
            Houxu(root);
    }
};

int findmin(int a)
{
    int temp = 0;
    if (a == 1) return 0;
    while (pow(2,temp) <= a)
    {
        temp++;
    }
    return temp - 1;
}

Tree BuildHeap(int* a, int size)
{
    Tree tree;
    int temp1;
    double temp2;
    for (int i = 0; i < size; i++)
    {
        temp1 = findmin(i + 1) + 1;
        temp2 = i - pow(2, temp1 - 1) + 2;
        cout << temp1 << " " << temp2 << " " << endl;
        tree.Addnum((double)a[i], temp1, (int)temp2);
    }
    tree.Display(1);
    cout << endl;
    int lastnode = size / 2;
    for (int i = lastnode; i >= 0; i--)
    {
        tree.chengdui(tree.findpoint(i + 1), i + 1);
    }
    tree.Display(1);
    return tree;
}

int scanmaxpos(int* series, int size)
{
    int thresh = series[0];
    int a = 0;
    for (int j = 1; j < size; j++)
    {
        if (series[j] > thresh)
        {
            thresh = series[j];
            a = j;
        }
    }
    return a;
}


int main()
{
    int a[15] = { 14,7,8,12,5,1,13,6,2,3,4,11,10,15,9 };
    BuildHeap(a, 15);
}


void Qianxu(Node* p)
{
    cout << p->Getvalue() << " ";
    if (p->Getleftnode() != NULL)
        Qianxu(p->Getleftnode());
    if (p->Getrightnode() != NULL)
        Qianxu(p->Getrightnode());
}

void Zhongxu(Node* p)
{
    if (p->Getleftnode() != NULL)
        Zhongxu(p->Getleftnode());
    cout << p->Getvalue() << " ";
    if (p->Getrightnode() != NULL)
        Zhongxu(p->Getrightnode());
}

void Houxu(Node* p)
{
    if (p->Getleftnode() != NULL)
        Houxu(p->Getleftnode());
    if (p->Getrightnode() != NULL)
        Houxu(p->Getrightnode());
    cout << p->Getvalue() << " ";
}

归并排序

递归算法+有序子列的归并，视频：数据结构-浙江大学哔哩哔哩bilibili
利用到递归思想的归并排序，代码如下：

#include<iostream>
#include<cmath>
using namespace std;

void Merge(int* a,int size,int start)
{
    if (size == 2)
    {
        int tp;
        if (a[start] > a[start + 1])
        {
            tp = a[start + 1];
            a[start + 1] = a[start];
            a[start] = tp;
        }
    }
    else
    {
        Merge(a, size / 2, start);
        Merge(a, size / 2, start + size / 2);
        int *temp;
        temp = new int[size];
        int start1 = start;
        int start2 = start + size / 2;
        int amtp = start1;
        int bmtp = start2;
        int cmtp = 0;
        while (amtp < start2 && bmtp < start + size)
        {
            if (a[amtp] < a[bmtp]) temp[cmtp++] = a[amtp++];
            else temp[cmtp++] = a[bmtp++];
        }
        while (amtp < start2)
            temp[cmtp++] = a[amtp++];
        while (bmtp < start + size)
            temp[cmtp++] = a[bmtp++];
        for (int i = start1; i < start1 + size; i++)
            a[i] = temp[i - start1];
    }
}

int main()
{
    int a[16] = { 14,7,8,12,5,1,13,6,2,16,3,4,11,10,15,9 };
    Merge(a, 16, 0);
    for (int i = 0; i < 16; i++)
        cout << a[i]<<" ";
}

DFS和BFS

DFS和树的前序遍历类似，而BFS和树的层序遍历类似。
BFS广度优先搜索，代码如下：

#include<iostream>
#include<cmath>
using namespace std;

class Node{
public:
    Node(int val){
        value=val;
        in=0;
        out=0;
        }
    int value;
    int in; //入度,有多少个边指向此结点
    int out;    //出度，有多少条边由此结点发散
    list<Node*> nexts;  //此结点是from的情况下，邻居结点
    list<Edge*> edges;  //从此结点出发，发散出边的集合

};

class Edge
{
public:
    int weight;
    Node* from;
    Node* to;
    Edge(); 
    Edge(int _weight,Node* _from,Node* _to)
    {
        weight=_weight;
        from=_from;
        to=_to; 
    }   
};

class Graph{
public:
    map<int,Node*> nodes;// 点序号和结点的映射集合
    set<Edge*> edges;   //边的集合

};

Graph* CreateGraph(int matrix[][3],int n)   //n表示边数 即matrix.size()
{ 
    Graph* graph=new Graph;
    for(int i=0;i!=n;i++)
    {
        int weight=matrix[i][0];
        int from=matrix[i][1];
        int to=matrix[i][2];
        if(graph->nodes.find(from)==graph->nodes.end()) 
        {
            graph->nodes[from]=new Node(from);
        }   

        if(graph->nodes.find(to)==graph->nodes.end())   
        {
            graph->nodes[to]=new Node(to);
        }   

        Node* fromnode=graph->nodes[from];
        Node* tonode=graph->nodes[to];

        Edge* newedge=new Edge(weight,fromnode,tonode);
        fromnode->nexts.push_back(tonode);
        fromnode->out++;
        fromnode->edges.push_back(newedge);

        tonode->in++;

        graph->edges.insert(newedge);   

    }
    return graph;
}

//宽度(广度)优先遍历
void bfs(Node* node)
{
    if(node==NULL)
    {
        return;
    }   
    deque<Node*>    deq;
    set<Node*> set;

    deq.push_back(node);
    set.insert(node);
    while(deq.size()!=0)
    {   
        Node* cur=deq.front();  //保存deq队列首元
        deq.pop_front();//出队列打印
        cout<<cur->value<<" ";
        for(Node* next:cur->nexts)
        {
            if(set.find(next)==set.end())
            {               
                deq.push_back(next);
                set.insert(next);
            }
        }   
    }
    cout<<endl;
}

DFS深度优先搜索，代码如下：

#include <iostream>

#define N 5
using namespace std;

int maze[N][N] = {
    { 0, 1, 1, 0, 0 },
    { 0, 0, 1, 0, 1 },
    { 0, 0, 1, 0, 0 },
    { 1, 1, 0, 0, 1 },
    { 0, 0, 1, 0, 0 }
};
int visited[N + 1] = { 0, };

void DFS(int start)
{
    visited[start] = 1;
    for (int i = 1; i <= N; i++) {
        if (!visited[i] && maze[start - 1][i - 1] == 1)
            DFS(i);
    }
    cout << start << " ";
}

int main()
{
    for (int i = 1; i <= N; i++) {
        if (visited[i] == 1)
            continue;
        DFS(i);
    }
    system("pause");

    return 0;
}