廣義表

廣義表，又稱列表，也是一種線性存儲(chǔ)結(jié)構(gòu)。同數(shù)組類似，廣義表中既可以存儲(chǔ)不可再分的元素，也可以存儲(chǔ)廣義表，記作：

LS = (a1,a2,...,an)

通常，廣義表中存儲(chǔ)的單個(gè)元素稱為“原子”，而存儲(chǔ)的廣義表稱為“子表”。
注意，A = () 和 A= (())是不一樣的。前者是空表，而后者是包含一個(gè)子表的廣義表，只不過這個(gè)子表是空表。

當(dāng)廣義表不是空表時(shí)，稱第一個(gè)數(shù)據(jù)（原子或子表）為“表頭”，剩下的數(shù)據(jù)構(gòu)成的新廣義表為“表尾”。
除非廣義表為空表，否則廣義表一定具有表頭和表尾，且廣義表的表尾一定是一個(gè)廣義表。

廣義表的存儲(chǔ)

由于廣義表中既可存儲(chǔ)原子（不可再分的數(shù)據(jù)元素），也可以存儲(chǔ)子表，因此很難使用順序存儲(chǔ)結(jié)構(gòu)表示，通常情況下廣義表結(jié)構(gòu)采用鏈表實(shí)現(xiàn)。
使用順序表實(shí)現(xiàn)廣義表結(jié)構(gòu)，不僅需要操作n維數(shù)組（例如{1,{2,{3,4}}}就需要使用三維數(shù)組存儲(chǔ)），還會(huì)造成存儲(chǔ)空間的浪費(fèi)。
使用鏈表存儲(chǔ)廣義表，首先需要確定鏈表中結(jié)點(diǎn)的結(jié)構(gòu)。由于廣義表中可同事存儲(chǔ)原子和子表兩種形式的數(shù)據(jù)，因此鏈表結(jié)點(diǎn)的結(jié)構(gòu)也有兩種，如圖1 所示：

圖1 廣義表結(jié)點(diǎn)的兩種類型

如圖1 所示，表示原子的結(jié)點(diǎn)由兩部分構(gòu)成，分別是tag標(biāo)記位和原子的值，表示子表的結(jié)點(diǎn)由三部分構(gòu)成，分別是tag標(biāo)記位、hp指針和tp指針。

tag標(biāo)記位勇于區(qū)分結(jié)點(diǎn)是原子還是子表，通常原子的tag值為0，子表的tag值為1。子表結(jié)點(diǎn)中的hp指針用于連接本子表中存儲(chǔ)的原子或子表，tp指針用于連接廣義表中下一個(gè)原子或子表。

因此，廣義表中兩種節(jié)點(diǎn)的C語言表示代碼為：

typedef struct GLNode{
  int tag;//標(biāo)志域
  union{
     char atom;//原子節(jié)點(diǎn)的值域
     struct{
        struct GLNode *hp, *tp;
    }prt;//子表結(jié)點(diǎn)的指針域，hp指向表頭；tp指向表尾
  };
}*Glist;

這里用到了union共用體，因?yàn)橥粫r(shí)間此字節(jié)不是原子結(jié)點(diǎn)就是子表結(jié)點(diǎn)，當(dāng)表示原子結(jié)點(diǎn)時(shí)，就使用atom變量；反之則使用ptr結(jié)構(gòu)體。

例如，廣義表{a,{b,c,d}}是由一個(gè)原子a和子表{b,c,d}構(gòu)成，而子表{b,c,d}又是由原子b、c和d構(gòu)成，用鏈表存儲(chǔ)該廣義表如圖2所示：

圖2 廣義表{a,{b,c,d}}的結(jié)構(gòu)示意圖

圖2 可以看到，存儲(chǔ)原子a、b、c、d時(shí)都是用子表包裹著表示的，因?yàn)樵觓和子表{b,c,d}在廣義表中同屬一級(jí)，而原子b、c、d也同屬一級(jí)。

