广义表的实现！

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



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

设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任意操作，另外一个节点都不会出现错误。