数据结构

常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆、图，它们可以从“逻辑结构”和“物理结构”两个维度进行分类。

1 数组与链表

数组（array）是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。我们将元素在数组中的位置称为该元素的索引（index）。

1.1 数组常用操作

初始化数组
访问元素

数组元素被存储在连续的内存空间中，这意味着计算数组元素的内存地址非常容易。给定数组内存地址（首元素内存地址）和某个元素的索引，我们可以使用公式计算得到该元素的内存地址，从而直接访问该元素。
插入元素

数组元素在内存中是“紧挨着的”，它们之间没有空间再存放任何数据。如果想在数组中间插入一个元素，则需要将该元素之后的所有元素都向后移动一位，之后再把元素赋值给该索引。
删除元素

同理，若想删除索引 i 处的元素，则需要把索引 i 之后的元素都向前移动一位。
遍历数组
查找元素

在数组中查找指定元素需要遍历数组，每轮判断元素值是否匹配，若匹配则输出对应索引。

因为数组是线性数据结构，所以上述查找操作被称为“线性查找”。
扩容数组

在复杂的系统环境中，程序难以保证数组之后的内存空间是可用的，从而无法安全地扩展数组容量。因此在大多数编程语言中，数组的长度是不可变的。

如果我们希望扩容数组，则需重新建立一个更大的数组，然后把原数组元素依次复制到新数组。这是一个 O(n) 的操作，在数组很大的情况下非常耗时。

1.2 数组的优点与局限性

数组存储在连续的内存空间内，且元素类型相同。这种做法包含丰富的先验信息，系统可以利用这些信息来优化数据结构的操作效率。

空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。
支持随机访问：数组允许在 O(1) 时间内访问任何元素。
缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。

连续空间存储是一把双刃剑，其存在以下局限性。

插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。
长度不可变：数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大。
空间浪费：如果数组分配的大小超过实际所需，那么多余的空间就被浪费了。

1.3 数组典型应用

数组是一种基础且常见的数据结构，既频繁应用在各类算法之中，也可用于实现各种复杂数据结构。

随机访问：如果我们想随机抽取一些样本，那么可以用数组存储，并生成一个随机序列，根据索引实现随机抽样。
排序和搜索：数组是排序和搜索算法最常用的数据结构。快速排序、归并排序、二分查找等都主要在数组上进行。
查找表：当需要快速查找一个元素或其对应关系时，可以使用数组作为查找表。假如我们想实现字符到 ASCII 码的映射，则可以将字符的 ASCII 码值作为索引，对应的元素存放在数组中的对应位置。
机器学习：神经网络中大量使用了向量、矩阵、张量之间的线性代数运算，这些数据都是以数组的形式构建的。数组是神经网络编程中最常使用的数据结构。
数据结构实现：数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如，图的邻接矩阵表示实际上是一个二维数组。

链表（linked list）是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。

链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。

链表的组成单位是节点（node）对象。每个节点都包含两项数据：节点的“值”和指向下一节点的“引用”。

链表的首个节点被称为“头节点”，最后一个节点被称为“尾节点”。
尾节点指向的是“空”。

1.4 链表常用操作

初始化链表

建立链表分为两步，第一步是初始化各个节点对象，第二步是构建节点之间的引用关系。初始化完成后，我们就可以从链表的头节点出发，通过引用指向 next 依次访问所有节点。

插入节点

在链表中插入节点非常容易。假设我们想在相邻的两个节点 n0 和 n1 之间插入一个新节点 P ，则只需改变两个节点引用（指针）即可，时间复杂度为 O(1) 。
删除节点

在链表中删除节点也非常方便，只需改变一个节点的引用（指针）即可。

请注意，尽管在删除操作完成后节点 P 仍然指向 n1 ，但实际上遍历此链表已经无法访问到 P ，这意味着 P 已经不再属于该链表了。
访问节点

在链表中访问节点的效率较低。如上一节所述，我们可以在 O(1) 时间下访问数组中的任意元素。链表则不然，程序需要从头节点出发，逐个向后遍历，直至找到目标节点。也就是说，访问链表的第 i 个节点需要循环 i−1 轮，时间复杂度为 O(n) 。
查找节点

