广义表的创建及C语言代码实现

广义表的创建及C语言代码实现

广义表（Generalized List）是一种线性表的推广形式，其元素可以是原子也可以是另一个广义表。本文将详细介绍广义表的创建方法及其C语言代码实现，包括字符串切割、广义表创建和深度计算等核心功能。

广义表的创建

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

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

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

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;
        }
    }
}

广义表的深度

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

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;
}