为什么写这篇文章

《数据结构》这门课有很多教材，各种概念十分混乱。为了解决概念之间的矛盾，写下这篇博客。
比如严蔚敏的书中存在数据类型和数据结构的混乱，数据类型和ADT的混乱。书上所写本就自相矛盾，因此引用严书中的内容所写的文章或者录制的慕课大概率是存在问题的。

计算机科学的各种定义是对实践经验的总结，掺杂了人的主观意识，也就是人为规定的，很多定义，包括数据 结构，至今没有被公认，不像自然定理一样亘古不变，所以建议从历史发展的角度，结合实践经验理解，不要死记硬背，但不是不要记！

信息与数据

数据是信息的载体,是描述客观事物的数字、字符、图片、声音等符号的集合，所有的数据在计算机中以二进制比特的形式表示。
信息是数据的内涵。
少量数据可能包含很多信息。似乎所有的数据都可能有用，正如黑格尔所说的“存在即合理”。

数据、数据对象、数据元素、数据项之间的关系
数据元素是数据的基本单位，也称为元素、记录等，通常作为一个整体考虑。
数据项是组成数据元素的具有独立含义的、不可分割的最小单位。
数据对象是性质相同的数据元素的集合。

程序执行中所用的数据都存于内存。任何数据对象在能用期间都有存储位置，占据一定数量的存储单元。内存单元按顺序排，每个单元有一个称为内存地址的编号，内存数据都是通过地址访问的。高级语言把存储单元、地址等低级概念用变量等高级概念掩盖起来，使写程序时可以不必过多关心这方面细节。但内存与地址等仍是最基本的重要概念 。

个人感觉，严书两个版本对数据元素的理解有不同。这从对数据结构的定义的差别中可以感受到。详见后文存储结构部分。
若是按照严书¹ 理解，数据元素和关系区别开。
若是按照严书²理解，数据元素包括数据和逻辑关系，即表示关系的数据也算是数据元素或数据元素的一部分。

数据类型

数据类型的本质是固定内存大小上的储存方案和操作方案。
数据类型关注的是比特组合表示什么，也就是怎么用比特组合表示数据的问题，关注的是一个数据元素的data representation。

数据类型的概念最早出现在高级程序设计语言，发源于硬件，是一种解释计算机中的数据的手段，是一个抽象的概念。
计算机内所有的的数据都是二进制数字，电路工程师设计一个CPU，需要人工制定一个规则来使用数据，要考虑如何对数字进行编码表示，并根据编码规则设计加法器、乘法器等。
如果没有了这个规则，就说不清比特串代表什么，不知道从哪里开始到哪里结束代表一个数字，有可能8个比特代表一个整数，有可能16个比特代表一个整数，也可能是浮点数或者其他的数。
工程师将数字按类别分组，用一个编码方式解释一个类里的所有数字，不同类的数字采用不同的编码方式。这个方法算是一种简单的抽象，毕竟总不能一个数字专门定制一个规则。

写程序也就是要描述怎么表示数据并处理数据。
高级程序设计语言，在硬件提供的编码方式的基础上，继续将数据抽象分类，使属于同一类型的数据具有相同的编码规则，并为程序员提供了数据描述机制。
比如C语言，将若干位的比特数字规定为整型数字，并命名为int类型，还提供声明和定义机制，如int a；标识符a表示内存中的一块区域，按照int类型的规定使用这块区域。
这种描述数据的机制，在程序设计中被规范地称为数据类型。

数据类型规定了一类数据所有可能取值的范围，以及在这些值上允许进行的操作。可能所有的CPU都提供int类型，但如果编码方式不同，能在其上进行的操作的过程不同，电路实现不同，严格地讲，就不能算作同一种数据类型。
在计算机发展初期，计算机主要处理数值计算问题，整数、浮点数等是经常用到的运算对象，所以CPU一般会支持整数、浮点数等数字的计算。整数、浮点数等数据模型简单，不需要设计复杂的存储方法，因此不重视数据结构。

使用某种编程语言编写的代码相对于编译后的比特流代码是抽象的，用高级编程语言定义的数据类型相对于CPU支持的数据类型是抽象的。从这个角度也可以说用高级编程语言定义的数据类型，是抽象数据类型。

随着程序设计的规范，抽象数据类型被提出。抽象数据类型（Abstract Data Type，简称ADT）是数据类型的数学抽象，是一个数学模型以及定义在该模型上的一组操作，不考虑其具体实现，也不依赖特定的编程语言。

