1.3　数据的逻辑结构与存储结构

数据结构的主要任务就是通过分析数据对象的结构特征，包括逻辑结构及数据对象之间的关系，并把逻辑结构表示成计算机可实现的物理结构，以便设计、实现算法。

1.3.1　逻辑结构

数据的逻辑结构（Logical Structure）是指在数据对象中数据元素之间的相互关系。数据元素之间存在不同的逻辑关系，构成了以下4种结构类型。

（1）集合结构。集合结构中的数据元素除了同属于一个集合外，数据元素之间没有其他关系。这就像数学中的自然数集合，集合中的所有元素都属于该集合，除此之外，没有其他特性。例如，数学中的正整数集合{5,67,978,20,123,18}，集合中的数除了属于正整数外，元素之间没有其他关系。数据结构中的集合关系就类似于数学中的集合。集合结构如图1-5所示。

（2）线性结构。线性结构中的数据元素之间是一对一的关系。线性结构如图1-6所示。数据元素之间存在先后次序关系，其中，a是b的直接前驱，b是a的直接后继。

（3）树形结构。树形结构中的数据元素之间存在一种一对多的层次关系。树形结构如图1-7所示。这就像学校的组织结构图，学校下面是教学的院系、行政机构及一些研究所。

（4）图结构。图结构中的数据元素是多对多的关系。如图1-8所示就是一个图结构。城市之间的交通路线图就是多对多的关系，a、b、c、d、e、f、g是7个城市，城市a到城市b、e、f都存在一条直达路线，而城市b到城市a、c、f也存在一条直达路线。

图1-5　集合结构

图1-6　线性结构

图1-7　树形结构

图1-8　图结构

1.3.2　存储结构

存储结构（Storage Structure）也称为物理结构（Physical Structure），指的是数据的逻辑结构在计算机中的存储形式。数据的存储结构应能正确反映数据元素之间的逻辑关系。

数据元素的存储结构形式通常有顺序存储结构和链式存储结构两种。顺序存储是把数据元素存放在一组地址连续的存储单元里，其数据元素间的逻辑关系和物理关系是一致的。采用顺序存储的字符串“abcdef”地址连续的存储结构如图1-9所示。链式存储是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的，数据元素的存储关系并不能反映其逻辑关系，因此需要借助指针来表示数据元素之间的逻辑关系。字符串“abcdef”的链式存储结构如图1-10所示。

图1-9　顺序存储结构

图1-10　链式存储结构

数据的逻辑结构和物理结构是密切相关的，在学习数据结构的过程中，你将会发现，任何一个算法的设计取决于选定的数据逻辑结构，而算法的实现则依赖于所采用的存储结构。

如何描述存储结构呢？通常是借助Java、C、C++、Python等高级程序设计语言中提供的数据类型进行描述的。例如，对于数据结构中的顺序表，可以用Java语言中的数组来表示；对于链表，可以用Java语言中的类进行描述，通过引用类型记录元素之间的逻辑关系。