重学数据结构

了解不同的数据存储类型

线性表

1. 顺序表： 顺序表是线性表的一种物理存储结构，它将元素存储在一块连续的内存空间中。每个元素占用固定大小的空间，并通过下标（或索引）来唯一确定其位置。访问、插入和删除操作的时间复杂度主要取决于操作的位置和数组的实现方式。具体特点如下：

   • 访问速度快：由于元素存储在连续的内存空间中，可以通过下标直接访问，时间复杂度为O(1)。
   • 插入和删除效率受位置影响：在表尾插入和删除元素的时间复杂度为O(1)，但在表头或中间位置进行这些操作可能需要移动大量元素，时间复杂度为O(n)。
   • 预分配存储空间：创建顺序表时需要预先确定容量，当元素数量超过预设容量时，可能需要动态扩容，涉及内存的重新分配和数据的迁移。

2. 链表： 链表是线性表的另一种物理存储结构，它不要求元素在内存中连续存放，而是通过“指针”将元素（节点）非连续地链接在一起。每个节点包含两部分：数据域（存储元素本身）和指针域（存储指向下一个节点的地址）。链表根据指针的连接方式不同，又可分为单链表、双链表和循环链表等。其特点如下：

   • 访问速度相对较慢：访问链表中的元素需要从头节点开始，沿着指针逐个查找，时间复杂度为O(n)。
   • 插入和删除操作灵活：在任何位置插入或删除元素，只需改变相应节点的指针即可，时间复杂度为O(1)（不考虑查找节点的时间）。
   • 动态分配存储空间：链表不需要预先分配存储空间，随着元素的增删，会自动调整。

   ---

栈

是一种特殊类型的线性表，它遵循后进先出（Last In, First Out, LIFO）原则。形象地说，栈就像一个垂直堆放物品的容器，新添加的元素（压栈）总是放在栈顶，而取出元素（弹栈）也总是从栈顶开始，保证最后放入的元素最先被取出。这种特性使得栈在很多需要保持操作顺序、回溯状态或者实现递归算法等问题上有着广泛的应用。

栈的基本操作包括：

1. Push (压栈)：向栈顶添加一个元素。如果栈已满，则可能导致溢出错误（在实际编程中需要适当处理）。
2. Pop (弹栈)：移除并返回栈顶元素。如果栈为空，则进行此操作会导致下溢错误（同样需要妥善处理）。
3. Peek (查看栈顶元素)：返回栈顶元素但不移除它，允许检查栈顶元素而不改变栈的状态。
4. Is Empty (判断栈是否为空)：检查栈内是否没有任何元素，如果是，则返回真值，否则返回假值。
5. Size (获取栈内元素数量)：返回栈内当前存储的元素数量。

栈在计算机科学中有多种实现方式，如基于数组的栈和基于链表的栈。基于数组的栈有固定容量限制，优点是访问速度快，缺点是在栈满时若要继续压栈，可能需要重新分配更大的数组并复制原有数据。基于链表的栈则可以动态增长，无需预先设定容量，插入和删除操作更为灵活，但访问速度相对基于数组的栈略慢。

栈的应用场景包括但不限于：

• 函数调用堆栈：编译器在实现函数调用时，会使用栈来保存函数的局部变量、返回地址等信息，每次函数调用都会对应一次压栈操作，函数返回时对应一次弹栈操作。
• 表达式求值与括号匹配：计算逆波兰表达式（后缀表达式）时，利用栈暂存操作数和运算符，按照特定规则进行弹栈和计算。在检查字符串中的括号是否正确配对时，也可以使用栈记录未关闭的左括号，遇到右括号时检查栈顶元素是否匹配。
• 深度优先搜索（DFS）：在遍历图或树时，栈用于保存待访问节点，实现回溯过程。
• 撤销/重做功能：在文本编辑器或绘图软件中，用户执行的操作序列可以储存在栈中，撤销操作相当于弹栈，重做操作则是将之前弹出的元素重新压栈。

总之，栈作为一种基础数据结构，以其特有的LIFO特性在解决需要保持操作顺序、实现递归逻辑或进行回溯等问题时发挥着关键作用。

队列

队列是一种线性数据结构，它遵循先进先出（First In, First Out, FIFO）的原则。形象地比喻，队列就像日常生活中的排队场景：最早到达队列的人（元素）会最先离开队列。这种特性使得队列在处理任务调度、消息传递、资源分配等问题上具有重要应用价值。

队列的基本操作包括：

