常用数据结构和算法

一、引言

编写代码时我们经常会用到各种别人造好的轮子，比如比较常用的c++标准库，这里面就涉及到很多基本的数据结构以及算法。例如std::vector，std::array数组，std::list双向链表，std::forward_list单向链表及std::sort排序算法等。这章主要分别介绍常用数据结构的实现和常用算法实现。

二、常用数据结构

2.1、数组

数组比较容易理解，就是一块连续的内存。一个简答的动态数组实现如下：

头文件

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
#ifndef LRVECTOR_H
#define LRVECTOR_H

#include <stddef.h>
template <typename T >
class LRVector
{
public:
    LRVector();
    ~LRVector();

    T &operator[](size_t index) const;

    void push_back(const T &data);

    void resize(size_t size);
    void reserve(size_t size);
    size_t size() const;
    size_t capacity() const;

    void printAll();

private:
    void init();

private:
    size_t m_size;
    size_t m_capacity;

    T *m_pDataArray;
};

#endif // LRVECTOR_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
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 "lrvector.h"

#include <iostream>
#include <vector>
#include <exception>

template <typename T>
LRVector<T>::LRVector():
    m_size(0),
    m_capacity(4)
{
    init();
}

template<typename T>
LRVector<T>::~LRVector()
{
    if (m_pDataArray) {
        delete []m_pDataArray;
        m_pDataArray = nullptr;
    }
}

template<typename T>
T &LRVector<T>::operator[](size_t index) const
{
    if (index < m_size) {
        return m_pDataArray[index];
    } else {
        throw std::runtime_error("index out of range");
    }
}

template<typename T>
void LRVector<T>::push_back(const T &data)
{
    /*内存足够直接追加赋值，不够则进行扩容然后再赋值*/
    if (m_size >= m_capacity) {
        reserve(m_capacity * 2);
    }
    m_pDataArray[m_size] = data;
    ++m_size;
}

template<typename T>
void LRVector<T>::resize(size_t size)
{
    if (size <= m_capacity) {
        m_size = size;
    }
}

template<typename T>
void LRVector<T>::reserve(size_t size)
{
    /*先判断内存大小已经足够，不够重新分配完整内存，将原始数据拷贝过来，然后销毁原始内存，将指针指向新分配的内存*/
    if (size <= m_capacity) {
        return;
    }
    T *pDataArrayTmp = new T[size];
    for (size_t index = 0; index < m_size; ++index) {
        pDataArrayTmp[index] = m_pDataArray[index];
    }
    if (m_pDataArray) {
        delete []m_pDataArray;
        m_pDataArray = pDataArrayTmp;
    }
    m_capacity = size;

}

template<typename T>
size_t LRVector<T>::size() const
{
    return m_size;
}

template<typename T>
size_t LRVector<T>::capacity() const
{
    return m_capacity;
}

template<typename T>
void LRVector<T>::printAll()
{
    for (size_t index = 0; index < m_size; ++index) {
        std::cout << m_pDataArray[index] << " ";
    }
    std::cout << "size=" << m_size << " capacity=" << m_capacity << std::endl;
}

template<typename T>
void LRVector<T>::init()
{
    if (m_capacity > 0) {
        m_pDataArray = new T[m_capacity];
    }
}

使用模板简单实现了一个模板动态数组，由于头文件和实现分离了，可以直接包含cpp。

2.2、单向链表

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
#ifndef FORWARDLIST_H
#define FORWARDLIST_H

#include <iostream>
/*
 * 模板单向链表
*/

template<typename T>
class ForwardList
{
public:
    struct ForwardNode {
    public:
        ForwardNode(const T &data): m_data(data), m_pNextNode(nullptr) {}

        T m_data;
        ForwardNode *m_pNextNode;
    };

    ForwardList(): m_pHead(nullptr)
    {

    }

    ~ForwardList()
    {
        clear();
    }

    T &front()
    {
        if (m_pHead) {
            return m_pHead->m_data;
        }
    }

