廣義表
廣義表的定義
廣義表的存儲(chǔ)結(jié)構(gòu)
廣義表的M元多項(xiàng)式
廣義表的遞歸算法

一立轧、廣義表的定義：
廣義表(Lists尚揣，又稱列表)是一種非線性的數(shù)據(jù)結(jié)構(gòu)翠拣，是線性表的一種推廣闸英。
廣義表一般記作 LS = (d1,d2,....,dn);
其中LS是廣義表的名稱,n是它的長(zhǎng)度;

單元素（數(shù)據(jù)元素）和子表（廣義表）
表頭（第一個(gè)元素d1）、表尾（剩余元素組成的表）

二钝凶、廣義表的存儲(chǔ)結(jié)構(gòu)：
首先我們看一下順序存儲(chǔ)結(jié)構(gòu)仪芒，如：?jiǎn)卧亍⒆颖砀荨卧氐嗝⒆颖怼⒆颖怼?br> 可以看出這樣存儲(chǔ)很復(fù)雜哟沫，你不知道要分配多少存儲(chǔ)空間給一個(gè)元素饺蔑。

廣義表順序存儲(chǔ)結(jié)構(gòu)舉例.png

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：
每個(gè)數(shù)據(jù)元素用一個(gè)結(jié)點(diǎn)表示。（兩種類型的結(jié)點(diǎn)：表結(jié)點(diǎn)和元素結(jié)點(diǎn)）

廣義表的兩種結(jié)點(diǎn).png

（頭尾鏈表存儲(chǔ)表示）
可以看到嗜诀，結(jié)點(diǎn)內(nèi)容包含這些信息
表結(jié)點(diǎn)：標(biāo)志域猾警、指示表頭的指針域、指示表尾的指針域
元素結(jié)點(diǎn)：標(biāo)志域隆敢、值域

這種結(jié)構(gòu)的三個(gè)好處：
指針域的作用是用來判斷列表是否為空
容易分清列表中單元素和子表所在層次--发皿？如下圖中：BC在同一層，BC的內(nèi)容在同一層拂蝎。
最高層的表結(jié)點(diǎn)個(gè)數(shù)即為列表的長(zhǎng)度--穴墅？比如說D的長(zhǎng)度為3，表示元素A,B,C公3個(gè)温自。

廣義表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu).jpg

其中D為共享表封救，E為遞歸表。

（擴(kuò)展線性鏈表存儲(chǔ)表示）
另一種結(jié)點(diǎn)結(jié)構(gòu)的鏈表表示列表
表結(jié)點(diǎn)和原子結(jié)點(diǎn)均由三個(gè)域組成：標(biāo)志域捣作、指示表頭的指針域和指示表尾的指針域；原子結(jié)點(diǎn)的三個(gè)域?yàn)椋簶?biāo)志域鹅士、值域和指示表尾的指針域券躁。

一元多項(xiàng)式--線性表
一元多項(xiàng)式可以很容易的表示為線性表如：2X^8-9X^5+5*X2+8，構(gòu)成的線性表為{{2,8}, {-9,5}, {5,2}, {8,0}}

M元多項(xiàng)式---廣義表 關(guān)聯(lián)掉盅？

廣義表與M元多項(xiàng)式.png

廣義表的遞歸算法（對(duì)于非遞歸表且無(wú)共享子表的廣義表）（遞歸：基本項(xiàng) 和 歸納項(xiàng)）
可實(shí)現(xiàn)廣義表的三種操作：
1也拜、求廣義表的深度 即表中括弧的重?cái)?shù)。
將廣義表分解成n個(gè)子表趾痘，分別（遞歸）求得每個(gè)子表的深度慢哈。（遞歸的終止條件是空表和單元素）

3種情況的廣義表的深度分別為：
空表的深度=1；
原子的深度=0永票；
廣義表的深度= Max{子表的深度}+1卵贱；
具體實(shí)現(xiàn)：

2滥沫、復(fù)制廣義表
3種情況的廣義表復(fù)制：
空表直接復(fù)制；
原結(jié)點(diǎn)直接復(fù)制得到键俱；
復(fù)制表頭+表尾 （使用遞歸）
具體實(shí)現(xiàn)：

3兰绣、建立廣義表的存儲(chǔ)結(jié)構(gòu)
3種情況：
空表的情況；
單字符建立的子表（一個(gè)原子結(jié)點(diǎn)）的情況编振；
由最簡(jiǎn)單的子表組合成廣義表：廣義表與子表的關(guān)系缀辩，相鄰兩個(gè)子表的關(guān)系。

