数据结构

1、数据结构的定义

数据结构（Data Structure）是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

数据结构包括逻辑结构和存储结构两个层次。

2、逻辑结构

数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
数据的逻辑结构有两个要素：一是数据元素；二是关系。数据元素的含义如前所述，关系是指数据元素间的逻辑关系。根据数据元素之间关系的不同特性，通常有四类基本结构，如图所示。它们的复杂程度依次递进。

四类基本逻辑结构关系图下面四种结构中所举的示例是以某班级学生作为数据对象（数据元素是学生的学籍档案记录），来分别考察数据元素之间的关系。
（1）集合结构数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。
（2）线性结构数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。
（3）树结构数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多个组长，每位组长管理多名组员，从而构成树形结构。
（4）图结构或网状结构数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图状结构或网状结构。

其中集合结构、树结构和图结构都属于非线性结构。

3、存储结构

数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构。把数据对象存储到计算机时，通常要求既要存储各数据元素的数据，又要存储数据元素之间的逻辑关系，数据元素在计算机内用一个结点来表示。数据元素在计算机中有两种基本的存储结构，分别是顺序存储结构和链式存储结构。

（1）顺序存储结构顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。

对于前面的“学生基本信息表”，假定每个结点（学生记录）占用50个存储单元，数据从0号单元开始由低地址向高地址方向存储，对应的顺序存储结构如表所示。

顺序存储结构

（2）链式存储结构顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。

假定给前面的“学生基本信息表”中的每个结点附加一个“下一个结点地址”，即后继指针字段，用于存放后继结点的首地址，则可得到如表所示的链式存储结构。从表中可以看出，每个结点占用两个连续的存储单元，一个存放结点的信息，另一个存放后继结点的首地址。

链式存储结构

为了更清楚地反映链式存储结构，可采用更直观的图示来表示，如“学生基本信息表”的链式存储结构可用如图所示的方式表示。