什么是数据结构？

数据结构将数字、字符、布尔值和整数等基本数据类型组合成一个内聚的格式。单独来看，每种原始数据类型都只有一个值。当它们组合成一个数据结构时，就可以实现更高级别的数据运算，例如排序、搜索、插入和删除。

例如，销售团队希望跟踪每天的销售数字。该团队可以将这些数据存储在一种名为“数组”的数据结构中，而不是单独记录每个数据点。（有关更多信息，请参阅“数据结构类型”）。

在 Python 中，数组可能如下所示：

daily_sales = [500, 800, 600, 1200, 950]

使用数组可以让团队将所有这些数据集中在一起，在需要时轻松检索数据点，并对单个元素和整个数组执行函数。

计算机程序员依靠数据结构来构建有效的应用程序。在计算机科学和数据科学领域，数据结构对操作系统、数据库、网站、图形、分析、区块链、机器学习 (ML) 应用程序等至关重要。

由于数据结构是编写有效代码的基础，因此它们通常是编程初学者的第一课。它们也是计算机编程职位面试中常见的题目。

数据结构很重要，因为它们使计算机更容易处理大型、复杂的信息集。通过逻辑地组织数据元素，数据结构提高了计算机代码的效率，使代码更易于理解。

程序员使用数据结构来提高算法的速度和强度，算法是完成计算任务的指令集。在计算机编程中，这种组合被称为“数据结构和算法”的“DSA”。DSA 帮助程序员应对时间复杂性和空间复杂性的双重挑战。

时间复杂度是根据输入量来衡量算法完成任务所需时间的指标。空间复杂度是衡量算法根据输入量使用多少内存的指标。

程序员可以使用数学指标 Big O 符号来度量空间复杂度和时间复杂度。他们可以确定哪些数据结构和算法可以为特定任务提供最快的运行时和最大的空间效率。

数据结构在动态规划这种快速解决复杂问题的技术中也发挥着重要作用。

动态规划通过递归将问题分解为若干子模块。继而分别求解各子模块，最终将子解重组为原问题的完整解决方案。

数据结构通过为程序提供存储和检索每个子解的方法，并在处理过程中保持数据元素的逻辑组织，从而实现动态规划。

例如，计算值可以保存在数组中。当需要构建完整解决方案时，程序可直接从数组中调取这些数值，无需重复计算。

借助这些能力，程序员可以节省时间并更高效地解决问题。

数据结构分为两大类：线性和非线性。

在线性数据结构中，数据以线性方式排列，每个数据元素按顺序一个接一个地放置。这种排列使得按顺序遍历和访问元素变得很容易。

线性数据结构被认为简单直接，易于实现。这一类别中常见的数据结构包括数组、链表和队列。

在非线性数据结构中，其组织逻辑突破了线性顺序排列的局限。例如，数据点可以按层次结构排序或在网络中连接。

由于它们不是线性相互连接，非线性结构中的元素不能像线性数据结构那样在一次遍历中全部访问。非线性数据结构的示例包括树和图表。

程序员可能会使用多种类型的数据结构，具体取决于他们正在构建的系统以及他们需要对数据执行的操作。常见的数据结构包括：

• 数组
• 队列
• 堆栈
  
• 链表
• 树
• 图表
• 哈希

数组是最基本、应用最广泛的数据结构类型之一。它们将类型相似的数据项存储在相邻的内存位置。这种结构可以便于查找和访问相同类型的项目。

用途：数组的常见用途包括排序、存储、搜索和访问数据。数组还可以用作实现其他数据结构的基础，例如队列和堆栈。

举例说明：一个客户服务中心每天客户满意度平均得分的数组可能如下所示：

average_customer_score = [4, 3.5, 3.7, 4.1, 3.4, 4.9]

队列数据结构按照预定的顺序执行数据操作，该顺序称为“FIFO”，即“先进先出”。这意味着第一个添加的数据项将第一个被删除。程序员经常使用这种数据结构来创建优先级队列，其类似于等待列表。

用途：队列数据结构可用于确定播放列表中的下一首歌曲、下一个可访问共享打印机的用户或客户服务中心中下一个要接听的电话。

示例：等待与客户服务中心代表通话的客户可能会被置于这样的队列中：

queue = [customer 1, customer 2, customer 3]

当代表有空时，他们会自动与队列中的第一个客户联系，然后该客户将从列表中删除。现在，队列如下所示：

queue = [customer 2, customer 3]

与队列类似，堆栈数据结构按照预定的顺序执行数据操作。然而，堆栈不是采用先进先出 (FIFO) 格式，而是采用后进先出 (LIFO) 格式。最后添加的数据项将最先被删除。

用途：堆栈可用于帮助确保正确打开和关闭计算机代码中的括号或标记、跟踪最近的浏览器历史记录或撤消应用程序中的最近操作。

例如：许多应用程序使用堆栈来跟踪用户操作，以便可以轻松撤消这些操作。例如，文本编辑器可能会维护一个如下所示的堆栈：