    void pushFront(const T &val)
    {
        if (!m_pHead) {
            ForwardNode *pNode = new ForwardNode(val);
            m_pHead = pNode;
        } else {
            auto temp = m_pHead;
            ForwardNode *pNode = new ForwardNode(val);
            m_pHead = pNode;
            m_pHead->m_pNextNode = temp;
        }
    }
    void popFront()
    {
        if (m_pHead) {
            auto temp = m_pHead->m_pNextNode;
            delete m_pHead;
            m_pHead = temp;

        }
    }

    void insertAfter(const T &val, const unsigned int pos = 0)
    {
        if (!m_pHead) {
            ForwardNode *pNode = new ForwardNode(val);
            m_pHead = pNode;
        } else {
            unsigned int currentPos = 0;
            auto currentNode = m_pHead;
            while (currentPos < pos) {
                auto nextNode = currentNode->m_pNextNode;
                if (nextNode) {
                    ++currentPos;
                    currentNode = nextNode;
                } else {
                    break;
                }

            }
            auto temp = currentNode->m_pNextNode;
            ForwardNode *pNode = new ForwardNode(val);
            currentNode->m_pNextNode = pNode;
            pNode->m_pNextNode = temp;
        }
    }

    void print()
    {
        auto temp = m_pHead;
        while (temp) {
            std::cout << temp->m_data << " " ;
            temp = temp->m_pNextNode;
        }
        std::cout << std::endl;
    }

    void remove(const T &val)
    {
        /*
         * p作为上一个节点
         * q作为要找到需要删除的节点
        */
        ForwardNode *currentNode = nullptr;
        ForwardNode *preNode = nullptr;
        currentNode = m_pHead;
        while (currentNode && currentNode->m_data != val) {
            preNode = currentNode;
            currentNode = currentNode->m_pNextNode;
        }
        if (currentNode) {
            if (currentNode == m_pHead) {
                m_pHead = m_pHead->m_pNextNode;
            } else {
                preNode->m_pNextNode = currentNode->m_pNextNode;

            }
            delete currentNode;
            currentNode = nullptr;
        }
    }

    void reverse()
    {
        if (m_pHead) {
            ForwardNode *pre = m_pHead;
            ForwardNode *next = m_pHead->m_pNextNode;
            pre->m_pNextNode = nullptr;
            while (next) {
                m_pHead = next->m_pNextNode;
                next->m_pNextNode = pre;
                pre = next;
                next = m_pHead;
            }
            m_pHead = pre;
        }

    }

    void clear()
    {
        while (m_pHead) {
            auto temp = m_pHead;
            m_pHead = m_pHead->m_pNextNode;
            delete temp;
            temp = nullptr;
        }
    }


private:
    ForwardNode *m_pHead;
};
#endif // FORWARDLIST_H

这是一个模板单向链表，实现了简单的前后插入、删除、清空、反转等操作。

2.3、双向链表

2.4、二叉树

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
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>
#include <initializer_list>
#include <queue>
using namespace std;

class BinaryNode
{
public:
    BinaryNode(int value): m_value(value), m_pLeftNode(nullptr), m_pRightNode(nullptr) {}
    int m_value;
    BinaryNode *m_pLeftNode;
    BinaryNode *m_pRightNode;
};

