[数据结构与算法]数据结构中的原子、分子和物质

《数据结构中的原子、分子和物质》原文链接，阅读体验更佳！
学习数据结构和算法是写出高效率代码的必由之路，在实际的工作中，我们可能不会亲自去造轮子，比如实现一个排序算法，实现一个红黑树，因为主流语言的库中都包含了常用的数据结构和算法的实现，我们可以直接使用；我们不去亲自造轮子，甚至我们可以没有造轮子的能力，但是，各种各样的轮子具有什么样的特性，适用于什么样的场景我们还是需要了解的，只有这样，我们才能因地制宜，在合适的赛道上选择最合适的轮子，达到最好的效果。

提到数据结构，我们自然而然会想到算法，而我们在讨论算法的时候，又会自然而然想到算法所操作的数据结构。实际上，数据结构和算法是密不可分的，好的数据结构可以造就简单高效的算法，而一些算法的实现也依赖于特定的数据结构。我们只谈数据结构，当然是可以的，我们可以在很短的时间内把几种常见的数据结构都介绍一遍。但是事后我们可能没有什么感觉，如果我们把相应的算法也拿出来研究一下，我们可能才会体会到数据结构背后所蕴含的深意。

比如平衡二叉查找树和红黑树都是特殊的树，但是它们对“树”这个结构的约束不同，造就了它们的不同特性，而对一个大类的数据结构施加不同的约束来解决特定问题的现象也是非常常见的。

通过上面的介绍，你可能觉得，数据结构和算法二者之中是不是数据结构占主导地位呢？其实也不尽然，在很多时候，我们的程序想要做什么才是最重要的。我们的程序是接收输入的数据，进行计算然后输出结果的逻辑机器，在程序这道“美味”里，数据就是我们的柴米油盐，算法就是我们的烹饪技艺，二者相辅相成。但是，巧妇难为无米之炊，所以，这里我们先介绍一下数据，文末再来讨论一下数据结构和算法的关系。

数据结构中的基本概念和术语

• 数据

  数据是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型，也就是说我们这里的数据其实就是符号，而这些符号必须具备两个前提：

  • 可以输入到计算机
  • 能被计算机程序处理

• 数据元素

  数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。比如在人类中，什么是数据元素呀？当然就是人了。

• 数据项

  一个数据元素可以由若干个数据项组成。比如人这样的数据元素，可以有眼睛、鼻子、嘴巴、手、脚等这些数据项，而数据项本身可能是另一个数据元素，数据项和数据元素之间的关系有点像面向对象中对象之间的组合、聚合等关系。

• 数据对象

  数据对象是性质相同的元素的集合，是数据的子集。什么叫性质相同呢？是指数据元素具有相同数量和类型的数据项，比如，还是以人为例，人都有姓名、生日、性别等相同的数据项。

  既然数据对象是数据的子集，在实际应用中，处理的数据元素通常具有相同的性质，在不产生混淆的情况下，我们都将数据对象简称为数据。

什么是数据结构

什么是数据结构呢？有了上面的基本概念和术语的介绍，我们就可以来介绍一下什么是数据结构了。

结构，简单的理解就是关系，比如分子结构，说的就是组成分子的原子之间的排列方式。严格点说，结构是指各个组成部分相互搭配和排列的方式。在现实世界中，不同元素之间不是独立的，而是存在特定的关系，我们将这些关系称为结构。

那数据结构是什么？**数据结构是相互之间存在一种或者多种特定关系的数据元素的集合。**在计算机中，数据元素并不是孤立的、杂乱无章的，而是具有内在联系的数据集合。数据元素之间存在一种或多种特定的关系也就是数据的组织形式。

数据结构是一门研究非数值计算的程序设计中的操作对象，以及它们之间的关系和操作等相关问题的学科。数据结构是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这些结构定义相适应的操作，确保结构经过所规定的操作之后仍能保持原有的结构类型。

通过上面的介绍，我们可以知道数据结构包含两个主要的方面，即逻辑结构和物理结构，数据的逻辑结构指的是反映数据元素之间逻辑关系，其中的逻辑关系是指数据元素前后间的关系，而与它们在计算机中的存储位置无关，逻辑结构主要包含以下几个方面：

• 集合：结构中的元素之间除了“属于同一个集合”之外没有其他关系；
• 线性结构：结构中的元素存在一对一的相互关系；
• 树形结构：结构中的元素存在一对多的关系；
• 图形结构：结构中的元素存在多对多的关系。

数据的逻辑结构也是数据结构所重点关注的内容。

而物理结构则是指数据在计算机存储空间中的存放形式，我们这里的存储空间主要是针对计算机内存而言的，像硬盘、光盘这样的外部存储器的数据组织通常用文件结构来描述。

