程序员面试必备的八大数据结构

短命女 2022-11-06 04:58 216阅读 0赞

> 写在前面：大家好！我是【AI 菌】，一枚爱弹吉他的程序员。我`热爱AI、热爱分享、热爱开源`！ 这博客是我对学习的一点总结与记录。如果您也对 `深度学习、机器视觉、算法、Python、C++` 感兴趣，可以关注我的动态，我们一起学习，一起进步~  
> 我的博客地址为：[【AI 菌】的博客][AI]  
> 我的Github项目地址是：[【AI 菌】的Github][AI _Github]

--------------------

作者：Krahets  
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/50e446/  
来源：力扣（LeetCode）

--------------------

### 文章目录 ###

*   *  前言
     *  一、线性数据结构
     *   *  (1) 数组
         *  (2) 链表
         *  (3) 栈
         *  (4) 队列
     *  二、非线性数据结构
     *   *  (1) 树
         *  (2) 图
         *  (3) 散列表
         *  (4) 堆

## 前言 ##

数据结构是为实现对计算机数据有效使用的各种数据组织形式，服务于各类计算机操作。不同的数据结构具有各自对应的适用场景，**旨在降低各种算法计算的时间与空间复杂度，达到最佳的任务执行效率。**

如下图所示，常见的数据结构可分为**线性数据结构**与**非线性数据结构**，具体为：「数组」、「链表」、「栈」、「队列」、「树」、「图」、「散列表」、「堆」。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center]  
从零开始学习算法的同学对数据结构的使用方法可能尚不熟悉，本文将初步介绍各数据结构的基本特点，以及Python3 或 C++ 语言中各数据结构的初始化与构建方法。

## 一、线性数据结构 ##

### (1) 数组 ###

数组是将相同类型的元素存储于连续内存空间的数据结构。根据数组长度可不可变，可分为静态数组和动态数组。

如下图所示，构建静态数组需要在初始化时给定长度，并对数组每个索引元素赋值：  
![在这里插入图片描述][20210308091254948.png_pic_center]  
C++代码示例如下：

// 初始化一个长度为 5 的数组 array
    int array[5];
    // 元素赋值
    array[0] = 2;
    array[1] = 3;
    array[2] = 1;
    array[3] = 0;
    array[4] = 2;

或者可以使用直接赋值的初始化方式，代码如下：

int array[] = { 2, 3, 1, 0, 2};

**动态数组**是经常使用的数据结构，其基于数组和扩容机制实现，相比普通数组更加灵活。常用操作有：访问元素、添加元素、删除元素。

下面采用C++中的vector类来初始化一个动态数组，并向其末尾添加元素。代码如下：

// 初始化动态数组
    vector<int> array;
    
    // 向尾部添加元素
    array.push_back(2);
    array.push_back(3);
    array.push_back(1);
    array.push_back(0);
    array.push_back(2);

Python代码如下：

# 初始化动态数组
    array = []
    
    # 向尾部添加元素
    array.append(2)
    array.append(3)
    array.append(1)
    array.append(0)
    array.append(2)

我总结了C++中动态数组类vector的用法，想要快速上手的同学，可以前往学习：[【C++养成计划】动态数组 —— 快速上手 STL vector 类（Day14）][C_ _ _ STL vector _Day14]

### (2) 链表 ###

链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是**非连续**的。链表的节点对象具有两个成员变量：「值 val」和「后继节点引用 next」。

C++代码如下：

struct ListNode { 
        int val;        // 节点值
        ListNode *next; // 后继节点引用
        ListNode(int x) : val(x), next(NULL) { }
    };

Python代码如下：

class ListNode:
        def __init__(self, x):
            self.val = x     # 节点值
            self.next = None # 后继节点引用

如下图所示，建立此链表需要实例化每个节点，并构建各节点的引用指向。  
![在这里插入图片描述][20210308101234854.png_pic_center]  
C++示例如下：

// 实例化节点
    ListNode *n1 = new ListNode(4); // 节点 head
    ListNode *n2 = new ListNode(5);
    ListNode *n3 = new ListNode(1);
    
    // 构建引用指向
    n1->next = n2;
    n2->next = n3;

Python示例如下：

# 实例化节点
    n1 = ListNode(4) # 节点 head
    n2 = ListNode(5)
    n3 = ListNode(1)
    
    # 构建引用指向
    n1.next = n2
    n2.next = n3

