全屏显示专题章节

在上一小节中已给出数据结构的概念，数据结构是指相互之间存在一种或多种特定关系的数据元素集合。这个描述是一种非常简单的解释。数据元素间的相互关系具体应包括三个方面：数据的逻辑结构、数据的物理结构、数据的运算集合。

数据的逻辑结构是指数据元素之间逻辑关系的描述。数据结构的形式定义为：数据结构是一个二元组Data＿Structure＝（D，R），其中D是数据元素的有限集，R是D上关系的有限集。

根据数据元素之间关系的不同特性，通常有下列四类基本的结构。

结构中的数据元素之间除了同属于一个集合的关系外，无任何其他关系。各个数据元素是“平等”的，它们的共同属性是“同属于一个集合”，类似于数学中的集合，如图1－3所示。

结构中的数据元素之间存在着一对一的线性关系，如图1－4所示。

结构中的数据元素之间存在着一对多的层次关系，如图1－5所示。

结构中的数据元素之间存在着多对多的任意关系，如图1－6所示。

如果一个数据结构不是线性结构，可称为非线性结构。显然，在非线性结构中，各数据元素之间的前后继关系要比线性结构复杂，因此，对非线性结构的存储与处理比线性结构要复杂得多。线性结构与非线性结构都可以是空的数据结构。一个空的数据结构究竟是属于线性结构还是属于非线性结构，这要根据具体情况来确定。如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。

存储结构（又称物理结构）是逻辑结构在计算机中的存储映像，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。

数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后继关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间前后继关系的信息。

逻辑结构与存储结构的关系为：存储结构是逻辑关系的映像与元素本身映像。逻辑结构是抽象，存储结构是实现，两者综合起来建立了数据元素之间的结构关系。

数据元素存储结构形式有两种：顺序存储和链式存储。

（1）顺序存储结构

顺序存储结构是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的，如图1－7所示。

顺序存储就排队按顺序站好，每个人占一小段空间。在学习C语言时，数组就是这样的顺序存储结构。要建立一个8个整型元素的数组，计算机就会在内存中开辟一段连续的能存储8个整型数据的空间，数组一个一个存放到空间里。

（2）链式存储结构

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

显然，链式存储就灵活多了，数据存在哪里不重要，只要有一个指针存放了相应的地址就能找到它。

逻辑结构是面向问题的，物理结构是面向计算机的，基本目标就是将数据及其逻辑关系存储到计算机中。存好之后做什么呢，就是运算。

数据的存储不同决定了运算不同。通常，一个数据结构中的元素结点可能是在动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点，也可以删除数据结构中的某个结点（称为删除运算）。插入与删除是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。在对数据结构的处理过程中，不仅数据结构中的结点（即数据元素）个数在动态地变化，而且各数据元素之间的关系也有可能在动态地变化。

如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。在一个空的数据结构中插入一个新的元素后就变为非空；在只有一个数据元素的数据结构中，将该元素删除后就变为空的数据结构。