2.2　数据结构概述

数据是信息的载体，是描述客观事物的数字、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号集合。数据结构研究的是关系，即数据元素相互之间存在的一种或多种特定关系的集合。

我们把数据结构分为逻辑结构和物理结构，前者指数据对象中数据元素之间的相互关系；后者指数据的逻辑结构在计算机中的存储方式。

1.4大逻辑结构

（1）集合结构：其中的数据元素除了同属一个集合外，之间没有特别的关系。

（2）线性结构：其中的数据元素关系是一对一的关系。

（3）树形结构：其中的数据元素关系是一对多的层次关系。

（4）图形结构：其中的数据元素关系是多对多的关系。

2.物理结构

物理结构指如何把数据元素存储到计算机的存储器中，主要相对于内存而言，硬盘、软盘、光盘等外部存储器的数据组织常用文件结构来描述。

数据元素的存储结构形式主要有如下两种。

（1）顺序存储结构：把数据元素存放在地址连续的存储单元中，数据间的逻辑关系和物理关系是一致的，如数组。

（2）链式存储结构：把数据元素存放在任意的一组存储单元中，这组存储单元可以是连续的或非连续的。这种存储结构并不能反映其逻辑关系，因此需要一个指针存放数据元素的地址。这样通过地址就可以找到相关联的元素的位置，每个元素具有自己的值和指向其他元素的一个指针。一个形象的例子是在银行等待叫号时我们可以任意移动，但是需要关注是否叫到自己的前一个号。可以看出相比于顺序存储结构，链式存储结构更加灵活。