//廣義表,包括廣義表的建立,求深度,復(fù)制; 采用的是將廣義表劃分為"頭"和"尾"的模式踪央。
//這些操作以"(((a,b),(c,d)),(e,(f,g),h),z)"形式的字符串為基礎(chǔ).一對(duì)括號(hào)代表一個(gè)表.
public class GLists {
    //節(jié)點(diǎn)類型
    public static int ATOM = 0;
    public static int LIST = 1;


    public int tag;//用于區(qū)分節(jié)點(diǎn)

    public Object atom;//原子類型
    public GLists hp, tp;//指向表頭和表尾


    //建立廣義表"(((a,b),(c,d)),(e,(f,g),h),z)"這樣形式的字符串為內(nèi)通建立廣義表
    //同樣采用遞歸方式臀玄。結(jié)束條件是空表和原子。
    //遞歸建立表頭和表尾
    public static GLists createGList(GLists L, String s) {
        System.out.println(s);
        GLists p = null;
        GLists q = null;

        if (s.equals("()")) {
            L = null;//如果是空表
        }
        else {
            L = new GLists();
            if (s.length() == 1) {
                L.tag = ATOM;
                L.atom = s.charAt(0);
            }//創(chuàng)建單原子廣義表
            else {
                L.tag = LIST;
                p = L;
                String sub = s.substring(1, s.length() - 1);

                do {//小尾中脫出頭畅蹂，循環(huán)建立同一層次的結(jié)點(diǎn)
                    Temp temp = new Temp(sub);
                    String hsub = sever(temp);
                    sub = temp.string;

                    p.hp = createGList(p.hp, hsub);
                    q = p;//hsub是頭建立頭

                    if (!sub.isEmpty()) {//如果有尾
                        p = new GLists();
                        p.tag = LIST;
                        q.tp = p;
                    }
                } while (!sub.isEmpty());
                q.tp = null;
            }
        }

        return L;
    }


    //該函數(shù)處理(((a,b),(c,d)),(e,(f,g),h),z)后健无，hstr = ((a,b),(c,d)) str = (e,(f,g),h),z.
//等于把表頭和表尾分開
    public static String sever(Temp t) {
        String str = t.string;
        int n = str.length();
        int i = 0;
        int k = 0;
        char ch;
        String hstr = null;

        do {
            ch = str.charAt(i);
            i++;

            if (ch == '(') {
                k++;
            } else if (ch == ')') {
                k--;
            }
        } while (i < n && (ch != ',' || k != 0));

        if (i < n) {
            hstr = str.substring(0, i - 1);
            str = str.substring(i);
        } else {
            hstr = str;
            str = "";
        }

        t.string = str;
        return hstr;
    }

    //求廣義表的深度
    public static int GetDeepth(GLists L) {
        if (L == null) {
            return 1;//空表
        }
        if (L.tag == ATOM) {
            return 0;//原子
        }
        int max = 0;
        GLists p = L;
        for (; p != null; p = p.tp) {//求同一層的光儀表元素的最大深度
            int tem = GetDeepth(p.hp);
            if (tem > max) {
                max = tem;
            }
        }

        return max + 1;
    }

    //復(fù)制廣義表
    public static GLists Copy(GLists M, GLists L) {//復(fù)制廣義表,把L復(fù)制到M
        if (L == null) {
            M = null;//空表
        } else {
            M = new GLists();
            M.tag = L.tag;
            if (M.tag == ATOM) {
                M.atom = L.atom;
            } else {
                M.hp = Copy(M.hp, L.hp);//復(fù)制頭
                M.tp = Copy(M.tp, L.tp);//復(fù)制尾
            }
        }
        return M;
    }

    public static void main(String[] args) {
        GLists L = null;
        String s = "(((a,b),(c,d)),(e,(f,g),h),z)";

        //建表
        L = GLists.createGList(L, s);
        //求表深度
        int len = GLists.GetDeepth(L);
        System.out.println(len);
        //表復(fù)制
        GLists M = null;
        M = GLists.Copy(M, L);
    }
}

//為了應(yīng)對(duì)值傳遞，只能傳遞引用拷貝魁莉，無(wú)法傳遞“地址”的問題
class Temp {
    String string = "";

    public Temp(String s) {
        string = s;
    }
}