遍历链表，查找其中值为 target 的节点，输出该节点在链表中的索引。此过程也属于线性查找。

1.5 常见链表类型

常见的链表类型包括三种。

单向链表：即前面介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 None 。
环形链表：如果我们令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。
双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。

1.6 链表典型应用

单向链表通常用于实现栈、队列、哈希表和图等数据结构。

双向链表常用于需要快速查找前一个和后一个元素的场景，比如在红黑树、B 树。

环形链表常用于需要周期性操作的场景，比如操作系统的资源调度。

1.7 数组 vs. 链表

	数组	链表
存储方式	连续内存空间	分散内存空间
容量扩展	长度不可变	可灵活扩展
内存效率	元素占用内存少、但可能浪费空间	元素占用内存多
访问元素	O(1)	O(n)
添加元素	O(n)	O(1)
删除元素	O(n)	O(1)

2 栈与队列

栈（stack）是一种遵循先入后出逻辑的线性数据结构。

我们可以将栈类比为一弹夹，最先进去弹夹的子弹会在弹夹的底部，也就会在最后才会射出，而最后进去弹夹的子弹会在最顶部，最先射出。

我们把堆叠元素的顶部称为“栈顶”，底部称为“栈底”。将把元素添加到栈顶的操作叫作“入栈”，删除栈顶元素的操作叫作“出栈”。

2.1 栈的常用操作

具体的方法名需要根据所使用的编程语言来确定。在此，我们以常见的 push()（入栈）、pop()（出栈）、peek() （访问栈顶元素，不出栈）命名。

通常情况下，我们可以直接使用编程语言内置的栈类。然而，某些语言可能没有专门提供栈类，这时我们可以将该语言的“数组”或“链表”当作栈来使用，并在程序逻辑上忽略与栈无关的操作。

2.2 栈的实现

栈遵循先入后出的原则，因此我们只能在栈顶添加或删除元素。然而，数组和链表都可以在任意位置添加和删除元素，因此栈可以视为一种受限制的数组或链表。换句话说，我们可以“屏蔽”数组或链表的部分无关操作，使其对外表现的逻辑符合栈的特性。

2.2.1 基于链表的实现

使用链表实现栈时，我们可以将链表的头节点视为栈顶，尾节点视为栈底。

对于入栈操作，我们只需将元素插入链表头部，这种节点插入方法被称为“头插法”。而对于出栈操作，只需将头节点从链表中删除即可。

2.2.2 基于数组的实现

使用数组实现栈时，我们可以将数组的尾部作为栈顶。入栈与出栈操作分别对应在数组尾部添加元素与删除元素，时间复杂度都为 O(1) 。

2.3 栈的典型应用

浏览器中的后退与前进、软件中的撤销与反撤销。每当我们打开新的网页，浏览器就会对上一个网页执行入栈，这样我们就可以通过后退操作回到上一个网页。后退操作实际上是在执行出栈。如果要同时支持后退和前进，那么需要两个栈来配合实现。
程序内存管理。每次调用函数时，系统都会在栈顶添加一个栈帧，用于记录函数的上下文信息。在递归函数中，向下递推阶段会不断执行入栈操作，而向上回溯阶段则会不断执行出栈操作。

队列（queue）是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。

我们将队列头部称为“队首”，尾部称为“队尾”，将把元素加入队尾的操作称为“入队”，删除队首元素的操作称为“出队”。

2.4 队列常用操作

我们采取和栈类似的命名方法 push()（入队）、pop()（出队）、peek() （访问队首元素，不出队）。

2.5 队列实现

为了实现队列，我们需要一种数据结构，可以在一端添加元素，并在另一端删除元素，链表和数组都符合要求。

2.5.1 基于链表的实现

我们可以将链表的“头节点”和“尾节点”分别视为“队首”和“队尾”，规定队尾仅可添加节点，队首仅可删除节点。

2.5.2 基于数组的实现

在数组中删除首元素的时间复杂度为 O(n) ，这会导致出队操作效率较低。然而，我们可以采用以下巧妙方法来避免这个问题。

我们可以使用一个变量 front 指向队首元素的索引，并维护一个变量 size 用于记录队列长度。定义 rear = front + size ，这个公式计算出的 rear 指向队尾元素之后的下一个位置。