严蔚敏的数据结构中说，数据类型和抽象数据类型实质上是一个概念¹。个人认为将两个概念当作一个是不严谨的。
书中说是一个概念，是因为书中认为，对于使用数据类型的普通用户来说，不必了解的细节都被封装了，尽管实现不同，但数学特性相同，在用户看来都是一样的。
但数据结构的思想不依赖于特定的编程语言，数据结构这门课从数据结构的逻设计出发，最终深入底层讨论数据的存储方法，逻辑和物理要区分开。
数据类型即使封装了细节，还是已经包含了具体实现，而抽象数据类型并不涉及具体实现。当然我们在实际使用中，也确实对两个概念几乎完全不做区分，是因为大多时候我们不依赖于数据类型的实现细节，但这不代表不知道如何实现，有时也需要考虑数据类型的实现。

对于高级的程序员，要多多少少对实现方法具备一些了解，即使不考虑数据类型的实现，也要或多或少地考虑程序设计语言的特性，并不是完全只需要考虑其数学上的抽象特性。
对于依赖实现细节的硬件工程师来说，数据类型和抽象数据类型显然是不一样的。

数据结构

数据在内存或者硬盘中不是胡乱存储的，就像图书馆的书不是随便放在书架上的，所以为了研究怎么摆放计算机中的数据更好，就有了《数据结构》这门课。

什么是数据结构

