數(shù)據(jù)結(jié)構(gòu)教程第二十課廣義表

教學(xué)目的： 廣義表的定義及存儲結(jié)構(gòu)
    教學(xué)重點： 廣義表的操作及意義
    教學(xué)難點： 廣義表存儲結(jié)構(gòu)
    授課內(nèi)容：
    一、廣義表的定義
    廣義表是線性表的推廣，其表中的元素可以是另一個廣義表,或其自身.
    廣義表的定義:
    ADT GList{
    數(shù)據(jù)對象:D={i=1,2,...,n>=0;ei(-AtomSet或ei(-GList,
    AtomSet為某個數(shù)據(jù)對象}
    數(shù)據(jù)關(guān)系:R1={|ei-1,ei(-D,2=    基本操作:
    InitGlist(&L);
    操作結(jié)果:創(chuàng)建空的廣義表L
    CreateGList(&L,S);
    初始條件:S是廣義表的書寫形式串
    操作結(jié)果:由S創(chuàng)建廣義表L
    DestroyGlist(&L);
    初始條件:廣義表L存在
    操作結(jié)果:銷毀廣義表L
    CopyGlist(&T,L);
    初始條件:廣義表L存在
    操作結(jié)果:由廣義表L復(fù)制得到廣義表T
    GListLength(L);
    初始條件:廣義表L存在
    操作結(jié)果:求廣義表L的長度,即元素個數(shù)
    GListDepth(L);
    初始條件:廣義表L存在
    操作結(jié)果:求廣義表L的深度
    GlistEmpty(L);
    初始條件:廣義表L存在
    操作結(jié)果:判斷廣義表L是否為空
    GetHead(L);
    初始條件:廣義表L存在
    操作結(jié)果:取廣義表L的頭
    GetTail(L);初始條件:廣義表L存在
    操作結(jié)果:取廣義表L的尾
    InsertFirst_GL(&L,e);
    初始條件:廣義表L存在
    操作結(jié)果:插入元素e作為廣義表L的第一元素
    DeleteFirst_GL(&L,&e);
    初始條件:廣義表L存在
    操作結(jié)果:刪除廣義表L的第一元素,并用e返回其值
    Traverse_GL(L,Visit());
    初始條件:廣義表L存在
    操作結(jié)果:遍歷廣義表L,用函數(shù)Visit處理每個元素
    }ADT GList
    廣義表一般記作:LS=(a1,a2,...,an)
    其中LS是廣義表的名稱,n是它的長度,ai可以是單個元素也可是廣義表,分別稱為原子和子表,當(dāng)廣義表非空時,稱第一個元素a1為LS的表頭稱其余元素組成的廣義表為表尾.
    二、廣義表的存儲結(jié)構(gòu)
    廣義表的頭尾鏈表存儲表示
    typedef emnu{ATOM,LIST} ElemTag;
    typedef struct GLNode{
    ElemTag tag;
    union{
    AtomType atom;
    struct{struct GLNode *hp,*tp;}ptr;
    }
    }
    有A、B、C、D、E五個廣義表的描述如下：
    A=() A是一個空表,它的長度為零
    B=(e) 列表B只有一個原子e,B的長度為1.
    C=(a,(b,c,d)) 列表C的長度為2,兩個元素分別為原子a和子表(b,c,d)
    D=(A,B,C) 列表D的長度為3,三個元素都是列表,顯然,將子表的值代入后,則有D=((),(e),(a,(b,c,d)))
    E=(a,E) 這是一個遞歸的表,它的長度為2,E相當(dāng)于一個無限的列表E=(a,(a,(a,...)))