logo

数据结构

wangzf / 2024-04-04

目录

数据结构分类

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

逻辑结构: 线性与非线性

逻辑结构揭示了数据元素之间的逻辑关系：

逻辑结构可分为 “线性” 和 “非线性” 两大类：线性结构比较直观， 指数据在逻辑关系上呈线性排列，元素之间是一对一的顺序关系； 非线性结构则相反，呈非线性排列，元素之间是一对多或多对多的关系。

img

物理结构: 连续与分散

存储结构

当算法程序运行时，正在处理的数据主要存储在内存中。下图展示了一个计算机内存条， 其中每个黑色方块都包含一块内存空间。我们可以将内存想象成一个巨大的 Excel 表格， 其中每个单元格都可以存储一定大小的数据。系统通过内存地址来访问目标位置的数据。 计算机根据特定规则为表格中的每个单元格分配编号，确保每个内存空间都有唯一的内存地址。 有了这些地址，程序便可以访问内存中的数据。

img

内存是所有程序的共享资源，当某块内存被某个程序占用时，则无法被其他程序同时使用了。 因此在数据结构与算法的设计中，内存资源是一个重要的考虑因素。 比如，算法所占用的内存峰值不应超过系统剩余空闲内存；如果缺少连续大块的内存空间， 那么所选用的数据结构必须能够存储在分散的内存空间内。

如下图所示，物理结构反映了数据在计算机内存中的存储方式， 可分为连续空间存储（数组）和分散空间存储（链表）。 物理结构从底层决定了数据的访问、更新、增删等操作方法， 两种物理结构在时间效率和空间效率方面呈现出互补的特点。

img

值得说明的是，所有数据结构都是基于数组、链表或二者的组合实现的。 例如，栈和队列既可以使用数组实现，也可以使用链表实现； 而哈希表的实现可能同时包含数组和链表。

链表在初始化后，仍可以在程序运行过程中对其长度进行调整，因此也称“动态数据结构”。 数组在初始化后长度不可变，因此也称“静态数据结构”。值得注意的是， 数组可通过重新分配内存实现长度变化，从而具备一定的“动态性”。

基本数据类型

当谈及计算机中的数据时，我们会想到文本、图片、视频、语音、3D 模型等各种形式。 尽管这些数据的组织形式各异，但它们都由各种基本数据类型构成。

基本数据类型是 CPU 可以直接进行运算的类型，在算法中直接被使用，主要包括以下几种：

基本数据类型以二进制的形式存储在计算机中。一个二进制位即为 1 比特。在绝大多数现代操作系统中， 1 字节(byte)由 8 比特(bit)组成。

基本数据类型的取值范围取决于其占用的空间大小。下面以 Java 为例：

数字编码

字符编码

数据结构-数组与链表

数组–array

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

img

数组常用操作

1 初始化数组

可以根据需求选用数组的两种初始化方式：无初始值、给定初始值。 在未指定初始值的情况下，大多数编程语言会将数组元素初始化为 0。

arr: list[int] = [0] *5
nums: list[int] = [1, 3, 2, 5, 4]

2 访问元素

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

img

我们发现数组首个元素的索引为 0，这似乎有些反直觉，因为从 1 开始计数会更自然。 但从地址计算公式的角度看，索引本质上是内存地址的偏移量。首个元素的地址偏移量是 0， 因此它的索引为 0 是合理的。

import random

def random_access(nums: list[int]) -> int:
    """
    随机访问元素
    """
    # 在区间 [0, len(num) - 1] 中随机抽取一个数字
    random_index = random.randint(0, len(nums) - 1)
    # 获取并返回随机元素
    random_num = nums[random_index]

    return random_num

3 插入元素

数组元素在内存中是“紧挨着的”，它们之间没有空间再存放任何数据。 如下图所示，如果想在数组中间插入一个元素，则需要将该元素之后的所有元素都向后移动一位， 之后再把元素赋值给该索引。值得注意的是，由于数组的长度是固定的， 因此插入一个元素必定会导致数组尾部元素“丢失”。

