扫码获取更多资源

●广义表的链式表示及操作实现

由于广义表中元素可以具有不同结构(原子或子表)，很难釆用顺序存储结构表示，通常 釆用链式存储结构，每个数据元素可以使用一个结点表示。广义表的链式表示有两种形式： 头尾链表和扩展线性链表。

●头尾链表

如果广义表非空，则可以分解为表头和表尾；反之，一对确定的表头和表尾可以确定唯 一一个广义表。根据这一性质，广义表可以釆用头尾链表(Head-Tail Linked)存储结构。 由于广义表中的数据元素既可以是广义表也可以是原子，因此在头尾链表中的结点结构也 有两种：一种是表结点，用以存储广义表；另一种是原子结点，用于存储原子。为了区分这 两类结点，在结点中还要设置一个标志域。

表结点：由三个域组成，分别为标志域(tag=l)、指示表头结点的指针域hp和指示 表尾结点的指针域tp,如图5-20(a)所示。

原子结点：由两个域组成，分别为标志域(tag = O)和存储原子数据的值域data,如 图5-20(b)所示。

扩展线性链表

广义表是线性表的一种推广和扩充，因此也可以釆用另一种结点结构的链表表示广义 表，称为扩展线性链表(Extended Linklist).在扩展线性尾链表中的结点结构也有两种：一 种是表结点，用于存储广义表；另一种是原子结点，用于存储原子。为了区分这两类结点， 在结点中也要设置一个标志域。

联系我们：