1. 廣義表的創(chuàng)建

        如圖所示，廣義表的每一個結(jié)點相互串聯(lián)，有些結(jié)點存儲原子數(shù)據(jù)，有些結(jié)點則存儲另一份廣義表數(shù)據(jù)，我們創(chuàng)建數(shù)據(jù)string ss = "(2,3,4, (1, (3, ( 7,8 ) ),2) )";其基本可以分成4層，每一個層中一個括號表示下一層，在數(shù)學(xué)表示中，我們也常用括號的級數(shù)表示廣義表。

        因此，廣義表的創(chuàng)建就需要進(jìn)行連接，連接的方法是更具tag進(jìn)行判斷本結(jié)點中是Atom（原子）還是Node（結(jié)點），再根據(jù)其中的選擇進(jìn)行相對應(yīng)的連接，可以由如下圖可知。

        對于代碼的書寫，我們首先需要對傳入的字符串進(jìn)行切割，將每一組括號”()”進(jìn)行分割，每一組括號其中就表示的一份新的廣義表，我們需要找到括號并且與這個括號相互匹配的括號數(shù)進(jìn)行對應(yīng)，找到并切割掉，以此分離出表頭串，方便我們進(jìn)行后續(xù)的操作。

void sever(string &str,string &hstr){
    //將非空串str分割成兩部分，hstr是表頭
    int n = str.size();
    int i = -1;
    int k = 0; //k記錄尚未配對的“(” 數(shù)
    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();
     }
}

        我們通過分割以后可以通過上文介紹的方法進(jìn)行指針的相互指引，核心就是要注意tag的判斷，以及Atom/Node域是使用共用體創(chuàng)建的，要注意兩者的空間不可以重疊，嚴(yán)格使用if(){}else{}的語法結(jié)構(gòu)不要亂套。

void CreateGList(GList &L,string s){
    //采用頭尾鏈表存儲結(jié)構(gòu)，創(chuàng)建L
    if(s.compare(emp) == 0) L = NULL;
    else{
        L = (GList)malloc(sizeof(GLNode));
        if(!L) exit(0);
        if(s.size() == 1){ //單個元素，建立原子節(jié)點 
            L->tag = ATOM;
            L->atom = s[0];
        }else{ //表節(jié)點 ,表尾 
            L->tag = LIST;
            GList p,q;
            p = L; //p是指向當(dāng)前子表(表尾節(jié)點)的指針 
            string sub;
            sub = s.substr(1,s.size()-2); //去掉外層括號 
            string hsub;
            do{ //重復(fù)建立n個子表 
                sever(sub,hsub); //sub中分理出表頭串hsub ，同時，sub去除了hsub
                CreateGList(p->ptr.hp,hsub);
                q = p; //記錄p，下面sub不為空，要再建立一個表尾節(jié)點，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. 廣義表的深度

我們只需要根據(jù)表的情況進(jìn)行一個遞歸調(diào)用即可判斷，當(dāng)然需要特判一下空表的情況。

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