img

def insert(nums: list[int], num: int, index: int):
    """
    在数组的索引 index 处插入元素 num
    """
    # 把索引 index 以及之后的所有元素向后移动一位
    for i in range(len(nums) - 1, index, -1):
        nums[i] = nums[i - 1]
    # 将 num 赋给 index 处的元素
    nums[index] = num

4 删除元素

若想删除索引 $i$ 处的元素，则需要把索引 $i$ 之后的元素都向前移动一位。 请注意，删除元素完成后，原先末尾的元素变得“无意义”了，所以我们无须特意去修改它。

img

def remove(nums: list[int], index: int):
    """
    删除索引 index 处的元素
    """
    for i in range(index, len(nums) - 1):
        nums[i] = nums[i +1]

总的来看，数组的插入与删除操作有以下缺点。

5 遍历数组

在大多数编程语言中，我们既可以通过索引遍历数组，也可以直接遍历获取数组中的每个元素：

def traverse(nums: list[int]):
    """
    遍历数组
    """
    count = 0
    # 通过索引遍历数组
    for i in range(len(nums)):
        count += nums[i]
    # 直接遍历数组元素
    for num in nums:
        count += num
    # 同时遍历数组索引和元素
    for i, num in enumerate(nums):
        count += num[i]
        count += num

6 查找元素

在数组中查找指定元素需要遍历数组，每轮判断元素值是否匹配，若匹配则输出对应索引。 因为数组是线性数据结构，所以上述查找操作被称为“线性查找”。

def find(nums: list[int], target: int) -> int:
    """
    在数组中查找指定元素
    """
    for i in range(len(nums)):
        if num[i] == target:
            return i
    return -1

7 扩容数组

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

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

def extend(nums: list[int], enlarge: int) -> list[int]:
    """
    扩展数组长度
    """
    # 初始化一个扩展长度后的数组
    res = [0] * (len(nums) + enlarge)
    # 将原数组中的所有元素复制到新数组
    for i in range(len(nums)):
        res[i] = nums[i]
    # 返回扩展后的新数组
    return res

数组的优点与局限性

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

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

数组典型应用

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

链表-linked list

内存空间是所有程序的公共资源，在一个复杂的系统运行环境下，空闲的内存空间可能散落在内存各处。 我们知道，存储数组的内存空间必须是连续的，而当数组非常大时，内存可能无法提供如此大的连续空间。 此时链表的灵活性优势就体现出来了。

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

img

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

在下面的链表节点 ListNode 除了包含值，还需额外保存一个引用（指针）。 因此在相同数据量下，链表比数组占用更多的内存空间。

class ListNode:
    """
    链表节点类
    """
    def __init__(self, val: int):
        self.val: int = val  # 节点值
        self.next: ListNode | None = None

链表常用操作

1 初始化链表

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

# 初始化链表 1 -> 3 -> 2 -> 5 -> 4

# 初始化各个节点
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(4)

# 构建
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

数组整体是一个变量，比如数组 nums 包含元素 nums[0] 和 nums[1] 等， 而链表是由多个独立的节点对象组成的。我们通常将头节点当作链表的代称， 比如以上代码中的链表可记作链表 n0。

2 插入节点

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

相比之下，在数组中插入元素的时间复杂度为 $O(n)$，在大数据量下的效率较低。

img

def insert(n0:ListNode, P: ListNode):
    """
    在链表的节点 n0 之后插入节点 P
    """
    n1 = n0.next
    P.next = n1
    n0.next = P

3 删除节点

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

img

def remove(n0: ListNode):
    """
    删除链表的节点 n0 之后的首个节点
    """
    if not n0.next:
        return
    # n0 -> P -> n1
    P = n0.next
    n1 = P.next
    n0.next = n1

4 访问节点

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