如果您想进一步学习C++中栈的用法，可以看我的之前写的文章：[【C++养成计划】链表 —— 快速上手STL list 类（Day11）][C_ _ _STL list _Day11]

### (3) 栈 ###

栈是一种具有 **「先入后出」** 特点的抽象数据结构，可使用**数组或链表**实现。

如下图所示，通过常用操作「入栈 push()」,「出栈 pop()」，展示了栈的先入后出特性。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center 1]  
C++代码示例如下：

stack<int> stk;
    stk.push(1); // 元素 1 入栈
    stk.push(2); // 元素 2 入栈
    stk.pop();   // 出栈 -> 元素 2
    stk.pop();   // 出栈 -> 元素 1

Python代码示例如下：

stack = [] # Python 可将列表作为栈使用
    stack.append(1) # 元素 1 入栈
    stack.append(2) # 元素 2 入栈
    stack.pop()     # 出栈 -> 元素 2
    stack.pop()     # 出栈 -> 元素 1

想进一步学习C++中栈的用法，可以看我的之前写的文章：[【C++养成计划】栈 —— 快速上手 STL stack 类（Day12）][C_ _ _ STL stack _Day12]

### (4) 队列 ###

队列是一种具有 **「先入先出」** 特点的抽象数据结构，可使用链表实现。

如下图所示，通过常用操作「入队 push()」,「出队 pop()」，展示了队列的先入先出特性。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center 2]  
C++示例代码如下：

queue<int> que;
    que.push(1); // 元素 1 入队
    que.push(2); // 元素 2 入队
    que.pop();   // 出队 -> 元素 1
    que.pop();   // 出队 -> 元素 2

Python示例代码如下：

# Python 通常使用双端队列 collections.deque
    from collections import deque
    
    queue = deque() # 实例化一个队列
    queue.append(1) # 元素 1 入队
    queue.append(2) # 元素 2 入队
    queue.popleft() # 出队 -> 元素 1
    queue.popleft() # 出队 -> 元素 2

想进一步学习C++中队列的用法，可以看我的之前写的文章：[【C++养成计划】队列 —— 快速上手STL queue类（Day13）][C_ _ _STL queue_Day13]

## 二、非线性数据结构 ##

### (1) 树 ###

树是一种非线性数据结构，根据子节点数量可分为 **「二叉树」** 和 **「多叉树」**，最顶层的节点称为 **「根节点 root」**。以二叉树为例，每个节点包含三个成员变量：**「值 val」、「左子节点 left」、「右子节点 right」** 。

如下图所示，建立此二叉树需要实例化每个节点，并构建各节点的引用指向。  
![在这里插入图片描述][20210308103413950.png_pic_center]  
C++示例代码如下：

struct TreeNode { 
        int val;         // 节点值
        TreeNode *left;  // 左子节点
        TreeNode *right; // 右子节点
        TreeNode(int x) : val(x), left(NULL), right(NULL) { }
    };
    
    // 初始化节点
    TreeNode *n1 = new TreeNode(3); // 根节点 root
    TreeNode *n2 = new TreeNode(4);
    TreeNode *n3 = new TreeNode(5);
    TreeNode *n4 = new TreeNode(1);
    TreeNode *n5 = new TreeNode(2);
    
    // 构建引用指向
    n1->left = n2;
    n1->right = n3;
    n2->left = n4;
    n2->right = n5;

Python示例代码如下：

class TreeNode:
        def __init__(self, x):
            self.val = x      # 节点值
            self.left = None  # 左子节点
            self.right = None # 右子节点
            
    # 初始化节点
    n1 = TreeNode(3) # 根节点 root
    n2 = TreeNode(4)
    n3 = TreeNode(5)
    n4 = TreeNode(1)
    n5 = TreeNode(2)
    
    # 构建引用指向
    n1.left = n2
    n1.right = n3
    n2.left = n4
    n2.right = n5

### (2) 图 ###

图是一种非线性数据结构，由 **「节点（顶点）vertex」** 和 **「边 edge」** 组成，每条边连接**一对顶点**。根据边的方向有无，图可分为 **「有向图」** 和 **「无向图」**。本文以无向图为例开展介绍。

如下图所示，此无向图的 **顶点** 和 **边** 集合分别为：

*  顶点集合： vertices = \{1, 2, 3, 4, 5\}
 *  边集合： edges = \{(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5), (4, 5)\}  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center 3]

表示图的方法通常有两种：

