数据结构的图形表示

2.2.2　数据结构的图形表示

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

例如，一天时间的数据结构可以用如图2-1所示的图形来表示。

图2-1　一天时间数据结构的图形表示

又如，反映家庭成员间辈份关系的数据结构可以用如图2-2所示的图形表示。

图2-2　家庭成员间辈分关系数据结构的图形表示

显然，用图形方式表示一个数据结构是很方便的，并且，也比较直观。有时在不会引起误会的情况下，在前件节点到后件节点连线上的箭头可以省去。例如，在如图2-2所示中，即使将“父亲”节点与“儿子”节点连线上的箭头以及“父亲”节点与“女儿”节点连线上的箭头都去掉，同样表示了“父亲”是“儿子”与“女儿”的前件，“儿子”与“女儿”均是“父亲”的后件，而不会引起误会。

例2-3　用图形表示数据结构B=（D，R），其中

D={d_i|1≤i≤7}={d₁，d₂，d₃，d₄，d₅，d₆，d₇}

R={（ d₁，d₃），（d₁，d₇），（d₂，d₄），（d₃，d₆），（d₄，d₅）}

这个数据结构的图形表示如图2-3所示。

在数据结构中，没有前件的节点称为根节点：没有后件的节点称为终端节点（也称为叶子节点）。例如，如图2-1所示的数据结构中，元素“早上”所在的节点（简称为节点“早上”，下同）为根节点，节点“晚上”为终端节点；在如图2-2所示的数据结构中，节点“父亲”为根节点，节点“儿子”与“女儿”均为终端节点；在如图2-3所示的数据结构中，有两个根节点d₁与d₂，有三个终端节点d₆、d₇、d₅。在数据结构中除了根节点与终端节点外的其他节点一般称为内部节点。

图2-3　例2-3数据结构的图形表示

通常，一个数据结构中的元素节点是动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新节点（称为插入运算），也可以删除数据结构中的某个节点（称为删除运算）。插入与删除是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。在对数据结构的处理过程中，不仅数据结构中的节点（即数据元素）个数在动态地变化，而且，各数据元素之间的关系也有可能在动态地变化。例如，一个无序表可以通过排序处理而变成有序表；一个数据结构中的根节点被删除后，它的某一个后件可能就变成了根节点；在一个数据结构中的终端节点后插入一个新节点后，则原来的那个终端节点就不再是终端节点而成为内部节点了。有关数据结构的基本运算将在后面讲到具体数据结构时再介绍。