def access(head: ListNode, index: int) -> ListNode | None:
    """
    访问链表中索引为 index 的节点
    """
    for _ in range(index):
        if not head:
            return None
        head = head.next
    
    return head

5 查找节点

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

def find(head: ListNode, target: int) -> int:
    """
    在链表中查找值为 target 的首个节点
    """
    index = 0
    while head:
        if head.val == target:
            return index
        head = head.next
        index += 1
    return -1

数组 VS. 链表

总结了数组和链表的各项特点并对比了操作效率。由于它们采用两种相反的存储策略， 因此各种性质和操作效率也呈现对立的特点。

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

常见链表类型

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

img

链表的典型应用

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

双向链表常用于需要快速查找前一个和后一个元素的场景：

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

列表–list

列表（list）是一个抽象的数据结构概念，它表示元素的有序集合， 支持元素访问、修改、添加、删除和遍历等操作，无须使用者考虑容量限制的问题。 列表可以基于链表或数组实现。

为解决此问题，我们可以使用动态数组（dynamic array）来实现列表。 它继承了数组的各项优点，并且可以在程序运行过程中进行动态扩容。

实际上，许多编程语言中的标准库提供的列表是基于动态数组实现的， 例如 Python 中的 list 、Java 中的 ArrayList 、C++ 中的 vector 和 C# 中的 List 等。 在接下来的讨论中，我们将把 “列表” 和 “动态数组” 视为等同的概念。

列表常用操作

1 初始化列表

通常使用 “无初始值” 和 “有初始值” 这两种初始方法：

# 初始化列表

# 无初始值
nums: list[int] = []

# 有初始值
nums: list[int] = [1, 3, 2, 5, 4]

2 访问元素

列表本质上是数组，因此可以在 $O(1)$ 时间内访问和更新元素，效率很高。

# 访问元素
num: int = nums[1]  # 访问索引 1 处的元素

# 更新元素
nums[1] = 0  # 将索引 1 处的元素更新为 0

3 插入与删除元素

相较于数组，列表可以自由地添加与删除元素。在列表尾部添加元素的时间复杂度为 $O(1)$， 但插入和删除元素的效率仍与数组相同，时间复杂度为 $O(n)$。

# 清空列表
nums.clear()

# 在尾部添加元素
nums.append(1)
nums.append(3)
nums.append(2)
nums.append(5)
nums.append(4)

# 在中间插入元素
nums.insert(3, 6)  # 在索引 3 处插入数字 6

# 删除元素
nums.pop(3)  # 删除索引 3 处的元素

4 遍历列表

与数组一样，列表可以根据索引遍历，也可以直接遍历各元素。

# 通过索引遍历列表
count = 0
for i in range(len(nums)):
    count += nums[i]

# 直接遍历列表元素
for num in nums:
    count += num

5 拼接列表

给定一个新列表 nums1，可以将其拼接到原列表的尾部。

# 拼接两个列表
nums1: list[int] = [6, 8, 7, 10, 9]
nums += nums1  # 将列表 nums1 拼接到 nums 之后

6 排序列表

完成列表的排序后，我们便可以使用在数组类算法题中经常考查的 “二分查找” 和 “双指针” 算法。

# 排序列表
nums.sort()  # 排序后，列表元素从小到大排列

列表实现

许多编程语言内置了列表，例如 Java、C++、Python 等。它们的实现比较复杂， 各个参数的设定也非常考究，例如初始容量、扩容倍数等。

为了加深对列表工作原理的理解，我们尝试实现一个简易版列表，包括以下三个重点设计：