基于此设计，数组中包含元素的有效区间为 [front, rear - 1]。

入队操作：将输入元素赋值给 rear 索引处，并将 size 增加 1 。
出队操作：只需将 front 增加 1 ，并将 size 减少 1 。

你可能会发现一个问题：在不断进行入队和出队的过程中，front 和 rear 都在向右移动，当它们到达数组尾部时就无法继续移动了。为了解决此问题，我们可以将数组视为首尾相接的“环形数组”。

对于环形数组，我们需要让 front 或 rear 在越过数组尾部时，直接回到数组头部继续遍历。这种周期性规律可以通过“取余操作”来实现 (front + 1) % n ，也就是循环队列。

**双向队列（double-ended queue）**提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作。也就是在队列的基础上加上对头看入队，对尾可出队。

2.6 队列典型应用

淘宝订单。购物者下单后，订单将加入队列中，系统随后会根据顺序处理队列中的订单。在双十一期间，短时间内会产生海量订单，高并发成为工程师们需要重点攻克的问题。
各类待办事项。任何需要实现“先来后到”功能的场景，例如打印机的任务队列、餐厅的出餐队列等，队列在这些场景中可以有效地维护处理顺序。

3 哈希表

哈希表（hash table），通过建立键 key 与值 value 之间的映射（map 也是哈希表），实现高效的元素查询。具体而言，我们向哈希表中输入一个键 key ，则可以在 O(1) 时间内获取对应的值 value 。

给定 n 个学生，每个学生都有“姓名”和“学号”两项数据。假如我们希望实现“输入一个学号，返回对应的姓名”的查询功能，则可以采用哈希表来实现。

除哈希表外，数组和链表也可以实现查询功能，它们的效率对比如表所示。

	数组	链表	哈希表
查找元素	O(n)	O(n)	O(1)
添加元素	O(1)	O(1)	O(1)
删除元素	O(n)	O(n)	O(1)

观察发现，在哈希表中进行增删查改的时间复杂度都是 O(1) ，非常高效。

3.1 哈希表常用操作

哈希表的常见操作包括：初始化、查询操作、添加键值对和删除键值对等。

哈希表有三种常用的遍历方式：遍历键值对、遍历键和遍历值。

3.2 哈希表简单实现

我们先考虑最简单的情况，仅用一个数组来实现哈希表。在哈希表中，我们将数组中的每个空位称为桶（bucket），每个桶可存储一个键值对。因此，查询操作就是找到 key 对应的桶，并在桶中获取 value 。

那么，如何基于 key 定位对应的桶呢？这是通过哈希函数（hash function）实现的。哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。在哈希表中，输入空间是所有 key ，输出空间是所有桶（数组索引）。换句话说，输入一个 key ，我们可以通过哈希函数得到该 key 对应的键值对在数组中的存储位置。

输入一个 key ，哈希函数的计算过程分为以下两步。

通过某种哈希算法 hash() 计算得到哈希值。
将哈希值对桶数量（数组长度）capacity 取模，从而获取该 key 对应的数组索引 index 。

index = hash(key) % capacity

随后，我们就可以利用 index 在哈希表中访问对应的桶，从而获取 value 。

设数组长度 capacity = 100、哈希算法 hash(key) = key ，易得哈希函数为 key % 100 。

3.3 哈希冲突与扩容

从本质上看，哈希函数的作用是将所有 key 构成的输入空间映射到数组所有索引构成的输出空间，而输入空间往往远大于输出空间。因此，理论上一定存在“多个输入对应相同输出”的情况。

对于上述示例中的哈希函数，当输入的 key 后两位相同时，哈希函数的输出结果也相同。例如，查询学号为 12836 和 20336 的两个学生时，我们得到：

12836 % 100 = 36 20336 % 100 = 36

两个学号指向了同一个姓名，这显然是不对的。我们将这种多个输入对应同一输出的情况称为哈希冲突（hash collision）。

容易想到，哈希表容量 n 越大，多个 key 被分配到同一个桶中的概率就越低，冲突就越少。因此，我们可以通过扩容哈希表来减少哈希冲突。

例如：扩容前键值对 (136, A) 和 (236, D) 发生冲突，扩容后冲突消失。

