根据广义表的不同形式，可以用线性表、树和图等数据结构或其修改形式来存储和实现广义表。

对于定长的广义表可以用数组来存储，但是只能顺序地访问。最简单的方法是把括号也作为符号存储在数组中。

可以使用链表结构存储，广义表结点的定义如下：

    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();     // 周游广义表    };

来源：我是码农，转载请保留出处和链接！