class MyList:
    """
    列表类
    """

    def __init__(self):
        """
        构造方法
        """
        self._capacity: int = 10  # 列表容量
        self._arr: list[int] = [0] * self._capacity  # 数组（存储列表元素）
        self._size: int = 0  # 列表长度（当前元素数量）
        self._extend_ratio: int = 2  # 每次列表扩容倍数
    
    def size(self) -> int:
        """
        获取列表长度（当前元素数量）
        """
        return self._size
    
    def capacity(self) -> int:
        """
        获取列表容量
        """
        return self._capacity
    
    def get(self, index: int) -> int:
        """
        访问元素
        """
        # 索引如果越界，则抛出异常，下同
        if index < 0 or index > self._size:
            raise IndexError("索引越界")
        return self._arr[index]

    def set(self, num: int, index: int):
        """
        更新元素
        """
        if index < 0 or index >= self._size:
            raise IndexError("索引越界")

内存与缓存

物理结构在很大程度上决定了程序对内存和缓存的使用效率，进而影响算法程序的整体性能。

计算机存储设备

计算机中包括三种类型的存储设备：

下表展示了它们在计算机系统中的不同角色和性能特点。

img

我们可以将计算机存储系统想象为下图所示的金字塔结构。 越靠近金字塔顶端的存储设备的速度越快、容量越小、成本越高。 这种多层级的设计并非偶然，而是计算机科学家和工程师们经过深思熟虑的结果。

img

总的来说，硬盘用于长期存储大量数据，内存用于临时存储程序运行中正在处理的数据， 而缓存则用于存储经常访问的数据和指令，以提高程序运行效率。 三者共同协作，确保计算机系统高效运行。

如下图所示，在程序运行时，数据会从硬盘中被读取到内存中，供 CPU 计算使用。 缓存可以看作 CPU 的一部分，它通过智能地从内存加载数据，给 CPU 提供高速的数据读取， 从而显著提升程序的执行效率，减少对较慢的内存的依赖。

img

数据结构的内存效率

在内存空间利用方面，数组和链表各自具有优势和局限性：

数据结构的缓存效率

缓存虽然在空间容量上远小于内存，但它比内存快得多，在程序执行速度上起着至关重要的作用。 由于缓存的容量有限，只能存储一小部分频繁访问的数据，因此当 CPU 尝试访问的数据不在缓存中时， 就会发生缓存未命中（cache miss）， 此时 CPU 不得不从速度较慢的内存中加载所需数据。 显然，“缓存未命中” 越少，CPU 读写数据的效率就越高，程序性能也就越好。 我们将 CPU 从缓存中成功获取数据的比例称为缓存命中率（cache hit rate），这个指标通常用来衡量缓存效率。

为了尽可能达到更高的效率，缓存会采取以下 数据加载机制：

实际上，数组和链表对缓存的利用效率是不同的，主要体现在以下几个方面：

总体而言，数组具有更高的缓存命中率， 因此它在操作效率上通常优于链表。这使得在解决算法问题时， 基于数组实现的数据结构往往更受欢迎。

需要注意的是，高缓存效率并不意味着数组在所有情况下都优于链表。 实际应用中选择哪种数据结构，应根据具体需求来决定。 例如，数组和链表都可以实现 “栈” 数据结构，但它们适用于不同场景。

数据结构-栈与队列

栈

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

可以将栈类比为桌面上的一摞盘子，如果想取出底部的盘子，则需要先将上面的盘子依次移走。 将盘子替换为各种类型的元素（如整数、字符、对象等），就得到了栈这种数据结构。 把堆叠元素的顶部称为 “栈顶”，底部称为 “栈底”。 将把元素添加到栈顶的操作叫作“入栈”，删除栈顶元素的操作叫作“出栈”。

img

栈的常用操作

栈的常用操作如下表所示，具体的方法名需要根据所使用的编程语言来确定。 在此，我们以常见的 push()、pop()、peek() 命名为例。

img

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

# Python 没有内置的栈类，可以把 list 当作栈来使用

# 初始化栈
stack: list[int] = []

# 元素入栈
stack.append(1)
stack.append(3)
stack.append(2)
stack.append(5)
stack.append(4)

# 访问栈顶元素
peek: int = stack[-1]

# 元素出栈
pop: int = stack.pop()

# 获取栈的长度
size: int = len(stack)