数据的物理结构应该能正确反映数据元素之间的逻辑关系，这才是最为关键的，如何存储数据元素之间的逻辑关系，是实现物理结构的重点和难点，也就是我们编码的重点和难点，因为落到具体的编码的时候，数据结构所做的其实就是如何用具体的物理结构实现抽象的逻辑结构。

数据的物理结构主要有两种形式，即顺序结构和链式结构：

• 顺序存储结构是把数据存储在连续的内存空间中，其数据元素之间的逻辑关系是通过数据元素在内存中的相对位置来表示的。
• 链式存储结构是把数据存放在任意的内存空间中，可以是连续的，也可以是不连续的，它借助指示元素存储位置的指针来表示数据元素之间的逻辑关系。

结构中的原子、分子和物质

上文中，我们从介绍了一下数据结构的基本概念，对数据结构有了一个定性的认识，但是，在落实到具体的编程语言的时候，数据结构又是如何呈现的呢？本文接下来的内容就简单介绍一下编程语言是如何为数据提供结构的。

提到数据结构我们不自觉得会想到数据类型，没错，无论是什么样的数据，无论数据是有结构的还是没有结构的，在高级程序设计语言中都可以体现为一个数据类型，比如Java语言中的java.util.LinkedList这个数据类型就是一个链表的具体实现。

毫无疑问，LinkedList是有结构的，而java.lang.String也是Java中的一个数据类型，但是String是具有结构的数据类型吗？通常，我们把一个String看做一个单纯的值，我们不认为它是具有结构的，无论其底层的实现是怎样的，也无论一个字符串有多长。

单独的一个数字、一个字符串，我们不能说它是有结构的，因为它就是一个单纯的值；而一个数组我们可以认为它是有结构的，因为它包含自己的元素，是一个存放数据的容器。

1976年，瑞士计算机科学家，Algol W，Modula，Oberon 和 Pascal 语言的设计师 Niklaus Emil Wirth写了一本非常经典的书《Algorithms + Data Structures = Programs》，即算法 + 数据结构 = 程序。

这本书主要写了算法和数据结构的关系，对计算机科学产生了深远的影响。同时这本书也阐明了编程语言的两个方面——数据和对数据的操作。

这本书的第一章中，作者基于Pascal语言阐述了他对结构的理解，并且把结构分为了三个层次，分别为标量数据，基本数据结构和高级数据结构。

标量数据

标量数据的特点是其本身只是代表一个数据，不具有结构信息，或者说我们不用考虑它们的底层是如何实现的，不用考虑它们的结构信息，只需要把它们理解为一个简单的值就可以了。

比如说Python中，所有的值都是引用类型的，也就是所有的值都是对象，但是其中的一些类型比如数字、字符串，我们可以把它们简单的认为他们只是单纯的值。

标量数据是每一门高级语言都会提供的基础设施，而每一个标量数据都有一个对应的数据类型，标量数据的元数据信息就是由其对应的数据类型所提供的，比如Java中的8大基本数据类型和String类。

标量数据是数据结构中的原子，它是不可再分的，是最终的信息载体。

基本数据结构

基本数据结构为我们提供了把标量数据或者其他的数据结构组合在一起的基本手段，数据之间的组合形式其实一共就只有两种：

• 一种是异构或者同构的数据组合成一个有意义的整体，成为一个新的数据类型，本质上其实就是用户自定义数据类型；对应到上文介绍的数据结构的基本术语中，就是数据元素的定义。

• 另一种组合方式是多个同构(或者一定具有某个或者某些相同的特征可以让我们对它们进行一致的看待)的数据组合成一个群体，对应到上文中介绍的数据结构的基本术语中就是对数据对象的定义。

  我们会在这个群体中进行一系列的操作，比如遍历每一个成员、从中寻找某一个或者某一些满足某个条件的成员、修改某一个成员的信息、添加一个新成员等等。

对于这两种数据的组合方式，基本数据结构都可以进行支持。常见的基本数据结构只有四种，分别是数组、结构体、元组和联合体。其中数组和结构体是所有的高级语言都会提供或者提供类似特性的基本数据结构，而元组和联合体并不是所有的语言都提供的基本数据结构。

基本数据结构往往是由语言直接提供的基础设施，使用他们其实在很大程度上是在使用语言的编译器，所以基本数据结构都具有一定的静态特性，尤其是在具有静态类型的高级语言中，基本数据结构一经声明之后其结构信息就不能在运行时发生变化了，比如C语言中的数组在声明之后其长度就是固定的，结构体在声明之后其拥有哪些成员也是固定的，并不能在运行时发生变化，Java中的数组和类也是类似的。

下面我们就简单介绍一下每一种基本数据结构，看看它们分别都对哪些数据组合方式提供支持：