数据结构是(数据对象)与(对象中数据元素之间的关系）的集合，是（逻辑上） 组织、（物理上）存储数据的方法，当然在计算机里也是数据，当然也是一门课。
数据结构关注的是数据对象的data strorage。

数据结构起源于程序设计，并随着程序设计的发展而发展。人们在进行程序设计时通常关注两个重要的问题，一是如何将待处理的数据存储到计算机内存中，二是如何设计相应的算法操作这些数据，即数据处理。数据表示的本质是数据结构设计，数据处理的本质是算法设计。
计算机发展初期，人们使用计算机主要处理数值计算问题，所涉及的运算对象是简单的整数、浮点数、字符及布尔型数据，不需要设计复杂的存储方法，因此不重视数据结构。
非数值计算的问题越来越重要，如何表示数据成为重要的问题，数据结构及抽象数据类型被提出，从而使程序设计越来越规范。

在早期的面向过程的结构化程序设计中，程序设计一般原则——程序=数据结构+算法，就是先分析数据的数学模型和要对其进行的操作，确定如何存储数据和怎么实现操作，在这之后编写程序就很容易了。
而结构化程序设计中，数据和过程分离，所以把数据结构定义为二元组（D，S），D为数据元素的有限集，S为关系的有限集，未考虑数据结构上的操作。由于结构化程序设计影响深远，所以习惯性地把数据结构定义为二元组。

在面向对象程序设计中，数据结构可以看作一个容器对象。利用面向对象的开发方式，数据和过程放在一起，所以有时候，数据结构又包含了其上的操作，变成了三元组（D，S，P）。
而我们上这门课，肯定是要讨论数据结构上的操作的，所以用面向对象的方法描述数据结构更合适。

数据结构，作为一门课程，这门课研究的是（数据的逻辑上的组织方法和物理上的存储方法），也就是（先把数据模型化，再研究如何放在计算机里表示）。这门课不是程序设计课2.0，而是要通过精心设计数据结构，为程序带来更高的运行或者存储效率。

所以数据结构包含逻辑结构和存储结构两个层次（不是并列）。
编写程序将逻辑结构映射成存储结构，并实现可在数据结构上进行的各种操作。

以下几条来自不同教材里对数据结构的定义，对比体会。

1. 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。¹²
   个人认为，这句话把关系作为数据元素的定语，关系和数据元素的地位不够平等。书中也说这是书中的一种简单解释。而且第二版²由此出发的对存储结构的定义让人感觉有些疑惑。
2. 数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。³
3. 数据结构是ADT的物理实现。⁴
   如果把数据结构当成一个容器对象，这个对象的抽象类，即ADT。 编程是在描述解决问题的办法，则在编程中，ADT的实现是对（组织、存储数据的方法和对数据进行的操作）的抽象模型的具体描述。想一想编程中如何实现数据结构，比如C语言，差不多就是声明结构类型和函数，将其定义，再初始化，好像很大一部分工作就是在实现某种ADT，也就是在具体描述组织、存储数据的方法和对数据进行的操作。在程序运行时，ADT的物理实现就可以是一个容器对象。

逻辑结构

逻辑结构从逻辑关系上描述数据，也就是数据的数学模型，与数据的在计算机中的存储无关。这个模型考虑的不只限于现有的有限数据，还要考虑范围更广的同类的数据。

任意一个数据元素可以和n（n>=0）个数据元素有逻辑上的关系。
逻辑结构可以分为四类：

• 多对多的关系为图结构或网状结构；
• 一对多为树结构；
• 一对一为线性结构；
• 除了同为一个集合外，别无其它关系为集合结构。
  逻辑结构也可以分为 线性结构 和 非线性结构两大类。
  可以认为，图结构表示的关系最复杂；树是一种特殊的图；线性结构是一种特殊的树结构，也是一种特殊的图结构；集合是没有关系的图结构。

存储结构

若是按照严书¹，数据元素和关系区别开。
​数据结构在计算机中的表示（又称映像）称为数据的物理结构，又称存储结构。它包括数据元素的表示和关系的表示。
​数据元素的位串称为元素或节点，他的子位串称为数据域。因此元素或结点可看成是数据元素在计算机中的映像。

若是按照严书²，数据元素包括数据和逻辑关系。
​ 数据对象在计算机中的存储表示称为数据的存储结构。把数据对象存储到计算机时，通常既要存储各数据元素的数据，又要存储数据元素之间的逻辑关系。

严书¹提到数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像。
按照严书¹的理解，重点在关系的表示。

1. 顺序映像，借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，即通过相对位置来寻址。
2. 非顺序映像，使用地址表示数据元素之间的逻辑关系。比如为了表示结点之间的关系，给每个结点附加指针字段，用于存放后继元素的存储地址。

个人理解，顺序映像本质上是隐式表示关系，非顺序映像本质上是显式表示关系。
综合使用顺序映像和非顺序映像来存储数据，总结起来有四种基本方法，即殷人昆的书提到顺序存储方法、链式存储方法、索引存储方法和散列存储方法。⁵

1. 顺序存储方法，该方法把逻辑上相邻的元素放到物理位置上相邻的存储单元中，数据元素之间的逻辑关系由顺序映像表示，也就是有存储单元的邻接位置关系来体现。由此得到的存储表示称为顺序存储结构。所谓的顺序不只包括无间隔的紧邻，诸如间隔k个字节，a^k个字节，都算是顺序存储。

2. 链式存储方法，该方法不要求逻辑上相邻的元素在物理上相邻，㢝之间的逻辑关系由附加的指针指示。由此得到的存储表示称为链式存储结构。

   1和2基本上是两个极端。顺序存储结构占用内存严重，链式存储结构寻址困难，综合两者的特性，做出寻址容易，插入删除也容易的数据结构。

3. 索引存储方式，采用附加的索引表的方式来存储节点信息的一种存储方式。索引表由若干索引项组成。索引存储方式中索引项的一般形式为(关键字、地址)。

4. 散列存储方法，根据结点的关键字计算直接得到该结点的存储地址。

四种基本存储方法，既可单独使用，也可组合使用。
同一种逻辑结构使用不同的存储方法可以实现不同的存储结构。

严书²提到数据元素在计算机中有两种基本的存储结构，分别是顺序存储结构和链式存储结构。
按照²的理解，有这两种基础的存储结构，可以组合成其他数据结构的存储结构，比如，散列表。

总之，存储结构是逻辑结构在计算机中的物理映射，也就是抽象的数据在内存里的物理实现。
把数据存储到计算机中，通常既要存储数据元素，又要存储数据元素之间的逻辑关系。
存储结构=物理结构=存储表示=物理表示=存储映像=物理映像

ADT、数据类型、数据结构之间的关系

不同语言的《数据结构》

数据结构考虑的是数据对象的Data storage——怎么存数据对象的问题，而数据类型考虑的是数据元素的Data representation——怎么表示数据元素的问题。

⁶为了描述数据，程序语言提供的数据机制必须足够丰富，以满足人们写程序的实际需要。程序语言的机制不能无限地庞大，使语言过分臃肿，难以使用；这些机制也不应过于低级，一直需要描述一点点东西都非常繁琐。 后面这种情况正是机器语言和汇编语言的一个弱点。
经过几十年的研究和实践，目前高级语言领域在这个方面已经形成了一套公认有效的方式，一般语言都采用这种模式的数据机制，其基本框架包括几个互相联系的方面：

1. 把语言要处理的数据对象划分为一些类型，每个类型是一个数据值的集合。例如C语言里的int类型是这个类型能够表示的所有合法整数值的集合。
2. 提供一组基本数据类型，为他们确定书写方式，提供一组相关的基本操作（运算），以支持程序中队基本数据类型的表示和使用。
3. 提供了一组由简单的数据类型或数据对象构造更加复杂的数据类型或数据对象的手段，反复使用这些手段可以一层层地构造起任意复杂的数据结构，以满足程序中处理复杂数据的需要。

市面上有各种语言的数据结构的书，但是程序设计语言只是一种描述数据结构的工具，我们当然可以不使用数据类型这个概念，可以不用某种高级程序设计语言，可以直接用01比特，可以只用自然语言描述数据结构，《数据结构》这门课归根结底是要想办法有组织地把01比特存储在内存中。
不过为了简化描述抽象算法，分类与评价数据结构，使用高级程序设计语言，尤其是其中的ADT的概念，来讲解数据结构。
ADT的思想和面向对象是一致的，我们既要考虑数据结构，也要考虑其上的操作，所以用面向对象的方法描述数据结构比较方便、有效，但本课程大都在大学低年级开设，用C语言的描述方法更符合学生的实际情况。
数据结构是一门介于软件和硬件之间的课，重要的不是用什么语言，而是要理解数据逻辑上的组织方式和在内存中的存储方式，所以说这门课不是程序设计课。

数据结构与抽象数据类型

网友认为数据结构是一种抽象的封装，我们平时写程序都是直接去调用这些数据结构，而没有去想它们的内部实现是怎样的。
这种想法有些不严谨。网友说的是编程语言的数据类型。
使用某种编程语言编写的代码相对于编译后的比特流代码是抽象的，用高级编程语言定义的数据类型相对于CPU支持的数据类型是抽象的。从这个角度也可以说用高级编程语言定义的数据类型，是抽象数据类型。
《数据结构》这门课使用哪门语言不重要，重要的是抽象地描述，所以有的教材直接使用ADT的概念，而不是数据类型。
可以认为，抽象数据类型，是逻辑结构+运算在程序设计中的等价概念，是数据结构的接口描述。

从程序设计的角度看，抽象数据类型使用不同的存储方法可以实现不同的数据类型，然后在程序运行中，数据类型体现为代码段中的对内存空间的操作指令，比如取多少个字节作为操作数放进寄存器或者将多少个字节写回内存等，从而规范了数据在内存中的存储，从而把逻辑结构表示为存储结构，并实现算法。例如，列表的抽象数据类型可以以数组或链表为基础来实现为数据类型。
对于可操作数据对象完全相同的数据类型，如果给它定义具有不同功能的一组，则可形成不同的抽象数据类型。例如队列和优先级队列，它们可能使用相同的顺序表结构来实现为数据类型，但队列是先进先出，优先级队列是优先级高的先出，具有各不相同的服务，是不同的抽象数据类型。

我们平时编程中调用的是封装好的数据类型或者数据类型模板，利用某种数据类型定义数据，把数据组织、存储成数据结构。
比如C++的STL的vector，他是一个顺序型容器类模板，我们可以利用 vector类模板，定义一个可以存储并管理int类型数据的vector< int >类型的容器，容器是一个能存储并管理对象的对象。这个对象与存储在对象中的其他对象一起构成了一个数据结构，也就是带有关系的数据元素的集合。

一般我们在高级程序设计语言的层面进行软件设计。抽象数据类型处于软件层面，是编程语言理论的概念。而数据结构是在硬件和软件之中都有被用到，和语言无关，关注的是数据逻辑上的组织方式和在内存中是怎么存储的，最终还是要实现为01比特流。在编程中，我们使用数据类型描述组织、存储数据的方式和操作。在程序运行中，把数据元素组织、存储成带关系的数据元素的集合，也就是数据结构的存储结构。

反过来说，数据结构是组织和存储的方法，而不是操作方法。我们可以把组织和存储的方法和操作方法结合并抽象成数据类型，在更高的层次上进行软件分析和设计。

抽象数据类型的概念与面向对象方法的思想是一致的。。。。未完待续

未完待续

孤立地理解某一个概念，而不注意他们之间的联系是不可取的。
比如，我们想定义一个整数类型，数学里的整数取值范围是无穷的。
由于CPU的工作机制决定了它每次计算的数得是定长的，而定长就表示它只能表示有限范围内的数。虽然只要内存无限，当然可以设计出没有位数上限的整数运算的硬件。但是CPU为了通用，只提供最基本数据类型，不提供其他多余的功能。
那么我们通过软件的方式来实现一个取值范围无穷的整数类型，使用高级程序设计语言提供的int类型构造这个ADT，显然逻辑上是线性结构，存储上可以选择链表或者顺序表。

未完待续