广义表(二)

点击打开在线编译器,边学边练

1. 广义表的创建

        如图所示,广义表的每一个结点相互串联,有些结点存储原子数据,有些结点则存储另一份广义表数据,我们创建数据string ss = "(2,3,4, (1, (3, ( 7,8 ) ),2) )";其基本可以分成4层,每一个层中一个括号表示下一层,在数学表示中,我们也常用括号的级数表示广义表。

56.png


        因此,广义表的创建就需要进行连接,连接的方法是更具tag进行判断本结点中是Atom(原子)还是Node(结点),再根据其中的选择进行相对应的连接,可以由如下图可知。

78.png

        对于代码的书写,我们首先需要对传入的字符串进行切割,将每一组括号”()”进行分割,每一组括号其中就表示的一份新的广义表,我们需要找到括号并且与这个括号相互匹配的括号数进行对应,找到并切割掉,以此分离出表头串,方便我们进行后续的操作。

void sever(string &str,string &hstr){
    //将非空串str分割成两部分,hstr是表头
    int n = str.size();
    int i = -1;
    int k = 0; //k记录尚未配对的“(” 数
    char ch;    
    do{ //搜索最外层第一个( 
        ++i;
        ch = str[i];
        if(ch == '(') ++k;
        else if(ch == ')') --k;
    }while(i<n&&(ch != ','||k!=0));
     if(i<n){
         hstr =str.substr(0,i);
         str = str.substr(i+1,n-i-1);
     }else{
         hstr = str.substr(0,str.size());
         str.clear();
     }
}


        我们通过分割以后可以通过上文介绍的方法进行指针的相互指引,核心就是要注意tag的判断,以及Atom/Node域是使用共用体创建的,要注意两者的空间不可以重叠,严格使用if(){}else{}的语法结构不要乱套。

void CreateGList(GList &L,string s){
    //采用头尾链表存储结构,创建L
    if(s.compare(emp) == 0) L = NULL;
    else{
        L = (GList)malloc(sizeof(GLNode));
        if(!L) exit(0);
        if(s.size() == 1){ //单个元素,建立原子节点 
            L->tag = ATOM;
            L->atom = s[0];
        }else{ //表节点 ,表尾 
            L->tag = LIST;
            GList p,q;
            p = L; //p是指向当前子表(表尾节点)的指针 
            string sub;
            sub = s.substr(1,s.size()-2); //去掉外层括号 
            string hsub;
            do{ //重复建立n个子表 
                sever(sub,hsub); //sub中分理出表头串hsub ,同时,sub去除了hsub
                CreateGList(p->ptr.hp,hsub);
                q = p; //记录p,下面sub不为空,要再建立一个表尾节点,q记录上一层的p,用以连接q->ptr.tp = q 
                if(!sub.empty()) {
                    p = (GList)malloc(sizeof(GLNode));
                    if(!p)exit(0);
                    p -> tag = LIST;
                    q -> ptr.tp = p;
                }
            }while(!sub.empty());
            q -> ptr.tp = NULL;
        }
    }
}



2. 广义表的深度

我们只需要根据表的情况进行一个递归调用即可判断,当然需要特判一下空表的情况。

int GListDepth(GList L) {
    if(!L) return 1; //空表1
    if(L->tag ==ATOM ) return 0;
    GList pp;
    //遍历同一层,递归下一层,取表尾,取表头,第一步先去一个表头 
    int max;
    for(max = 0, pp =L;pp!=NULL;pp = pp->ptr.tp){
        int dep = GListDepth(pp->ptr.hp) ;
        if(dep > max) max = dep; //这一步比较,是比较同一层的depth 
    }
    return max+1;
}



本文固定URL:https://www.dotcpp.com/course/133

上一课:广义表(一)
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记
Dotcpp在线编译      (登录可减少运行等待时间)