1.  **邻接矩阵**： 使用数组 vertices 存储顶点，邻接矩阵 edges 存储边； edges\[i\]\[j\] 代表节点 i+1 和 节点 j+1 之间是否有边。  
    ![在这里插入图片描述][2021030810462640.png_pic_center]  
    C++代码实现如下：

int vertices[5] = { 1, 2, 3, 4, 5};
    int edges[5][5] = { { 0, 1, 1, 1, 1},
                       { 1, 0, 0, 1, 0},
                       { 1, 0, 0, 0, 1},
                       { 1, 1, 0, 0, 1},
                       { 1, 0, 1, 1, 0}};

1.  **邻接表**： 使用数组 vertices 存储顶点，邻接表 edges 存储边。 edges 为一个二维容器，第一维 i 代表顶点索引，第二维 edges\[i\]存储此顶点对应的**边集合**；例如 edges\[0\] = \[1,2,3,4\] 代表 vertices\[0\] 的边集合为 \[1,2,3,4\] 。 ![在这里插入图片描述][20210308105223606.png_pic_center]  
    C++代码实现如下：

int vertices[5] = { 1, 2, 3, 4, 5};
    vector<vector<int>> edges;
    
    vector<int> edge_1 = { 1, 2, 3, 4};
    vector<int> edge_2 = { 0, 3};
    vector<int> edge_3 = { 0, 4};
    vector<int> edge_4 = { 0, 1, 4};
    vector<int> edge_5 = { 0, 2, 3};
    edges.push_back(edge_1);
    edges.push_back(edge_2);
    edges.push_back(edge_3);
    edges.push_back(edge_4);
    edges.push_back(edge_5);

> **邻接矩阵 VS 邻接表 ：**  
> 邻接矩阵的大小只与节点数量有关，即 N^2，其中 N 为节点数量。因此，当边数量明显少于节点数量时，使用邻接矩阵存储图会造成较大的内存浪费。  
> **因此，邻接表 适合存储稀疏图（顶点较多、边较少）； 邻接矩阵 适合存储稠密图（顶点较少、边较多）。**

### (3) 散列表 ###

散列表是一种非线性数据结构，**通过利用 Hash 函数将指定的「键 key」映射至对应的「值 value」，以实现高效的元素查找。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center 4]

> 设想一个简单场景：小力、小特、小扣的学号分别为 10001, 10002, 10003 。现需求从「姓名」查找「学号」。

则可通过建立姓名为 key ，学号为 value 的散列表实现此需求，C++代码如下：

// 初始化散列表
    unordered_map<string, int> dic;
    
    // 添加 key -> value 键值对
    dic["小力"] = 10001;
    dic["小特"] = 10002;
    dic["小扣"] = 10003;
    
    // 从姓名查找学号
    dic.find("小力")->second; // -> 10001
    dic.find("小特")->second; // -> 10002
    dic.find("小扣")->second; // -> 10003

Python代码如下：

# 初始化散列表
    dic = { }
    
    # 添加 key -> value 键值对
    dic["小力"] = 10001
    dic["小特"] = 10002
    dic["小扣"] = 10003
    
    # 从姓名查找学号
    dic["小力"] # -> 10001
    dic["小特"] # -> 10002
    dic["小扣"] # -> 10003

**自行设计 Hash 函数：**

> 假设需求：从「学号」查找「姓名」。将三人的姓名存储至以下数组中，则各姓名在数组中的索引分别为 0, 1, 2 。

string names[] = {  "小力", "小特", "小扣" };

此时，我们构造一个简单的 Hash 函数（ % 为取余符号 ），公式如下：  
![在这里插入图片描述][20210308111355970.png_pic_center]  
C++封装函数如下：

int hash(int id) { 
        int index = (id - 1) % 10000;
        return index;
    }

于是，我们构建了以学号为 key 、姓名对应的数组索引为 value 的散列表。利用此 Hash 函数，则可在 O(1) 时间复杂度下通过学号查找到对应姓名，即：

names[hash(10001)] // 小力
    names[hash(10002)] // 小特
    names[hash(10003)] // 小扣

![在这里插入图片描述][20210308111650369.png_pic_center]  
注：以上设计只适用于此示例，实际的 Hash 函数需保证低碰撞率、 高鲁棒性等，以适用于各类数据和场景。

### (4) 堆 ###