圖2 中鏈表存儲(chǔ)的廣義表用C語言代碼表示為：

Glist createGlist(Glist C) {
    //廣義表C
    C = (Glist)malloc(sizeof(Glist));
    C->tag = 1;
    //表頭原子‘a(chǎn)’
    C->prt.hp = (Glist)malloc(sizeof(Glist));
    C->prt.hp->tag = 0;
    C->prt.hp->atom = 'a';
    //表尾子表{b,c,d},是一個(gè)整體
    C->prt.tp = (Glist)malloc(sizeof(Glist));
    C->prt.tp->tag = 1;
    C->prt.tp->prt.hp = (Glist)malloc(sizeof(Glist));
    C->prt.tp->prt.tp = NULL;
    //開始存放下一個(gè)數(shù)據(jù)元素(b,c,d),表頭為‘b’，表尾為(c,d)
    C->prt.tp->prt.hp->tag = 1;
    C->prt.tp->prt.hp->prt.hp = (Glist)malloc(sizeof(Glist));
    C->prt.tp->prt.hp->prt.hp->tag = 0;
    C->prt.tp->prt.hp->prt.hp->atom = 'b';
    C->prt.tp->prt.hp->prt.tp = (Glist)malloc(sizeof(Glist));
    //存放子表(c,d),表頭為c，表尾為d
    C->prt.tp->prt.hp->prt.tp->tag = 1;
    C->prt.tp->prt.hp->prt.tp->prt.hp = (Glist)malloc(sizeof(Glist));
    C->prt.tp->prt.hp->prt.tp->prt.hp->tag = 0;
    C->prt.tp->prt.hp->prt.tp->prt.hp->atom = 'c';
    C->prt.tp->prt.hp->prt.tp->prt.tp = (Glist)malloc(sizeof(Glist));
    //存放表尾d
    C->prt.tp->prt.hp->prt.tp->prt.tp->tag = 1;
    C->prt.tp->prt.hp->prt.tp->prt.tp->prt.hp = (Glist)malloc(sizeof(Glist));
    C->prt.tp->prt.hp->prt.tp->prt.tp->prt.hp->tag = 0;
    C->prt.tp->prt.hp->prt.tp->prt.tp->prt.hp->atom = 'd';
    C->prt.tp->prt.hp->prt.tp->prt.tp->prt.tp = NULL;
    return C;
}

廣義表的另一種存儲(chǔ)結(jié)構(gòu)

另一套表示廣義表中原子和子表結(jié)構(gòu)的結(jié)點(diǎn)，如圖3所示：

圖3 廣義表的另一套結(jié)點(diǎn)結(jié)構(gòu)

如圖3所示，表示原子的結(jié)點(diǎn)構(gòu)成由tag標(biāo)記位、原子值和tp指針構(gòu)成，表示子表的結(jié)點(diǎn)還是由tag標(biāo)記位、hp指針和tp指針構(gòu)成。

圖3的結(jié)點(diǎn)結(jié)構(gòu)用C語言代碼表示為：

typedef struct GLNode {
    int tag;//標(biāo)志域
    union{
        int atom;//原子結(jié)點(diǎn)的值域
        struct GLNode *hp;//子表結(jié)點(diǎn)的指針域，hp指向表頭
    };
    struct GLNode *tp;//這里的tp相當(dāng)于鏈表的next指針，用于指向下一個(gè)數(shù)據(jù)元素
}*Glist;

采用圖3的結(jié)點(diǎn)結(jié)構(gòu)存儲(chǔ)廣義表{a,{b,c,d}}的示意圖如圖4所示：

圖4 廣義表{a,{b,c,d}}的存儲(chǔ)結(jié)構(gòu)示意圖

圖4 存儲(chǔ)廣義表對(duì)應(yīng)的C語言代碼為：