# 判断是否为空
is_empty: bool = len(stack) == 0

栈的实现

为了深入了解栈的运行机制，我们来尝试自己实现一个栈类。

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

基于链表的实现

使用链表实现栈时，我们可以将链表的头节点视为栈顶，尾节点视为栈底。 对于入栈操作，我们只需将元素插入链表头部，这种节点插入方法被称为 “头插法”。 而对于出栈操作，只需将头节点从链表中删除即可。

img

img

img

class ListNode:
    """
    链表节点类
    """
    def __init__(self, val: int):
        self.val: int = val  # 节点值
        self.next: ListNode | None = None


class LinkedListStack:
    """
    基于链表实现的栈
    """

    def __init__(self):
        """
        构造方法
        """
        self._peek: ListNode | None = None
        self._size: int = 0
    
    def size(self) -> int:
        """
        获取栈的长度
        """
        return self._size
    
    def is_empty(self) -> bool:
        """
        判断栈是否为空
        """
        return not self._peek
    
    def push(self, val: int):
        """
        入栈
        """
        node = ListNode(val)
        node.next = self._peek
        self._peek = node
        self._size += 1
    
    def pop(self) -> int:
        """
        出栈
        """
        num = self.peek()
        self._peek = self._peek.next
        self._size -= 1
        return num
    
    def peek(self) -> int:
        """
        访问栈顶元素
        """
        if self.is_empty():
            raise IndexError("栈为空")
        return self._peek.val
    
    def to_list(self) -> list[int]:
        """
        转化为列表用于打印
        """
        arr = []
        node = self._peek
        while node:
            arr.append(node.val)
            node = node.next
        arr.reverse()
        return arr

基于数组的实现

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

img

img

img

class ArrayStack:
    """
    基于数组实现的栈
    """

    def __init__(self):
        """
        构造方法
        """
        self._stack: list[int] = []
    
    def size(self) -> int:
        """
        获取栈的长度
        """
        return len(self._stack)
    
    def is_empty(self) -> bool:
        """
        判断栈是否为空
        """
        return self._stack == []
    
    def push(self, item: int):
        """
        入栈
        """
        self._stack.append(item)
    
    def pop(self) -> int:
        """
        出栈
        """
        if self.is_empty():
            raise IndexError("栈为空")
        return self._stack.pop()
    
    def peek(self) -> int:
        """
        访问栈顶元素
        """
        if self.is_empty():
            raise IndexError("栈为空")
        return self._stack[-1]
    
    def to_list(self) -> list[int]:
        """
        返回列表用于打印
        """
        return self._stack

两种实现对比

综上，我们不能简单地确定哪种实现更加节省内存，需要针对具体情况进行分析。

栈的典型应用

队列

队列（queue）是一种遵循先入先出规则的线性数据结构。顾名思义，队列模拟了排队现象， 即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。 我们将队列头部称为 “队首”，尾部称为 “队尾”，将把元素加入队尾的操作称为 “入队”， 删除队首元素的操作称为 “出队”。

img

队列常用操作

队列的常见操作如下表所示。需要注意的是，不同编程语言的方法名称可能会有所不同。 我们在此采用与栈相同的方法命名。

img

from collections import deque

# 初始化队列
# 在 Python 中，一般将双向队列类 deque 当作队列使用，
# 虽热 queue.Queue() 是纯正的队列类，但不太好用，因此不推荐
que: deque[int] = deque()

# 元素入队
que.append(1)
que.append(3)
que.append(2)
que.append(5)
que.append(4)

# 访问队首元素
front: int = que[0]

# 元素出队
pop: int = que.popleft()

# 获取队列的长度
size: int = len(que)

# 判断队列是否为空
is_empty: bool = len(que) == 0

队列实现

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

基于链表的实现

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

img

img

img

