1.1.2　数据结构

1.数据结构研究和讨论的问题

数据结构主要研究和讨论以下三方面的问题：

①数据的逻辑结构。数据集合中各数据元素之间固有的逻辑关系。

②数据的存储结构。对数据进行处理时，各数据元素在计算机中的存储关系。

③对各种数据结构进行的运算。

2.数据元素及其联系

数据元素具有广泛的含义，一般来说，现实世界中客观存在的一切个体都可以是数据元素。在具有相同特征的数据元素集合中，各个数据元素之间存在某种关系，这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系来描述。前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义随具体对象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。

3.数据的逻辑结构

数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构有两个要素：数据元素的集合、各数据元素之间的前后件关系。

4.数据的存储结构

数据的逻辑结构在计算机存储空间中的存放方式称为数据的存储结构，又称数据的物理结构。

一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等。而采用不同的存储结构，其数据处理的效率是不同的。

5.数据结构的图形表示

一个数据结构除了用二元关系表示外，还可以直观地用图形表示。在数据结构的图形表示中，对于数据集合中每一个数据元素用中间标有元素值的方框表示，一般称为数据结点，简称结点。为了进一步表示各数据元素之间的前后件关系，用一条有向线段从前件结点指向后件结点。

在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点（又称叶子结点）。数据结构中除了根结点与终端结点外的其他结点一般称为内部结点。

例如：描述一年四季的季节名如图1-1-2所示。其中，春是夏的前件，夏是春的后件，春是根，冬是终端结点（叶子结点）。

6.线性结构与非线性结构

根据数据结构中各数据元素之间前后件关系的复杂程度，分为线性结构与非线性结构，如果一个非空的数据结构满足下列两个条件：①有且仅有一个根结点；②每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构，又称线性表。

如果一个数据结构不是线性结构，则称为非线性结构，如图1-1-3所示。对非线性结构的存储与处理比线性结构要复杂得多。