数据结构

基本数据结构

阵列

最简单的数据结构类型是一个线性数组。也被称为一维数组。一个数组可以容纳多个相同类型的值（整数、浮点数、字符串等）。访问数组内的元素是非常快的。一个数组通常是固定大小的。在一开始就定义了数组的大小后，如果不创建一个新的更大的数组并将所有的值复制到新的数组中，可能就无法增加数组的大小。在计算机科学中，数组数据结构或简称数组是由元素（值或变量）的集合组成的数据结构，每个元素由至少一个数组索引或键来识别。阵列的存储方式是，每个元素的位置可以通过一个数学公式从其索引元组中计算出来。

例如，一个由10个整数变量组成的数组，索引为0到9，可以作为10个字存储在内存地址2000、2004、2008、2036，这样，索引为i的元素的地址为2000+4×i。

由于矩阵的数学概念可以表示为一个二维网格，二维数组有时也被称为矩阵。在某些情况下，"向量 "一词在计算中被用来指代数组，尽管图元而不是向量是更正确的数学等同物。阵列经常被用来实现表格，特别是查询表；表格这个词有时被用作阵列的同义词。

数组是最古老和最重要的数据结构之一，几乎每个程序都会用到。它们也可以用来实现许多其他数据结构，如列表和字符串。它们有效地利用了计算机的寻址逻辑。在大多数现代计算机和许多外部存储设备中，内存是一个由字组成的一维数组，其索引是其地址。处理器，特别是矢量处理器，通常为数组操作进行了优化。

数组很有用，因为元素的索引可以在运行时计算出来。在其他方面，这个特点允许一个单一的迭代语句处理数组中任意多的元素。由于这个原因，一个数组数据结构的元素被要求具有相同的大小，并且应该使用相同的数据表示。有效的索引图集和元素的地址（以及因此而产生的元素寻址公式）在数组使用时通常是固定的，但并非总是如此。

术语数组通常用于指数组数据类型，这是一种由大多数高级编程语言提供的数据类型，由一个值或变量的集合组成，可以通过运行时计算的一个或多个索引来选择。阵列类型通常由数组结构实现；然而，在一些语言中，它们可能由散列表、链接列表、搜索树或其他数据结构实现。

链接列表

链接数据结构是一组通过引用连接起来的信息/数据。这些数据通常被称为节点。引用通常被称为链接或指针。从这里开始，节点和指针这两个词将被用来表示这些概念。

在链接数据结构中，指针只被取消引用或比较是否相等。因此，链接数据结构与数组不同，数组需要添加和减去指针。

链接列表、搜索树和表达树都是链接数据结构。它们在诸如拓扑排序和集合联合查找等算法中也很重要。

堆栈

堆栈是一种基本的数据结构，在逻辑上可以被认为是由一个真实的物理堆栈或堆积物所代表的线性结构，这种结构中项目的插入和删除发生在被称为堆栈顶部的一端。这个基本概念可以通过把你的数据集想象成一摞盘子或书来说明，在这里你只能把最上面的项目从堆栈中拿出来，以便把东西从里面移走。这种结构在整个编程中都被使用。

堆栈的基本实现也被称为 "后进先出 "结构；然而，堆栈的实现有不同的变化。

基本上有三种操作可以在堆栈上执行。它们是

• 将一个项目插入（"推"）到一个堆栈中
• 从堆栈中删除（"弹出"）一个项目
• 显示堆栈顶部的内容（"偷看"）。

排队

队列是一种抽象的数据类型或线性数据结构，其中第一个元素从一端（"尾部"）插入，现有元素的删除从另一端（"头部"）发生。队列是一个 "先入先出 "的结构。"先入先出 "意味着先放在队列中的元素会先出来，而最后放在队列中的元素会最后出来。队列的一个例子是人们排队等候。队伍中的第一个人先走，队伍中的最后一个人最后走。

向队列中添加一个元素的过程称为 "排队"，从队列中删除一个元素的过程称为 "脱队"。

图表

图是一种抽象的数据类型，旨在实现数学中的图和超图概念。

图数据结构由一组有限的（可能是可变的）有序对组成，称为边或弧，某些实体称为结点或顶点。在数学中，一条边（x,y）被称为从x指向y。节点可能是图结构的一部分，也可能是由整数指数或引用表示的外部实体。图形数据结构也可以将一些边缘值与每个边缘联系起来，如一个符号标签或一个数字属性。

树木

树是最强大的高级数据结构之一。它经常出现在人工智能（AI）和设计等高级学科中。令人惊讶的是，树在一个更基本的应用中也很重要--保持一个有效的索引。

当使用树时，很有可能会使用索引。最简单的索引类型是一个关键字段的排序列表。一棵树通常有一个确定的结构。在二进制树的情况下，你可以使用二进制搜索来定位任何项目，而不需要查看每一个项目。

树数据类型是一种图的类型，这意味着许多用于遍历图的算法也适用于树，然而，这些算法可以非常相似，并且必须有一个专门的起始节点，即没有其他节点链接到它的节点。

简单的有序列表的问题发生在你开始添加新的项目并必须保持列表的排序时--它可以合理有效地完成，但需要一些修改。此外，线性索引不容易共享，因为当一个用户编辑它时，整个索引需要被 "锁定"，而树的一个 "分支 "可以被锁定，其他分支可以被其他用户编辑（因为它们不能被影响）。

哈希表

哈希表是一个数组，其中每个索引都指向基于哈希值的链接列表。散列值是一个由散列函数确定的值。散列函数根据它所存储的数据确定一个唯一的值。这允许在恒定的时间内访问数据，因为计算机总是知道要去哪里找。

每个节点都指向另一个节点。