1、前言

data structure

数据结构是计算机科学中非常重要的一部分和关键组成部分。如果没有不同类型的数据结构，就不可能有效地存储信息。数据结构是一种有效存储、操作和检索数据的方法。数据结构广泛用于几乎所有计算机科学领域。

2、什么是数据结构

logo

数据结构是一种在计算机中构建/组织数据的方法，以便我们可以以最有效的方式利用这些数据。使用数据结构的主要目的是降低每个可能计算的空间和时间复杂性。计算机科学中有各种各样的数据结构，如数组、链表、堆栈、队列、树和图等。

3、数据结构的基本术语

基本术语

数据结构中最常用的一些术语是：

数据：它是值的集合或单个值，需要存储在某个地方以备将来使用。例如，在学校和大学中，学生的详细信息（如学生证、学生姓名等）由数据组成。

组项：组数据项是给定数据的子数据项。例如，学生姓名可以包括名字、中间名和姓氏。

记录：记录是不同数据项的集合。例如，一个学生的记录包括他的名字、中间名、姓氏、电话号码、卷号、地址等。

文件：文件是多条记录的集合。例如，如果一门课程有 200 名学生注册，那么我们可以将所有这些学生的记录存储在一个文件中。

实体：实体是各种对象的类。每个实体都包含各种属性。

属性：属性描述实体的特定属性。一个实体可以有多个属性。

字段：字段表示实体的属性。

4、数据结构类型

数据结构类型

在最基本的层面上，我们将数据结构分为两类：原始和非原始。我们可以进一步将非原始数据结构分为线性和非线性。

4.1 原始数据结构

原始数据结构是默认在编程语言中定义的数据结构。它不包括任何其他方法。

例如，int、long、float、double、char 等是一些原始数据结构。它们也称为基元数据类型。它们不能一次保存多个值。

4.2 非原始数据结构

非原始数据结构是那些不是编程语言内置的。通常，程序员定义这些数据结构是为了简化他们的问题。与原始数据结构相比，非原始数据结构具有一定的优势，例如它们一次可以保存多个值。此外，它们很容易访问。

我们可以进一步将非原始数据结构分为两类：线性和非线性数据结构。

5、线性数据结构

线性结构

顾名思义，线性数据结构是那些可以以线性或顺序方式保存数据的结构。在线性数据结构中，每个元素都与其前一个元素和下一个元素有联系。线性数据结构的一些示例包括：数组、链表、堆栈和队列。

6、非线性数据结构

非线性数据结构

非线性数据结构是指数据不是按顺序排列的，而是以分层格式排列数据。由于分层排列，我们无法一次性遍历整个数据。

在效率以及空间和时间复杂性方面，非线性数据结构比线性数据结构更有效。

非线性数据结构进一步分为静态和动态。

6.1 静态数据结构

静态数据结构是那些具有固定内存大小的数据结构，该内存大小在编译时决定。在静态数据结构中，如果我们曾经给数据结构指定了特定的大小，则无法在运行时收缩或扩展它。静态数据结构最合适的例子是数组。

6.2 动态数据结构

顾名思义，这些数据结构具有不同的内存大小，即我们也可以在运行时根据时间和需要更改大小。我们在运行时将内存大小分配给动态数据结构。

动态数据结构的几个示例是列表、堆栈、队列、树和图。

7、数据结构的基本操作

数据结构执行的最常见操作包含以下几部分：

搜索：每当我们希望找到特定元素时，我们都会对数据结构执行搜索操作。

遍历：遍历包括访问数据结构中的所有值。

插入：插入包括将新元素添加/插入到预先存在的数据结构中。

更新：更新操作有助于操作数据结构中的一个或多个元素。

删除：此操作有助于从数据结构中删除一个或多个元素。

合并：用于组合两个或多个数据结构。合并操作主要对同类型的数据结构执行。

排序：排序意味着按升序或降序排列给定数据。

8、数据结构的特征

时间 & 空间复杂度

时间复杂度：时间复杂度为我们提供了在特定数据结构上执行特定操作所需的时间。所花费的时间应该是最短的，以便提高程序的效率。

空间复杂度：空间复杂度告诉我们任何操作完成其执行所需的额外内存空间。我们应该尝试使用尽可能少的额外空间来执行程序。

正确性：这个特性说明我们需要正确实现数据结构的接口。

9、为什么需要学习数据结构

为什么需要数据结构呢？这个问题的简单答案是减少空间和时间的复杂性，以及提高代码的效率。

让我们借助一个小例子来理解。假设我们希望在 500 名学生中搜索某个系中特定学生的记录。考虑学生记录根据其卷号按升序排序。

如果我们一个接一个地从头到尾开始搜索，将花费很多时间。但是，如果我们使用二进制搜索，即我们首先转到中间记录并检查要搜索的记录是在中间记录之后还是之前。通过这种方式，我们将搜索减少了一半。这是展示数据结构如何提高任何计算效率的示例之一。在整个计算机科学中，数据结构有很多这样的用途。

如果我们在日常生活中看到，我们会看到很多数据结构的例子。例如，我们所有人的学习桌上都摆放着几本书。这堆书是堆栈实现的一个示例。另一个例子是，每当我们去银行或排队买电影票时，我们都遵循先进先出的原则。这是队列数据结构的实现。

10、数据结构的优点减少任何问题的计算时间。这些有助于以更有效的方式利用可用的内存空间。确保代码的可重用性，因为我们可以在程序中只为堆栈或任何数据结构编写一次代码，并在多个位置使用它。抽象数据类型（ADT）为我们提供了理解和使用数据结构的最佳方式，而无需深入研究实现细节。有多种选择。我们可以根据自己的需要和要解决问题的需要选择任何一种数据结构。数据结构提供了科学的计算方法，有助于提高速度、效率和更容易实现数据结构上的操作。11、数据结构的应用每当我们有顺序和固定大小的数据实现时，数组都很有用。例如，在在线或视频游戏以及在线编码竞赛中，我们有玩家或学生的姓名和位置。这些排行榜是在数组的帮助下创建的。我们在所有递归操作中使用堆栈，因为函数调用使用堆栈。在网页中，我们利用链表从该网页中的给定 URL 访问另一个网页。优先级队列有助于实现堆和其他数据结构。优先级队列也用于 CPU 的调度算法。为了找到两点之间的最短路径，我们使用图的迪杰斯特拉最短路径算法。12、结论

学好数据结构 打好基础

数据结构是计算机科学最重要的组成部分之一。数据结构有助于提高任何程序的计算能力，并有助于减少解决问题所需的时间。因此，对数据结构有很好的了解是最重要的。