类似于数组扩容，哈希表扩容需将所有键值对从原哈希表迁移至新哈希表，非常耗时；并且由于哈希表容量 capacity 改变，我们需要通过哈希函数来重新计算所有键值对的存储位置，这进一步增加了扩容过程的计算开销。为此，编程语言通常会预留足够大的哈希表容量，防止频繁扩容。

负载因子（load factor） 是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常作为哈希表扩容的触发条件。

4 二叉树

二叉树（binary tree）是一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。

每个节点都有两个引用（指针），分别指向左子节点（left-child node）和右子节点（right-child node），该节点被称为这两个子节点的父节点（parent node）。当给定一个二叉树的节点时，我们将该节点的左子节点及其以下节点形成的树称为该节点的左子树（left subtree），同理可得右子树（right subtree）。

在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树。如果将“节点 2”视为父节点，则其左子节点和右子节点分别是“节点 4”和“节点 5”，左子树是“节点 4 及其以下节点形成的树”，右子树是“节点 5 及其以下节点形成的树”。

4.1 二叉树基本操作

初始化二叉树

与链表类似，首先初始化节点，然后构建引用（指针）。
插入与删除节点

与链表类似，在二叉树中插入与删除节点可以通过修改指针来实现。

Tip

需要注意的是，插入节点可能会改变二叉树的原有逻辑结构，而删除节点通常意味着删除该节点及其所有子树。因此，在二叉树中，插入与删除通常是由一套操作配合完成的，以实现有实际意义的操作。

4.2 常见二叉树类型

4.2.1 完美二叉树

完美二叉树（perfect binary tree）所有层的节点都被完全填满。在完美二叉树中，叶节点的度为 0 ，其余所有节点的度都为 2 ；若树的高度为 h ，则节点总数为 2h+1−1 ，呈现标准的指数级关系。完美二叉树也被称为满二叉树。

4.2.2 完全二叉树

完全二叉树（complete binary tree）只有最底层的节点未被填满，且最底层节点尽量靠左填充。请注意，完美二叉树也是一棵完全二叉树。

4.2.3 完满二叉树

满二叉树（full binary tree）除了叶节点之外，其余所有节点都有两个子节点。

4.2.4 平衡二叉树

如图 7-7 所示，平衡二叉树（balanced binary tree）中任意节点的左子树和右子树的高度之差的绝对值不超过 1 。

4.3 二叉树的退化

当二叉树的每层节点都被填满时，达到“完美二叉树”；而当所有节点都偏向一侧时，二叉树退化为“链表”。

完美二叉树是理想情况，可以充分发挥二叉树“分治”的优势。
链表则是另一个极端，各项操作都变为线性操作，时间复杂度退化至 O(n)。

5 堆

堆（heap）是一种满足特定条件的完全二叉树，主要可分为两种类型。

小顶堆（min heap）：任意节点的值 ≤ 其子节点的值。
大顶堆（max heap）：任意节点的值 ≥ 其子节点的值。

堆作为完全二叉树的一个特例，具有以下特性。

最底层节点靠左填充，其他层的节点都被填满。
我们将二叉树的根节点称为“堆顶”，将底层最靠右的节点称为“堆底”。
对于大顶堆（小顶堆），堆顶元素（根节点）的值是最大（最小）的。

需要指出的是，许多编程语言提供的是优先队列（priority queue）（就是一个队列，从队尾入队任意大小的元素，都是一个排好序的队列），这是一种抽象的数据结构，定义为具有优先级排序的队列。

实际上，堆通常用于实现优先队列，大顶堆相当于元素按从大到小的顺序出队的优先队列。从使用角度来看，我们可以将“优先队列”和“堆”看作等价的数据结构。

5.1 堆的实现

堆的存储与表示

完全二叉树非常适合用数组来表示。由于堆正是一种完全二叉树，因此我们将采用数组来存储堆。

当使用数组表示二叉树时，元素代表节点值，索引代表节点在二叉树中的位置。节点指针通过索引映射公式来实现。

给定索引 i ，其左子节点的索引为 2i+1 ，右子节点的索引为 2i+2 ，父节点的索引为 (i−1)/2（向下整除）。当索引越界时，表示空节点或节点不存在。

我们可以将索引映射公式封装成函数，方便后续使用。