class BinaryTree
{
public:
    BinaryTree(const initializer_list<int> &list)
    {
        if (list.size() <= 0) {
            return;
        }
        int rootValue = *list.begin();
        m_pRootNode = new BinaryNode(rootValue);

        for (auto iter = list.begin() + 1; iter < list.end(); ++iter) {
            insertNode(m_pRootNode, *iter);
        }
    }
    void insertNode(BinaryNode *pNode, int value)
    {
        if (!pNode) {
            cout << "Node is nullptr" << endl;
        } else {
            if (!pNode->m_pLeftNode) {
                pNode->m_pLeftNode = new BinaryNode(value);
            } else if (!pNode->m_pRightNode) {
                pNode->m_pRightNode = new BinaryNode(value);
            } else {
                insertNode(pNode->m_pLeftNode, value);
            }
        }
    }
    /*
     * 广度
    */
    void BreadthFirstTraverse()
    {
        if (!m_pRootNode) {
            cout << "Root node is nullptr" << endl;
            return;
        }
        queue<BinaryNode *> queue;
        queue.push(m_pRootNode);
        while (!queue.empty()) {
            BinaryNode *temp = queue.front();
            cout << temp->m_value << " ";
            queue.pop();
            if (temp->m_pLeftNode) {
                queue.push(temp->m_pLeftNode);
            }
            if (temp->m_pRightNode) {
                queue.push(temp->m_pRightNode);
            }
        }
        cout << endl;

    }
    /*
     * 前序：root->left->right
    */
    void deepthFrontFirstTraverse(BinaryNode *pNode)
    {
        if (pNode) {
            cout << pNode->m_value << " ";
            deepthFrontFirstTraverse(pNode->m_pLeftNode);
            deepthFrontFirstTraverse(pNode->m_pRightNode);
        }
    }
    void deepthFrontFirstTraverse()
    {
        if (m_pRootNode) {
            deepthFrontFirstTraverse(m_pRootNode);
            cout << endl;
        }
    }
    /*
     * 中序：left->root->right
    */
    void deepthMiddleFirstTraverse(BinaryNode *pNode)
    {
        if (pNode) {
            deepthMiddleFirstTraverse(pNode->m_pLeftNode);
            cout << pNode->m_value << " ";
            deepthMiddleFirstTraverse(pNode->m_pRightNode);
        }

    }
    void deepthMiddleFirstTraverse()
    {
        if (m_pRootNode) {
            deepthMiddleFirstTraverse(m_pRootNode);
            cout << endl;
        }
    }
    /*
     * 后序：left->right->root
    */
    void deepthBackFirstTraverse(BinaryNode *pNode)
    {
        if (pNode) {
            deepthBackFirstTraverse(pNode->m_pLeftNode);
            deepthBackFirstTraverse(pNode->m_pRightNode);
            cout << pNode->m_value << " ";
        }
    }
    void deepthBackFirstTraverse()
    {
        if (m_pRootNode) {
            deepthBackFirstTraverse(m_pRootNode);
            cout << endl;
        }
    }

private:
    BinaryNode *m_pRootNode;

};
#endif // BINARYTREE_H

上述代码实现了一个简单的二叉树创建（还有问题），三种深度优先遍历和广度优先遍历。

前、中、后三种深度优先遍历是针对根节点和左右节点相对顺序，遍历时每个节点的顺序都是如此。

三、常用算法