recent_actions = [typing ‘.’, space, typing ‘T’]

用户按下“撤销”按钮时，堆栈中最近的操作（“输入‘T’”）将被撤销。现在，堆栈是这样的：

recent_actions = [typing ‘.’, space]

链表按线性顺序存储数据项，每个项都连接到列表中的下一个项。这种结构可以轻松地插入新项目或删除现有项目，而无需移动整个数据集合。

用途：链表通常用于场景中的频繁插入和删除，例如 Web 浏览器历史记录、媒体播放器播放列表以及应用程序中的撤消或重做操作。

示例：媒体播放器中视频链表的简化版本可能如下所示：

Video 1 – Video 2 – Video 3

列表中的每个对象都指向下一个对象，因此当视频 1 结束时，它将指示媒体播放器启动视频 2。

树形数据结构，有时也称为前缀树，对于建立数据元素之间的层次关系非常有用。单个父节点位于树结构顶端，其子节点在下层逐级分支延伸。

不同类别的树（例如二叉搜索树、AVL 树和 B 树）具有不同的属性，并支持不同的功能。例如，在二叉搜索树中，每个节点最多有 2 个子节点。此结构有助于支持数据集的快速搜索。

用途：在机器学习应用程序中，树通常用于表示组织地图、文件系统、域名系统、数据库索引和决策树中的层次结构。

示例：

图形数据结构使用顶点和边来组织不同对象之间的关系。顶点是由点“表示”的数据点，边是连接顶点的线。

例如，在地图上，城市将是顶点，连接它们的道路将是边。以 Facebook 为例：用户即为顶点，连接用户的友谊关系则构成边。

用途：图数据结构通常与搜索算法一起使用，后者可在复杂的关系网中查找数据。常见的例子包括广度优先搜索（逐层搜索数据）和深度优先搜索（向下钻取多层数据以查找信息）。

示例：

哈希数据结构，有时也称为“哈希表”或“哈希映射”，使用哈希函数来存储数据值。哈希函数会生成一个哈希值，这是一个唯一的数字密钥，对应于内存中特定数据值的位置。

哈希表包含一个可搜索的索引，索引中存储着每个哈希值和数据值对，这使得从表中访问、添加和删除数据变得快捷和容易。

用途：哈希数据结构有助于快速检索电话簿、字典和人事目录中的数据。它们还可用于索引数据库、存储密码和负载平衡 IT 系统。

示例：一个简化版本的哈希表，用于组织智能手机的联系人列表，可能看起来像这样：

哈希函数将每个键映射到相应的索引。因此，当用户输入键（联系人的姓名）时，哈希表会在同一索引处返回关联的值（联系人的号码）。

数据结构在软件应用程序设计中至关重要，因为它们实现了抽象数据类型的具体形式。

抽象数据类型是一种数学模型，对数据类型的行为和可对其执行的操作进行分类。例如，队列的抽象数据类型定义了队列的行为（遵循 FIFO 原则）。队列数据结构提供了一种将数据格式化为队列的方法，以便计算机程序将 FIFO 原则应用于该数据。

许多编程语言，如 Python、Java和 JavaScript，都包含内置数据结构，以帮助开发人员更高效地工作。

数据结构在计算机程序中的常见用例包括：

• 数据存储和组织
• 索引
• 数据交换
• 搜索
• 可扩展性

数据结构能够以逻辑和高效的方式存储数据，并具有很高的数据持久化，因此可以轻松地从数据库和其他应用程序访问数据。数据结构还可以为大量数据提供逻辑组织，使其更容易进行排序、排列和处理。

例如，网站可以使用链表来存储用户活动日志。这些列表可以按时间顺序记录事件，事件之间的链接可以帮助全面了解用户在每个会话期间的操作。

数据结构可以通过将数据值映射到数据库中的相应数据项来索引信息，从而更轻松地查找和访问这些数据记录。

例如，一个电子商务网站可以使用哈希表将产品按类别进行索引。当用户只想查看某个类别时，网站可以使用哈希值快速检索所有相关产品，而无需搜索数据库中的每个产品。

数据结构对数据进行组织，以便可以在应用程序之间轻松共享。例如，许多应用程序使用队列来通过 TCP/IP 等协议管理和发送数据包。队列有助于确保按照数据包的创建顺序发送和接收数据包。

通过将数据组织得更易于应用程序和最终用户理解，数据结构使得数据的搜索和定位变得更加容易。

例如，图形数据结构可以让用户更容易在社交媒体网站上找到他们认识的人。图数据结构记录顶点或节点之间的关系。搜索算法可以追踪节点之间的连接，从而高效地定位相关用户。

数据结构通过帮助计算机程序处理大型数据集、解决复杂问题并更有效地使用资源，来支持系统的可扩展性。

例如，哈希表和树状结构都可以使在大数据集中查找相关信息变得更加容易。系统无需检查每个元素，只需使用正确的键或沿着树的正确路径进行查找。这有助于保持高性能，因为系统不需要使用许多资源来搜索大量数据。