Glist createGlist(Glist C) {
    C = (Glist)malloc(sizeof(Glist));
    C->tag = 1;
    C->hp = (Glist)malloc(sizeof(Glist));
    C->tp = NULL;
    //表頭原子a
    C->hp->tag = 0;
    C->hp->atom = 'a';
    C->hp->tp = (Glist)malloc(sizeof(Glist));
    C->hp->tp->tag = 1;
    C->hp->tp->hp = (Glist)malloc(sizeof(Glist));
    C->hp->tp->tp = NULL;
    //原子b
    C->hp->tp->hp->tag = 0;
    C->hp->tp->hp->atom = 'b';
    C->hp->tp->hp->tp = (Glist)malloc(sizeof(Glist));
    //原子c
    C->hp->tp->hp->tp->tag = 0;
    C->hp->tp->hp->tp->atom = 'c';
    C->hp->tp->hp->tp->tp = (Glist)malloc(sizeof(Glist));
    //原子d
    C->hp->tp->hp->tp->tp->tag = 0;
    C->hp->tp->hp->tp->tp->atom = 'd';
    C->hp->tp->hp->tp->tp->tp = NULL;
    return C;
}

需要注意的是，無論采用以上哪一種結(jié)點(diǎn)結(jié)構(gòu)存儲(chǔ)廣義表，都不要破壞廣義表中數(shù)據(jù)元素之間的并列關(guān)系。拿{a,{b,c,d}}來說，原子a和子表{b,c,d}是并列的，而在子表{b,c,d}中原子b、c、d是并列的。

廣義表的深度和長(zhǎng)度

廣義表的長(zhǎng)度，指的是廣義表中所包含的數(shù)據(jù)元素的個(gè)數(shù)。
由于廣義表中可以同時(shí)存儲(chǔ)原子和子表兩種類型的數(shù)據(jù)，因此在計(jì)算廣義表的長(zhǎng)度時(shí)規(guī)定，廣義表中存儲(chǔ)的每個(gè)原子算作一個(gè)數(shù)據(jù)，同樣每個(gè)子表也算作是一個(gè)數(shù)據(jù)。

例如，在廣義表{a,{b,c,d}}中，它包含一個(gè)原子和一個(gè)子表，因此該廣義表的長(zhǎng)度為2。
再比如，廣義表{{a,b}}中只有一個(gè)子表{a,b}，因此它的長(zhǎng)度為1。
廣義表規(guī)定，空表{}的長(zhǎng)度為0。
在編程實(shí)現(xiàn)求廣義表長(zhǎng)度時(shí)，由于廣義表的存儲(chǔ)使用的是鏈表結(jié)構(gòu)，有圖2和圖4兩種方式。

對(duì)于圖2來說，只需計(jì)算最頂層含有的結(jié)點(diǎn)數(shù)量，即可求的廣義表的長(zhǎng)度。

同理，對(duì)于圖4來說，由于其最頂層表示的此廣義表，而第二層表示的才是該廣義表中包含的數(shù)據(jù)元素，因此可以通過計(jì)算第二層中包含的結(jié)點(diǎn)數(shù)量，既可得廣義表的長(zhǎng)度。

這里給出計(jì)算圖2中廣義表長(zhǎng)度的C語言實(shí)現(xiàn)代碼：

int GlistLength(Glist C) {
    int number = 0;
    Glist P = C;
    while(P){
        number++;
        P = P->prt.tp;
    }
    return number;
}

廣義表的深度

廣義表的深度，可以通過觀察該表中所包含括號(hào)的層數(shù)間接得到。

圖5 廣義表示意圖

• 依次遍歷廣義表C的每個(gè)結(jié)點(diǎn)，若當(dāng)前結(jié)點(diǎn)為原子（tag值為0），則返回0；若為空表，則返回1；反之，則繼續(xù)遍歷該子表中的數(shù)據(jù)元素。
• 設(shè)置一個(gè)初始值為0的整型變量max，每次遞歸過程返回時(shí)，令max與返回值進(jìn)行比較，并取較大值。這樣，當(dāng)整個(gè)廣義表遞歸結(jié)束時(shí)，max+1就是廣義表的深度。