1. Enqueue (入队)：在队尾添加一个元素。如果队列已满（在某些实现中可能存在容量限制），则可能导致溢出错误。
2. Dequeue (出队)：移除并返回队首元素。如果队列为空，则进行此操作会导致下溢错误。
3. Front (查看队首元素)：返回队首元素但不移除它，允许检查队首元素而不改变队列的状态。
4. Is Empty (判断队列是否为空)：检查队列内是否没有任何元素，如果是，则返回真值，否则返回假值。
5. Size (获取队列内元素数量)：返回队列内当前存储的元素数量。

队列也有多种实现方式，常见的有两种：

• 基于数组的队列：使用数组来存储队列中的元素，通过两个指针（索引）分别标记队首和队尾的位置。当队尾达到数组边界时，可能需要进行循环（环形）利用数组空间或者重新分配更大的数组。
• 基于链表的队列：使用链表结构来实现队列，队首元素始终位于链表头部，队尾元素则在链表尾部。入队操作即在链表尾部添加节点，出队操作则删除链表头部节点。链表实现的队列通常没有固定容量限制，且能更灵活地处理元素的添加和移除。

队列在计算机科学及工程实践中有着广泛的应用，例如：

• 任务调度：操作系统中的进程或线程调度器常常使用队列来管理等待执行的任务。新提交的任务入队，处理器从队首取出任务进行执行。
• 消息传递：在消息传递系统中，消息通常被发送到一个队列中，接收者从队首取出并处理这些消息。这种模式可以实现异步通信，减轻系统间的直接依赖，并支持负载均衡和故障恢复。
• 缓冲区：在数据流处理、网络传输等场景中，队列作为临时缓冲区存储待处理或待发送的数据，起到平滑数据流、协调不同速率组件的作用。
• 广度优先搜索（BFS）：在遍历图或树时，队列用于保存待访问节点，实现逐层推进的搜索策略。

总的来说，队列作为一种基础数据结构，以其FIFO特性适用于任何需要按照元素进入顺序依次处理它们的场景，特别是在涉及任务调度、消息传递、资源分配以及搜索算法等方面具有重要应用价值。

树

树是一种非线性数据结构，它由n（n≥1）个有限节点组成一个具有层次关系的集合。每个节点包含一个或多个值，以及指向其子节点的引用（称为分支）。在树中，有一个特殊的节点被称为根节点（root），它是树的起点；除了根节点外，每个节点都有且仅有一个父节点；而没有子节点的节点被称为叶节点（leaf）。节点之间通过分支形成层次结构，最顶层是根节点，最底层是叶节点。

树的主要特性包括：

1. 层次性：树中的节点按层次进行组织，根节点位于第一层，其子节点位于第二层，以此类推。同一层的节点互称兄弟节点。
2. 无环性：树中任意两个节点之间不存在循环路径，即从一个节点出发，沿着分支只能到达有限个其他节点，最终终止于叶节点。
3. 节点间关系：每个节点与其子节点形成一对一的父子关系，子节点共享相同的父节点，但彼此之间无直接联系。

根据树的具体特征，有许多不同的树形结构，如二叉树、多叉树、平衡树、二叉搜索树（BST）、AVL树、红黑树、B树、B+树、哈夫曼树等。下面简要介绍几种常见的树结构：

• 二叉树：每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树进一步可分为满二叉树、完全二叉树、二叉搜索树（BST）等。
• 平衡树：是一种自平衡的二叉搜索树，如AVL树、红黑树等。这类树在插入、删除等操作后能通过旋转等手段保持左右子树的高度差不超过一定阈值，从而确保高效的查找、插入和删除操作。
• B树（B-Tree）和B+树：适用于磁盘等外部存储设备上的大规模数据存储，它们通过增加每个节点的子节点数（通常为几十到几千），减少树的高度，提高大数据量下的查询效率。B+树的叶子节点之间通过指针相连，形成有序链表，便于范围查询。
• 哈夫曼树（霍夫曼树）：是一种带权路径长度最短的二叉树，常用于数据压缩，构建过程中根据各节点的权重（频率）构建最优的编码方案。

树结构在计算机科学中有着广泛的应用，包括但不限于：