堆是一种基于 **「完全二叉树」** 的数据结构，可使用数组实现。以堆为原理的排序算法称为 **「堆排序」**，基于堆实现的数据结构为 **「优先队列」**。堆分为 **「大顶堆」** 和 **「小顶堆」**，大（小）顶堆：**任意节点的值不大于（小于）其父节点的值。**

> 完全二叉树定义： 设二叉树深度为 kk ，若二叉树除第 kk 层外的其它各层（第 11 至 k-1k−1 层）的节点达到最大个数，且处于第 kk 层的节点都连续集中在最左边，则称此二叉树为完全二叉树。

如下图所示，为包含 1, 4, 2, 6, 8 元素的小顶堆。将堆（完全二叉树）中的结点按层编号，即可映射到右边的数组存储形式。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center 5]  
通过使用「优先队列」的「压入 push()」和「弹出 pop()」操作，即可完成堆排序，C++实现代码如下：

/ 初始化小顶堆
    priority_queue<int, vector<int>, greater<int>> heap;
    
    // 元素入堆
    heap.push(1);
    heap.push(4);
    heap.push(2);
    heap.push(6);
    heap.push(8);
    
    // 元素出堆（从小到大）
    heap.pop(); // -> 1
    heap.pop(); // -> 2
    heap.pop(); // -> 4
    heap.pop(); // -> 6
    heap.pop(); // -> 8

Python实现代码如下：

from heapq import heappush, heappop
    
    # 初始化小顶堆
    heap = []
    
    # 元素入堆
    heappush(heap, 1)
    heappush(heap, 4)
    heappush(heap, 2)
    heappush(heap, 6)
    heappush(heap, 8)
    
    # 元素出堆（从小到大）
    heappop(heap) # -> 1
    heappop(heap) # -> 2
    heappop(heap) # -> 4
    heappop(heap) # -> 6
    heappop(heap) # -> 8

--------------------

***由于水平有限，博客中难免会有一些错误，有纰漏之处恳请各位大佬不吝赐教！***

![在这里插入图片描述][2020090613542669.png_pic_center]  
***推荐文章***

*  [【C++21天养成计划】不聊学习只谈干货（Day1）][C_21_Day1]
 *  [【人生苦短，我学 Python】序言——不学点Python你就out了？][Python_Python_out]
 *  [TF2.0深度学习实战（一）：分类问题之手写数字识别][TF2.0]

[AI]: https://blog.csdn.net/wjinjie
[AI _Github]: https://github.com/Keyird/DeepLearning-TensorFlow2.0
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center]: /images/20221023/158b0d34c9e74f6d9f105a07bb09bd06.png
[20210308091254948.png_pic_center]: /images/20221023/4d5fd7b3884d44ba8dee229b0851344f.png
[C_ _ _ STL vector _Day14]: https://ai-wx.blog.csdn.net/article/details/108381370
[20210308101234854.png_pic_center]: /images/20221023/4d700d2cd8d844d68431fb45fbf661b5.png
[C_ _ _STL list _Day11]: https://ai-wx.blog.csdn.net/article/details/106557562
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221023/18262ffdf3ba4784ac15d995897227ad.png
[C_ _ _ STL stack _Day12]: https://ai-wx.blog.csdn.net/article/details/107807392
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221023/8748dd15ac3043fdaa75a477cf0c9a0a.png
[C_ _ _STL queue_Day13]: https://ai-wx.blog.csdn.net/article/details/108126720
[20210308103413950.png_pic_center]: /images/20221023/1370a3bb52354a28a00b6e41ea9e232d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221023/34405b87d5784b75b465e4333080b420.png
[2021030810462640.png_pic_center]: /images/20221023/408fec98574b4f528e17c5e6fb0449aa.png
[20210308105223606.png_pic_center]: /images/20221023/c47e1150f84d4e2982780f1b65192390.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221023/71d18b799fc048e2bb011ed17a581506.png
[20210308111355970.png_pic_center]: /images/20221023/b6c61fb19a5140929d6b2ff7d0280ead.png
[20210308111650369.png_pic_center]: /images/20221023/2610df7e10d64a6197d974d6a751abb0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221023/3a0ddc98d4e645408c641fcc97efacc8.png
[2020090613542669.png_pic_center]: /images/20221023/0ba9d46302d34ee58079485183b872f3.png
[C_21_Day1]: https://blog.csdn.net/wjinjie/article/details/105316043
[Python_Python_out]: https://ai-wx.blog.csdn.net/article/details/110674503
[TF2.0]: https://ai-wx.blog.csdn.net/article/details/104700834