下载掌阅APP，畅读海量书库
立即打开
数据结构的主要任务就是通过分析数据对象的结构特征，包括逻辑结构及数据对象之间的关系，然后把逻辑结构表示成计算机可实现的物理结构，从而便于计算机处理。本节主要介绍数据的逻辑结构表示和存储结构的表示。
数据的 逻辑结构 （logical structure）是指在数据对象中数据元素之间的相互关系。数据元素之间存在不同的逻辑关系构成了以下4种结构类型。
（1） 集合 。结构中的数据元素除了同属于一个集合外，数据元素之间没有其他关系。这就像数学中的自然数集合，集合中的所有元素都属于该集合，除此之外，没有其他特性。例如，数学中的正整数集合{5，67，978，20，123，18}，集合中的数除了属于正整数外，元素之间没有其他关系。数据结构中的集合关系就类似于数学中的集合。集合表示如图1-3所示。
（2） 线性结构 。结构中的数据元素之间是一对一的关系。线性结构如图1-4所示。数据元素之间有一种先后的次序关系，a、b、c是一个线性表，其中，a是b的前驱，b是a的后继。
（3） 树形结构 。结构中的数据元素之间存在一种一对多的层次关系，树形结构如图1-5所示。这就像学校的组织结构图，学校下面是教学的院系、行政机构及一些研究所。
（4） 图结构 。结构中的数据元素是多对多的关系，图1-6就是一个图结构。城市之间的交通路线图就是多对多的关系，a、b、c、d、e、f、g是7个城市，城市a和城市b、e、f都存在一条直达路线，而城市b也和a、c、f存在一条直达路线。
图1-3 集合结构
图1-4 线性结构
图1-5 树形结构
图1-6 图结构
存储结构 （storage structure）也称为 物理结构 （physical structure），指的是数据的逻辑结构在计算机中存储形式。数据的存储结构应能正确反映数据元素之间的逻辑关系。
数据元素的存储结构形式通常有顺序存储结构和链式存储结构两种。顺序存储是把数据元素存放在一组地址连续的存储单元里，其数据元素间的逻辑关系和物理关系是一致的。采用顺序存储的字符串“abcdef”的存储结构如图1-7所示。链式存储是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的，数据元素的存储关系并不能反映其逻辑关系，因此需要借助指针来表示数据元素之间的逻辑关系。字符串“abcdef”的链式存储结构如图1-8所示。
图1-7 顺序存储结构
图1-8 链式存储结构
数据的逻辑结构和物理结构是密切相关的，今后在学习数据结构的过程中，读者将会发现，任何一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于所采用的存储结构。
如何描述存储结构呢？虽然存储结构涉及数据元素及其关系在存储器中的物理位置，但本书是建立在高级程序设计语言层次上的数据结构的操作，因此不能像上面那样直接以内存地址来描述存储结构，但可以借助高级程序设计语言中提供的数据类型来描述它，例如，可以用C语言中的一维数组类型来描述顺序存储结构用C语言中的自引用类型描述链式存储结构，其中用指针来表示元素之间的逻辑关系。