线性结构与非线性结构

2.2.3　线性结构与非线性结构

如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。在一个空的数据结构中插入一个新的元素后就变为非空数据结构；在只有一个数据元素的数据结构中，将该元素删除后就变为空的数据结构。

根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。

如果一个非空的数据结构满足下列两个条件：

（1）有且只有一个根节点；

（2）每一个节点最多有一个前件，也最多有一个后件。

则称该数据结构为线性结构。线性结构又称线性表。

由此可以看出，在线性结构中，各数据元素之间的前后件关系是很简单的。

特别需要说明的是，在一个线性结构中插入或删除任何一个节点后还应是线性结构。根据这一点，如果一个数据结构满足上述两个条件，但当在此数据结构中插入或删除任何一个节点后就不满足这两个条件了，则该数据结构不能称为线性结构。例如，如图2-4所示的数据结构显然是满足上述两个条件的，但它不属于线性结构这个类型，因为如果在这个数据结构中删除节点A后，就不满足上述的条件（1）。

图2-4　不是线性结构的数据结构特例

如果一个数据结构不是线性结构，则称之为非线性结构。如例2-2中反映家庭成员间辈分关系的数据结构就属于非线性结构。显然，在非线性结构中，各数据元素之间的前后件关系要比线性结构复杂，因此，对非线性结构的存储与处理比线性结构要复杂得多。

线性结构与非线性结构都可以是空的数据结构。一个空的数据结构究竟是属于线性结构还是属于非线性结构，这要根据具体情况来确定。如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。