class LinkedListQueue:
    """
    基于链表实现的队列
    """

    def __init__(self):
        """
        构造方法
        """
        self._front: ListNode | None = None  # 头节点 front
        self._rear: ListNode | Node = None  # 尾节点 rear
        self._size: int = 0
    
    def size(self) -> int:
        """
        获取队列的长度
        """
        return self._size
    
    def is_empty(self) -> bool:
        """
        判断队列是否为空
        """
        return not self._front
    
    def push(self, num: int):
        """
        入队
        """
        # 在尾节点后添加 num
        node = ListNode(num)
        # 如果队列为空，则令头、尾节点都指向该节点
        if self._front is None:
            self._front = node
            self._rear = node
        # 如果队列不为空，则将该节点添加到尾节点后
        else:
            self._rear.next = node
            self._rear = node
        self._size += 1
    
    def pop(self) -> int:
        """
        出队
        """
        num = self.peek()
        # 删除头节点
        self._front = self._front.next
        self._size -= 1
        return num

    def peek(self) -> int:
        """
        访问队首元素
        """
        if self.is_empty():
            raise IndexError("队列为空")
        return self._front.val

    def to_list(self) -> list[int]:
        """
        转化为列表用于打印
        """
        queue = []
        temp = self._front
        while temp:
            queue.append(temp.val)
            temp = temp.next
        return queue

基于数组的实现

在数组中删除首元素的时间复杂度为 $O(n)$，这会导致出队操作效率较低。 然而，我们可以采用以下巧妙方法来避免这个问题。我们可以使用一个变量 front 指向队首元素的索引， 并维护一个变量 size 用于记录队列长度。定义 rear = front + size， 这个公式计算出的 rear 指向队尾元素之后的下一个位置。 基于此设计，数组中包含元素的有效区间为 [front, rear - 1]，各种操作的实现方法如下图所示。

可以看到，入队和出队操作都只需进行一次操作，时间复杂度均为 $O(1)$。

img

img

img

class ArrayQueue:
    """基于环形数组实现的队列"""

    def __init__(self, size: int):
        """构造方法"""
        self._nums: list[int] = [0] * size  # 用于存储队列元素的数组
        self._front: int = 0  # 队首指针，指向队首元素
        self._size: int = 0  # 队列长度

    def capacity(self) -> int:
        """获取队列的容量"""
        return len(self._nums)

    def size(self) -> int:
        """获取队列的长度"""
        return self._size

    def is_empty(self) -> bool:
        """判断队列是否为空"""
        return self._size == 0

    def push(self, num: int):
        """入队"""
        if self._size == self.capacity():
            raise IndexError("队列已满")
        # 计算队尾指针，指向队尾索引 + 1
        # 通过取余操作实现 rear 越过数组尾部后回到头部
        rear: int = (self._front + self._size) % self.capacity()
        # 将 num 添加至队尾
        self._nums[rear] = num
        self._size += 1

    def pop(self) -> int:
        """出队"""
        num: int = self.peek()
        # 队首指针向后移动一位，若越过尾部，则返回到数组头部
        self._front = (self._front + 1) % self.capacity()
        self._size -= 1
        return num

    def peek(self) -> int:
        """访问队首元素"""
        if self.is_empty():
            raise IndexError("队列为空")
        return self._nums[self._front]

    def to_list(self) -> list[int]:
        """返回列表用于打印"""
        res = [0] * self.size()
        j: int = self._front
        for i in range(self.size()):
            res[i] = self._nums[(j % self.capacity())]
            j += 1
        return res

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

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

以上实现的队列仍然具有局限性：其长度不可变。然而，这个问题不难解决， 我们可以将数组替换为动态数组，从而引入扩容机制。

队列典型应用

双向队列

数据结构-哈希表

哈希表

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

img

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

img

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

哈希表常用操作

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

初始化哈希表

hmap: dict = {}

添加操作

# 在哈希表中添加键值对 (key, value)
hmap[12836] = "小哈"
hmap[15937] = "小啰"
hmap[16750] = "小算"
hmap[13276] = "小法"
hmap[10583] = "小鸭"

查询操作

