1. 簡介

數(shù)組可以存儲不允許再分割的數(shù)據(jù)元素，如字符’X’，數(shù)字11，當然他也可以存儲數(shù)組，二維數(shù)組就是一個例子，你可以理解二維數(shù)組的每一行的元素是一列中的對應(yīng)元素的組合。

廣義表是一種線性表，或者說，廣義表是一種線性表的推廣，它屬于多層次的線性表，廣義表中可以存儲不可以再分割的元素，同時也可以存儲一張廣義表（子表），因此適用情況相對靈活。

設(shè)ai為廣義表的第i個元素，廣義表是n（n≥0）個元素的一個序列，若n=0時則稱為空表。,廣義表GL的一般表示與線性表相同，即：

GL=(a1,a2,…,ai,…,an)

其中n表示廣義表的長度，即廣義表中所含元素的個數(shù)，n≥0。如果ai是單個數(shù)據(jù)元素，則ai是廣義表GL的原子；如果ai是一個廣義表，則ai是廣義表GL的子表。

一般來說，廣義表具有如下重要的特性：

（1）廣義表中的數(shù)據(jù)元素有相對次序

（2）廣義表的長度定義為最外層包含元素個數(shù)

（3）廣義表的深度定義為所含括弧的重數(shù)。其中原子的深度為0，空表的深度為1

（4）廣義表可以共享；一個廣義表可以為其他廣義表共享；這種共享廣義表稱為再入表

（5）廣義表可以是一個遞歸的表。一個廣義表可以是自已的子表。這種廣義表稱為遞歸表。遞歸表的深度是無窮值,長度是有限值

（6）任何一個非空廣義表GL均可分解為表頭head(GL) = a1和表尾tail(GL) = ( a2,…,an) 兩部分。 

2. 廣義表的結(jié)點設(shè)計

我們以常規(guī)方法來看，廣義表是一種不定規(guī)模的數(shù)據(jù)結(jié)構(gòu)，很難為之分配具體的空間，因此創(chuàng)建的方法采用動態(tài)的鏈式方法，動態(tài)的創(chuàng)建空間。

如圖：

        對于每一個結(jié)點而言由如上三大部分組成，其中Tag域為標志字段，其只有兩個參數(shù)，0或者1（Tag域使用int類型，在某些情況下因為只需要簡單判斷也可以使用更短的類型，如bool）；Atom/Node域的內(nèi)容由tag標志決定，當Tag為0時表示該節(jié)點是原子結(jié)點（即存放原子數(shù)據(jù)），當Tag為1時表示該節(jié)點為指向下一個廣義表的指針（即表結(jié)點），Link域存放與本元素同一層的下一個元素所在的結(jié)點地址，當本元素時所在層的最后一個元素時，Link域為NULL；

        鏈式法設(shè)計：

#define AtomType int
typedef enum{ATOM,LIST}ElemTag; //ATOM = 0：原子；LIST = 1:子表 
/*結(jié)點設(shè)計*/
typedef struct GLNode{
    ElemTag tag; //枚舉類型的標志域，只能取定義了的枚舉值
    union{   //union聯(lián)合體，下面兩部分只能取其一；要么取AtomType;要么取結(jié)構(gòu)體ptr,ptr包括兩個指針hp,tp 
        AtomType atom;
        struct{
            struct GLNode *hp,*tp;
        }ptr;
    }; 
}*GList; //定義廣義表類型，GList為指針

下面是子表法設(shè)計：

/*線性表存儲之擴展線性表 = 子表法*/ 
typedef struct GLNode{
    ElemTag tag;
    union{
        AtomType atom;
        struct GLNode *hp;    //對于列表，hp指向本列表內(nèi)部第一個元素，而tp是指向本層次上的下一個元素 
    };                        
    struct GLNode *tp;
} *GList;

        首先定義AtomType的數(shù)據(jù)類型，可以為基本的int型，也可以為一些其他的數(shù)據(jù)類型，包括簡單的char或者是復(fù)雜一些的結(jié)構(gòu)體，不過這里不建議創(chuàng)建過于復(fù)雜的結(jié)構(gòu)體。

其次，關(guān)于tag域的建立，我們可以使用一個枚舉建立，分別表示Atom/Node到底取何種值，而關(guān)于Atom/Node域，則可以建立一個union（共用體）來表示，共用體公用內(nèi)存空間，只能取其一賦值，這也符合廣義表的基本需求；而關(guān)于表達的Link域，我們使用鏈式的存儲方法可以化簡，而使用子表的方式則必須表達。