题目：广义表的存储结构

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

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

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

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

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

本文链接：http://www.54manong.com/?id=353