標籤: 暫無標籤

廣義表是一種非線性的數據結構,顧名思義,它也是線性表的一種推廣。它被廣泛的應用於人工智慧等領域的表處理語言LISP語言中。在LISP語言中,廣義表是一種最基本的數據結構,就連LISP 語言的程序也表示為一系列的廣義表。

1簡要介紹

線性表被定義為一個有限的序列(a1,a2,a3,…,an)其中ai被限定為是單個數據元素。廣義表也是n個數據元素d1,d2,d3,…,dn的有限序列,但不同的是,廣義表中的di 則既可以是單個元素,還可以是一個廣義表,通常記作:GL=(d1,d2,d3,…,dn)。GL是廣義表的名字,通常廣義表的名字用大寫字母表示。n是廣義表的長度。若其中di是一個廣義表,則稱di是廣義表GL的子表。在廣義表GL中,d1是廣義表GL的表頭,而廣義表GL其餘部分組成的表(d2,d3,…,dn)稱為廣義表的表尾。由此可見廣義表的定義是遞歸定義的。因為在定義廣義表時,又使用了廣義表的概念。

2應用舉例

l D=() 空表;其長度為零。
l A=(a,(b,c)) 表長度為2的廣義表,其中第一個元素是單個數據a,第二個元素是一個子表(b,c)。
l B=(A,A,D) 長度為3的廣義表,其前兩個元素為表A,第三個元素為空表D。
l C=(a,C) 長度為2遞歸定義的廣義表,C相當於無窮表C=(a,(a,(a,(…))))。
其中,A,B,C,D是廣義表的名字。下面以廣義表A為例,說明求表頭、表尾的操作如下:
head(A)=a; 表A的表頭是:a
tail(A)=((b,c)); 表A的表尾是((b,c))。廣義表的表尾一定是一個表。

3主要特點

(1) 廣義表的元素可以是子表,而子表還可以是子表…,由此,廣義表是一個多層的結構。
(2) 廣義表可以被其他廣義表共享。如:廣義表B就共享表A。在表B中不必列出表A的內容,只要通過子表的名稱就可以引用該表。
周遊廣義表

  周遊廣義表

(3) 廣義表具有遞歸性,如廣義表C。
由於廣義表GL=(d1,d2,d3,…,dn)中的數據元素既可以是單個元素,也可以是子表,因此對於廣義表,我們難以用順序存儲結構來表示它,通常我們用鏈式存儲結構來表示。表中的每個元素可用一個結點來表示。廣義表中有兩類結點,一類是單個元素結點,一類是子表結點。從上節得知,任何一個非空的廣義表都可以將其分解成表頭和表尾兩部分,反之,一對確定的表頭和表尾可以唯一地確定一個廣義表。由此,一個表結點可由三個域構成:標誌域,指向表頭的指針域,指向表尾的指針域。而元素結點置需要兩個域:標誌域和值域。

4存儲結構

擴展線性存儲
typedef enum {ATOM,LIST} ElemTag;
typedef struct GLNode
{ELemTag tag;
union
{AtomType atom;
struct GLNode *hp;
}
struct GLNode *ht;
}*GList;
上一篇[方惠南]    下一篇 [啟札]

相關評論

同義詞:暫無同義詞