• 数组

  数组是一系列同类型元素的集合，它使用一片连续的存储空间来存储数据，我们可以使用索引的方式对数组中的元素进行随机的访问，数组这种可以随机访问的特性非常重要，比如“散列”这个数据结构，就是利用了数组可以随机访问的特性才能达到近似常量级时间复杂度的搜索。

  数组这种基本数据结构其实是提供了把大量‘同构数据组合成一个群体’这种数据组合方式。

  而且，通常我们都是直接使用数组来表达物理存储结构中的顺序结构。

• 结构体/对象/类

  结构体在不同的语言中称呼可能有所不同，比如C语言，GoLang中我们称之为结构体，在Java中我们称之为类，而在JavaScript中称作对象，它们在逻辑上其实大体是等价的。结构体中存在成员，每个成员都有自己的名称，我们可以通过结构体成员的名称对结构体中的成员进行随机访问。在很多的实现中，结构体也是使用一段连续的内存进行存储的。

  结构体本质上其实就是用户自定义数据类型，它提供了对‘异构数据组合成一个具有意义的整体’这种数据组合方式的支持。

• 元组

  元组其实是综合了数组和结构体的特点，和数组类似的，它使用索引的方式对其中的元素进行随机访问；和结构体类似的，它是把异构的数组组合在一起，和结构体不同的是，它其中的成员没有名称，我们可以认为索引就是他们的名称。

  并不是所有的语言都会提供元组这种特性，比如Java，还有一些语言虽然没有直接提供对元组的支持，但是我们可以使用语言的其他特性来实现类似于元组的特性，比如再Kotlin中我们可以利用解构来实现一个元组类，而且在Kotlin中已经使用Data Class这个特性声明了最常用的二元组和三元组。

• 联合体/共用体

  联合体中可以声明多个成员，每一个成员都有自己的名称，但是在某一个时刻，只有一个成员是活跃的。这就要求联合体所占据的存储空间是它每一个成员所需要的存储空间的最大值。

  提供联合体这种特性的语言并不多，比如C语言就提供了，但是大部分语言都是不提供联合体的。

其实在 《Algorithms + Data Structures = Programs》 一书中，只是提到了数组和结构体这两种基本数据结构，而其书中提出，数组和结构体是每一门高级语言都应该提供的特性，是语言的基础设施。

我们可以认为基本数据结构是数据结构层级中的分子，它具提供了组合原子和其他分子的基本能力。

高级数据结构

高级数据结构最典型的特征就是**随着程序的运行，它的值和结构可能会发生变化。**因此，实现高级数据结构需要更加复杂的技术，最基本的就是动态内存分配技术。

比如我们通常使用指针把结构中的所有元素链接到一起的手段来实现一个链表，常见的高级数据结构有链表、哈希表、树、图等等。到了高级数据结构这个层面，我们已经开始涉及到数据结构中的逻辑结构了。

我们可以认为高级数据结构是数据结构层级中的物质，它们由分子构成(只通过标量数据的组合是无法形成高级数据结构的)，它具有无限的可能性和灵活性。同时我们的数据结构所重点描述的就是高级数据结构。

表示高级结构类型值所需的存储量在编译时是未知的;事实上，它在程序执行过程中可能会发生变化。这需要一些动态存储分配方案，在这种方案中，当相应的值“增长”时，存储会被占用，当值“收缩”时，可能会释放存储用于其他用途。因此，高级结构的表示问题显然是一个微妙而困难的问题，它的解决将严重影响过程的效率和对存储使用的经济性。只有在了解要在结构上执行的原语操作及其执行频率的基础上，才能做出合适的选择。因为语言的设计者和编译器都不知道这些信息，所以建议他从(通用)语言中排除高级结构。

——《Algorithms + Data Structures = Programs》

编程语言一般不会把高级数据结构作为语言的基础设施，而是一般采用标准库的形式对外提供，比如上文中提到过的Java语言中的java.util.LinkedList就是标准库中的一个类，我们也可以基于高级语言所提供的标量数据和基本数据结构这些基础设施来实现自己的高级数据结构。

而高级数据结构，所聚焦的问题其实也是把大量同构的数据组合成一个群体的问题。到了高级数据结构这个层次，基本上对应的就是数据结构中的逻辑结构了，而高级数据结构是使用基本数据结构组合而成，这也就意味着，上文中介绍的基本数据结构实际上是对应了数据结构中的物理结构，其中的数组毫无疑问就是对应的顺序存储结构，而链式存储结构我们需要使用结构体自定义包含指针成员的结构体类型来实现。

总结起来就是，我们在一门高级语言中，使用结构体类似的特性进行数据元素的定义，使用数组类似的特性实现数据结构的顺序存储，在定义数据元素的时候放入指针数据项来实现数据结构的链式存储。

算法和数据结构的关系

这片文章重点的笔墨都用来介绍数据结构了，并没有太多介绍算法的内容，但是这里我还是想阐述一下我对数据结构和算法之间关系的基本理解，为之后的文章做好铺垫。

