广义表的实现

广义表是一种复杂的数据结构,是线性表的扩展,能够表示树结构和图结构。

广义表是一 特殊的结构, 它兼有线性表、 树、图等结构的特点。 从各层元素各自具有的线性关系讲, 它应该是线性表的拓展; 从元素的分层方面讲,它有树结构的特点,但从元素的递归性和共享性等方面讲,它应该属于图结构。总之,它是一种更为复杂的非线性结构

设ai为广义表的第i个元素,则广义表Ls的一般表示与线性表相同:

            Ls=(a1,a2,…,ai,…,an)

其中n表示广义表的长度,即广义表中所含元素的个数,n≥0。如果ai是单个数据元素,则ai是广义表Ls的原子;如果ai是一个广义表,则ai是广义表Ls的子表,每一个ai称为Ls的直接元素。例如,下面的

            Ls=((a,b),c,(d,(e)))

就是一个合法的广义表表达式。

广义表具有如下重要的特性:
(1)广义表中的数据元素有相对次序;
(2)广义表的长度定义为最外层包含元素个数;
(3)广义表的深度定义为所含括弧的重数。其中原子的深度为0,空表的深度为1;
(4)广义表可以共享;一个广义表可以为其他广义表共享;这种共享广义表称为再入表;
(5)广义表可以是一个递归的表。一个广义表可以是自已的子表。这种广义表称为递归表。递归表的深度是无穷值,长度是有限值;

比较有趣的是第五点性质,一个广义表的可以是递归的,子表就是自己,那么就是这样  

        L=(a,L)=(a,(a,(a,(a,(a.......))))) ,这是一个无限的广义表,深度是无穷大,长度为2 。

广义表的结构有很多,有单链表广义表,有双链广义表等。这里描述的是单链广义表,采用以下结构

flag域为标记字段,该字段为0时,第二个域是Data,表示该节点是原子节点,flag为1时,表示该节点是子表,第二个域是SubList,存放子表第一个元素的地址。next是与本元素同一层的下一个元素所在节点的地址,当本元素是所在层的最后一个元素时,next域为NULL。

带头广义表会为每个节点设置一个表节点(称为元素的头结点),下图中,a、b、c、d四个节点的表节点就是橙色的节点,e、f的表节点是b,h、i的表节点的是f,以此类推。

有人可能会问,为什么要有最上面橙色的节点,答案是必须要有。如果没有最上面的橙色节点,那么上图的广义表就应该是 1,(3,((6),5)),2,(4)  ,而不是  (1,(3,((6),5)),2,(4))    去掉最上面橙色的表节点之后,我想求它的深度就很费解,它是指谁?a节点?a节点深度为 0,显然不对的。如果a节点的类型是子表,求出来的就是子表的深度。子表a的下一个节点是b,子表b的下一个节点是c,c的下一个节点是d,这样是四个广义表连在一起,而不是一个广义表!君不见任何一个广义表的表达式最外面都是一对括号嘛。所以我们必须加一个根结点(就是表节点),将a、b、c、d四个广义表作为根结点的子表。


广义表的代码结构设计如下

广义表有几个重要的操作——求广义表的深度、长度、遍历以及复制等。 在广义表中,同一层次的每个节点是通过next域链接起来的,所以可把它看做是由next域链接起来的单链表。这样,求广义表的长度就是求单链表的长度。


对于广义表的深度,等于所有子表中表的最大深度加1,如果为原子,深度为0。使用递归可以很好的解决这个问题。

对于表的遍历,使用递归也可以很快速解决。

广义表的复制也使用递归。


其实这种广义表的结构设计其实是有漏洞的。广义表的双链或单链表示都必须带头结点,否则对共享子表进行头插入和头删除操作将产生错误。举个栗子。

此时b和d是共享一个子表的,子表是e、f。

如果此时b对自己的子表进行头插了一个节点m,那么现在的情况是这样的,d指向的表头是错误的!而且实际情况中可能会有很多个节点共享这个子表。

所以比较完善的设计是为子表添加一个头结点,如下图。此时b和的依然共享一个子表,b和d任意操作,另外一个节点都不会出现错误。