• 文件系统：文件目录结构通常采用树形结构表示，每个目录（文件夹）被视为一个节点，其中包含指向子目录和文件的引用。
• 数据库索引：数据库管理系统常使用B树及其变种（如B+树）作为索引结构，以提高数据查询效率。
• 编译器：词法分析、语法分析阶段会使用树（如抽象语法树，AST）来表示源代码的结构，便于后续的语义分析和代码生成。
• 图形学：场景图、渲染树等用于描述图形渲染的层级结构，方便进行视口裁剪、层级排序、渲染优化等操作。
• 机器学习与数据挖掘：决策树、随机森林、神经网络中的计算图等都是树形结构在机器学习领域的应用。

总之，树作为一种高度抽象且灵活的数据结构，以其层次性和无环性很好地模拟了现实世界中许多具有层级关系的问题，广泛应用于计算机科学的各个领域，如文件系统、数据库、编译器、图形学、机器学习等。

图

图（Graph）是一种非线性数据结构，它由一组顶点（Vertices）和连接这些顶点的边（Edges）构成。图可以用来表示实体（顶点）之间的多种复杂关系（边），这些关系可能是双向的、有向的、有权重的，甚至可以有额外属性。图结构的灵活性使其成为描述各种离散系统中元素相互作用的理想模型，如社交网络、互联网、交通网络、电路设计、化学分子结构等。

基本概念：

• 顶点（Vertex）：图中的基本单元，通常代表一个实体或对象。在图论中，顶点集合通常记为 V。
• 边（Edge）：连接图中两个顶点的连线，表示顶点之间的某种关系。边可以是有向的（从一个顶点指向另一个顶点）或无向的（两个顶点间的关系是对称的）。有向边用箭头表示方向，无向边则没有方向性。边集通常记为 E。
• 邻接（Adjacency）：对于无向图，若两个顶点由一条边相连，则称它们互为邻接顶点；对于有向图，若一条边从顶点 u 指向顶点 v，则称 v 是 u 的邻接顶点，而不一定是反过来。每个顶点的邻接顶点集合称为该顶点的邻接列表。
• 度（Degree）：在一个无向图中，顶点的度是指与该顶点相连的边的数量。在有向图中，顶点的度分为入度（指向该顶点的边数）和出度（从该顶点出发的边数）。
• 路径（Path）：图中一系列顶点，使得每相邻的一对顶点之间都有一条边相连。路径可以是有向的（遵循边的方向）或无向的。路径的长度定义为其包含的边数。
• 连通性（Connectivity）：在无向图中，如果从任意一个顶点都可以通过一系列边到达其他任何顶点，则称该图是连通的。在有向图中，若存在从任意顶点到其他任何顶点的有向路径，则称该图为强连通的。
• 环（Cycle）：在无向图或有向图中，如果一条路径的起点和终点相同，并且这条路径上的顶点除起点/终点外其余均不重复，那么这条路径就构成了一个环。

特殊类型的图：

• 无向图：图中的边没有方向，表示顶点间的关系是对称的。
• 有向图：图中的边带有方向，表示顶点间的关系具有方向性。
• 加权图：图中的边附有一个数值（权重），表示关联顶点间关系的强度、距离或其他相关度量。
• 完全图：每对不同的顶点之间都恰有一条边相连（无向图）或一条有向边（有向图）。
• 简单图：图中不存在自环（一条边的起点和终点是同一个顶点）和多条平行边（两顶点间有多条相同的无向边或多条同向的有向边）。

图的表示方法：

• 邻接矩阵：用一个二维数组表示图，数组的行和列对应顶点，数组中的元素值表示相应顶点间是否存在边及边的权重（如果有）。对于稀疏图（边数远小于顶点数的平方），这种方法可能造成空间浪费。
• 邻接表：为每个顶点维护一个列表，列出所有与之相邻的顶点及其关联信息（如有权值）。这种方法对稀疏图更为高效。

图的应用实例：

• 社交网络：用户（顶点）之间的朋友关系（无向边）或关注关系（有向边）。
• 路由网络：路由器（顶点）之间的通信路径（边），边可能带有延迟或带宽等权重。
• 网页链接：网页（顶点）之间的超链接（有向边），用于搜索引擎的网页抓取和排名算法（如PageRank）。
• 地图导航：地点（顶点）之间的道路（边），边可能带有距离和时间等权重。
• 生物信息学：蛋白质（顶点）之间的交互（边），研究蛋白质网络的功能和调控机制。

图算法涵盖了广泛的计算机科学问题，包括搜索（如深度优先搜索、广度优先搜索）、最短路径（如Dijkstra算法、A*算法）、最小生成树（如Prim算法、Kruskal算法）、网络流（如Ford-Fulkerson算法）、图着色、匹配问题等。这些算法对于理解和解决基于图结构的问题至关重要。