3.1、排序算法

  • 冒泡排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    /*冒泡排序 O(n2) 基本思路：先把首位的当做最小的，然后遍历比较，
     *找到比他更小的就交换位置，每一趟循环筛选出来的最小的放在本次循环的首位，
     *然后去掉最小的继续排序剩余的数据，也就是把外层循环的起点向后偏移1位。
    */
    void bubbleSort(vector<int> &origin)
    {
        for (vector<int>::iterator it = origin.begin(); it != origin.end(); ++it) {
            for (vector<int>::iterator it1 = it + 1; it1 < origin.end(); ++it1) {
                if (*it1 < *it) {
                    std::swap(*it1, *it);
                }
            }
        }
    }

  • 插入排序

    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
    /*插入排序 O(n^2) ，具体耗费时间和有序区相关，如果情况比较好，最低n-1,
     *而冒泡这种时间固定为n^2,所以选择排序算法应该根据实际情况进行选择
     *基本思路，默认将第一位数据作为有序区域，后面的数据作为无序区域，
     *从无序区循环取数据（正序），跟有序区的数据从最相邻的位置进行比较（倒序），
     *如果无序区数据小于有序区域，则将有序区域数据移动到后一个位置，
     *直到没有有序数据比他小，就可以将该数据插入到当前有序区域序号的后面，
     *形成新的有序区域，然后逐渐扩大有序区域，完成排序。这个逻辑可以理解为有一排带数字
     *球体,插入的过程就是把前面比他大的球挤到后面去，直到没有球数字比他小，
     *他就会停下来，插入到比他小的球前面，然后循环，就这样每次有序区增加1个，
     *直到无序区消失
    */ 
    void insertSort(vector<int> &list)
    {
         unsigned int count = list.size();
         unsigned int i = 0;
         unsigned int j = 0;
         int temp = 0;
         //第一层循环无序区域，起点下标为1
         for (i = 1; i < count; ++i)
         {
             temp = list[i];
             //第二层循环和有序区逐个对比直到没有人比他小
             for (j = i - 1; (list[j] > temp); j--)
             {
                list[j + 1] = list[j];
             }
             list[j + 1] = temp;
         }
    }

  • 快速排序

    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
    /*快速排序，时间复杂度n(log n)
     *基本思路：p归位，分割，递归。先找到第一位的值的正确位置（左边比他小，右边比他大），将它放到找到的位置，
     *然后将数组以找到的位置分割为两部分，分别对两部分再进行递归。
    */
     vector<int>::iterator partition(vector<int>::iterator left, vector<int>::iterator right)
     {
         /*
         *取出左边第一位的值，这里将它理解为是空位，所以此时left为空位，假设
         *left为p点，那么就需要先倒序找到右边第一个比他小的，把right索引移到
         *该位置，假设此时right为p点，取出right的值填充到原来的p点的空位，此时
         *right索引成为新的p点。根据p点特性在去找正序查找左边比它大的，以left
         *索引为起点递增。找到后left成为新的p点，取出他的值给上一个p点空位。这样
         *完成一次整体操作之后，left索引和right索引会向中间压缩，如果left
         *索引小于right索引，说明中间还有部分序列没有遍历到。去掉左右遍历完的
         *部分，新的序列又回到开始的状态，然后继续循环。直到找到left和right
         *重叠，这时候把最初的取出的值放到p点，此时左边就都是小于它的值，右边
         *都是大于它的值。
        */
         int temp = *left;
         while (left < right) {
             //倒序查找右边第一个比他小的值
             while (left < right && *right >= temp) {
                  --right;
             }
             //找到结果，将该值放到空位，这里原本的位置变成新的空位
             *left = *right;
             //正序查找左边第一个比他大的值
             while (left < right && *left <= temp) {
                  ++left;
             }
             //找到结果，将该值放到空位，这里原本的位置变成新的空位
             *right = *left;
         }
         *left = temp;
         return left;
     }
     void quickSortPrivate(vector<int>::iterator left, vector<int>::iterator right)
     {
         if (left < right) {
             vector<int>::iterator mid = partition(left, right);
             quickSortPrivate(left, mid - 1);
             quickSortPrivate(mid + 1, right);
         }
     }

     void quickSort(vector<int> &list)
     {
          quickSortPrivate(list.begin(), list.end() - 1);
     }

  • std标准库排序

    1
    2
    3
    4
    5
    //std排序标准库，作为基准时间参考
     void stdSort(vector<int> &list)
     {
         std::sort(list.begin(), list.end());
     }

四种排序算法耗时对比，依次为冒泡排序，插入排序，标准库排序，快速排序。测试以std::vector为数据类型，为了排除数据的分布情况影响排序的效率，采取随机分配指定数量的数据进行测试，消耗时间通过std::chrono::steady_clock::now()前后的差值得出。数据如下：

数据大小/耗时（纳秒） 冒泡排序 插入排序 标准库排序 快速排序
1000 568800 85200 38900 44000
10000 131781600 9355300 554700 511900

可以看出冒泡排序效率最低，随着数据数量增长效率越来越低，标准库的效率和快速排序非常接近，效率很高，日常使用可以直接使用标准库。

3.2、遍历二叉树

二叉树遍历分为广度优先和深度优先，深度优先又分为前、中、后序优先。

  • 广度优先

数据结构与算法
#数据结构，算法
常用数据结构和算法
http://yoursite.com/2021/03/13/常用数据结构和算法/
作者
还在输入
发布于
2021年3月13日
许可协议