什么是数据结构

数据（Data）：从计算机的角度来看，数据是所有能被输入到计算机中且能被计算机处理的符号的集合。它是计算机操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式（二进制码的抽象表示？）。

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

数据元素（Data Element）：数据元素是数据中的一个个体，是数据的基本单位，在计算机中通常作为一个整体来进行考虑和处理。

数据项（Data Object）：一个数据元素可以由多个数据项组成。数据项是具有独立含义的数据最小单位。

数据、数据元素、数据项这三个的关系类似表、元组、属性之间的关系，不过表、元组、属性之间具有确定的关系，而数据、数据元素、数据项之间只有层次关系而没有具体的关系。

数据结构的定义

数据结构：数据结构是指数据以及数据相互之间的联系，可以看成是相互之间具有某种特定关系的数据元素的集合，因此，可以把数据结构看成是带结构的数据元素的集合。

数据结构包含以下几个方面：

数据元素之间的逻辑关系，即数据的逻辑结构（Logical Structure）。
数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物理结构（Physical Structure）。
施加在该数据上的操作，即数据的运算。

所以数据结构由三个部分组成：逻辑结构、物理结构、运算。

数据的逻辑结构（Logical Structure）是从逻辑关系上描述数据（主要是相邻关系，比如栈、队列、链表等），它与数据的存储无关，是独立于计算机的。因此，数据结构可以看作从具体问题中抽象出来的数学模型。
数据的存储结构（Physical Structure）是数据的逻辑结构在计算机存储器中的存储形式，它依赖于特定的计算机语言。
数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一组相应的运算。最常用的运算有：检索（查找）、插入、删除、更新、排序等。

逻辑结构是面向问题的，而物理结构就是面向计算机的，其基本的目标就是将数据及其逻辑关系存储到计算机的内存中。

对于一种数据结构，其逻辑结构总是唯一的，但它可以对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。

逻辑结构（Logical Structure）类型

在不产生混淆的情况下，通常将逻辑结构简称为数据结构。

数据的逻辑结构主要有以下几类：

集合（set）：集合中的元素相互独立，除了同属于一个集合之外，别无其他关系（集合中的元素不能重复）。
线性结构（linear structure）：线性结构中的节点具有一对一的关系，其特点是开始节点和终端节点都是唯一的，除开始节点和终端节点之外，其余节点有且仅有一个前驱，有且仅有一个后继。
树形结构（tree structure）：树形结构中的节点具有一对多的关系，其特点是每个节点最多只有一个前驱，但可以有多个后继，可以有多个终端节点。
图形结构（graph structure）：图形结构中的节点具有多对多的关系，其特点是每个节点的前驱和后继的数量都可以是任意的。

物理结构/存储结构（Physical Structure）类型

物理结构（Physical Structure），也称为存储结构，是指数据的逻辑结构在计算机中的存储形式。

数据是数据元素的集合，那么根据物理结构的定义，实际上就是如何把数据元素存储到计算机的存储器中。存储器主要是针对内存而言的，像硬盘、软盘、光盘等外部存俯器的数据组织通常用文件结构来描述。

数据的存储结构应正确反映数据元素之间的逻辑关系，这才是最为关键的。

数据元素的物理结构（存储结构）形式有四种：

顺序存储（sequence storage）
链式存储（linked storage）
索引存储（indexed storage）
哈希存储（hashing storage）

顺序存储（sequence storage）结构

把逻辑上相邻的节点存储在物理上相邻的存储单元里，节点之间的逻辑关系由存储单元的邻接关系来体现。

这种存储结构其实很简单，说白了，就是排队占位。大家都按顺序排好，每个人占一小段空间，大家谁也别插谁的队。我们之前学计算机语言时，数组就是这样的顺序存储结构。当你告诉计算机，你要建立一个有 9 个整型数据的数组时，计算机就在内存中找了片空地，按照一个整型所占位置的大小乘以 9 ，开辟一段连续的空间，于是第一个数组数据就放在第一个位置，第二个数据放在第二个，这样依次摆放。

优点：节省存储空间，可以实现节点的随机存取（每个节点对应一个序号，由该序号可直接确定节点的存储地址）
缺点：不便于修改（在对节点进行插入、删除的操作时，可能要移动一系列的节点）。

链式存储（linked storage）结构

链式存储（linked storage）结构不需要逻辑上相邻的节点在物理位置上也相邻，节点之间的逻辑关系由附加的指针字段表示。

换句话说，链式存储结构是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。数据元素的存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。

优点：便于修改（在进行插入、删除操作时，只需要修改对应节点的指针域，不必移动节点）。
缺点：存储空间利用率较低（有一部分空间用来存储节点之间的逻辑关系了），不能进行随机存取（因为逻辑上相邻的节点在物理位置上不一定相邻）。

索引存储（indexed storage）结构

该方法通常在存储节点信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中关键字唯一标识一个节点，地址则是指向该节点的指针。

优点：支持随机访问（因为索引表是顺序存储的，类似于 C 语言中的指针数组），具有较高的数据查询和修改效率（在进行插入、删除运算时，只需移动索引表中对应节点的存储地址，而不必移动节点表中的节点的数据）。

缺点：索引存储的方法增加了索引表，降低了存储空间的利用率。

哈希（或散列）存储（hashing storage）结构

该方法根据节点的关键字通过哈希（或散列）函数直接计算出一个值，并将这个值作为该节点的存储地址。

优点：哈希存储方法的优点就是查找数据快（只要给出要查找节点的关键字，就可以立即计算出对应节点的存储地址）。

缺点：哈希存储方法只存储节点的数据，不存储节点之间的逻辑关系。所以，哈希存储方法一般只适合要求能够快速查找和插入的场合。

总结

上面 4种基本的存储方法，既可以单独使用，也可以组合起来使用。同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构，主要根据运算方便和算法的时空要求来决定。

Reference

《数据结构教程（第二版）》

【Data Structure】什么是数据结构