/* 获取左子节点的索引 */
func (h *maxHeap) left(i int) int {
    return 2*i + 1
}

/* 获取右子节点的索引 */
func (h *maxHeap) right(i int) int {
    return 2*i + 2
}

/* 获取父节点的索引 */
func (h *maxHeap) parent(i int) int {
    // 向下整除
    return (i - 1) / 2
}

5.2 堆的常见操作

访问堆顶元素

堆顶元素即为二叉树的根节点，也就是列表的首个元素。
元素入堆

给定元素 val ，我们首先将其添加到堆底。添加之后，由于 val 可能大于堆中其他元素，堆的成立条件可能已被破坏，因此需要修复从插入节点到根节点的路径上的各个节点，这个操作被称为堆化（heapify）。

考虑从入堆节点开始，从底至顶执行堆化。我们比较插入节点与其父节点的值，如果插入节点更大，则将它们交换。然后继续执行此操作，从底至顶修复堆中的各个节点，直至越过根节点或遇到无须交换的节点时结束。

设节点总数为 n ，则树的高度为 O(log⁡n) 。由此可知，堆化操作的循环轮数最多为 O(log⁡n) ，元素入堆操作的时间复杂度为 O(log⁡n) 。
堆顶元素出堆

堆顶元素是二叉树的根节点，即列表首元素。如果我们直接从列表中删除首元素，那么二叉树中所有节点的索引都会发生变化，这将使得后续使用堆化进行修复变得困难。为了尽量减少元素索引的变动，我们采用以下操作步骤。
1. 交换堆顶元素与堆底元素（交换根节点与最右叶节点）。
2. 交换完成后，将堆底从列表中删除（注意，由于已经交换，因此实际上删除的是原来的堆顶元素）。
3. 从根节点开始，从顶至底执行堆化。
“从顶至底堆化”的操作方向与“从底至顶堆化”相反，我们将根节点的值与其两个子节点的值进行比较，将最大的子节点与根节点交换。然后循环执行此操作，直到越过叶节点或遇到无须交换的节点时结束。

与元素入堆操作相似，堆顶元素出堆操作的时间复杂度也为 O(log⁡n) 。

5.3 堆的常见应用

优先队列：堆通常作为实现优先队列的首选数据结构，其入队和出队操作的时间复杂度均为 O(log⁡n) ，而建堆操作为 O(n)（遍历堆化实现，可以自行了解），这些操作都非常高效。
堆排序：利用堆进行排序。
获取最大的 k 个元素：这是一个经典的算法问题，同时也是一种典型应用，例如选择热度前 10 的新闻作为微博热搜，选取销量前 10 的商品等。（大致思路就是建一个大小为 k 的堆小根堆）

6. 图

图（graph）是一种非线性数据结构，由顶点（vertex）和边（edge）组成。我们可以将图 G 抽象地表示为一组顶点 V 和一组边 E 的集合。以下示例展示了一个包含 5 个顶点和 7 条边的图。