# 向哈希表中输入键 key，得到值 value
name: str = hmap[15937]

删除操作

# 在哈希表中删除键值对 (key, value)
hmap.pop(10583)

遍历方式

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

# 遍历键值对 key -> value
for key, value in hmap.items():
    print(key, "->", value)

# 单独遍历键 key
for key in hmap.keys():
    print(key)

# 单独遍历值 value
for value in hmap.values():
    print(value)

哈希表简单实现

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

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

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

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

哈希冲突与扩容

哈希冲突

哈希算法

数据结构-树

二叉树

二叉树遍历

二叉树数组表示

二叉搜索树

AVL 树

数据结构-堆

堆

建堆操作

Top-k 问题

数据结构-图

图

图基本操作

图的遍历

图论简介

图论(Graph Theory)是数学的一个分支。它以图(Graph)为研究对象。 图论中的图是由若干给定的点及连接两点的线所构成的图形， 这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物， 用连接两点的线表示相应两个事物间具有这种关系

图论是一种表示“多对多”的关系，图是由顶点和边组成的(可以无边，但至少包含一个顶点)：

图可以分为有向图和无向图，在图中：

图可以分为有权图和无权图：

图又可以分为连通图和非连通图：

图中的顶点有度的概念：

图的类型：

图的表示

图在程序中的表示一般有两种方式：

  1. 邻接矩阵
    • 在 $n$ 个顶点的图需要有一个 $n \times n$ 大小的矩阵
    • 在一个无权图中，矩阵坐标中每个位置值为 1 代表两个点是相连的，0 表示两点是不相连的
    • 在一个有权图中，矩阵坐标中每个位置值代表该两点之间的权重，0 表示该两点不相连
    • 在无向图中，邻接矩阵关于对角线相等
  2. 邻接链表
    • 对于每个点，存储着一个链表，用来指向所有与该点直接相连的点
    • 对于有权图来说，链表中元素值对应着权重

邻接矩阵与邻接链表示例：

邻接矩阵和链表对比：

图的遍历

图的遍历就是要找出图中所有的点，一般有两种方法

相当于在漆黑的夜里，你只能看清你站的位置和你前面的路，但你不知道每条路能够通向哪里。 搜索的任务就是，给出初始位置和目标位置，要求找到一条到达目标的路径

广度优先搜索

广度优先搜索，可以被形象地描述为 “浅尝辄止”，它也需要一个队列以保持遍历过的顶点顺序， 以便按出队的顺序再去访问这些顶点的邻接顶点

实现思路：

  1. 顶点 $v$ 入队列
  2. 当队列非空时则继续执行，否则算法结束
  3. 出队列取得队头顶点 $v$；访问顶点 $v$ 并标记顶点 $v$ 已被访问
  4. 查找顶点 $v$ 的第一个邻接顶点 $col$
  5. 若 v 的邻接顶点 $col$ 未被访问过的，则 $col$ 继续
  6. 查找顶点 $v$ 的另一个新的邻接顶点 $col$，转到步骤 5 入队列， 直到顶点 $v$ 的所有未被访问过的邻接点处理完。转到步骤 2

要理解深度优先和广度优先搜索，首先要理解搜索步，一个完整的搜索步包括两个处理

  1. 获得当前位置上，有几条路可供选择
  2. 根据选择策略，选择其中一条路，并走到下个位置

深度优先搜索

基本思路：深度优先遍历图的方法是，从图中某顶点 $v$ 出发

  1. 访问顶点 $v$
  2. 从 $v$ 的未被访问的邻接点中选取一个顶点 $w$，从 $w$ 出发进行深度优先遍历
  3. 重复上述两步，直至图中所有和 $v$ 有路径相通的顶点都被访问到

最短路径算法

无权图

有权图

在有权图中，常见的最短路径算法有

迪杰斯特拉算法 Dijkstra

单源最短路径

佛洛伊德算法 Floyd

最小生成树

网络流建模