其實(shí)，每次遞歸返回的值都是當(dāng)前所在的子表的深度，原子默認(rèn)深度為0，空表默認(rèn)深度為1。
計(jì)算圖2中廣義表深度的C語言實(shí)現(xiàn)代碼：

int GlistDepth(Glist C) {
    // 如果表C為空表時(shí)，直接返回深度1
    if(!C) {
        return 1;
    }
    // 如果表C為原子時(shí)，直接返回0
    if(C->tag == 0) {
        return 0;
    }
    int max = 0;// 設(shè)置表C的初始深度為0
    for (Glist pp=C; pp; pp=pp->prt.tp) {
        int dep = GlistDepth(pp->prt.hp);
        if(dep > max) {
            max = dep;//每次找到表中遍歷到深度最大的表，并用max記錄
        }
    }
    // 程序運(yùn)行到此處，表明廣義表不是空表，由于原子返回的是0，而實(shí)際長(zhǎng)度是1，所以，此處要+1
    return max+1;
}

復(fù)制廣義表

對(duì)于任意一個(gè)非空廣義表來說，都是由兩部分組成：表頭和表尾。反之，只要確定的一個(gè)廣義表的表頭和表尾，那么這個(gè)廣義表就可以唯一確定下來。
復(fù)制一個(gè)廣義表，也是不斷的復(fù)制表頭和表尾的過程。如果表頭或者表尾同樣是一個(gè)廣義表，依舊復(fù)制其表頭和表尾。
所以，復(fù)制廣義表的過程，其實(shí)就是不斷的遞歸，復(fù)制廣義表中表頭和表尾的過程。

遞歸的出口有兩個(gè)：

1. 如果當(dāng)前遍歷的數(shù)據(jù)元素為空表，則直接返回空表。
2. 如果當(dāng)前遍歷的數(shù)據(jù)元素為該表的一個(gè)原子，那么直接復(fù)制，返回即可。

針對(duì)圖2 形式的存儲(chǔ)方式，其廣義表的復(fù)制C語言代碼實(shí)現(xiàn)：

void copyGlist(Glist C, Glist *T) {
    // 如果C為空表，那么復(fù)制表直接為空表
    if(!C) {
        *T = NULL;
    }
    else {
        // C不是空表，給T申請(qǐng)內(nèi)存空間
        *T = (Glist)malloc(sizeof(Glist));
        // 申請(qǐng)失敗，程序停止
        if(!*T){
            exit(0);
        }
        (*T)->tag = C->tag;//復(fù)制表C的tag值
        // 判斷當(dāng)前表元素是否為原子，如果是，直接復(fù)制
        if(C->tag == 0) {
            (*T)->atom = C->atom;
        }
        else {//復(fù)制子表
            copyGlist(C->prt.hp, &((*T)->prt.hp));//復(fù)制表頭
            copyGlist(C->prt.tp, &((*T)->prt.tp));//復(fù)制表尾
        }
    }
}

在實(shí)現(xiàn)復(fù)制廣義表的過程中，實(shí)現(xiàn)函數(shù)void copyGlist(Glist C, Glist *T);
其中，Glist *T，等同于：struct GLNode* *T，此為二級(jí)指針，不是一級(jí)指針。在主函數(shù)中，調(diào)用此函數(shù)時(shí)，傳入的是指針T的地址，而不是T。
這里使用的是地址傳遞，而不是值傳遞。如果在這里使用值傳遞，會(huì)導(dǎo)致廣義表T丟失結(jié)點(diǎn)，復(fù)制失敗。

摘自C語言中文網(wǎng)—數(shù)據(jù)結(jié)構(gòu)—廣義表