V={1,2,3,4,5},E={(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(4,5)},G={V,E}

如果将顶点看作节点，将边看作连接各个节点的引用（指针），我们就可以将图看作一种从链表拓展而来的数据结构。W相较于线性关系（链表）和分治关系（树），网络关系（图）的自由度更高，因而更为复杂。

6.1 图的常见类型与术语

根据边是否具有方向，可分为无向图（undirected graph）和有向图（directed graph）。

在无向图中，边表示两顶点之间的“双向”连接关系，例如微信或 QQ 中的“好友关系”。
在有向图中，边具有方向性，即 A→B 和 A←B 两个方向的边是相互独立的，例如抖音上的“关注”与“被关注”关系。

根据所有顶点是否连通，可分为连通图（connected graph）和非连通图（disconnected graph）。

对于连通图，从某个顶点出发，可以到达其余任意顶点。
对于非连通图，从某个顶点出发，至少有一个顶点无法到达。

我们还可以为边添加“权重”变量，从而得到有权图（weighted graph）。例如在”最公平“的游戏《王者X耀》中，系统会根据共同游戏时间来计算玩家之间的“亲密度”，这种亲密度网络就可以用有权图来表示。

图数据结构包含以下常用术语。

邻接（adjacency）：当两顶点之间存在边相连时，称这两顶点“邻接”。
路径（path）：从顶点 A 到顶点 B 经过的边构成的序列被称为从 A 到 B 的“路径”。
度（degree）：一个顶点拥有的边数。对于有向图，入度（in-degree）表示有多少条边指向该顶点，出度（out-degree）表示有多少条边从该顶点指出。

6.2 图的表示

图的常用表示方式包括“邻接矩阵”和“邻接表”。以下使用无向图进行举例。

6.2.1 邻接矩阵

设图的顶点数量为 n ，邻接矩阵（adjacency matrix）使用一个 n×n 大小的矩阵来表示图，每一行（列）代表一个顶点，矩阵元素代表边，用 1 或 0 表示两个顶点之间是否存在边。

如图 9-5 所示，设邻接矩阵为 M、顶点列表为 V ，那么矩阵元素 M[i,j]=1 表示顶点 V[i] 到顶点 V[j] 之间存在边，反之 M[i,j]=0 表示两顶点之间无边。

邻接矩阵具有以下特性。

在简单图中，顶点不能与自身相连，此时邻接矩阵主对角线元素没有意义。
对于无向图，两个方向的边等价，此时邻接矩阵关于主对角线对称。
将邻接矩阵的元素从 1 和 0 替换为权重，则可表示有权图。

使用邻接矩阵表示图时，我们可以直接访问矩阵元素以获取边，因此增删查改操作的效率很高，时间复杂度均为 O(1) 。然而，矩阵的空间复杂度为 O($n^2$) ，内存占用较多。

6.2.2 邻接表

邻接表（adjacency list）使用 n 个链表来表示图，链表节点表示顶点。第 i 个链表对应顶点 i ，其中存储了该顶点的所有邻接顶点（与该顶点相连的顶点）。

邻接表仅存储实际存在的边，而边的总数通常远小于 $n^2$ ，因此它更加节省空间。然而，在邻接表中需要通过遍历链表来查找边，因此其时间效率不如邻接矩阵。

邻接表结构与哈希表中的“链式地址”非常相似，因此我们也可以采用类似的方法来优化效率。比如当链表较长时，可以将链表转化为 AVL 树（平衡二叉树）或红黑树，从而将时间效率从 O(n) 优化至 O(log⁡n) ；还可以把链表转换为哈希表，从而将时间复杂度降至 O(1) 。

6.3 图的常见应用

	顶点	边	图计算问题
社交网络	用户	好友关系	潜在好友推荐
地铁线路	站点	站点间的连通性	最短路线推荐

参考资料：https://www.hello-algo.com/

CCNU数据结构实验：https://github.com/Serendipity565/CCNU-Data-Structures

算法

#算法

数据结构

https://serendipity565.github.io/posts/0c921f3052e9/

作者

Serendipity

发布于

2024年12月4日

许可协议

BY-SERENDIPITY565

Git Commit 规范上一篇

MySql事务下一篇

数据结构

分类

根据逻辑结构：线性与非线性

根据物理结构：连续与分散

1 数组与链表

1.1 数组常用操作

1.2 数组的优点与局限性

1.3 数组典型应用

1.4 链表常用操作

1.5 常见链表类型

1.6 链表典型应用

1.7 数组 vs. 链表

2 栈与队列

2.1 栈的常用操作

2.2 栈的实现

2.2.1 基于链表的实现

2.2.2 基于数组的实现

2.3 栈的典型应用

2.4 队列常用操作

2.5 队列实现

2.5.1 基于链表的实现

2.5.2 基于数组的实现

2.6 队列典型应用

3 哈希表

3.1 哈希表常用操作

3.2 哈希表简单实现

3.3 哈希冲突与扩容

4 二叉树

4.1 二叉树基本操作

4.2 常见二叉树类型

4.2.1 完美二叉树

4.2.2 完全二叉树

4.2.3 完满二叉树

4.2.4 平衡二叉树

4.3 二叉树的退化

5 堆

5.1 堆的实现

5.2 堆的常见操作

5.3 堆的常见应用

6. 图

6.1 图的常见类型与术语

6.2 图的表示

6.2.1 邻接矩阵

6.2.2 邻接表

6.3 图的常见应用