简介

数据结构可以被定义为一组数据元素，它提供了一种在计算机中存储和组织数据的有效方法，从而可以有效地使用它。数据结构的一些例子是数组、链表、堆栈、队列等。数据结构被广泛用于计算机科学的几乎每一个方面，如操作系统、编译器设计、人工智能、图形等。

数据结构是许多计算机科学算法的主要部分，因为它们使程序员能够以一种有效的方式处理数据。它在提高软件或程序的性能方面起着至关重要的作用，因为软件的主要功能是尽可能快地存储和检索用户的数据。

基本术语

数据结构是任何程序或软件的构建块。为一个程序选择合适的数据结构是程序员最困难的任务。就数据结构而言，我们使用了以下术语。

• 数据。数据可以被定义为一个基本的值或值的集合，例如，学生的名字和它的 ID 是关于学生的数据。
• 组项目（Group Items）。有下级数据项的数据项被称为组项，例如，学生的名字可以有名字和姓氏。
• 记录（Record）。记录可以被定义为各种数据项的集合，例如，如果我们谈论学生实体，那么它的名字、地址、课程和分数可以被组合在一起，形成学生的记录。
• 文件（File）：文件是一种类型的实体的各种记录的集合，例如，如果班上有 60 名员工，那么在相关的文件中会有 20 条记录，每条记录包含每个员工的数据。
• 属性和实体（Attribute and Entity）。一个实体代表了某一类的对象。它包含各种属性。每个属性代表该实体的特定属性。
• 字段（Field）。字段是代表一个实体的属性的单一基本信息单位。

数据结构的需求

由于应用程序越来越复杂，数据量也与日俱增，可能会出现以下问题。

• 处理器速度：为了处理非常大的数据量，需要高速处理，但由于数据每天都在增长，每个实体有数十亿个文件，处理器可能无法处理这么多的数据量。
• 数据搜索。考虑一个商店的库存规模为 106 件物品，我们的应用程序需要搜索一个特定的项目，它每次都需要遍历 106 个项目，从而导致搜索过程变慢。
• 多个请求。如果成千上万的用户同时在网络服务器上搜索数据，那么有可能在这个过程中，一个非常大的服务器会出现故障。

为了解决上述问题，我们使用了数据结构。数据被组织起来形成一个数据结构，使所有的项目都不需要被搜索，所需的数据可以被立即搜索到。

数据结构的优势

• 效率。一个程序的效率取决于对数据结构的选择。例如：假设我们有一些数据，我们需要对某个特定的记录进行搜索。在这种情况下，如果我们把数据组织在一个数组中，我们将不得不按顺序逐个元素进行搜索，因此，在这里使用数组可能不是很有效率。有一些更好的数据结构可以使搜索过程变得高效，如有序数组、二叉搜索树或哈希表。

• 可重用性。数据结构是可重复使用的，也就是说，一旦我们实现了一个特定的数据结构，我们就可以在任何其他地方使用它。数据结构的实现可以被编译成库，可以被不同的客户使用。

• 抽象。数据结构是由 ADT 指定的，它提供了一个抽象的层次。客户端程序只通过接口使用数据结构，而不涉及实现细节。

数据结构的分类

• 线性数据结构。如果一个数据结构的所有元素都以线性顺序排列，那么它就被称为线性数据结构。在线性数据结构中，元素是以非层次的方式存储的，除了第一个和最后一个元素，每个元素都有继承者和前任。下面给出了线性数据结构的类型。
  • 数组。数组是一个类似类型的数据项的集合，每个数据项被称为数组的一个元素。元素的数据类型可以是任何有效的数据类型，如 char, int, float 或 double。数组中的元素共享相同的变量名，但每个元素都有一个不同的索引号，称为下标。数组可以是一维的，二维的或多维的。
  • 链表。链表是一种线性数据结构，用于维护内存中的列表。它可以被看作是存储在非相邻内存位置的节点的集合。列表中的每个节点都包含一个指向其相邻节点的指针。
  • 堆栈。堆栈是一个线性列表，其中只允许在一端插入和删除，称为顶部。堆栈是一种抽象的数据类型（ADT），可以在大多数编程语言中实现。它被命名为堆栈，因为它的行为就像现实世界中的堆栈，例如：一堆盘子或一副牌等等。
  • 队列。队列是一个线性列表，其中的元素只能在称为后端的一端插入，只能在称为前端的另一端删除。它是一个抽象的数据结构，类似于堆栈。队列是在两端打开的，因此它遵循先进先出（FIFO）的方法来存储数据项。
• 非线性数据结构。这种数据结构不形成序列，即每个项目或元素以非线性排列方式与两个或多个其他项目相连。数据元素不按顺序结构排列。下面给出了非线性数据结构的类型。
  • 树。树是一种多层次的数据结构，其元素之间具有层次关系，称为节点。层次结构中最底层的节点被称为叶子节点，而最顶层的节点被称为根节点。每个节点都包含指向相邻节点的指针。树形数据结构基于节点之间的父子关系。除了叶子节点外，树中的每个节点都可以有一个以上的孩子，而除了根节点外，每个节点最多可以有一个父节点。树可以被分为许多类别。
  • 图。图可以被定义为由称为边的链接所连接的元素集合（用顶点表示）的图形表示。图与树的不同之处在于，图可以有循环，而树不能有循环。

对数据结构的操作

• 遍历。每个数据结构都包含数据元素的集合。遍历数据结构意味着访问数据结构中的每个元素，以执行一些特定的操作，如搜索或排序。例子：如果我们需要计算一个学生在 6 个不同科目中获得的平均分数，我们需要遍历整个分数数组并计算总和，然后我们将这个总和除以科目数，即 6，以便找到平均分数。
• 插入。插入可以被定义为在数据结构的任何位置添加元素的过程。如果数据结构的大小为 n，那么我们只能在其中插入 n-1 个数据元素。
• 删除：从数据结构中删除一个元素的过程被称为删除。我们可以在数据结构中的任何位置删除一个元素。如果我们试图从一个空的数据结构中删除一个元素，就会发生下溢。
• 搜索：在数据结构中寻找一个元素的位置的过程被称为搜索。有两种算法来执行搜索，线性搜索和二分搜索。
• 排序。将数据结构按特定顺序排列的过程被称为排序。有许多算法可以用来进行排序，例如，插入排序、选择排序、冒泡排序等。
• 合并。当两个大小分别为 M 和 N 的列表 A 和列表 B，具有类似的元素类型，通过聚合或连接产生第三个列表，即大小为（M+N）的列表 C，那么这个过程被称为合并。