当前位置:首页 » 数据结构练习题 » 正文

题目:广义表的存储结构

1518 人参与  2018年09月10日 21:46  分类 : 数据结构练习题  评论

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

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

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

    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

数据结构  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!