数据结构与算法

Hello 算法 (https://www.hello-algo.com/)

初始算法

算法

定义

算法（algorithm）是在有限时间内解决特定问题的一组指令或操作步骤，问题明确，包含清晰的输入和输出定义，具有可行性，能够在有限步骤、时间和内存空间下完成，各步骤都有确定的含义，在相同的输入和运行条件下，输出始终相同。

数据结构

数据结构（data structure）是组织和存储数据的方式，涵盖数据内容、数据之间关系和数据操作方法。空间占用尽量小，以节省计算机内存，数据操作尽可能快速，涵盖数据访问、添加、删除、更新等，提供简介的数据表示和逻辑信息，以便算法高效运行。

数据结构设计是一个充满权衡的过程，比如链表相较于数组，在数据添加和删除操作上更加便捷，但牺牲了数据访问速度；图相较于链表，提供了更丰富的逻辑信息，但需要占用更大的内存空间。

数据结构与算法的关系

数据结构为算法提供了结构化存储的数据，以及操作数据的方法，数据结构本身仅存储数据信息，结合算法才能解决特定问题。

数据结构

分类

1. 线性与非线性 逻辑结构可分为“线性”和“非线性”两大类。线性结构比较直观，指数据在逻辑关系上呈线性排列；非线性结构则相反，呈非线性排列。

• 线性数据结构：数组、链表、栈、队列、哈希表，元素之间是一对一的顺序关系。
• 非线性数据结构：树、堆、图、哈希表。

非线性数据结构可以进一步划分为树形结构和网状结构。

• 树形结构：树、堆、哈希表，元素之间是一对多的关系。
• 网状结构：图，元素之间是多对多的关系。

复杂度分析

数组与链表

数组

数组（array）是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。

以连续的内存空间存储，在数组中访问元素非常高效，可以在 O（1） 时间内随机访问数组中的任意一个元素。

插入：将该元素之后的元素向后移动一位； 删除：删除该元素，把后面的元素向前移动； 插入和删除的平均时间复杂度为O（n）

扩容的话，难以保证数组之后的内存空间是可用的，从而无法安全地扩展数组容量，需要重新建立一个更大的数组，把原数组元素一次复制到新数组，这也是一个O（n）的操作。

优点：空间效率高，分配了连续的内存块，无需额外的结构开销；支持随机访问，访问时间O（1）；缓存局部性，

局限性：插入与删除的效率低，长度不可变，空间浪费（如果分配的大于其所需要的）

链表

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

class ListNode:
    """链表节点类"""
    def __init__(self, val: int):
        self.val: int = val               # 节点值
        self.next: ListNode | None = None # 指向下一节点的引用

# 初始化链表 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

插入节点：只需改变两个节点引用（指针）即可，时间复杂度为  O（1）。 删除节点：只需改变一个节点的引用（指针）即可，时间复杂度为  O（1）。

访问节点：效率就较低下了，链表需要从头节点出发，逐个向后遍历，直至找到目标节点。时间复杂度O（n）

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

栈

stack。是遵循先入后出逻辑的线性数据结构。