一、广义表的存储结构

根据广义表的不同形式，可以用线性表、树和图等数据结构或其修改形式来存储和实现广义表。
    对于定长的广义表可以用数组来存储，但是只能顺序地访问。最简单的方法是把括号也作为符号存储在数组中。
    可以使用链表结构存储，广义表结点的定义如下：
template <class T>
class GenListNode {
public:
   int type;  // 表示该结点是ATOM或者SubLIST
   T element; // 如果是ATOM，则存储它的值
   // 如果是LIST ,则指向它的元素的首结点
   GenListNode<T> *child;
   GenListNode<T> *next; // 指向下一个结点
  ...... // 其他函数
};
    然而，不带表头的广义表链在删除结点的时候会出现问题，删除结点data就必须进行链调整。因此，增加一个头指针来标志，简化删除、插入操作。此外，在访问循环链的时候会出现循环访问，所以需要一个标志位来记录该结点是否已经被访问过。
    改进的广义表结点类型如下：
template <class T>
class GenListNode {
public:
   int type;  // 表示该结点是ATOM or LIST
   struct {
      int ref;      // 如果是表头结点则，存储该结点被引用次数
      char* Name;   // 表头名称
      int mark;     // 本子表是否被访问过
   } headNode;
   GenListNode<T> *child;        // 如果是LIST ,则指向子表
   T element;                    // 如果是ATOM，则存储它的值
   GenListNode<T> *next;         // 指向下一个结点
   void GenListTraversal ();     // 周游该结点的子孙
   void GenListTraversalHelp(GenListNode<T> *node);
  ......
};
对应的广义表定义如下：
// GenList是一个原子元素类型为T的广义表
/ /如果要实现能够存储多种数据类型的广义
// 表，只需要嵌套的使用它
template <class T>
class GenList {
private:
    GenListNode<T> *head;    // 头结点,存储头信息
    GenListNode<T> *current; // 当前指针的位置
public:
    GenList(char *Name);
    ~GenList();
    void Insert(T element);      // 在尾部加入一个元素结点
    void Insert(GenList<T> *gl); // 在尾部插入一个子表
    GenListNode<T> *GetHead();   // 取头结点
    GenListNode<T> *GetNext();   // 取当前结点的下一个
    GenListNode<T> *GetPrev();   // 取当前结点的前一个
    void MoveFirst();    // 当前指针指向head
    int Remove();        // 删除当前结点
    void ViewList();     // 周游广义表
};