数据结构

在计算机科学和软件工程中，数据结构是用于存储和组织数据的对象。 它是一种结构，因为数据以特定方式排列和链接，以实现高效访问和管理。

数据结构的特征不仅在于它们包含的数据，而且最重要的是通过对这些数据的操作来启用和实施访问和管理。

数据结构 en 的确定（定义）一般基于对数据存储和必要操作的准确描述（规范）。 这个具体规范定义了操作的一般行为，因此从数据结构的具体实现中抽象出来。

如果考虑的重点不转移到操作的具体实现上，术语数据结构通常被称为抽象数据类型。从数据结构到抽象数据类型的转换没有明确定义，而仅取决于观点看法。 鉴于许多数据结构的内存需求经常变化，动态数据类型也被提及，它们在技术上基于动态内存管理。

大多数数据结构除了其基本形式外，还具有许多专门用于完成特定任务的专业化。 例如，B 树作为数据结构树的一种特化，特别适用于数据库实现。

对于许多算法，资源需求，即所需的运行时间和内存需求，取决于使用合适的数据结构。

以下数据结构通常是为经典命令式编程开发和优化的。 其他编程范例（例如函数式编程）可能需要不同的数据结构。

记录（也称为“元组”或英文记录）是最简单的数据结构en。 它们通常包含以明确定义的数字和顺序包含其他值的值。 记录通常由它们包含的一个或多个元素标识，通常称为数据字段。

字段（也称为数组）是最简单的数据结构。 这里保存了几个相同基本数据类型的变量。 可以通过索引访问各个元素。 从技术上讲，这是将值添加到内存中数组的起始地址以获得对象的地址。 xxx需要的操作是索引存储和索引读取，它们可以直接访问数组的每个元素。 在一维的情况下，数组通常称为向量，在二维的情况下，称为表或矩阵。 数组决不限于二维，而是可以用于任意数量的维度。 由于它们的简单性和基本重要性，大多数编程语言都提供了这种数据结构的具体实现，作为基本语言范围内的复合数据类型数组。

赋值表（也称为关联数组或键值对）是一种特殊情况，其中存储的数据不是通过数字索引访问，而是通过键访问。 实现关联数组的一种可能方法是哈希表。

另一个特殊情况是数量。 这里不能通过索引或键来访问具体的值。 她精神错乱。 它对应于一个映射表，其中的键只能出现一次，但没有值。

（链接）列表是一个数据结构，用于动态存储任意数量的对象。 作为一项特殊功能，链表的每个列表元素都包含对下一个元素的引用，因此对象的整体成为对象的串联。 与列表相关的操作相对不明确。 它们经常用于更复杂的数据结构en，而不是使用操作，它们的元素通常出于效率原因直接访问。 程序库中提供的列表在其底层数据结构中通常要复杂得多，并且通常根本不代表真实的列表，而是向外界展示它们自己。 列表总是线性结构。 如果前驱和后继双向链接，则称为双向链表。

队列中可以存储任意数量的对象，但存储的对象只能是相同的顺序在他们得救时再次阅读。 这符合 FIFO 原则，对于队列的定义和规格，其中存储了哪些对象是无关紧要的。 至少操作属于队列

• 入队以入队并
• 出列以再次读取xxx个保存的对象并将其从队列中移除。

队列通常实现为链表，但内部可以使用数组； 在这种情况下，元素的数量是有限的。

一个栈中可以存储任意数量的对象，但是存储的对象只能倒序读取。 这符合后进先出原则。 对于堆栈内存的定义和规格，其中存储了哪些对象是无关紧要的。 至少操作属于一个栈

• push 将一个对象压入栈中
• pop 重新读取并弹出最后保存的对象。
• （top 或 peek 阅读顶部元素而不删除它）

top 操作不是强制性的，但通常用于替换 pop/push，因为“测试”top 元素通常很有趣。 堆栈通常实现为列表，但也可以是向量。

deque（双端队列）是一种类似于队列或栈的数据结构。 它结合了数据结构的两个属性。 不同之处在于可以在任一端读取、插入或删除数据。

队列的一个特化是优先级队列，也称为优先级队列。 称为优先队列。 这背离了先进先出原则。 执行入队操作（在本例中也称为插入操作）根据每个对象携带的给定优先级将对象排序到优先级队列中。 出队操作总是返回具有最高优先级的对象。 优先级队列主要是用堆来实现的。

作为数据结构的图形可以克服链接的单向性。 这里的操作也是插入、删除和查找一个对象。 计算机中最著名的图形表示是邻接矩阵、关联矩阵和邻接表。 可以使用半边数据结构映射平面图。

树是图论中图的特殊形式。 通常只有外树被用作数据结构。 从根开始，可以将多个相同类型的对象链接在一起，从而打破列表的线性结构并发生分支。 由于树是计算机科学中最常用的数据结构之一，因此有很多专业化。

例如，在二叉树中，孩子的数量最多为两个，而在高度平衡树中，每个节点的左右子树的高度相差不大。

有序树，尤其是搜索树，将树结构中的元素有序存储，以便快速找到树中的元素。 这里进一步区分了具有作为平衡版本的 AVL 树（包括斐波那契树）的二叉搜索树和 B 树及其变体 B* 树。 B 树的特化又是 2-3-4 树，通常实现为红黑树。

没有排序，但“嵌套”的是几何树结构，如 R 树及其变体。 这里，只搜索那些与请求区域重叠的子树。

尽管树的结构是多维的，但它们在对象的串联中通常是单向的。 存储对象的链接从树的根开始，然后从那里到树的节点。

堆（也称堆或堆）结合了树的数据结构和优先级队列的操作。 除了 insert、remove 和 extractMin 等最低限度必要的操作外，堆通常还有其他操作，例如 merge 或 changeKey。 根据优先队列中的优先顺序使用最小堆或xxx堆。 堆的进一步特化是二叉堆、二项式堆和斐波那契堆。 堆大多建在树上。