数据结构基础理论

数据（Data）是客观事物的符号表示，是所有能够输入到计算机中并被计算机程序处理的符号的总称。

数据元素（Data Element）是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

数据项（Data Item）是组成数据元素的、有独立含义的、不可分割的最小单位。

数据对象（Data Object）是性质相同的数据元素的集合，是数据的一个子集。

数据结构（Data Structure）是相互之间存在一种或多种特定关系的数据元素的集合。

1、逻辑结构

数据的逻辑结构是从逻辑关系上来描述数据，它与数据的存储无关，是独立于计算机的。

通常有四类基本结构，复杂程度依次递进：

集合结构、线性结构、树结构、图结构。

（1）集合结构：数据元素之间除了“属于同一集合”的关系外，别无其他关系。

（2）线性结构：数据元素之间存在一对一的关系。

（3）树结构：数据元素之间存在一对多的关系。

（4）图结构或网状结构：数据元素之间存在多对多的关系。

（附上本人拙劣的画工画的一张层次图，便于理解和记忆）

2、存储结构

数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构。数据元素在计算机中有两种基本的存储结构，分别为顺序存储结构和链式存储结构。

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

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