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

内容摘要
广义表的每一个结点相互串联,有些结点存储原子数据,有些结点则存储另一份广义表数据,我们创建数据string ss
文章正文

1. 广义表的创建

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

数据结构59

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

数据结构60

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

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;
}
代码注释
[!--zhushi--]

作者:喵哥笔记

IDC笔记

学的不仅是技术,更是梦想!