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

1．逻辑结构

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

（1）集合。该结构中的数据元素除了同属于一个集合外，数据元素之间没有其他关系。例如，在正整数集合｛1，2，3，5，6，9｝中，数据元素除了属于正整数外，不存在其他关系。集合表示如图1-1所示。

（2）线性结构。该结构中的数据元素之间是一对一的关系，数据元素之间存在一种先后的次序关系。正在餐厅排队就餐的顾客就是一个线性结构，A、B、C分别是排队的3名顾客，其中，A排在B的前面，B排在A的后面。线性结构如图1-2所示。

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

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

图1-1　集合结构

图1-2　线性结构

图1-3　树形结构

图1-4　图结构

2．存储结构

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

数据元素的存储结构形式通常有两种：顺序存储结构和链式存储结构。顺序存储是把数据元素存放在一块地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的，即逻辑上相邻的元素，其物理位置也相邻。在C/C++/Java语言中，通常采用数组作为顺序存储结构存放元素。数组a［］存储各元素的情况如图1-5所示。在链式存储结构中，逻辑上相邻的元素，其存储位置不一定相邻，分配的一组存储单元可以是连续的，也可以是不连续的，为了表示元素之间的逻辑关系，需要用一个被称为“指针”的数据域指示数据元素的存放位置，这样通过地址就可以找到相关联数据元素的位置。链式存储结构如图1-6所示。

图1-5　顺序存储结构

图1-6　链式存储结构

数据的逻辑结构和物理结构是数据对象的逻辑表示和物理表示，数据结构要对建立起来的逻辑结构和物理结构进行处理，就需要建立起计算机可以运行的程序集合。