当计算机在解决一个问题的时候，一般都存在多种不同的方法。对于小型问题，只要管用，采用什么样的方法提现不出太大的差别。但是对于大型问题(或者需要解决大量小型问题的应用)，我们就需要设计和选择能够有效利用时间和空间的方法了。

到底是数据结构决定算法还是算法决定数据结构呢？这一直是一个争论不休的话题。其实在《Algorithms + Data Structures = Programs》对数据结构和算法之间的关系进行了比较详细的论述。

我们的程序是由算法和数据结构组成的，而算法是用来操作数据结构的，这就给我们一种直观的感受——数据比算法更重要，**因为我们必须现有一些数据才能对它们进行操作。**确实，算法的实现强烈得依赖于底层的数据结构，而随着我们对数据结构了解的深入，我们也会深刻体会到，不同的数据结构的特性是不一样的，这也就意味着不同的数据结构执行不同的操作的成本是不一样的，比如数组可以随机访问，而链表的随机访问则只能基于遍历来实现。

这是不是就意味着数据结构决定我们所要使用的算法呢？

其实并不是这样的，我们的程序其实是对现实世界的建模，我们总会定义一组数据来代表真实的情况，而这一选择必须以待解决的问题为指导。**也就是说，我们的程序想要做什么，往往更具有决定性。**比如我们可能需要对大量的数据按照一定的顺序进行遍历，又比如我们可能需要能够非常快速定位到某一个特定的数据，这种待解决问题的场景其实就是我们要施加于数据的操作，也就是算法层面的东西了，这样的场景会在一定程度上决定我们所能采用的数据结构。

而数据结构的选择还受限于我们将要用来解决问题的工具——编程语言的限制。而通常来说，这两个方面都是我们所要考虑的。

数据表示的选择通常是相当困难的，它不是由解决问题的工具唯一决定的，它必须总是按照要对数据进行的操作来进行选择。

总的来说，我认为数据结构和算法的关系是这样的：

• 数据结构是为算法服务的，因为不同的数据结构具有不同的特性，有的数据结构支持的算法，换成另一种结构可能就不行了，比如我们可以对一个有序的数组进行二分查找，但是对于一个有序的链表，我们就无法使用二分查找算法了。在特定的场景中选择合适的数据结构能够使得我们的程序更加简单高效。
• 我们所要对数据进行的操作(我们所要采用的算法)反过来驱动我们进行数据结构的选择。我们的每一个场景都会要求对数据做什么样的操作，而想要对数据做特定的操作必须有能够支持这样操作的数据结构的支持，所以算法在一定程度上能决定我们对数据结构的选择。

总的来说数据结构和算法之间的关系并不是简单的谁决定谁的关系，二者其实是一种互为决定的关系，从物理上来说，数据结构决定了算法，而在逻辑意义上，算法决定了我们对数据结构的选择。

抽象数据类型(ADT)

上文中，我们提到了，不同的数据结构具有不同的特性，进行不同操作的成本是不一样的，所以对于一个数据结构，它不止包含了结构，还应该包含可以应用于该数据结构的操作，从这个角度来看，我们定义一个数据结构本质上其实也是在定义一个数据类型。我们通常使用抽象数据类型来定义一个数据结构。

抽象数据类型(ADT)是一种能够对使用者隐藏数据表示的数据类型。**抽象数据类型的主要特征在于将数据和操作数据的函数实现关联，并将数据表示隐藏起来。**在使用抽象数据类型的时候我们的注意力集中在API描述的操作上而不会去关注数据的表示；而在我们实现抽象数据类型的时候，我们的注意力集中在数据的表示并实现对数据的各种操作。

如果你熟悉面向对象编程，那么通过上面的描述你就可以知道这不就是面向对象中的封装特性吗。是的，如果我们使用一门基于类的面向对象的编程语言比如Java，定义一个抽象数据类型将是意见非常自然的事情——我们只需要定义一个类就好了。

但是在早期的面向过程的编程语言中，自定义的数据类型只能包含状态而不能包含动作，比如C语言中的结构体，我们如果想在结构体中保存动作，那么就只能在结构体中声明一个指向函数的指针，或者是我们需要使用一种被称作抽象数据类型的伪代码来描述一个数据结构，然后在头文件中定义函数对结构体进行操作。

所以，在介绍数据结构和算法的时候，我使用以类为基础的面向对象的Java语言，Java语言中的一个类(class)就是一个天然的抽象数据类型，或者我们可以使用接口定义一组行为。

总结

以上就是我对数据结构和算法的基本理解，本人深知自己技术水平和表达能力有限，文章中一定存在不足和错误，欢迎与我进行交流(laomst@163.com)，跟我一起讨论，修改文中的不足和错误，感谢您的阅读。